Collaborative Research: Scalable, Robust, and Distributed Nonconvex Approaches for Structured Tensor Recovery

Tensors, which naturally extend the concepts of vectors and matrices to multiple dimensions, have become ubiquitous due to the accessibility of numerous affordable and deployable sensors capable of collecting data on the same object or phenomenon from multiple perspectives. This proliferation is further accelerated by the powerful and flexible models that tensors can provide for representing multi-attribute data and multiway interactions, rendering tensors indispensable in modern data science across various fields of science and engineering. Among various applications, a fundamental task is to estimate tensors from highly incomplete measurements. This challenge emerges due to the exponential growth in the number of potential viewpoint combinations or multiway interactions, while our data collection capability increases only polynomially. Even if sufficient data could be collected, the amount of data may overwhelm the computational and storage resources of a single machine. Fortunately, in many practical applications, tensors often obey certain low-dimensional representations. This project will exploit these representations to address key challenges in modern data science across a spectrum of scenarios, spanning from centralized to distributed settings, while also accounting for the presence of maliciously perturbed measurements. By advancing the field of tensor analysis, this project has significant potential benefits across diverse areas such as signal processing, biomedical imaging, machine learning, and quantum information science. This project will develop a unified framework for exploiting low-dimensional structures for tensor recovery from incomplete measurements. To overcome computational challenges for large-scale tensors, this project will develop computationally and statistically efficient optimization methods that directly optimize over the low-dimensional structures (or factors in various tensor decomposition models). Our work will first study the stable embeddings of low-dimensional tensors from random yet structured linear measurements to determine the number of measurements needed for a stable recovery. This project will then leverage the stable embedding results to characterize the geometric landscape of the factorized nonconvex problems over the low-dimensional structures. The geometric landscape analysis will enable us to develop efficient local search algorithms with guaranteed convergence to the target tensors. In cases where privacy is a concern or the measurements overwhelm the computational and storage resources of a single machine, this project will enhance the algorithms with distributed optimization techniques that offer similar convergence and recovery guarantees, along with consensus guarantees. 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.