An overview of low-rank matrix recovery from incomplete observations

Abstract

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.

References in corpus (7)

• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Sparse Phase Retrieval from Short-Time Fourier Measurements
• Fast matrix completion without the condition number
• Probabilistic low-rank matrix completion on finite alphabets
• Collaboratively Learning Preferences from Ordinal Data
• Sharp oracle inequalities for the prediction of a high-dimensional matrix
• Identifiability in Blind Deconvolution with Subspace or Sparsity Constraints

Cited by in corpus (110)

• Edge Learning for B5G Networks with Distributed Signal Processing: Semantic Communication, Edge Computing, and Wireless Sensing
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Inference and Uncertainty Quantification for Noisy Matrix Completion
• Global Optimality in Low-rank Matrix Optimization
• The Numerics of Phase Retrieval
• The Non-convex Geometry of Low-rank Matrix Optimization
• Static and Dynamic Robust PCA and Matrix Completion: A Review
• Implicit Regularization in Deep Matrix Factorization
• Implicit Regularization in Deep Learning May Not Be Explainable by Norms
• ME-Net: Towards Effective Adversarial Robustness with Matrix Estimation
• Approximate Message Passing with Unitary Transformation for Robust Bilinear Recovery
• Federated Learning via Over-the-Air Computation
• Plug-in Estimation in High-Dimensional Linear Inverse Problems: A Rigorous Analysis
• Data Shuffling in Wireless Distributed Computing via Low-Rank Optimization
• Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Number
• Leveraging the Restricted Isometry Property: Improved Low-Rank Subspace Decomposition for Hybrid Millimeter-Wave Systems
• Bilinear Recovery using Adaptive Vector-AMP
• Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensing
• The Global Optimization Geometry of Low-Rank Matrix Optimization
• ENLIVE: An Efficient Nonlinear Method for Calibrationless and Robust Parallel Imaging
• Matrix completion with deterministic pattern - a geometric perspective
• From Symmetry to Geometry: Tractable Nonconvex Problems
• Multi-Frequency Phase Retrieval for Antenna Measurements
• Color Image Inpainting via Robust Pure Quaternion Matrix Completion: Error Bound and Weighted Loss
• Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization
• Composite optimization for robust blind deconvolution
• Harmonic Mean Iteratively Reweighted Least Squares for Low-Rank Matrix Recovery
• Stochastic Low-Rank Bandits
• Harnessing Structures for Value-Based Planning and Reinforcement Learning
• Provable Tensor-Train Format Tensor Completion by Riemannian Optimization
• MOSES: A Streaming Algorithm for Linear Dimensionality Reduction
• Riemannian Low-Rank Model Compression for Federated Learning with Over-the-Air Aggregation
• Conditions for Estimation of Sensitivities of Voltage Magnitudes to Complex Power Injections
• Dynamic matrix recovery from incomplete observations under an exact low-rank constraint
• A Non-convex One-Pass Framework for Generalized Factorization Machine and Rank-One Matrix Sensing
• Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction
• Near-optimal matrix recovery from random linear measurements
• NGS Based Haplotype Assembly Using Matrix Completion
• Rank $2r$ iterative least squares: efficient recovery of ill-conditioned low rank matrices from few entries
• On Convergence of the Alternating Projection Method for Matrix Completion and Sparse Recovery Problems
• Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach
• TARM: A Turbo-type Algorithm for Affine Rank Minimization
• Sensor Network Localization via Riemannian Conjugate Gradient and Rank Reduction: An Extended Version
• Iterative Calculation of Characteristic Modes Using Arbitrary Full-wave Solvers
• Recursive Importance Sketching for Rank Constrained Least Squares: Algorithms and High-order Convergence
• On Low-rank Trace Regression under General Sampling Distribution
• Fast Low-Rank Matrix Estimation without the Condition Number
• Multispectral snapshot demosaicing via non-convex matrix completion
• Maximum entropy low-rank matrix recovery
• Adapformer: Adaptive Channel Management for Multivariate Time Series Forecasting
• Nonconvex Robust Low-rank Matrix Recovery
• Matrix Completion with Weighted Constraint for Haplotype Estimation
• Total Least Squares Phase Retrieval
• The Landscape of Non-convex Empirical Risk with Degenerate Population Risk
• Goodness-of-fit tests on manifolds
• Optimal tuning-free convex relaxation for noisy matrix completion
• Gain and phase calibration of sensor arrays from ambient noise by cross-spectral measurements fitting
• Deep inference of latent dynamics with spatio-temporal super-resolution using selective backpropagation through time
• Nonconvex Low-Rank Matrix Recovery with Arbitrary Outliers via Median-Truncated Gradient Descent
• Improved Algorithms for Matrix Recovery from Rank-One Projections
• Matrix Completion With Variational Graph Autoencoders: Application in Hyperlocal Air Quality Inference
• Information-Guided Sampling for Low-Rank Matrix Completion
• New Low Rank Optimization Model and Convex Approach for Robust Spectral Compressed Sensing
• Limitations of Implicit Bias in Matrix Sensing: Initialization Rank Matters
• Quality control, data cleaning, imputation
• Bridging Convex and Nonconvex Optimization in Robust PCA: Noise, Outliers, and Missing Data
• Dimension Reduction for Origin-Destination Flow Estimation: Blind Estimation Made Possible
• Analysis of Optimal Thresholding Algorithms for Compressed Sensing
• Exact matrix completion based on low rank Hankel structure in the Fourier domain
• Implicit Regularization and Entrywise Convergence of Riemannian Optimization for Low Tucker-Rank Tensor Completion
• Implicit Regularization in Tensor Factorization
• Characterizing high-dimensional quantum contextuality
• On Ambiguity in Linear Inverse Problems: Entrywise Bounds on Nearly Data-Consistent Solutions and Entrywise Condition Numbers
• Low-Rank Matrix Completion: A Contemporary Survey
• Theoretical Guarantees for Low-Rank Compression of Deep Neural Networks
• Binary Matrix Completion Using Unobserved Entries
• Understanding Notions of Stationarity in Non-Smooth Optimization
• Rank one tensor completion problem
• Streaming Principal Component Analysis From Incomplete Data
• On the equivalence of two post-quantum cryptographic families
• Low solution rank of the matrix LASSO under RIP with consequences for rank-constrained algorithms
• Topological Interference Management with User Admission Control via Riemannian Optimization
• Asymptotic Log-Det Rank Minimization via (Alternating) Iteratively Reweighted Least Squares
• The Nonconvex Geometry of Linear Inverse Problems
• Lecture notes on non-convex algorithms for low-rank matrix recovery
• Solving the Robust Matrix Completion Problem via a System of Nonlinear Equations
• Efficient MCMC Sampling for Bayesian Matrix Factorization by Breaking Posterior Symmetries
• Rank-One Measurements of Low-Rank PSD Matrices Have Small Feasible Sets
• Leveraging Subspace Information for Low-Rank Matrix Reconstruction
• Optimal Sample Complexity for Stable Matrix Recovery
• Paying down metadata debt: learning the representation of concepts using topic models
• The radius of statistical efficiency
• Sketching sparse low-rank matrices with near-optimal sample- and time-complexity using message passing
• On Recovering the Best Rank-r Approximation from Few Entries
• Robust spectral compressive sensing via vanilla gradient descent
• Maximum a Posteriori Inference of Random Dot Product Graphs via Conic Programming
• Convex Reconstruction of Structured Matrix Signals from Linear Measurements (I): Theoretical Results
• Zorro: A Model Agnostic System to Price Consumer Data
• Several classes of stationary points for rank regularized minimization problems
• Entry-Specific Bounds for Low-Rank Matrix Completion under Highly Non-Uniform Sampling
• Matrix Completion for Survey Data Prediction with Multivariate Missingness
• Over-Parametrized Matrix Factorization in the Presence of Spurious Stationary Points
• Lattices from tight frames and vertex transitive graphs
• Learning with Semi-Definite Programming: new statistical bounds based on fixed point analysis and excess risk curvature
• Regularization parameter selection for low rank matrix recovery
• Enhanced image approximation using shifted rank-1 reconstruction
• Regularisation for PCA- and SVD-type matrix factorisations
• Error bound of critical points and KL property of exponent $1/2$ for squared F-norm regularized factorization