Low rank matrix recovery from rank one measurements

详细信息    查看全文

• 作者：Richard Kueng^a ; ^{richard.kueng@physik.uni-freiburg.de} ; Holger Rauhut^b ; ^{rauhut@mathc.rwth-aachen.de} ; Ulrich Terstiege^b ; ^{terstiege@mathc.rwth-aachen.de}
• 关键词：94A20 ; 94A12 ; 60B20 ; 90C25 ; 81P50
• 刊名：Applied and Computational Harmonic Analysis
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：42
• 期：1
• 页码：88-116
• 全文大小：707 K
• 卷排序：42

文摘

We study the recovery of Hermitian low rank matrices X∈Cn×nX∈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,…,ama1,…,am, i.e., the measurements are given by bj=tr(Xajaj⁎). The case where the matrix X=xx⁎X=xx⁎ to be recovered is of rank one reduces to the problem of phaseless estimation (from measurements bj=|〈x,aj〉|2bj=|〈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 ajaj, j=1,…,mj=1,…,m, being chosen independently at random according to a standard Gaussian distribution, or ajaj being sampled independently from an (approximate) complex projective t  -design with t=4t=4. In the Gaussian case, we require m≥Crnm≥Crn measurements, while in the case of 4-designs we need m≥Crnlog⁡(n)m≥Crnlog⁡(n). Our results are uniform in the sense that one random choice of the measurement vectors ajaj 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.