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

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

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.