Source-linked AI summary
An overview of low-rank matrix recovery from incomplete observations
Mark A. Davenport, Justin Romberg
TL;DR
Large low-rank matrices are often only partially or indirectly observed, creating a recovery problem across many applications. The paper surveys practical algorithms, observation models, and theoretical guarantees for exploiting low-rank structure. It also discusses applications and shows that recovery behavior depends on the observation setting and its assumptions.
Problem
Many applications involve large low-rank matrices that cannot be fully observed, requiring recovery from incomplete or indirect measurements.
Method
The paper surveys common low-rank recovery algorithms, several observation models, their theoretical guarantees, and representative applications.
Results
The survey reports that low-rank matrices can sometimes be recovered efficiently, while recovery guarantees depend on observation models and additional assumptions such as coherence.
Takeaways & Limitations
Low-rank recovery provides a framework for handling incomplete measurements across applications including recommendation systems and blind deconvolution.
Takeaways & Limitations
Alternating-projection methods have few general convergence guarantees, and their final solutions depend heavily on initialization.
Abstract
from arXiv · showhide
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.
1 Introduction
Low-rank matrices occur across signal processing, machine learning, graph, sensing, and other scientific applications, but their large size and incomplete observability make recovery challenging. This survey reviews efficient recovery methods, their theoretical guarantees, and representative applications.
- Low-rank matrices arise in ensembles of signals, system identification, graph adjacency, distance, item-response, machine-learning, and quantum-state problems.Examples include correlated sensor or video data, low-order dynamical systems, social-network graphs, recommendation systems, and rank-one pure quantum states.
- Low-rank modeling supports classical and modern machine-learning techniques, including principal component analysis, multitask learning, and natural language processing.
- Large matrices are often impossible or prohibitively expensive to observe fully, leaving only incomplete measurements such as sparse ratings or graph connections.The paper identifies incomplete observation as a central obstacle in applications involving sensor arrays, graphs, and recommendation systems.
- Low-rank structure can enable surprisingly efficient recovery from incomplete observations, although recovery is not always possible in general.Recent advances, including work connected to compressive sensing, have substantially improved understanding of these problems.
- The survey covers practical recovery algorithms, theoretical guarantees, observation requirements, additional assumptions, and applications that recast quadratic or bilinear systems as low-rank recovery.The theoretical discussion addresses several concrete observation models and emphasizes the number of observations needed for reliable recovery.
2 The Matrix Recovery Problem
The paper formulates recovery of an approximately low-rank matrix from noisy linear measurements and surveys three principal observation models. These include random projections, matrix completion from sampled entries, and related application-driven models.
- A target matrix X0 of size M × N is modeled as exactly or approximately rank R, with R much smaller than M and N.Its singular-value decomposition uses nonnegative singular values and orthonormal left and right singular vectors.
- Rank-R matrices require O(R(M + N)) parameters rather than MN, motivating recovery from relatively few measurements.
- The observation model is y = A(X0) + z, where A is a linear operator formed from inner products with L predefined M × N matrices and z represents noise.
- The survey focuses on random projections and matrix completion, in which A returns a subset of target entries.The random-projection model uses independently and identically distributed random variables, while matrix completion uses sensing matrices with one nonzero entry each.
- The paper notes that imaging- and signal-processing applications motivate additional observation models beyond the three models emphasized in the survey.
3 Algorithms for Matrix Recovery
Matrix recovery algorithms range from SVD-based approximation to convex nuclear-norm optimization and nonconvex factorized methods, with trade-offs in tractability, storage, and scalability.
- 3.1 Low-rank approximation: The Eckart-Young theorem solves best rank-R approximation by truncating the singular value decomposition, retaining the largest singular values.For medium-scale problems, high-precision SVD computation has complexity O(K^2 max(M, N)).
- 3.1 Low-rank approximation: Hard and soft singular-value thresholding provide equivalent regularization views, with soft thresholding shrinking retained singular values instead of abruptly removing them.The nuclear norm, equal to the sum of singular values, supplies a convex proxy for rank.
- 3.2 Low-rank recovery and nuclear norm minimization: Exact rank-constrained recovery is generally NP-hard, whereas nuclear-norm minimization remains a tractable convex alternative solvable with proximal algorithms.Analytical results give conditions under which related formulations exactly recover low-rank matrices from measurements.
- 3.2 Low-rank recovery and nuclear norm minimization: Large-scale implementations reduce storage and computation by factorizing X as L R^T, while Burer-Monteiro formulations can have globally optimal local minima under rank conditions.These formulations are nonconvex but are used in state-of-the-art large-scale matrix recovery implementations.
- 3.4 Alternating projections: Alternating factor updates solve least-squares subproblems and are popular for large-scale matrix factorization, often outperforming nuclear-norm minimization when the rank is very small.Each update solves a linear system involving R M or R N variables.
- 3.5 Other algorithms for matrix recovery: Other recovery approaches use alternative rank proxies, including the convex max-norm and the smooth but nonconvex log-determinant function.Locally minimizing the log-determinant subject to convex constraints tends to produce low-rank solutions in practice.
4 Matrix Recovery from Gaussian Observations
Gaussian random projections provide a clean theoretical model for low-rank recovery: matrix-RIP establishes uniform measurement preservation, while convex-geometric analysis gives sharper nuclear-norm guarantees.
- Matrix restricted isometry property: Matrix-RIP makes rank-R matrices distinguishable from their measurements and guarantees unique images for distinct rank-R matrices.The property preserves pairwise distances up to multiplicative factors for all rank-R matrices simultaneously.
- Matrix restricted isometry property: Gaussian measurements satisfy matrix-RIP with high probability using an observation count proportional to R(M + N).The stated bound is L ≳ δ^-2R(M + N), with probability at least 1 − C′e^-c′L.
- Algorithmic guarantees: Nuclear norm minimization recovers rank-R X0 when δ ≤ 0.3, while iterative hard thresholding is guaranteed for δ ≤ 1/3 with linear convergence.These are algorithm-specific consequences of matrix-RIP.
- Algorithmic guarantees: Matrix-RIP uniformity yields stability when measurements contain noise or the target matrix is only approximately low rank.The same simultaneous preservation property supports robustness across the analyzed algorithms.
- Algorithmic guarantees: Matrix-RIP analysis is broadly applicable across algorithms but often produces looser bounds than Gaussian-specific nuclear-norm results.The survey contrasts general matrix-RIP guarantees with more precise conditions for nuclear norm minimization.
- Convex geometry and Gaussian widths: Nuclear norm recovery succeeds when the measurement null space intersects the tangent cone at X0 only at the origin.The tangent cone contains directions that decrease the nuclear norm, and the affine feasibility geometry determines uniqueness.
- Convex geometry and Gaussian widths: A random subspace avoids a cone with high probability when its codimension is at least the cone’s squared Gaussian width.For the nuclear-norm tangent cone, w(TB(X0))^2 ≤ 3R(M + N − R) gives a sharp sufficient measurement condition.
- Convex geometry and Gaussian widths: The Gaussian-width threshold is nearly necessary: sufficiently fewer observations make equality-constrained nuclear norm minimization fail with probability close to one.Numerical experiments predict success or failure from M, N, and R.
5 Matrix Completion
Matrix completion recovers low-rank matrices from randomly observed entries, but feasibility depends on incoherence because some low-rank matrices concentrate information in only a few entries. Under incoherence and related assumptions, nuclear norm minimization provides high-probability recovery guarantees, with observation requirements shaped by rank, coherence, and logarithmic dimension factors.
- Observation model: Matrix completion observes entries indexed by a subset of the full matrix, unlike Gaussian random projections.This structured observation model matches settings such as surveys, recommendation systems, and large-scale graphs.
- Which matrices can be completed?: Sparse singular vectors can concentrate a rank-one matrix’s energy in a few entries, making recovery from a small number of observations impossible without prior information.Most entries then provide little information, and some matrices may lie in the measurement operator’s nullspace.
- Which matrices can be completed?: Coherence measures whether the row and column spaces distribute information across entries; low coherence makes completion from few observations potentially feasible.Incoherent matrices have coherence close to 1, whereas highly coherent spaces can require observing nearly every entry.
- Recovery guarantees: Under incoherence assumptions, nuclear norm minimization recovers a rank-R matrix with high probability from uniformly sampled entries when the observation bound is satisfied.The guarantee assumes bounds on the coherences of the singular-vector spaces and an additional bound involving E = UV^*.
- Recovery guarantees: The required observations scale with incoherence and include a logarithmic dimension factor; near-maximal incoherence can require observing nearly every entry.At least O(M log M) observations are needed just to observe every row at least once under uniform random sampling.
- Recovery guarantees: The noise-free, exactly low-rank result also has analogues for noisy observations and approximately low-rank matrices, with error determined by noise and approximation error.Related results extend recovery guarantees beyond the exact, noise-free setting.
- Recovery guarantees: Dual-certificate analysis establishes exact recovery by proving both that a suitable certificate suffices and that random samples produce one with high probability.This approach avoids relying directly on an RIP-based argument, which faces difficulties because differences of incoherent matrices need not be incoherent.
6 Nonlinear Observation Models
Nonlinear observation models address applications where measurements are quantized, compared, or otherwise transformed before observation. In one-bit settings, noise can make recovery well-posed, while likelihood-based methods extend low-rank recovery to broader nonlinearities and noise models.
- Nonlinear observation models: Many practical observations apply nonlinear transformations such as quantization to low-rank matrix measurements, creating a gap between standard recovery theory and applications.Recommendation systems are given as an example where observed ratings may not follow the standard observation model.
- One-bit observations: One-bit observations retain only a binary outcome, and standard low-rank recovery assumptions and algorithms become ill-posed in the noise-free case.Rescaling the underlying matrix does not change sign observations, so its scale cannot be identified.
- One-bit observations: Noise has a dithering effect that can make one-bit recovery well-posed and, with sufficiently many measurements, allow arbitrarily precise recovery.The theory can recover certain approximately low-rank matrices with error proportional to R(M + N)/L.
- One-bit observations: The one-bit matrix-completion approach replaces a quadratic fidelity constraint with the negative log-likelihood under the observation model.This can remain a convex optimization problem for many common noise distributions.
- One-bit observations: A key limitation is that likelihood-based recovery requires knowledge of the noise distribution.The method can nevertheless be applied with variants of the algorithms used for other low-rank recovery problems when the resulting optimization is convex.
- Beyond one-bit observations: The framework extends to paired and ordinal comparisons, where observations encode preferences or relative relationships between matrix entries.More general finite-alphabet quantization can be handled by computing the relevant log-likelihood for regularized maximum-likelihood estimation.
- Beyond one-bit observations: Related techniques address signal-dependent Poisson noise and broader exponential-family noise models beyond bounded or Gaussian perturbations.These extensions broaden low-rank recovery to count data and other non-Gaussian settings.
7 Lifting
Lifting recasts quadratic and bilinear inverse problems as linear recovery problems with rank constraints, allowing low-rank recovery theory and algorithms to be applied. The survey covers phase retrieval, blind deconvolution, and related guarantees and limitations.
- 7 Lifting: Quadratic equations in a vector become linear equality constraints on a rank-1 matrix after lifting.This reformulation lets low-rank recovery methods address quadratic systems.
- 7.1 Phase retrieval: PhaseLift treats phase retrieval as rank-constrained linear recovery, while PhaseCut provides a different relaxation with identical recovery conditions.For generic measurements, uniqueness up to sign requires L ≥ 2N − 1, while convex recovery results use larger logarithmic or linear-in-N sample regimes.
- 7.1 Phase retrieval: Recovery guarantees often depend on randomized measurement diversity, whereas physical acquisition systems may not provide isotropic random measurements.The survey describes signal modulation and short-time Fourier-transform measurements as application-motivated alternatives.
- 7.1 Phase retrieval: Recent phase-retrieval results show convex relaxations, projection methods, alternating projections, and local descent can recover signals under stated measurement conditions.One result gives effectiveness when L ≳ N log^3 N; later work reports that L ≳ N observations suffice in a related setting.
- 7.2 Blind deconvolution: Blind deconvolution lifts convolution of two signals into recovery of a non-symmetric rank-1 matrix, with each output sample summing along a skew-diagonal.Finite support alone leaves the problem fundamentally hard because many signal pairs can fit the observations beyond scaling ambiguity.
- 7.2 Blind deconvolution: With known support and random-subspace assumptions, nuclear norm minimization recovers the blind-deconvolution matrix with high probability when max(K, N) ≤ Const · L log^3 L.The associated linear-model dimension can remain within a logarithmic factor of the ambient dimension.