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

协作研究：结构化传感非凸模型：理论、算法和应用

• 批准号: 2208612
• 负责人: HanQin Cai
• 金额: $ 12.14万
• 依托单位: University of California-Los Angeles
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-09-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2208612&HistoricalAwards=false
• 关键词: Collaborative; Research; Nonconvex; Models; Structured

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.

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