Analysis and Recovery of High-Dimensional Data with Low-Dimensional Structures

低维结构高维数据的分析与恢复

• 批准号: 1818751
• 负责人: Wenjing Liao
• 金额: $ 21.54万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-06-15 至 2021-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1818751&HistoricalAwards=false
• 关键词: Analysis; Recovery; Dimensional; Data; Low

Nowadays massive, high dimensional data sets arise in many fields of contemporary science and introduce new challenges. In machine learning, the well-known curse of dimensionality implies that, in order to achieve a fixed accuracy in prediction, a large number of training data is required. In image and signal recovery, a large number of measurements are needed to recover a high-dimensional vector, unless further assumptions are made. Fortunately, many real-world data sets exhibit low-dimensional geometric structures due to rich local regularities, global symmetries, repetitive patterns, or redundant sampling. The PI will explore low-dimensional geometric structures in data sets for feature extraction, data prediction and signal recovery. Dimension reduction and function approximation given a set of training data are of central interest in machine learning and data science. When data are concentrated near a low-dimensional set or the function has low complexity, the PI will develop new and fast machine learning algorithms whose performance depends on the complexity of the data or the function, instead of the dimension of the data sets. In image and signal recovery, an interesting problem is to recover a high-dimensional, sparse vector from a small number of structured measurements. This problem is challenging since sensing matrices arising from imaging and signal processing are often deterministic, structured and highly coherent (some columns are highly correlated), which does not allow one to apply standard theory and algorithms. The PI will utilize the structures of sensing matrices, develop efficient algorithms, and prove performance guarantees. The theory and fast algorithms developed in this project can be applied to a wide range of problems in data compression, image analysis, computer vision, and signal recovery. High dimensional data arise in many fields of contemporary science and introduce new challenges. Fortunately, many real-world data sets exhibit low-dimensional geometric structures. This project focuses on exploiting these low-dimensional geometric structures of the data sets, and developing novel methods for dimension reduction, function approximation, and signal recovery. The PI will work on two sets of problems. In the first one, a data set is modeled as point clouds in a D-dimensional space but concentrating near a d-dimensional manifold, where d is much smaller than D. She plans to exploit the geometric structures of the data sets to build low-dimensional representations of data and approximate functions on data. Function approximations in Euclidean spaces have been well studied; however, classical estimators converge to the true function extremely slowly in high dimensions. When data are concentrated near a d-dimensional manifold, or the function has low complexity, the PI aims at constructing estimators that converge to the true function at a faster rate depending on the intrinsic dimension d. The proposed approach is based on the PI's recent work on adaptive geometric approximations for intrinsically low-dimensional data, where a data-driven, fast and robust scheme was developed to construct low-dimensional geometric approximations of data. The second set of problems arise from imaging and signal processing where the goal is to recover a high-dimensional, sparse vector from its noisy low-frequency Fourier coefficients. It is related with super-resolution in imaging, as the missing high-frequency Fourier coefficients correspond to the high-resolution components of the vector. Many existing methods fail since some columns in the sensing matrix are highly correlated. The PI will utilize the structure of the sensing matrix, develop efficient algorithms and prove performance guarantees. A mathematical theory will be developed to explain the fundamental difficulty of super-resolution, as well as the resolution limit of superior subspace methods, such as MUSIC, ESPRIT, and the matrix pencil method.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

如今，海量、高维的数据集出现在当代科学的许多领域，并带来了新的挑战。在机器学习中，众所周知的维度灾难意味着，为了实现固定的预测精度，需要大量的训练数据。在图像和信号恢复中，除非做出进一步的假设，否则需要进行大量的测量来恢复高维向量。幸运的是，由于丰富的局部规则性、全局对称性、重复模式或冗余采样，许多真实世界的数据集显示出低维几何结构。PI将探索数据集中的低维几何结构，用于特征提取、数据预测和信号恢复。给定一组训练数据的降维和函数逼近是机器学习和数据科学中的核心问题。当数据集中在低维集合附近或函数的复杂度较低时，PI将开发新的快速机器学习算法，其性能取决于数据或函数的复杂度，而不是数据集的维度。在图像和信号恢复中，一个有趣的问题是从少量的结构化测量中恢复高维的稀疏向量。这一问题具有挑战性，因为成像和信号处理中产生的传感矩阵通常是确定性的、结构化的和高度相干的(一些列高度相关)，这使得人们不能应用标准的理论和算法。PI将利用感知矩阵的结构，开发高效的算法，并证明性能保证。该项目开发的理论和快速算法可广泛应用于数据压缩、图像分析、计算机视觉和信号恢复等领域。高维数据出现在当代科学的许多领域，并带来了新的挑战。幸运的是，许多真实世界的数据集展示了低维的几何结构。这个项目的重点是利用数据集的这些低维几何结构，并开发新的降维、函数逼近和信号恢复方法。PI将解决两组问题。在第一种方法中，数据集被建模为D维空间中的点云，但集中在d维流形附近，其中d比D小得多。她计划利用数据集的几何结构来构建数据的低维表示和对数据的近似函数。欧氏空间中的函数逼近已经得到了很好的研究；然而，在高维空间中，经典估计收敛到真实函数的速度非常慢。当数据集中在d维流形附近，或者函数的复杂度较低时，PI的目标是构造估计器，该估计器依赖于固有维度d以更快的速度收敛到真实函数。该方法基于PI最近关于本质低维数据的自适应几何逼近的工作，其中数据驱动的、快速的和健壮的方案被用来构造数据的低维几何逼近。第二组问题来自成像和信号处理，目标是从噪声的低频傅立叶系数中恢复高维稀疏向量。它与成像中的超分辨率有关，因为缺失的高频傅立叶系数对应于矢量的高分辨率分量。由于传感矩阵中的一些列高度相关，许多现有方法都失败了。PI将利用感知矩阵的结构，开发高效的算法并证明性能保证。将开发一个数学理论来解释超分辨率的基本困难，以及更优子空间方法的分辨率限制，如MUSIC、ESPRIT和矩阵铅笔方法。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Multiscale regression on unknown manifolds

• DOI: 10.3934/mine.2022028
• 发表时间: 2021-01
• 期刊: ArXiv
• 作者: Wenjing Liao;M. Maggioni;S. Vigogna

Sensor Calibration for Off-the-Grid Spectral Estimation

• DOI: 10.1016/j.acha.2018.08.003
• 发表时间: 2017-07
• 期刊: ArXiv
• 作者: Yonina C. Eldar;Wenjing Liao;Sui Tang

Efficient Approximation of Deep ReLU Networks for Functions on Low Dimensional Manifolds

• 发表时间: 2019-08
• 期刊: ArXiv
• 作者: Minshuo Chen;Haoming Jiang;Wenjing Liao;T. Zhao

Super-Resolution Limit of the ESPRIT Algorithm

• DOI: 10.1109/tit.2020.2974174
• 发表时间: 2020-07-01
• 期刊: IEEE TRANSACTIONS ON INFORMATION THEORY
• 影响因子: 2.5
• 作者: Li, Weilin;Liao, Wenjing;Fannjiang, Albert
• 通讯作者: Fannjiang, Albert

IDENT: Identifying Differential Equations with Numerical Time Evolution

• DOI: 10.1007/s10915-020-01404-9
• 发表时间: 2019-04
• 期刊: Journal of Scientific Computing
• 影响因子: 2.5
• 作者: S. Kang;Wenjing Liao;Yingjie Liu