Solving Complex Quadratic Systems With Full-Rank Random Matrices

Shuai Huang, Sidharth Gupta, Ivan Dokmanic

TL;DR

This paper presents a new, efficient method for recovering complex signals from quadratic measurements using full-rank random matrices. The approach, based on spectral initialization and Wirtinger flow, is proven to work with high probability, extending previous results from rank-1 matrices to more general scenarios.

What Problem Does This Paper Address?

Many real-world problems, from molecular geometry reconstruction to optical imaging and power system analysis, can be framed as recovering a signal from quadratic measurements. A well-studied version of this problem is "phase retrieval," where measurements are of the form $y_i = | \mathbf{a}_i^* \mathbf{x} |^2$, and the measurement matrices $\mathbf{a}_i \mathbf{a}_i^*$ are rank-1. However, many applications involve more general quadratic measurements $y_i = \mathbf{x}^* \mathbf{A}_i \mathbf{x}$, where $\mathbf{A}_i$ are full-rank matrices. Existing methods for these full-rank cases often rely on computationally expensive semidefinite relaxations. This paper tackles the challenge of efficiently solving these more general quadratic systems, particularly when the measurement matrices are complex and full-rank, and their entries follow a specific type of random distribution (rotation-invariant sub-Gaussian).

Methods

The authors propose a two-stage approach:

  1. Spectral Initialization: They estimate the signal's structure by constructing a matrix $S$ from the measurements, which is an estimate of $2\mathbf{x}\mathbf{x}^*$. The spectral initializer, $\mathbf{z}^{(0)}$, is then derived from the leading singular vector of $S$. This step provides a good initial guess for the signal.
  2. Wirtinger Flow (WF) Updates: The initial guess is then refined using an iterative optimization algorithm called Wirtinger Flow. This algorithm minimizes a nonconvex loss function that measures the difference between the observed measurements and those predicted by the current signal estimate.

The core theoretical contribution is proving that this standard framework (spectral initialization + WF) works efficiently and with high probability for the specified class of rotation-invariant sub-Gaussian measurement models, even with full-rank matrices. This is achieved by establishing a "regularity condition" for the loss function, which guarantees that the WF algorithm converges to a global optimum from the spectral initializer.

Datasets

Not discussed in the paper. The experiments use simulated data generated according to the described rotation-invariant sub-Gaussian measurement model.

Key Insights and Ideas

  • Generalizing Phase Retrieval: The paper successfully extends powerful recovery techniques from the well-understood rank-1 phase retrieval problem to the more general full-rank quadratic measurement setting.
  • Efficiency of Spectral Initialization: The spectral initialization step is crucial. It provides a starting point that is already close to the true solution, significantly simplifying the subsequent optimization.
  • Power of Wirtinger Flow: Wirtinger Flow, when initialized correctly, is shown to be an effective and efficient algorithm for navigating the nonconvex loss landscape and finding the global optimum.
  • The Role of Random Matrix Theory: The theoretical guarantees rely heavily on properties of rotation-invariant sub-Gaussian random matrices, which allow for simplified proofs compared to correlated measurement models.
  • Practical Implications: The method is applicable to a range of problems where quadratic measurements with full-rank matrices arise, potentially offering a more efficient alternative to existing methods.

Key Results

  • Theoretical Guarantees: The paper proves that for a number of measurements $m$ exceeding the signal dimension $n$ by a sufficiently large constant ($m > Cn$), the proposed method can recover the complex signal up to a global phase shift with high probability.
  • Efficiency: The spectral initialization, particularly when using power iteration to find the leading singular vector, is computationally efficient ($O(n^2)$).
  • Experimental Validation: Numerical experiments demonstrate that the spectral initializer gets closer to the true signal as the number of measurements increases. They also show a clear "phase transition" where recovery success rates jump from low to high as $m/n$ increases, typically around $m/n \approx 4$.
  • Image Reconstruction: The method was successfully applied to reconstruct image channels, showing good performance even with a small number of measurements ($m/n=4$).
  • Comparison to Random Initialization: Spectral initialization was shown to perform better than random initialization for low oversampling ratios ($m/n \in [1, 1.7]$).

Limitations and Future Work

  • "Sufficiently Large" Number of Measurements: The theoretical guarantees hold when $m > Cn$ for some constant $C$. Determining the precise value of $C$ and understanding the exact phase transition behavior for practical scenarios remains an area of interest.
  • General High-Rank Matrices: The current work focuses on rotation-invariant sub-Gaussian matrices. The authors express interest in extending their approach to work with general high-rank complex matrices that appear in various applications.
  • Optimization Landscape: While the paper leverages the success of Wirtinger Flow, it acknowledges recent work on the optimization landscape of similar nonconvex problems and suggests that similar favorable properties might exist for their problem. Future work could explore this further.
  • Robustness to Noise: The current analysis primarily focuses on exact measurements. Investigating the robustness of the method to noisy measurements would be a valuable extension.

Summary updated

Abstract

We tackle the problem of recovering a complex signal ${\boldsymbol{x}}\in \mathbb{C}^n$ from quadratic measurements of the form $y_i={\boldsymbol{x}}^*{\boldsymbol{A}}_i{\boldsymbol{x}}$ , where ${\boldsymbol{A}}_i$ is a full-rank, complex random measurement matrix whose entries are generated from a rotation-invariant sub-Gaussian distribution. We formulate it as the minimization of a nonconvex loss. This problem is related to the well understood phase retrieval problem where the measurement matrix is a rank-1 positive semidefinite matrix. Here we study the general full-rank case which models a number of key applications such as molecular geometry recovery from distance distributions and compound measurements in phaseless diffractive imaging. Most prior works either address the rank-1 case or focus on real measurements. The several papers that address the full-rank complex case adopt the computationally-demanding semidefinite relaxation approach. In this paper we prove that the general class of problems with rotation-invariant sub-Gaussian measurement models can be efficiently solved with high probability via the standard framework comprising a spectral initialization followed by iterative Wirtinger flow updates on a nonconvex loss. Numerical experiments on simulated data corroborate our theoretical analysis.
BibTeX
@article{huang2020solving,
  author = {Shuai Huang and Sidharth Gupta and Ivan Dokmanic},
  title = {{Solving Complex Quadratic Systems With Full-Rank Random Matrices}},
  journal = {IEEE Trans. Signal Process.},
  year = {2020},
  url = {https://openreview.net/forum?id=6TcosQsig3},
}
Figure