权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

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

基本信息

批准号：
2304489
负责人：
HanQin Cai
金额：
$ 12.14万
依托单位：
The University of Central Florida Board of Trustees
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2022
资助国家：
美国
起止时间：
2022-10-01 至 2025-08-31
项目状态：
未结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2304489&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的特殊结构，该项目旨在设计最佳有效的算法，并建立理论分析，以精确恢复点配置。第三个目标考虑测量可能稀疏损坏的设置。该项目旨在开发针对这种情况的快速和强大的算法，并对恢复保证进行必要的分析。为了实现这些目标，该项目利用了高维概率，黎曼优化，数值分析和谱图理论的工具。该项目将为培养对距离几何、优化理论和计算科学感兴趣的本科生和研究生提供机会。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

期刊论文数量（5）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Non-Convex Approaches for Low-Rank Tensor Completion under Tubal Sampling

DOI：
10.1109/icassp49357.2023.10094847
发表时间：
2023-03
期刊：
ICASSP 2023 - 2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)
影响因子：
0
作者：
Zheng Tan;Longxiu Huang;HanQin Cai;Y. Lou
通讯作者：
Zheng Tan;Longxiu Huang;HanQin Cai;Y. Lou

Towards Constituting Mathematical Structures for Learning to Optimize