Low rank matrix recovery from rank one measurements

DOI10.1016/J.ACHA.2015.07.007zbMATH Open1393.94310arXiv1410.6913OpenAlexW2963583445MaRDI QIDQ347516FDOQ347516

Richard Kueng, Holger Rauhut, Ulrich Terstiege

Publication date: 30 November 2016

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

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^{*}$ for some measurement vectors $a_1,\mathrm{...},a_m$, i.e., the measurements are given by $y_j=mathrmtr(X{a}_j{a}_j^{*})$. The case where the matrix $X=x{x}^{*}$ 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.

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)

Cites Work

• Phaselift: exact and stable signal recovery from magnitude measurements via convex programming
• ADMiRA: Atomic Decomposition for Minimum Rank Approximation
• Phase retrieval via matrix completion
• Title not available (Why is that?)
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Title not available (Why is that?)
• 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
• Characterization of the subdifferential of some matrix norms
• Compressed sensing
• User-friendly tail bounds for sums of random matrices
• Proximal Splitting Methods in Signal Processing
• Title not available (Why is that?)
• A mathematical introduction to compressive sensing
• Matrix Completion From a Few Entries
• Distinguishability of quantum states under restricted families of measurements with an application to quantum data hiding
• Quantum Computation and Quantum Information
• Tight informationally complete quantum measurements
• Distinguishing multi-partite states by local measurements
• Title not available (Why is that?)
• Sparse recovery under weak moment assumptions
• 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
• Recovering Low-Rank Matrices From Few Coefficients in Any Basis
• The invariants of the Clifford groups
• Averaging sets: A generalization of mean values and spherical designs
• Construction of spherical \(t\)-designs
• Spherical codes and designs
• Matrix recipes for hard thresholding methods
• Painless reconstruction from magnitudes of frame coefficients
• Randomizing quantum states: constructions and applications
• On signal reconstruction without phase
• Phase retrieval with polarization
• Low-rank Matrix Recovery via Iteratively Reweighted Least Squares Minimization
• Quasi-linear Compressed Sensing
• Quantum tomography via compressed sensing: error bounds, sample complexity and efficient estimators
• A partial derandomization of phaselift using spherical designs
• Phase retrieval from coded diffraction patterns
• Chebyshev-type quadrature on multidimensional domains
• Spherical 7-designs in \(2^n\)-dimensional Euclidean space
• Convex Recovery of a Structured Signal from Independent Random Linear Measurements
• Exact and Stable Covariance Estimation From Quadratic Sampling via Convex Programming
• Incoherence-Optimal Matrix Completion
• Blind Deconvolution Using Convex Programming
• Title not available (Why is that?)
• Numerical Cubature Using Error-Correcting Codes
• Improved recovery guarantees for phase retrieval from coded diffraction patterns
• Evenly distributed unitaries: On the structure of unitary designs
• Large deviation bounds for k -designs
• The Fourth Moment Method
• Generating a statet-design by diagonal quantum circuits

Cited In (44)

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

Uses Software

• UNLocBoX
• ADMiRA
• PhaseLift
• Wirtinger Flow

   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 👍 👎

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)