|| Sample-Efficient Low Rank Phase Retrieval
||Seyedehsara Nayer, Namrata Vaswani, Iowa State University, United States|
||D5-S4-T3: Topics in Recovery I
||Friday, 16 July, 23:00 - 23:20
||Friday, 16 July, 23:20 - 23:40
This work studies the Low Rank Phase Retrieval (LRPR) problem: recover an n x q rank-r matrix X* from y_k = |A_k^T x^*_k|, k=1, 2,..., q, where x*_k is the k-th column of X*. The different matrices A_k are i.i.d. with i.i.d. standard Gaussian entries in each. We obtain a new guarantee for solving LRPR using the AltMin algorithm, AltMinLowRaP, that was developed and studied in our earlier work. Our result proves the following: if the right singular vectors of X* satisfy the incoherence assumption, and if the total number of measurements, mq > C nr^2 (r + \log(1/\epsilon)), the AltMinLowRaP estimate converges geometrically to X*. In addition, we also need m > C max(r, \log q, \log n) because of the specific asymmetric nature of our problem. Here $C$ is a numerical constant that depends on the condition number and the incoherence parameter. Based on comparison with related well-studied problems -- low-rank matrix completion and sparse PR -- we argue why the above sample complexity cannot be improved any further for any non-convex (iterative) solution to LRPR (which is a problem with non-global and phaseless measurements).