Sensitivity of low-rank matrix recovery
From MaRDI portal
Publication:2100520
Abstract: We characterize the first-order sensitivity of approximately recovering a low-rank matrix from linear measurements, a standard problem in compressed sensing. A special case covered by our analysis is approximating an incomplete matrix by a low-rank matrix. We give an algorithm for computing the associated condition number and demonstrate experimentally how the number of linear measurements affects it. In addition, we study the condition number of the rank-r matrix approximation problem. It measures in the Frobenius norm by how much an infinitesimal perturbation to an arbitrary input matrix is amplified in the movement of its best rank-r approximation. We give an explicit formula for the condition number, which shows that it does depend on the relative singular value gap between the rth and (r+1)th singular values of the input matrix.
Recommendations
- Robust sensing of low-rank matrices with non-orthogonal sparse decomposition
- Low rank matrix recovery from rank one measurements
- The minimal measurement number for low-rank matrix recovery
- Recovering low-rank matrices from binary measurements
- Lower Bounds on the Mean-Squared Error of Low-Rank Matrix Reconstruction
- \(s\)-goodness for low-rank matrix recovery
- Nonconvex Robust Low-Rank Matrix Recovery
- Recovering Low-Rank and Sparse Components of Matrices from Incomplete and Noisy Observations
- Compressed sensing of low-rank plus sparse matrices
- Recovery of low-rank matrices based on the rank null space properties
Cites work
- A geometric approach to dynamical model order reduction
- A mathematical introduction to compressive sensing
- A Theory of Condition
- Algebraic compressed sensing
- An Extrinsic Look at the Riemannian Hessian
- COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
- Compressed sensing
- Condition. The geometry of numerical algorithms
- Convex multi-task feature learning
- Elementary differential geometry.
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- scientific article; zbMATH DE number 1617759 (Why is no real title available?)
- scientific article; zbMATH DE number 3842680 (Why is no real title available?)
- scientific article; zbMATH DE number 52497 (Why is no real title available?)
- scientific article; zbMATH DE number 5223994 (Why is no real title available?)
- Intrinsic volumes of symmetric cones and applications in convex programming
- Introduction to Riemannian Manifolds
- Introduction to Smooth Manifolds
- Low-Rank Matrix Approximations Do Not Need a Singular Value Gap
- Low-rank matrix completion by Riemannian optimization
- Matrix rigidity and the ill-posedness of robust PCA and matrix completion
- New estimates for the recursive low-rank truncation of block-structured matrices
- Optimization and dynamical systems
- Perturbation expansions and error bounds for the truncated singular value decomposition
- Random projections of smooth manifolds
- Riemannian Geometry
- Some remarks on the measurability of certain sets
- Stable signal recovery from incomplete and inaccurate measurements
- Structured Compressed Sensing: From Theory to Applications
- The Condition Number of Riemannian Approximation Problems
- The gap between theory and practice in function approximation with deep neural networks
- The geometry of graphs and some of its algorithmic applications
- Theory of semidefinite programming for sensor network localization
- Video Deraining and Desnowing Using Temporal Correlation and Low-Rank Matrix Completion
Cited in
(5)
This page was built for publication: Sensitivity of low-rank matrix recovery
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2100520)
