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^{\ast }$ 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^{\ast }$ from $y_k:=|A_k{}^{\prime }{x}_k^{\ast }|,k=1,2,\dots ,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 ${}^{\prime }$ denotes matrix transpose. The question is when can we solve LRPR with $m\ll 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 $mq\ge Cn{r}^4\log (1/\epsilon )$, the matrices $A_k$ contain i.i.d. standard Gaussian entries, and the right singular vectors of $X^{\ast }$ satisfy the incoherence assumption from matrix completion literature. Here $C$ is a numerical constant that only depends on the condition number of $X^{\ast }$ and on its incoherence parameter. Its time complexity is only $Cmqnr{\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. Finally, we also develop a simple extension of our results for the dynamic LRPR setting.

arXiv commentA short version of this work is in ICML 2019, this longer version is published in IEEE Trans. Info. Th on March 2020. Fixing minor but important errors in Lemmas 3.10, 3.11, 3.12 statements and in proof of the Term1 bound. No change to Theorem statement

References in corpus (17)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Guaranteed Matrix Completion via Non-convex Factorization
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Tight oracle bounds for low-rank matrix recovery from a minimal number of random measurements
• Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
• PETRELS: Parallel Subspace Estimation and Tracking by Recursive Least Squares from Partial Observations
• STFT Phase Retrieval: Uniqueness Guarantees and Recovery Algorithms
• Non-convex Robust PCA
• Low Rank Phase Retrieval
• Sketched SVD: Recovering Spectral Features from Compressive Measurements
• Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
• Reshaped Wirtinger Flow and Incremental Algorithm for Solving Quadratic System of Equations
• Provable Subspace Tracking from Missing Data and Matrix Completion
• Sparse Phase Retrieval via Truncated Amplitude Flow
• Nearly Optimal Robust Subspace Tracking
• Phaseless Subspace Tracking