Seyedehsara Nayer, 'Provable Low Rank Phase Retrieval', TADS Lunch-n-Learn

Presenter: Seyedehsara Nayer

Title: Provable Low Rank Phase Retrieval

Abstract: We study the Low Rank Phase Retrieval (LRPR) problem defined as follows: recover an n \times q matrix X^∗ of rank r from a different and independent set of m phaseless (magnitude-only) linear projections of each of its columns. To be precise, we need to recover X^∗ from y_k := |A_k' x^∗_k|, k = 1, 2, \cdots , q when the measurement matrices A_k are mutually independent. Here y_k is an m length vector, A_k is an $n \times m$ matrix, and ' denotes matrix transpose. The question is when can we solve LRPR with m < n? A reliable solution can enable fast and low-cost phaseless dynamic imaging, e.g., Fourier ptychographic imaging of live biological specimens. In this work, we develop the first provably correct approach for solving this LRPR problem. Our proposed algorithm, Alternating Minimization for Low-Rank Phase Retrieval (AltMinLowRaP), is an AltMin based solution and hence is also provably fast (converges geometrically). Our guarantee shows that AltMinLowRaP solves LRPR to \epsilon accuracy, with high probability, as long as m q ≥ C n r^4 \log(1/ \epsilon), the matrices A_k contain i.i.d. standard Gaussian entries, and the right singular vectors of X^∗ satisfy the incoherence assumption from matrix completion literature. Here C is a numerical constant that only depends on the condition number of X^∗ and on its incoherence parameter. This means that on average recovering every column needs C n r^4 \log(1/ \epsilon) which for large q is much smaller than n which is needed by regular Phase retrieval algorithms. Its time complexity is only C m q n r \log^2 (1/\epsilon ). Since even the linear (with phase) version of the above problem is not fully solved, the above result is also the first complete solution and guarantee for the linear case.

Bio: Sara Nayer is currently a PhD student in the Department of Electrical and Computer Engineering at Iowa State University. Previously, she was working at Signal Processing Research Laboratory, Sharif University of Technology. Her research interests are around various aspects of information science and focuses on Computer Vision, Signal Processing, and Statistical Machine Learning.

After the presentation, there will be a short time for discussion and questions afterwards.