Source-linked AI summary
Phase Retrieval using Alternating Minimization
Praneeth Netrapalli, Prateek Jain, Sujay Sanghavi
TL;DR
The paper addresses the lack of global convergence guarantees for widely used alternating-minimization methods in phase retrieval. It develops a resampled alternating-minimization algorithm and proves geometric convergence under Gaussian measurements, while also treating sparse signals. The results provide the first theoretical guarantee of this kind, but rely on resampling that may be impractical.
Problem
Phase retrieval seeks to recover a vector from magnitude-only measurements, while widely used alternating-minimization methods lack global convergence guarantees.
Method
The paper develops alternating-minimization algorithms, including a resampled version for analysis and a separate method for sparse signals.
Results
The resampled algorithm geometrically converges under Gaussian measurements, and the paper gives the first theoretical correctness guarantee for alternating minimization in phase retrieval.
Takeaways & Limitations
Alternating minimization can have rigorous recovery guarantees for phase retrieval while retaining better computational scaling than SDP-based methods in the sparse setting.
Takeaways & Limitations
The convergence guarantee uses different measurement samples in each iteration, which may be infeasible when collecting many measurements is impractical.
Abstract
from arXiv · showhide
Phase retrieval problems involve solving linear equations, but with missing sign (or phase, for complex numbers) information. More than four decades after it was first proposed, the seminal error reduction algorithm of (Gerchberg and Saxton 1972) and (Fienup 1982) is still the popular choice for solving many variants of this problem. The algorithm is based on alternating minimization; i.e. it alternates between estimating the missing phase information, and the candidate solution. Despite its wide usage in practice, no global convergence guarantees for this algorithm are known. In this paper, we show that a (resampling) variant of this approach converges geometrically to the solution of one such problem -- finding a vector $\mathbf{x}$ from $\mathbf{y},\mathbf{A}$, where $\mathbf{y} = \left|\mathbf{A}^{\top}\mathbf{x}\right|$ and $|\mathbf{z}|$ denotes a vector of element-wise magnitudes of $\mathbf{z}$ -- under the assumption that $\mathbf{A}$ is Gaussian. Empirically, we demonstrate that alternating minimization performs similar to recently proposed convex techniques for this problem (which are based on "lifting" to a convex matrix problem) in sample complexity and robustness to noise. However, it is much more efficient and can scale to large problems. Analytically, for a resampling version of alternating minimization, we show geometric convergence to the solution, and sample complexity that is off by log factors from obvious lower bounds. We also establish close to optimal scaling for the case when the unknown vector is sparse. Our work represents the first theoretical guarantee for alternating minimization (albeit with resampling) for any variant of phase retrieval problems in the non-convex setting.
1 Introduction
The paper studies phase retrieval from magnitude-only measurements and develops alternating-minimization methods with empirical and theoretical guarantees under Gaussian measurements.
- Problem: Phase retrieval recovers a complex vector from magnitudes of linear measurements when measurement phases are unavailable.The problem appears in crystallography, optics, spectroscopy, and tomography.
- Prior approaches: Alternating projection methods are widely used, but their performance has limited theoretical guarantees despite extensive empirical study.Convex alternatives instead lift recovery to a rank-one matrix problem and solve semidefinite programs.
- Guarantees: The resampled algorithm geometrically converges using O(n log^3 n log(1/ϵ)) i.i.d. random Gaussian measurements to accuracy ϵ.Different measurements are used at each iteration, increasing total measurements by the number of iterations.
- Method: The proposed algorithm retains the Gerchberg–Saxton and Fienup iterative structure while adding an initialization step and resampling for analysis.Without resampling, its iterative procedure is exactly the error reduction algorithm.
- Guarantees: The analysis gives the first theoretical correctness guarantee for resampled alternating minimization in phase retrieval.The guarantee concerns recovery of the underlying signal under the paper’s measurement model.
- Sparse phase retrieval: For sparse signals, another algorithm achieves a sample complexity depending on sparsity k and scales better computationally than SDP-based methods.The sparse method operates over C^n and uses x*’s minimum non-zero entry in its stated complexity.
- Broader significance: The results address a broader gap because alternating minimization often performs well empirically while convex relaxations provide the strongest analytical guarantees for non-convex problems.The authors suggest implications beyond phase retrieval.
- Limitation: Resampling is impractical when collecting many measurements is difficult, although experiments found reusing the same samples performed significantly better.The authors identify this as a key drawback of their convergence guarantee.
2 Notation
The notation section specifies conventions for vectors, matrices, complex conjugation, Gaussian vectors, and the phase projection operator.
- Notation: Bold capitals denote matrices, bold lowercase letters denote vectors, and non-bold letters denote scalars.The shorthand wlog means without loss of generality, while whp means with high probability.
- Complex notation: For complex vectors, |w| denotes the element-wise magnitude vector, while wT and AT denote Hermitian transposes.The notation also defines canonical basis vectors and complex conjugation.
- Distributions and operators: A standard complex Gaussian vector has independent real and imaginary parts distributed as N(0,I).The paper also defines Ph(z) as z/|z|.
3 Algorithm
AltMinPhase alternates updates of the signal and unknown measurement phases, using initialization and resampling to address nonconvexity and obtain convergence guarantees. Its iterations are computationally efficient, while the guarantee requires different measurements at each iteration.
- Algorithm: The phase-matrix formulation is nonconvex because C is constrained to be diagonal with unit-magnitude entries.
- Algorithm: AltMinPhase alternates between estimating the signal x and a diagonal phase matrix C in the magnitude-only recovery problem.Given C, it solves a least-squares problem for x; given x, it updates the phase estimate.
- Initialization: A spectral initialization uses the largest singular vector of S, and with m ≥ C1n log3 n Gaussian measurements it is within 1/100 of x∗ with high probability.The stated initialization result applies to standard complex normal measurements.
- Convergence: A resampled variant converges to the global optimum x∗ at a linear rate, providing the paper’s theoretical guarantee for alternating minimization in phase retrieval.The guarantee is established for the variant that uses different samples in each iteration.
- Efficiency: Each iteration has a closed-form least-squares update and avoids SVD computation, making AltMinPhase more computationally efficient than SDP-based methods.The paper states similar statistical complexity to PhaseLift and PhaseCut, while reporting lower computational cost.
- Limitation: The convergence guarantee requires resampling, which is impractical when applications cannot collect sufficiently many measurements.Geometric convergence over O(log(1/ϵ)) iterations increases the total measurement requirement by that factor.
4 Main Results: Analysis
The paper establishes theoretical guarantees for alternating minimization in phase retrieval with independent complex Gaussian measurements, using initialization followed by resampled iterations. The resulting algorithm geometrically converges to the true vector up to global phase, with sample complexity near established bounds and substantially lower computational cost than SDP methods.
- Setting and comparison: The analysis considers phase retrieval with iid standard complex Gaussian measurement vectors and compares Algorithm 2 with PhaseLift and PhaseCut.The comparison concerns both theoretical guarantees and computational complexity.
- Initialization: The initialization step returns a vector within a constant distance of x∗ with high probability when m ≥ Cn log^3 n.More samples can reduce the initialization distance constant.
- Geometric convergence: Resampled alternating minimization contracts the distance to x∗ geometrically when the current iterate is sufficiently close and each iteration uses an independent measurement matrix.The proof requires the current iterate to be fixed and independent of the newly sampled matrix.
- Proof intuition: The contraction proof relies on viewing each update as a perturbation of x∗ and showing that the push from the true magnitudes dominates the push from the current phases near the solution.The argument bounds both the update’s ℓ2 error and its component orthogonal to x∗.
- End-to-end guarantee: Combining initialization and contraction, Algorithm 2 outputs an estimate with ℓ2 error below ϵ up to a global phase under a Gaussian sample bound.The stated guarantee uses m greater than a bound of order n log n(log^2 n + log(1/ϵ)).
5 Sparse Phase Retrieval
SparseAltMinPhase first identifies the support of a sparse signal, then applies AltMinPhase to the resulting lower-dimensional phase-retrieval problem. The section gives support-recovery conditions and compares its complexity with ℓ1-regularized PhaseLift.
- Complexity: When k = O(1), Algorithm 3 runs in quasi-linear time because its complexity is dominated by support finding.The section contrasts this sparse algorithm with ℓ1-regularized PhaseLift, whose cited computational complexity is O(n3/ϵ2).
- Algorithm: SparseAltMinPhase first recovers the support of x∗, then solves phase retrieval on the resulting k-dimensional signal using Algorithm 2.This decomposes sparse recovery into support finding followed by lower-dimensional phase retrieval.
- Support recovery: Lemma 5.1 states that, with sufficiently many standard complex Gaussian measurements, Algorithm 3 recovers the support with high probability.The threshold depends on the minimum nonzero entry of x∗, and the supplied condition includes m > c (x∗ … 4 log n δ.
- Support recovery: Support detection works because coordinates in supp(x∗) produce larger expected values of Zij than coordinates outside the support.Concentration bounds then separate the two groups, preventing selection of elements outside the true support.
- Guarantees: For k-sparse x∗ with nonzero entries ±1/√k, Corollary 5.2 gives recovery up to accuracy ϵ under its stated measurement condition.The supplied passage fragments state the condition across m > c log n, k2 + k log2 k + k log 1, and recovery probability greater than 1 −1.
6 Experiments
The experiments compare AltMinPhase with PhaseLift, PhaseCut, and random initialization across measurement schemes, noise levels, and iteration counts. AltMinPhase matches competitors in measurement or recovery behavior while requiring substantially less computation and exhibiting geometric error decay.
- Experimental protocol: The noiseless success criterion is ∥x − x∗∥2 < 10^-2, with the smallest successful sample count estimated from 20 runs requiring an empirical success ratio of at least 0.8.The methods were implemented in Matlab, while PhaseLift and PhaseCut code came from their authors.
- Multiple random illumination filters: For multiple random illumination filters, AltMinPhase has measurement complexity similar to PhaseLift and PhaseCut but is orders of magnitude faster.The comparison is shown in Figure 2, which uses a logarithmic scale.
- Multiple random illumination filters: AltMinPhase uses a similar number of filters as PhaseLift and PhaseCut but is computationally much more efficient, while outperforming random initialization.Figure 2 reports this comparison for random Gaussian illumination filters.
- Noisy phase retrieval: Under noisy measurements, AltMinPhase and PhaseCut have comparable recovery error, while PhaseLift incurs significantly larger error.The experiment fixes n = 64 and m = 6n and varies Gaussian noise level σ.
- Geometric decay: AltMinPhase’s error decreases geometrically with the number of iterations, consistent with the geometric-decay guarantee.The experiment uses standard complex Gaussian measurements with n = 64 and m = 6n.
A.1 Proof of the Initialization Step
The initialization proof analyzes a spectral matrix built from Gaussian measurements. It controls the deviation from its expectation and uses the resulting spectral structure to show that the leading singular vector is close to the target.
- Spectral initialization: The spectral initialization is based on x0, the top singular vector of S.The proof then bounds its alignment with the first canonical basis vector after using rotational invariance.
- Expectation structure: For complex Gaussian measurements, the expectation matrix is diagonal with D11 = 8 and Dii = 4 for i > 1.These entries arise from fourth- and mixed second-moment calculations.
- Proof strategy: The proof decomposes initialization into concentration of ∥S − D∥2 and a subsequent argument converting that bound into recovery of the leading singular vector.The two steps hold with probability greater than 1 − 4/m2.
- Concentration: Truncation replaces unusually large Gaussian vectors with zero, enabling boundedness conditions required by the matrix concentration theorem.The truncation retains aℓ when |a1ℓ|2 ≤ 2 log(m) and ∥aℓ∥2 ≤ 2n.
A.2 Proof of per step reduction in error
The per-step proof bounds the update error by decomposing it into components parallel and orthogonal to the true signal. Concentration of subexponential random variables and covering arguments establish the required uniform bounds.
- Coordinate reduction: The proof analyzes the update in coordinates where x∗ = e1 and xt = αe1 + √(1 − α2)e2, using rotational invariance.The global phase is chosen so α = ⟨xt, x∗⟩ ≥ 0.
- Concentration bounds: The key probabilistic step bounds sums of random variables Uℓ whose expectation is controlled by the current distance from x∗.Lemma A.3 provides concentration and an expectation bound for these correlated complex subexponential variables.
- Concentration bounds: Each Uℓ is shown to be subexponential, allowing concentration inequalities to control the aggregate update terms.The proof first bounds tails and expectations, then applies a subexponential concentration result.
- Uniform control: For every unit vector z orthogonal to x∗, Lemma A.4 bounds the corresponding update component in terms of dist(x∗, x).A covering net and union bound extend the fixed-z estimate uniformly over the orthogonal subspace.
- Auxiliary estimates: The proof handles complex Gaussian variables by separating phase and magnitude randomness and applying tail bounds for Gaussian-derived terms.Several auxiliary lemmas establish the needed expectation and concentration estimates.
B Proofs for Section 5
The proof analyzes random variables built from the measurement and sensing entries, establishes their expectations and concentration properties, and uses the sample-size hypothesis with a union bound to obtain separation with high probability.
- The proof introduces Zij for each j ∈ [n] and i ∈ [m] as the random variables used in the argument.
- The proof combines the theorem’s hypothesis on m with Taylor expansions and a union bound to show that, with probability greater than 1 − δ, the relevant averaged values are separated.
- For j ∉ S, the expectation satisfies E[Zij] = 2/π.
- Each Zij is sub-exponential with parameter c = O(1), because it is a product of two standard normal random variables.