Collaborative Research: Nonconvex Models for Structured Sensing: Theory, Algorithms, and Applications

技术的快速进步使收集大量数据的能力比以往任何时候都更加强大。虽然这类数据的丰富是有利的，但它带来了几个计算挑战。一个挑战是，数据可能包含大量缺失的条目。例如，在使用有限范围的物理测量设备时，或者在收集用户对我们缺乏完整信息的产品的偏好时，就是这种情况。已被证明对这个问题有用的一种方法是矩阵补全算法，该算法通过对数据的最小假设来预测丢失的条目。然而，在具有边信息的结构预测和推荐系统等问题中，度量不是入门级的。具体地说，观测是基础数据的一些条目的集合，即，用户可以访问这些条目的某些组合，而不是直接观察数据的条目。本课题旨在研究这一问题，即众所周知的矩阵感知问题。大多数以前的工作考虑了数据的测量随机丢失的情况，或者假设测量协议本身是随机的。在实际应用的推动下，该项目考虑了一个现实的设置，其中的测量是结构化和确定性的。本项目的一个关键目标是通过研究新的优化算法来提高矩阵感知的理论和计算水平。该项目的另一个目标是将构建的框架应用于稳健的结构预测和机器学习。本项目致力于研究一类广义矩阵恢复问题的可伸缩非凸算法。特别是，PI对在各种设置下具有确定性结构的测量的低阶矩阵传感问题感兴趣。主要方法是建立关于确定性测量基及其相关对偶基的最优化问题。这在一些温和的条件下产生了一个很好的问题。该项目围绕三个目标展开。在第一部分中，该项目研究了一种直接在低阶矩阵流形上优化的黎曼梯度下降算法的局部收敛。然后，恢复保证将主要取决于基和对偶基的光谱属性、采样方案和初始化。通过连接到谱图理论，将研究谱性质的严格估计和有效的初始化方法。第二个目标是设计一种针对欧几里德距离几何(EDG)问题的算法，其目的是在给定关于两两距离的部分信息的情况下估计点的形状。EDG是一个利用确定性结构测量的代表性问题。通过利用EDG的特殊结构，该项目旨在设计最优的高效算法，并为准确恢复点配置建立理论分析。第三个目标考虑测量可能被稀疏破坏的设置。该项目旨在开发针对这种情况的快速和健壮的算法，并为恢复保证进行必要的分析。为了实现这些目标，该项目利用了高维概率、黎曼优化、数值分析和谱图理论的工具。该项目将提供机会培养对距离几何、最优化理论和计算科学感兴趣的本科生和研究生。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

The rapid advance of technology has enabled more than ever the ability to collect large amounts of data. While the abundance of such data is advantageous, it brings forth several computational challenges. One challenge is the fact that data might contain numerous missing entries. This is the case for instance when using physical measurement devices with a limited range or in collecting user preferences for a product where we lack complete information. One line of methods that has proved to be useful for this problem is matrix completion algorithms which predict missing entries with minimalistic assumptions on the data. However, in problems such as structure prediction and recommendation system with side information, the measurements are not entry-wise. Specifically, the observations are an aggregate of some entries of the underlying data, i.e., rather than directly observing the entries of the data, the user has access to certain combinations of these entries. This project aims to study this problem which is well known as the matrix sensing problem. The majority of previous works consider the case where measurements of the data are missing at random or assume that the measurement protocol itself is random. Motivated by practical applications, this project considers a realistic setup where the measurements are structured and deterministic. A key goal of this project is to advance the state of art theory and computation of matrix sensing by studying new optimization algorithms. Another aim of the project is to apply the constructed framework to robust structure prediction and machine learning. This project seeks to study scalable non-convex methods for a class of generalized matrix recovery problems. In particular, PIs are interested in low-rank matrix sensing problems with deterministically structured measurements under various settings. The main approach is based on formulating the optimization problem with respect to a deterministic measurement basis and its associated dual basis. This yields a well-posed problem under some mild conditions. The project is centered on three objectives. In the first part, the project studies the local convergence of a Riemannian gradient descent algorithm that directly optimizes over the manifold of low-rank matrices. The recovery guarantee then will depend mainly on the spectral properties of the basis and the dual basis, the sampling scheme, and the initialization. Tight estimation of the spectral properties and effective initialization method will be investigated by bridging connections to spectral graph theory. The second objective is to design an algorithm tailored for the Euclidean distance geometry (EDG) problem which aims to estimate the configuration of points given partial information about pairwise distances. EDG is a representative problem that utilizes deterministically structured measurements. By leveraging the special structure of EDG, the project aims to design optimally efficient algorithms and establish theoretical analysis for the exact recovery of the point configuration. The third objective considers the setting where the measurements might be sparsely corrupted. The project aims to develop fast and robust algorithms tailored to this case and carry out the necessary analysis for recovery guarantees. To realize these objectives, the project leverages tools from high-dimensional probability, Riemannian optimization, numerical analysis, and spectral graph theory. The project will provide opportunities to train undergraduate and graduate students with interests in distance geometry, optimization theory, and computational science.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.