Provable Low Rank Phase Retrieval
Seyedehsara Nayer, Praneeth Narayanamurthy, Namrata Vaswani
Abstract
We study the Low Rank Phase Retrieval (LRPR) problem defined as follows: recover an n X × 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 <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</sub> := |A <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</sub> 'x* <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</sub> |, k = 1, 2, . . . , q when the measurement matrices Ak are mutually independent. Here y <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</sub> is an m length vector, A <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</sub> is an n × 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 ∈ accuracy, with high probability, as long as mq ≥ Cnr <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">4</sup> log(1/∈), the matrices Ak 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. Its time complexity is only Cmqnr log <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> (1/∈). 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. Finally, we also develop a simple extension of our results for the dynamic LRPR setting.