An Overview of Low-Rank Matrix Recovery From Incomplete Observations

By Mark A. Davenport, Justin K. Romberg. IEEE Journal on Selected Topics in Signal Processing, 2016

466 citations recorded by the source corpus.

Low-rank matrices play a fundamental role in modeling and computational methods for signal processing and machine learning. In many applications where low-rank matrices arise, these matrices cannot be fully sampled or directly observed, and one encounters the problem of recovering the matrix given only incomplete and indirect observations. This paper provides an overview of modern techniques for exploiting low-rank structure to perform matrix recovery in these settings, providing a survey of recent advances in this rapidly-developing field. Specific attention is paid to the algorithms most commonly used in practice, the existing theoretical guarantees for these algorithms, and representative practical applications of these techniques.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Geophysics

View Paper: https://www.semanticscholar.org/paper/1444291de46351f308bf561f9b13552aa9a4d815

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

1. Wei Hu
2. Yuejie Chi
3. Yuxin Chen
4. Yue M. Lu
5. Nadav Cohen
6. Bart Vandereycken
7. Noam Razin
8. André Uschmajew

In Computer Vision and Pattern Recognition

1. André Uschmajew
2. Wei Hu
3. Sanjeev Arora
4. Chi Jin
5. Rong Ge
6. Yue M. Lu
7. Yuejie Chi
8. Yuxin Chen

In Geophysics

1. Laura Balzano
2. Yue M. Lu
3. Yuejie Chi
4. Nadav Cohen

Citations in the corpus

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, background): “amongst others, dropping or replacing the low-rank constraint (1b) by a nuclear norm constraint [1–3, 11–13], and solving the convexified problem in the full matrix space (i.”
• The non-convex geometry of low-rank matrix optimization (2016, background): “In spite of their optimal statistical performance [13–15, 18], the original convex optimization problems cannot be scaled to solve the practical problems that originally motivate their development even with specialized first-order algorithms.”
• Implicit Regularization in Deep Matrix Factorization (2019, background): “However, an extensive body of work (see [11] for a survey) has shown that if W ∗ is low-rank, certain technical assumptions (e.”
• Edge Learning for B5G Networks With Distributed Signal Processing: Semantic Communication, Edge Computing, and Wireless Sensing (2022, unknown): “Problems of sparse optimization and low-rank optimization occur frequently in ML and signal processing [165], [166], [167], [168], whose”
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis (2017, background): “Such problems are studied extensively [Fazel, 2002, Rennie and Srebro, 2005, Cand`es and Recht, 2009] and has many applications in recommendation systems [Koren, 2009], see survey by Davenport and Romberg [2016].”
• On critical points of quadratic low-rank matrix optimization problems (2020, background): “We refer to [1] for more references on the RIP.”
• Federated Learning via Over-the-Air Computation (2018, background): “Sparse optimization and low-rank optimization have attracted much attention in machine learning, signal processing, high-dimensional statistics, as well as wireless communication [30], [31], [32], [33], [34].”
• Streaming PCA and Subspace Tracking: The Missing Data Case (2018, methodology): “the low-rank matrix completion problem [7], [71]–[74]), the only results in the streaming case with missing data are local convergence results for GROUSE and the work of [75], where the authors consider recovering a low-rank positive semidefinite matrix observed with missing data using stochastic gr”
• Implicit Regularization in Deep Learning May Not Be Explainable by Norms (2020, background): “However, an extensive body of work (see [26] for a survey) has shown that if W ∗ is low-rank, certain technical assumptions (e.”
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution (2017, background): “Under certain incoherence conditions imposed upon the ground truth matrix, exact recovery is guaranteed under near-optimal sample complexity [14,23,38,51,93].”
• Low-rank Solutions of Linear Matrix Equations via Procrustes Flow (2015, unknown): “O C ] 5 F eb”