Solving systems of phaseless equations via Kaczmarz methods: A proof of concept study

Ke Wei

TL;DR

This paper introduces a novel family of Kaczmarz-based methods for solving the challenging "phaseless" or "phase retrieval" problem, which is fundamental in many imaging and sensing applications. By cleverly integrating a phase selection heuristic into the well-established Kaczmarz method for linear systems, these new algorithms demonstrate significant computational advantages and require fewer measurements for successful signal recovery compared to existing state-of-the-art methods.

What Problem Does This Paper Address?

Phase retrieval is the problem of recovering a signal (or vector) from measurements of its magnitudes, where the phase information is lost. This is a common scenario in fields like X-ray crystallography, diffraction imaging, and microscopy, where detectors can only measure intensity (magnitude squared) and not the phase of the wave. Mathematically, this translates to solving a system of quadratic equations of the form $y_r = | \langle a_r, x \rangle |^2$, where $x$ is the unknown signal, $a_r$ are known measurement vectors, and $y_r$ are the measured magnitudes. A key challenge is that solutions are only unique up to a global phase factor. Existing methods like Error Reduction (ER) and Wirtinger Flow have been developed, but this paper aims to leverage the efficiency of Kaczmarz methods, traditionally used for linear systems, for this non-linear phase retrieval problem.

Methods

The core contribution is the adaptation of the Kaczmarz method for solving systems of linear equations to the phase retrieval problem. The authors propose two main variants:

  • Simple Kaczmarz Method for Phase Retrieval: This method iteratively projects the current estimate onto a hyperplane defined by one of the phaseless equations. The crucial innovation is the integration of a "phase selection heuristic." In each iteration, the phase of the current estimate's projection is used to approximate the true phase, allowing the algorithm to proceed as if it were solving a linear system.
  • Block Kaczmarz Method for Phase Retrieval: This extends the simple method by processing multiple equations (rows of the measurement matrix) simultaneously in blocks. This can lead to faster convergence and better utilization of computational resources, especially when leveraging optimized linear algebra routines.

The algorithms are developed by extending the iterative projection idea of Kaczmarz methods. For linear systems, Kaczmarz projects onto a hyperplane. For phase retrieval, the projection is adapted to account for the quadratic nature of the measurements and the unknown phase.

Datasets

The paper does not introduce new datasets. Instead, it uses simulated data generated according to three models:

  • Gaussian Model: Measurement vectors are drawn from a Gaussian distribution.
  • Unitary Model: The measurement matrix is constructed from unitary matrices.
  • Coded Diffraction Model: This model is inspired by optical imaging and uses Fourier transforms with specific "coded diffraction patterns."

The experiments are conducted on both 1D and 2D signals.

Key Insights and Ideas

  • Kaczmarz for Phase Retrieval is Feasible: The paper demonstrates that the Kaczmarz method, a workhorse for linear systems, can be effectively adapted to the non-linear phase retrieval problem by incorporating a phase selection heuristic.
  • Computational Efficiency: The proposed Kaczmarz-based methods offer significant computational speedups compared to established algorithms like ER and Wirtinger Flow, especially for complex signals and certain measurement models.
  • Measurement Efficiency: The Kaczmarz methods often require fewer measurements for successful signal recovery than existing methods, particularly in real-valued scenarios.
  • Block Processing Advantage: The block Kaczmarz method, by processing multiple measurements at once, can leverage optimized linear algebra libraries (like BLAS and FFT) to achieve substantial speed improvements.
  • Condition Number Matters: The success of the block Kaczmarz method is shown to be sensitive to the condition numbers of the submatrices formed by the blocks. Large condition numbers can hinder accurate recovery.

Key Results

  • Gaussian Models: For real Gaussian signals, the simple and block Kaczmarz methods (with smaller block sizes) achieve high recovery probabilities with approximately 2.5n measurements, significantly outperforming ER (4.5n) and Wirtinger Flow (5n). For complex Gaussian signals, they also show competitive performance, requiring around 4n measurements.
  • Unitary Model: The Kaczmarz method recovers real signals with high probability using about 3n measurements, while ER needs 4.5n.
  • Coded Diffraction Model: The block Kaczmarz method demonstrates strong performance, often requiring fewer measurements than ER and Wirtinger Flow, especially in 2D cases. For instance, in 2D, it needs about 4n measurements, while ER and Wirtinger Flow require 6n and 10n, respectively.
  • Computation Time: Table 1 shows that the block Kaczmarz method is dramatically faster than ER and Wirtinger Flow, often by an order of magnitude, particularly for complex models. For example, it's ten times faster than ER and twenty times faster than Wirtinger Flow for the Milky Way Galaxy reconstruction.
  • Robustness to Noise: The algorithms exhibit desirable linear scaling of relative error with noise level, indicating good robustness.

Limitations and Future Work

  • Phase Selection Heuristic: The paper acknowledges that the phase selection heuristic is an approximation. While effective, its performance relies on how well it approximates the true phase. Further analysis of this heuristic's impact is suggested.
  • Condition Number Sensitivity: The performance of the block Kaczmarz method is shown to degrade when the condition numbers of the submatrices are large. This suggests that understanding and potentially mitigating this sensitivity could be an area for future research.
  • Number of Measurements: A central question remains: precisely how many measurements are theoretically sufficient for Kaczmarz methods to guarantee successful recovery across all scenarios?
  • Exploiting Signal Structure: The authors suggest that further performance improvements might be possible by incorporating prior knowledge about the signal's structure (e.g., sparsity, real-valued).
  • Extension to Related Problems: The Kaczmarz framework could potentially be extended to other related problems like blind deconvolution and self-calibration.
  • Relaxation Parameter: Figure 5 suggests that a relaxation parameter, similar to that used for linear systems, can accelerate convergence for phase retrieval, opening avenues for further optimization.

Summary updated

Abstract

We study the Kaczmarz methods for solving systems of quadratic equations, i.e., the generalized phase retrieval problem. The methods extend the Kaczmarz methods for solving systems of linear equations by integrating a phase selection heuristic in each iteration and overall have the same per iteration computational complexity. Extensive empirical performance comparisons establish the computational advantages of the Kaczmarz methods over other state-of-the-art phase retrieval algorithms both in terms of the number of measurements needed for successful recovery and in terms of computation time. Preliminary convergence analysis is presented for the randomized Kaczmarz methods.
BibTeX
@misc{wei2015solving,
  author = {Ke Wei},
  title = {{Solving systems of phaseless equations via Kaczmarz methods: A proof of concept study}},
  year = {2015},
  eprint = {1502.01822},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1502.01822},
}
Figure