Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5773547 | Applied and Computational Harmonic Analysis | 2017 | 29 Pages |
Abstract
We study the recovery of Hermitian low rank matrices XâCnÃn 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 ajajâ for some measurement vectors a1,â¦,am, i.e., the measurements are given by bj=tr(Xajajâ). The case where the matrix X=xxâ to be recovered is of rank one reduces to the problem of phaseless estimation (from measurements bj=|ãx,ajã|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 aj, j=1,â¦,m, being chosen independently at random according to a standard Gaussian distribution, or aj being sampled independently from an (approximate) complex projective t-design with t=4. In the Gaussian case, we require mâ¥Crn measurements, while in the case of 4-designs we need mâ¥Crnlogâ¡(n). Our results are uniform in the sense that one random choice of the measurement vectors aj 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, Krahmer and Kueng. 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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Analysis
Authors
Richard Kueng, Holger Rauhut, Ulrich Terstiege,