Low rank matrix recovery from rank one measurements

DOI10.1016/J.ACHA.2015.07.007MaRDI QIDQ347516zbMATH OpenOpenAlexFDO

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

(54)

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

Describes a project that uses

Uses Software

• Wirtinger Flow
• PhaseLift
• ADMiRA
• UNLocBoX

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)