Provable Low Rank Phase Retrieval

Seyedehsara Nayer, Praneeth Narayanamurthy, Namrata VaswaniIEEE Trans. Information Theory 2020 · DOI

TL;DR

This paper introduces the first provably correct algorithm, AltMinLowRaP, for the Low Rank Phase Retrieval (LRPR) problem, enabling efficient recovery of low-rank matrices from magnitude-only linear measurements. This breakthrough significantly reduces the number of measurements needed compared to standard phase retrieval, opening doors for faster and more cost-effective dynamic imaging applications.

What Problem Does This Paper Address?

The classical Phase Retrieval (PR) problem aims to reconstruct a signal from the magnitudes of its linear projections. A significant challenge in PR is the requirement for a large number of measurements, typically proportional to the signal's dimension ($m \ge n$). This paper tackles the Low Rank Phase Retrieval (LRPR) problem, which arises when the unknown signal is structured as a low-rank matrix. The goal is to recover this low-rank matrix from magnitude-only linear measurements, but with a crucial advantage: the number of measurements per column ($m$) can be significantly smaller than the dimension of each column ($n$), specifically $m \ll n$. This is particularly relevant for dynamic imaging scenarios where capturing many frames (columns) is necessary, and each frame might be related to others, forming a low-rank structure. The paper addresses the lack of provably correct algorithms for this LRPR problem, especially in the regime where $m \ll n$.

Methods

The core contribution is the development of AltMinLowRaP (Alternating Minimization for Low-Rank Phase Retrieval), an algorithm that leverages an alternating minimization approach. Key aspects include:

  • Spectral Initialization: A novel spectral initialization step is proposed to estimate the column space of the target low-rank matrix. This step is crucial for kickstarting the alternating minimization process.
  • Alternating Minimization: The algorithm iteratively alternates between updating the estimate of the column space (represented by a matrix $U$) and the low-rank matrix itself (represented by $B$, where $X = UB$).
  • Phase Retrieval for Subproblems: For updating $B$, the algorithm breaks down the problem into smaller, independent, $r$-dimensional standard phase retrieval problems for each column.
  • Provable Guarantees: The paper provides theoretical guarantees for the algorithm's convergence to an $\epsilon$-accurate solution with high probability, under specific assumptions on the measurement matrices (iid Gaussian) and the structure of the unknown matrix (right incoherence).
  • Linear Version Solution: The work also provides the first provable solution for the linear version of the LRPR problem (where the phase information is available), which was previously unsolved.

Datasets

The paper evaluates its algorithm on:

  • Synthetic Data: Generated data is used to compare the performance of AltMinLowRaP against existing methods under various settings of $n$, $q$, $r$, and $m$.
  • Real Videos: Two real video sequences (a plane and a moving mouse) are used, simulated with Coded Diffraction Pattern (CDP) measurements. This allows for evaluation in a more realistic scenario where the underlying signal is only approximately low-rank.

Key Insights and Ideas

  • Low-rank structure is key to reducing measurement complexity: The paper demonstrates that by exploiting the low-rank property of the signal, it's possible to recover it with significantly fewer measurements ($m \ll n$) than required for standard phase retrieval.
  • Alternating minimization is effective for LRPR: The proposed AltMinLowRaP algorithm shows that an iterative approach can effectively handle the non-convexity and magnitude-only constraints of the LRPR problem.
  • Spectral initialization is crucial: The success of the alternating minimization hinges on a good initial estimate of the signal's subspace, which the paper provides through a novel spectral method.
  • The linear version of LRPR was surprisingly unsolved: The paper highlights that even the simpler linear version of the LRPR problem lacked provable guarantees, underscoring the novelty of their contribution.
  • Practical implications for dynamic imaging: The ability to recover low-rank signals with fewer measurements has direct applications in fields like dynamic biomedical imaging, enabling faster and less intrusive data acquisition.

Key Results

  • Provable Guarantees: AltMinLowRaP is shown to recover the low-rank matrix $X^*$ to $\epsilon$ accuracy with high probability, provided $mq > Cnr^4 \log(1/\epsilon)$ and the right incoherence assumption holds.
  • Sample Complexity Improvement: The algorithm achieves a sample complexity that depends on $r$ and is significantly better than standard PR methods when $r$ is small, especially when $m \ll n$. For example, when $q \gg nr^4$, $m$ can be as low as $O(r^4 \log(1/\epsilon))$.
  • Time Complexity: The algorithm has a geometric convergence rate, with a time complexity of $O(mqnr \log^2(1/\epsilon))$.
  • Experimental Validation: Numerical experiments on both synthetic and real data demonstrate that AltMinLowRaP outperforms existing methods, including unstructured PR algorithms and prior LRPR heuristics, especially in the low-measurement regime.
  • Comparison with Sparse PR: The paper shows that for slowly changing videos, the low-rank model provides a better reconstruction than wavelet-sparse models.

Limitations and Future Work

  • Assumptions: The theoretical guarantees rely on assumptions such as iid Gaussian measurement matrices and right incoherence of the unknown matrix. The practical performance might degrade if these assumptions are violated.
  • Sample Splitting: The theoretical analysis assumes sample splitting (using disjoint sets of measurements for initialization and updates), which increases the total number of measurements required. The authors suggest exploring alternating gradient descent to remove this requirement.
  • Dependence on $\kappa$ and $\mu$: The sample complexity has a dependence on the condition number ($\kappa$) and incoherence parameter ($\mu$) of the matrix $X^*$. The authors suggest that further work might reduce this dependence.
  • Future Work: The authors propose several avenues for future research:
  • Removing the sample-splitting requirement.
  • Reducing the dependence on $\kappa$ and $\mu$.
  • Analyzing a modified algorithm for the linear version of the problem to potentially improve guarantees.
  • Exploring the use of the right incoherence assumption within the algorithm itself.
  • Investigating the possibility of solving phaseless Low-Rank Matrix Sensing (LRMS).
  • Developing algorithms that exploit both low-rank and column-wise sparsity.

Summary updated

BibTeX
@article{nayer2020provable,
  author = {Seyedehsara Nayer and Praneeth Narayanamurthy and Namrata Vaswani},
  title = {{Provable Low Rank Phase Retrieval}},
  journal = {IEEE Trans. Information Theory},
  year = {2020},
  doi = {10.1109/tit.2020.2984478},
}
Figure