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:
- 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.
- 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