ABSTRACT

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.

Please report errors in award information by writing to: awardsearch@nsf.gov.