All Dates/Times are Australian Eastern Standard Time (AEST)

Technical Program

Paper Detail

Paper IDD5-S4-T3.1
Paper Title Sample-Efficient Low Rank Phase Retrieval
Authors Seyedehsara Nayer, Namrata Vaswani, Iowa State University, United States
Session D5-S4-T3: Topics in Recovery I
Chaired Session: Friday, 16 July, 23:00 - 23:20
Engagement Session: Friday, 16 July, 23:20 - 23:40
Abstract 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).