Stable low-rank matrix recovery via null space properties

DOI10.1093/IMAIAI/IAW014zbMATH Open1388.94018arXiv1507.07184OpenAlexW2963863416MaRDI QIDQ4606522FDOQ4606522

Holger Rauhut, Ulrich Terstiege, Richard Kueng, Maryia Kabanava

Publication date: 8 March 2018

Published in: Information and Inference: A Journal of the IMA (Search for Journal in Brave)

Abstract: The problem of recovering a matrix of low rank from an incomplete and possibly noisy set of linear measurements arises in a number of areas. In order to derive rigorous recovery results, the measurement map is usually modeled probabilistically. We derive sufficient conditions on the minimal amount of measurements ensuring recovery via convex optimization. We establish our results via certain properties of the null space of the measurement map. In the setting where the measurements are realized as Frobenius inner products with independent standard Gaussian random matrices we show that $10r(n_1+n_2)$ measurements are enough to uniformly and stably recover an $n_{1}imes{n}_2$ matrix of rank at most $r$. We then significantly generalize this result by only requiring independent mean-zero, variance one entries with four finite moments at the cost of replacing $10$ by some universal constant. We also study the case of recovering Hermitian rank-$r$ matrices from measurement matrices proportional to rank-one projectors. For $mgeqCrn$ rank-one projective measurements onto independent standard Gaussian vectors, we show that nuclear norm minimization uniformly and stably reconstructs Hermitian rank-$r$ matrices with high probability. Next, we partially de-randomize this by establishing an analogous statement for projectors onto independent elements of a complex projective 4-designs at the cost of a slightly higher sampling rate $mgeqCrnlogn$. Moreover, if the Hermitian matrix to be recovered is known to be positive semidefinite, then we show that the nuclear norm minimization approach may be replaced by minimizing the $el{l}_2$-norm of the residual subject to the positive semidefinite constraint. Then no estimate of the noise level is required a priori. We discuss applications in quantum physics and the phase retrieval problem.

Full work available at URL: https://arxiv.org/abs/1507.07184

zbMATH Keywords

convex optimizationlow-rank matrix recoveryquantum state tomographyphase retrievalnuclear norm minimizationcomplex projective designsrandom measurementspositive semidefinite least squares problem

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Phaselift: exact and stable signal recovery from magnitude measurements via convex programming
• Phase Retrieval via Wirtinger Flow: Theory and Algorithms
• ADMiRA: Atomic Decomposition for Minimum Rank Approximation
• Phase retrieval via matrix completion
• Simultaneous analysis of Lasso and Dantzig selector
• Restricted eigenvalue properties for correlated Gaussian designs
• Exact matrix completion via convex optimization
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• Some estimates of norms of random matrices
• User-friendly tail bounds for sums of random matrices
• A mathematical introduction to compressive sensing
• Distinguishability of quantum states under restricted families of measurements with an application to quantum data hiding
• Quantum tomography under prior information
• Quantum Computation and Quantum Information
• Tight informationally complete quantum measurements
• Characterization of the law of the iterated logarithm in Banach spaces
• On sparse reconstruction from Fourier and Gaussian measurements
• The convex geometry of linear inverse problems
• Learning without concentration
• Bounding the Smallest Singular Value of a Random Matrix Without Concentration
• Living on the edge: phase transitions in convex programs with random data
• Painless reconstruction from magnitudes of frame coefficients
• Low-rank Matrix Recovery via Iteratively Reweighted Least Squares Minimization
• Stable optimizationless recovery from phaseless linear measurements
• Solving quadratic equations via phaselift when there are about as many equations as unknowns
• Quantum tomography via compressed sensing: error bounds, sample complexity and efficient estimators
• On the Uniqueness of Nonnegative Sparse Solutions to Underdetermined Systems of Equations
• A partial derandomization of phaselift using spherical designs
• Condition Numbers of Gaussian Random Matrices
• Null space conditions and thresholds for rank minimization
• Convex Recovery of a Structured Signal from Independent Random Linear Measurements
• Exact and Stable Covariance Estimation From Quadratic Sampling via Convex Programming
• Improved recovery guarantees for phase retrieval from coded diffraction patterns
• Low rank matrix recovery from rank one measurements
• Strong converse for identification via quantum channels
• Sharp recovery bounds for convex demixing, with applications
• Normalized iterative hard thresholding for matrix completion
• The role of topology in quantum tomography
• Compressive Multiplexing of Correlated Signals

Cited In (25)

• Mixing properties of stochastic quantum Hamiltonians
• Complex phase retrieval from subgaussian measurements
• Guarantees of Riemannian optimization for low rank matrix recovery
• Stable and robust $\ell_p$-constrained compressive sensing recovery via robust width property
• Title not available (Why is that?)
• Phase retrieval with PhaseLift algorithm
• WARPd: A Linearly Convergent First-Order Primal-Dual Algorithm for Inverse Problems with Approximate Sharpness Conditions
• An analysis of noise folding for low-rank matrix recovery
• Fast state tomography with optimal error bounds
• Compressive statistical learning with random feature moments
• Estimation of low rank density matrices: bounds in Schatten norms and other distances
• Gradient descent for deep matrix factorization: dynamics and implicit bias towards low rank
• Perturbation analysis of low-rank matrix stable recovery
• On the robustness of noise-blind low-rank recovery from rank-one measurements
• Tensor-free proximal methods for lifted bilinear/quadratic inverse problems with applications to phase retrieval
• Jointly low-rank and bisparse recovery: Questions and partial answers
• On connections between amplitude flow and error reduction for phase retrieval and ptychography
• 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
• Null space conditions and thresholds for rank minimization
• Low-rank matrix recovery via rank one tight frame measurements
• Algebraic compressed sensing
• Truncated sparse approximation property and truncated \(q\)-norm minimization
• Statistical analysis of compressive low rank tomography with random measurements
• Proof methods for robust low-rank matrix recovery

Uses Software

• ADMiRA
• PhaseLift
• Wirtinger Flow

This page was built for publication: Stable low-rank matrix recovery via null space properties

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4606522)