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 (34)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Quantum state tomography via compressed sensing
• Phase Retrieval via Wirtinger Flow: Theory and Algorithms
• The Convex Geometry of Linear Inverse Problems
• A Simpler Approach to Matrix Completion
• User-friendly tail bounds for sums of random matrices
• Recovering low-rank matrices from few coefficients in any basis
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Estimation of high-dimensional low-rank matrices
• Self-Calibration and Biconvex Compressive Sensing
• Matrix Completion from Noisy Entries
• Incoherence-Optimal Matrix Completion
• Randomized algorithms for matrices and data
• Guaranteed Blind Sparse Spikes Deconvolution via Lifting and Convex Optimization
• Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
• A Max-Norm Constrained Minimization Approach to 1-Bit Matrix Completion
• Phase transitions and sample complexity in Bayes-optimal matrix factorization
• Sparse Phase Retrieval from Short-Time Fourier Measurements
• Compressed Sensing and Affine Rank Minimization under Restricted Isometry
• Poisson Matrix Recovery and Completion
• Subspace Evolution and Transfer (SET) for Low-Rank Matrix Completion
• Fast matrix completion without the condition number
• Phase Recovery, MaxCut and Complex Semidefinite Programming
• Dropping Convexity for Faster Semi-definite Optimization
• Consistent Basis Pursuit for Signal and Matrix Estimates in Quantized Compressed Sensing
• Noisy Matrix Completion under Sparse Factor Models
• Lifting for Blind Deconvolution in Random Mask Imaging: Identifiability and Convex Relaxation
• Exponential Family Matrix Completion under Structural Constraints
• The local convexity of solving systems of quadratic equations
• 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
• Conjugate gradient acceleration of iteratively re-weighted least squares methods

Cited by in corpus (112)

• 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
• Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
• Inference and Uncertainty Quantification for Noisy Matrix Completion
• Global Optimality in Low-rank Matrix Optimization
• Phase transitions and sample complexity in Bayes-optimal matrix factorization
• 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
• Color Image Inpainting via Robust Pure Quaternion Matrix Completion: Error Bound and Weighted Loss
• Multi-Frequency Phase Retrieval for Antenna Measurements
• Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization
• Harmonic Mean Iteratively Reweighted Least Squares for Low-Rank Matrix Recovery
• Composite optimization for robust blind deconvolution
• 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
• Conditions for Estimation of Sensitivities of Voltage Magnitudes to Complex Power Injections
• A Non-convex One-Pass Framework for Generalized Factorization Machine and Rank-One Matrix Sensing
• Riemannian Low-Rank Model Compression for Federated Learning with Over-the-Air Aggregation
• Dynamic matrix recovery from incomplete observations under an exact low-rank constraint
• 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
• On Low-rank Trace Regression under General Sampling Distribution
• Recursive Importance Sketching for Rank Constrained Least Squares: Algorithms and High-order Convergence
• Iterative Calculation of Characteristic Modes Using Arbitrary Full-wave Solvers
• Maximum entropy low-rank matrix recovery
• Matrix Completion with Weighted Constraint for Haplotype Estimation
• Multispectral snapshot demosaicing via non-convex matrix completion
• Fast Low-Rank Matrix Estimation without the Condition Number
• Total Least Squares Phase Retrieval
• Adapformer: Adaptive Channel Management for Multivariate Time Series Forecasting
• Nonconvex Robust Low-rank Matrix Recovery
• Deep inference of latent dynamics with spatio-temporal super-resolution using selective backpropagation through time
• 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
• Improved Algorithms for Matrix Recovery from Rank-One Projections
• Nonconvex Low-Rank Matrix Recovery with Arbitrary Outliers via Median-Truncated Gradient Descent
• Gain and phase calibration of sensor arrays from ambient noise by cross-spectral measurements fitting
• Information-Guided Sampling for Low-Rank Matrix Completion
• New Low Rank Optimization Model and Convex Approach for Robust Spectral Compressed Sensing
• Bridging Convex and Nonconvex Optimization in Robust PCA: Noise, Outliers, and Missing Data
• Quality control, data cleaning, imputation
• Matrix Completion With Variational Graph Autoencoders: Application in Hyperlocal Air Quality Inference
• Limitations of Implicit Bias in Matrix Sensing: Initialization Rank Matters
• Exact matrix completion based on low rank Hankel structure in the Fourier domain
• Dimension Reduction for Origin-Destination Flow Estimation: Blind Estimation Made Possible
• Analysis of Optimal Thresholding Algorithms for Compressed Sensing
• Binary Matrix Completion Using Unobserved Entries
• On Ambiguity in Linear Inverse Problems: Entrywise Bounds on Nearly Data-Consistent Solutions and Entrywise Condition Numbers
• Characterizing high-dimensional quantum contextuality
• On the equivalence of two post-quantum cryptographic families
• Implicit Regularization and Entrywise Convergence of Riemannian Optimization for Low Tucker-Rank Tensor Completion
• Implicit Regularization in Tensor Factorization
• Theoretical Guarantees for Low-Rank Compression of Deep Neural Networks
• Low-Rank Matrix Completion: A Contemporary Survey
• Understanding Notions of Stationarity in Non-Smooth Optimization
• Rank one tensor completion problem
• Streaming Principal Component Analysis From Incomplete Data
• Lecture notes on non-convex algorithms for low-rank matrix recovery
• Topological Interference Management with User Admission Control via Riemannian Optimization
• The Nonconvex Geometry of Linear Inverse Problems
• Asymptotic Log-Det Rank Minimization via (Alternating) Iteratively Reweighted Least Squares
• Low solution rank of the matrix LASSO under RIP with consequences for rank-constrained algorithms
• Error bound of critical points and KL property of exponent $1/2$ for squared F-norm regularized factorization
• Leveraging Subspace Information for Low-Rank Matrix Reconstruction
• Solving the Robust Matrix Completion Problem via a System of Nonlinear Equations
• Over-Parametrized Matrix Factorization in the Presence of Spurious Stationary Points
• Entry-Specific Bounds for Low-Rank Matrix Completion under Highly Non-Uniform Sampling
• Efficient MCMC Sampling for Bayesian Matrix Factorization by Breaking Posterior Symmetries
• Paying down metadata debt: learning the representation of concepts using topic models
• Robust spectral compressive sensing via vanilla gradient descent
• Convex Reconstruction of Structured Matrix Signals from Linear Measurements (I): Theoretical Results
• Zorro: A Model Agnostic System to Price Consumer Data
• Maximum a Posteriori Inference of Random Dot Product Graphs via Conic Programming
• Several classes of stationary points for rank regularized minimization problems
• Optimal Sample Complexity for Stable Matrix Recovery
• The radius of statistical efficiency
• On Recovering the Best Rank-r Approximation from Few Entries
• Sketching sparse low-rank matrices with near-optimal sample- and time-complexity using message passing
• Lattices from tight frames and vertex transitive graphs
• Enhanced image approximation using shifted rank-1 reconstruction
• Regularisation for PCA- and SVD-type matrix factorisations
• Rank-One Measurements of Low-Rank PSD Matrices Have Small Feasible Sets
• Matrix Completion for Survey Data Prediction with Multivariate Missingness
• Regularization parameter selection for low rank matrix recovery
• Learning with Semi-Definite Programming: new statistical bounds based on fixed point analysis and excess risk curvature