Proof methods for robust low-rank matrix recovery
From MaRDI portal
(Redirected from Publication:2106469)
Abstract: Low-rank matrix recovery problems arise naturally as mathematical formulations of various inverse problems, such as matrix completion, blind deconvolution, and phase retrieval. Over the last two decades, a number of works have rigorously analyzed the reconstruction performance for such scenarios, giving rise to a rather general understanding of the potential and the limitations of low-rank matrix models in sensing problems. In this article, we compare the two main proof techniques that have been paving the way to a rigorous analysis, discuss their potential and limitations, and survey their successful applications. On the one hand, we review approaches based on descent cone analysis, showing that they often lead to strong guarantees even in the presence of adversarial noise, but face limitations when it comes to structured observations. On the other hand, we discuss techniques using approximate dual certificates and the golfing scheme, which are often better suited to deal with practical measurement structures, but sometimes lead to weaker guarantees. Lastly, we review recent progress towards analyzing descent cones also for structured scenarios -- exploiting the idea of splitting the cones into multiple parts that are analyzed via different techniques.
Recommendations
- On the convex geometry of blind deconvolution and matrix completion
- An analysis of noise folding for low-rank matrix recovery
- Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence
- Low rank matrix recovery with adversarial sparse noise
- Uniqueness conditions for low-rank matrix recovery
Cites work
- scientific article; zbMATH DE number 4061904 (Why is no real title available?)
- scientific article; zbMATH DE number 967931 (Why is no real title available?)
- A Probabilistic and RIPless Theory of Compressed Sensing
- A mathematical introduction to compressive sensing
- A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
- A partial derandomization of phaselift using spherical designs
- A simpler approach to matrix completion
- An algebraic characterization of injectivity in phase retrieval
- Blind Deconvolution Meets Blind Demixing: Algorithms and Performance Bounds
- Blind Deconvolution Using Convex Programming
- Blind Demixing and Deconvolution at Near-Optimal Rate
- Blind Recovery of Sparse Signals From Subsampled Convolution
- Bounding the smallest singular value of a random matrix without concentration
- Characterization of the subdifferential of some matrix norms
- Complex phase retrieval from subgaussian measurements
- Convex Recovery of a Structured Signal from Independent Random Linear Measurements
- Convex multi-task feature learning
- Decoding by Linear Programming
- Exact matrix completion via convex optimization
- Explicit frames for deterministic phase retrieval via PhaseLift
- Guaranteed Matrix Completion via Non-Convex Factorization
- Harmonic mean iteratively reweighted least squares for low-rank matrix recovery
- Identifiability in Bilinear Inverse Problems With Applications to Subspace or Sparsity-Constrained Blind Gain and Phase Calibration
- Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution
- Improved recovery guarantees for phase retrieval from coded diffraction patterns
- Incoherence-Optimal Matrix Completion
- Learning without concentration
- Living on the edge: phase transitions in convex programs with random data
- Localization from incomplete noisy distance measurements
- Low rank matrix recovery from rank one measurements
- Low-rank matrix completion using alternating minimization
- Low-rank matrix recovery via iteratively reweighted least squares minimization
- Matrix Completion From a Few Entries
- Matrix completion from noisy entries
- Noisy low-rank matrix completion with general sampling distribution
- Noisy matrix completion: understanding statistical guarantees for convex relaxation via nonconvex optimization
- Non-Bayesian Activity Detection, Large-Scale Fading Coefficient Estimation, and Unsourced Random Access With a Massive MIMO Receiver
- Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion
- On the convex geometry of blind deconvolution and matrix completion
- Optimal injectivity conditions for bilinear inverse problems with applications to identifiability of deconvolution problems
- Optimal rates of convergence for noisy sparse phase retrieval via thresholded Wirtinger flow
- Painless reconstruction from magnitudes of frame coefficients
- Phase Retrieval Without Small-Ball Probability Assumptions
- Phase retrieval from coded diffraction patterns
- Phase retrieval via Wirtinger flow: theory and algorithms
- Phase retrieval via matrix completion
- Phase retrieval: stability and recovery guarantees
- Phaselift: exact and stable signal recovery from magnitude measurements via convex programming
- Practical sketching algorithms for low-rank matrix approximation
- Recovering Low-Rank Matrices From Few Coefficients in Any Basis
- Robust Nonnegative Sparse Recovery and the Nullspace Property of 0/1 Measurements
- Simultaneously Structured Models With Application to Sparse and Low-Rank Matrices
- Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems
- Solving quadratic equations via phaselift when there are about as many equations as unknowns
- Sparse Approximate Solutions to Linear Systems
- Sparse power factorization: balancing peakiness and sample complexity
- Stable low-rank matrix recovery via null space properties
- Stable signal recovery from incomplete and inaccurate measurements
- Suprema of chaos processes and the restricted isometry property
- The Power of Convex Relaxation: Near-Optimal Matrix Completion
- The convex geometry of linear inverse problems
- User-friendly tail bounds for sums of random matrices
Cited in
(5)- scientific article; zbMATH DE number 7283488 (Why is no real title available?)
- On the convex geometry of blind deconvolution and matrix completion
- Uniform recovery guarantees for quantized corrupted sensing using structured or generative priors
- Stability of low-rank matrix recovery and its connections to Banach space geometry
- Recovery of low-rank matrices based on the rank null space properties
This page was built for publication: Proof methods for robust low-rank matrix recovery
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2106469)
