TL;DR
This paper tackles the challenging phase retrieval problem, aiming to reconstruct a signal from its intensity measurements. The authors propose a gradient descent algorithm that achieves global convergence even from random initializations, a significant improvement over existing methods. They also demonstrate that for real-valued signals, the problem becomes locally convex, simplifying the optimization process.
What Problem Does This Paper Address?
Phase retrieval is a fundamental problem in various scientific fields, including X-ray crystallography, microscopy, and optics. It involves recovering a complex signal from measurements of its Fourier transform's intensity, but crucially, not its phase. This loss of phase information makes the problem inherently difficult, often leading to non-convex optimization landscapes with many local minima. While existing methods like alternating projections exist, they can struggle with convergence and are often less effective for complex-valued signals. This paper addresses the generalized phase retrieval problem, where a signal $x \in \mathbb{C}^n$ is recovered from $m$ intensity measurements $y_r = | \langle a_r, x \rangle |^2$, and aims to provide a more robust and efficient algorithm with theoretical guarantees.
Methods
The core of the paper lies in reformulating the phase retrieval problem as a least-squares minimization problem: $f(z) = \frac{1}{2m} \sum_{r=1}^m (|\langle a_r, z \rangle|^2 - y_r)^2$. Despite the non-convexity of this cost function, the authors analyze the global convergence of a gradient descent algorithm. A key contribution is proving that with a sufficiently large number of measurements ($m$), this algorithm can converge to a global minimizer starting from a random initialization, unlike previous work that required spectral initialization.
To accelerate convergence, they explore and apply efficient line search methods, specifically Nonlinear Conjugate Gradient (NCG) and Limited-memory BFGS (LBFGS). They also derive the analytical expressions for the gradient and Hessian of the cost function using Fréchet derivatives, which they find to be more compact than using Wirtinger derivatives. A significant theoretical finding is the proof of local convexity for the cost function when the target signal $x$ is real-valued, which simplifies the optimization landscape near the solution.
Datasets
The paper does not introduce new datasets. Instead, it uses synthetic data generated according to two common models for sampling vectors:
- Gaussian Model: Sampling vectors $a_r \in \mathbb{C}^n$ are drawn from a complex Gaussian distribution.
- Coded Diffraction Pattern (CDP) Model: This model is described as more physically realizable and involves specific types of masks and distributions for their entries.
The authors also use a real-valued image ("Cameraman") for demonstrating performance on real-valued signals.
Key Insights and Ideas
- Global Convergence from Random Initialization: The most significant insight is proving that gradient descent can achieve global convergence for this non-convex problem, even when starting from a random point, provided enough measurements are available. This is a crucial step towards practical, robust phase retrieval.
- Local Convexity for Real Signals: The discovery that the cost function becomes locally convex for real-valued signals is a major theoretical simplification. This suggests that for real signals, the optimization problem is much better behaved, making it easier to find the correct solution.
- LBFGS Superiority: Numerical simulations consistently show that the LBFGS algorithm, a line search method, outperforms other tested methods (including alternative projection) in terms of both convergence speed and computational cost (measured by FFT calls).
- Sampling Complexity: The paper provides theoretical bounds on the number of measurements required for successful recovery, linking it to the dimension of the signal ($n$) and logarithmic factors, which align with their analysis.
Key Results
- Theoretical Guarantees: The paper provides theoretical guarantees for the global convergence of gradient descent with an appropriate stepsize, under the assumption of sufficient measurements (e.g., $m = O(n \log n)$ for Gaussian models).
- Local Convexity Proof: A formal proof of local convexity for the cost function when the signal is real-valued is presented.
- Numerical Performance:
- LBFGS algorithm demonstrates superior performance compared to Steepest Descent, NCG, and Alternative Projection methods in numerical simulations.
- The empirical sampling complexity for successful recovery matches theoretical predictions, with recovery achieved for $m \approx 7n$ in the Gaussian model for $n=1024$.
- For real-valued signals, fewer measurements are needed for successful recovery compared to complex-valued signals.
Limitations and Future Work
- Real-Valued Signal Assumption for Local Convexity: The proof of local convexity is currently limited to sampling vectors following the Gaussian model and real-valued signals. It's an open question whether this holds for CDP models or complex signals.
- Randomness in Sampling: The theoretical analysis relies on random sampling vectors, which can be difficult to implement in practice. Future work could focus on reducing this randomness requirement.
- Complexity of NCG/LBFGS Analysis: While NCG and LBFGS show better practical performance, their theoretical convergence analysis for non-convex problems is more complex and not fully addressed in this paper.
- Signal Structure: The paper suggests exploring how signal structures, such as sparsity, could further improve performance and reduce sampling complexity.
- Practical Implementation: Investigating how to further improve the performance of numerical algorithms and reduce sampling complexity for practical implementations remains an area for future research.
Summary updated