Low rank matrix recovery from rank one measurements

DOI10.1016/J.ACHA.2015.07.007zbMATH1393.94310OpenAlexW2963583445MaRDI QIDQ347516FDOQ347516

Authors Richard Kueng, Holger Rauhut, Ulrich Terstiege

Publication date 30 November 2016

Published in Applied and Computational Harmonic Analysis (Search for Journal in Brave)

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

zbMATH Keywords

convex optimizationmatrix completionquantum state tomographyphase retrievalcomplex projective designslow rank matrix recoveryrandom measurements

Mathematics Subject Classification ID

Convex programming (90C25) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Random matrices (probabilistic aspects) (60B20) Quantum state estimation, approximate cloning (81P50) Sampling theory in information and communication theory (94A20)

Abstract: We study the recovery of Hermitian low rank matrices $Xinmathbb{C}^{nimesn}$ from undersampled measurements via nuclear norm minimization. We consider the particular scenario where the measurements are Frobenius inner products with random rank-one matrices of the form $a_j{a}_j^{\ast }$ for some measurement vectors $a_1,\mathrm{...},a_m$, i.e., the measurements are given by $y_j=mathrmtr(X{a}_j{a}_j^{\ast })$. The case where the matrix $X=x{x}^{\ast }$ to be recovered is of rank one reduces to the problem of phaseless estimation (from measurements, $y_j=|langlex,a_{j}angle{|}^2$ via the PhaseLift approach, which has been introduced recently. We derive bounds for the number $m$ of measurements that guarantee successful uniform recovery of Hermitian rank $r$ matrices, either for the vectors $a_j$, $j=1,\mathrm{...},m$, being chosen independently at random according to a standard Gaussian distribution, or $a_j$ being sampled independently from an (approximate) complex projective $t$-design with $t=4$. In the Gaussian case, we require $mgeqCrn$ measurements, while in the case of $4$-designs we need $mgeqCrnlog(n)$. Our results are uniform in the sense that one random choice of the measurement vectors $a_j$ guarantees recovery of all rank $r$-matrices simultaneously with high probability. Moreover, we prove robustness of recovery under perturbation of the measurements by noise. The result for approximate $4$-designs generalizes and improves a recent bound on phase retrieval due to Gross, Kueng and Krahmer. In addition, it has applications in quantum state tomography. Our proofs employ the so-called bowling scheme which is based on recent ideas by Mendelson and Koltchinskii.

Recommendations

• Low-rank matrix recovery via rank one tight frame measurements
• Recovering low-rank matrices from binary measurements
• The minimal measurement number for low-rank matrix recovery
• Low-Rank Positive Semidefinite Matrix Recovery From Corrupted Rank-One Measurements
• Recovery of low-rank matrices based on the rank null space properties
• Recovering Low-Rank Matrices From Few Coefficients in Any Basis
• Reconstruction of a high-dimensional low-rank matrix
• Low-rank Matrix Recovery from Noisy, Quantized and Erroneous Measurements
• Low-rank matrix recovery via iteratively reweighted least squares minimization
• Low-Rank Matrix Estimation from Rank-One Projections by Unlifted Convex Optimization

Cites work

• scientific article; zbMATH DE number 5968745 (Why is no real title available?)
• scientific article; zbMATH DE number 1033382 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• A mathematical introduction to compressive sensing
• A partial derandomization of phaselift using spherical designs
• ADMiRA: Atomic Decomposition for Minimum Rank Approximation
• An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems
• Averaging sets: A generalization of mean values and spherical designs
• Blind Deconvolution Using Convex Programming
• Bounding the smallest singular value of a random matrix without concentration
• Characterization of the subdifferential of some matrix norms
• Chebyshev-type quadrature on multidimensional domains
• Compressed sensing
• Construction of spherical \(t\)-designs
• Convex Recovery of a Structured Signal from Independent Random Linear Measurements
• Cubature formulas, geometrical designs, reproducing kernels, and Markov operators
• Distinguishability of quantum states under restricted families of measurements with an application to quantum data hiding
• Distinguishing multi-partite states by local measurements
• Evenly distributed unitaries: On the structure of unitary designs
• Exact and Stable Covariance Estimation From Quadratic Sampling via Convex Programming
• Exact matrix completion via convex optimization
• Generating a state \(t\)-design by diagonal quantum circuits
• Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
• Improved recovery guarantees for phase retrieval from coded diffraction patterns
• Incoherence-Optimal Matrix Completion
• Large deviation bounds for \(k\)-designs
• Learning without concentration
• Living on the edge: phase transitions in convex programs with random data
• Low-rank matrix recovery via iteratively reweighted least squares minimization
• Matrix Completion From a Few Entries
• Matrix recipes for hard thresholding methods
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Numerical Cubature Using Error-Correcting Codes
• On signal reconstruction without phase
• Painless reconstruction from magnitudes of frame coefficients
• Phase retrieval from coded diffraction patterns
• Phase retrieval via matrix completion
• Phase retrieval with polarization
• Phaselift: exact and stable signal recovery from magnitude measurements via convex programming
• Proximal splitting methods in signal processing
• Quantum computation and quantum information. 10th anniversary edition
• Quantum tomography via compressed sensing: error bounds, sample complexity and efficient estimators
• Quasi-linear compressed sensing
• Randomizing quantum states: constructions and applications
• Recovering Low-Rank Matrices From Few Coefficients in Any Basis
• Sparse recovery under weak moment assumptions
• Spherical 7-designs in \(2^n\)-dimensional Euclidean space
• Spherical codes and designs
• The Fourth Moment Method
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• The convex geometry of linear inverse problems
• The invariants of the Clifford groups
• Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements
• Tight informationally complete quantum measurements
• User-friendly tail bounds for sums of random matrices

Cited in

(48)

• Recovery algorithms for high-dimensional rank one tensors
• Statistical analysis of compressive low rank tomography with random measurements
• The phase transition of matrix recovery from Gaussian measurements matches the minimax MSE of matrix denoising
• Robust sensing of low-rank matrices with non-orthogonal sparse decomposition
• The minimal measurement number for low-rank matrix recovery
• Performance bounds of the intensity-based estimators for noisy phase retrieval
• Recovering low-rank matrices from binary measurements
• Sensitivity of low-rank matrix recovery
• Recovering Low-Rank and Sparse Components of Matrices from Incomplete and Noisy Observations
• Riemannian optimization for phase retrieval from masked Fourier measurements
• Almost everywhere injectivity conditions for the matrix recovery problem
• Applied harmonic analysis and data processing. Abstracts from the workshop held March 25--31, 2018
• Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems
• Jointly low-rank and bisparse recovery: questions and partial answers
• Proof methods for robust low-rank matrix recovery
• Low-Rank Matrix Estimation from Rank-One Projections by Unlifted Convex Optimization
• Quantization for low-rank matrix recovery
• \( \Gamma \)-conjugate weight enumerators and invariant theory
• Multi-parameter estimation beyond quantum Fisher information
• Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval
• Sparse signal reconstruction via the approximations of \(\ell_0\) quasinorm
• Communication-Efficient Distributed Eigenspace Estimation
• Constrained quantum tomography of semi-algebraic sets with applications to low-rank matrix recovery
• Uniqueness conditions for low-rank matrix recovery
• PhaseMax: stable guarantees from noisy sub-Gaussian measurements
• Phase retrieval from Fourier measurements with masks
• Low rank tensor recovery via iterative hard thresholding
• The numerics of phase retrieval
• Phase retrieval using random cubatures and fusion frames of positive semidefinite matrices
• Dynamical quantum tomography
• Stable low-rank matrix recovery via null space properties
• Time for dithering: fast and quantized random embeddings via the restricted isometry property
• Efficient matrix sensing using rank-1 Gaussian measurements
• Recovery of low-rank matrices based on the rank null space properties
• A comparative study of estimation methods in quantum tomography
• The local convexity of solving systems of quadratic equations
• Tensor theta norms and low rank recovery
• Low-rank matrix recovery via rank one tight frame measurements
• Phase retrieval for affine groups over prime fields
• Fast state tomography with optimal error bounds
• On connections between amplitude flow and error reduction for phase retrieval and ptychography
• WARPd: a linearly convergent first-order primal-dual algorithm for inverse problems with approximate sharpness conditions
• Complex phase retrieval from subgaussian measurements
• Norm and trace estimation with random rank-one vectors
• Phaselift is robust to a constant fraction of arbitrary errors
• Phase retrieval with PhaseLift algorithm
• An Unbiased Approach to Low Rank Recovery
• On the robustness of noise-blind low-rank recovery from rank-one measurements

Describes a project that uses

Uses Software

• UNLocBoX
• ADMiRA
• PhaseLift
• Wirtinger Flow

This page was built for publication: Low rank matrix recovery from rank one measurements

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