Weighted Riemannian Optimization for Solving Quadratic Equations from Gaussian Magnitude Measurements

1. Problem Statement

The paper addresses the Generalized Phase Retrieval problem. The goal is to reconstruct a complex signal $x \in \mathbb{C}^n$ from $m$ phaseless measurements given by:
$$y_k = |\langle a_k, x \rangle|^2, \quad k = 1, \dots, m$$
where $a_k$ are known measurement vectors (specifically, random complex Gaussian vectors) and $y_k$ are the observed magnitudes. The phase information is lost, making the problem non-convex and ill-posed without additional constraints.

The authors reformulate this problem using a "lifting" technique. By defining $X = xx^*$, the quadratic equations become linear in terms of the rank-1 positive semidefinite (PSD) matrix $X$:
$$y_k = \langle a_k a_k^*, X \rangle$$
The problem is thus transformed into finding a rank-1 solution to a system of linear equations on the manifold of rank-1 matrices.

2. Methodology

2.1 Unification of Existing Algorithms

The authors first unify two major classes of existing non-convex phase retrieval algorithms under a Riemannian Gradient Descent (RGD) framework on the manifold $\mathcal{M}_1$ (the set of Hermitian rank-1 matrices):

1. Canonical RGD: Operates directly on the matrix manifold using the standard (canonical) metric inherited from the ambient space of Hermitian matrices.
2. Wirtinger Flow (WF): Operates on the vector space but is shown to be equivalent to an RGD algorithm on the matrix manifold using a specific pseudo-inner product (weighted metric).

2.2 The Convergence Limitation

The paper identifies a critical bottleneck in existing methods: the condition number ($\kappa_g$) of the sensing operator restricted to the tangent space of the manifold.

• The convergence rate of RGD is linear, governed by $1 - O(\kappa_g^{-1})$.
• For both Canonical RGD and WF, the condition number $\kappa_g$ is strictly greater than 1 (approaching 2 and 4, respectively, for Gaussian measurements), even as the number of samples $m \to \infty$.
• This prevents the convergence factor from approaching 0, leading to suboptimal convergence speeds.

2.3 Proposed Solution: Weighted RGD (WRGD)

To overcome this, the authors propose a Weighted Riemannian Gradient Descent (WRGD) algorithm based on a newly designed Riemannian metric.

• Metric Design: They construct a metric $\langle \cdot, \cdot \rangle_o$ such that the expected value of the squared norm of the measurement operator matches the metric norm:
  $$\|W\|_o^2 = \mathbb{E}\left[ \frac{1}{m} \|A(W)\|_2^2 \right] = \|W\|_F^2 + \text{tr}(W)^2$$
  This metric is derived from the expectation of the inner product of the measurements.
• Near-Isometry: Under this new metric, the sensing operator $A$ acts as a near-isometry on the tangent space. As the truncation parameters increase, the condition number $\kappa_o$ approaches 1.
• Truncated Variant (TWRGD): To ensure stability and handle outliers in the gradient, the authors introduce a Truncated WRGD (TWRGD) algorithm. This involves:
  1. Initialization: Using a truncated spectral method to generate an initial guess close to the true solution.
  2. Truncation: Applying adaptive truncation rules to the gradient calculation to filter out "bad" measurements that deviate significantly from the expected behavior.
  3. Update: Performing gradient descent steps using the weighted metric and projecting back to the rank-1 manifold via SVD.

3. Key Contributions

1. Optimal Metric Derivation: The paper derives a simple, computationally efficient Riemannian metric that induces near-isometry for the sensing operator. This is a theoretical breakthrough, as it allows the condition number to approach 1, unlike previous metrics.
2. Theoretical Recovery Guarantees:
   • The authors prove that TWRGD converges linearly to the global minimum (the true rank-1 matrix $X$) with a contraction factor that can be made arbitrarily close to 0.
   • This is achieved with optimal sample complexity of $m = O(n)$ (specifically $m \geq c n$) for random complex Gaussian measurements.
   • The proof relies on establishing a "Restricted Near-Isometry Property" and "Restricted Weak Correlation" under the new metric.
3. Algorithmic Efficiency: The proposed algorithm maintains the computational complexity of vector-based methods (like WF) despite operating on matrices, as the updates can be computed via vector operations without full matrix SVDs at every step.

4. Results

Theoretical Results

• Convergence Rate: The contraction factor $\nu$ of TWRGD decreases to 0 as the truncation parameters ($\tau_0, \tau_1, \tau_2$) increase. In contrast, existing methods (Canonical RGD, TWF) have a non-zero lower bound on their contraction factors.
• Sample Complexity: The algorithm succeeds with $O(n)$ measurements, which is information-theoretically optimal for phase retrieval.

Empirical Results

Numerical experiments were conducted on noise-free signals ($n=1000$) with complex Gaussian measurements.

• Comparison: TWRGD was compared against Truncated Riemannian Gradient Descent (TRGD), Truncated Wirtinger Flow (TWF), and Truncated Amplitude Flow (TAF).
• Performance:
  • Iterations: TWRGD required significantly fewer iterations to reach a target Mean Squared Error (MSE) compared to all competitors.
  • Time: TWRGD achieved the fastest convergence in terms of CPU time.
  • Condition Number: The experiments confirmed that the condition number for TWRGD approaches 1, while TRGD and TWF remained strictly above 1, validating the theoretical analysis.
  • Success Rate: TWRGD achieved high-probability exact recovery (MSE < $10^{-3}$) once $m \approx 5n$, outperforming TWF and matching or exceeding the performance of TAF and TRGD.

5. Significance

This paper makes a significant contribution to the field of phase retrieval and Riemannian optimization by:

• Bridging Theory and Practice: It demonstrates that the choice of Riemannian metric is not just a mathematical detail but a critical factor determining the convergence speed of optimization algorithms.
• Optimizing Convergence: By designing a metric that aligns with the statistical properties of the measurement operator, the authors achieve a convergence rate that is theoretically optimal (approaching zero contraction factor), a feat previously unattainable with standard metrics.
• Practical Impact: The proposed TWRGD algorithm offers a faster and more robust solution for phase retrieval problems, which are fundamental in fields like X-ray crystallography, diffraction imaging, and microscopy.

In summary, the paper establishes that by carefully tailoring the Riemannian metric to the data generation process (Gaussian measurements), one can transform a standard gradient descent algorithm into a near-optimal solver for phase retrieval, achieving both theoretical optimality and superior empirical performance.