Source-linked AI summary
Phase retrieval with polarization
Boris Alexeev, Afonso S. Bandeira, Matthew Fickus, Dustin G. Mixon
TL;DR
Phase retrieval seeks to reconstruct signals from intensity-only measurements despite lost phase information and algorithmic limitations. This paper uses interferometry-inspired measurements on expander graphs and an efficient phase-retrieval procedure, with stable noisy guarantees at O(M log M) measurements and O(M) noiseless scaling. The authors note that the noisy-case logarithmic factor may reflect the current analysis rather than a fundamental requirement.
Problem
Phase retrieval must reconstruct signals from intensity measurements that lose phase information and may support nonunique or unstable practical recovery.
Method
The paper combines interferometry-inspired measurement vectors with expander-graph connectivity, relative-phase propagation, and least-squares reconstruction.
Results
The procedure achieves O(M) measurements in the noiseless setting and a stable noisy guarantee with N ∼ CM log M measurements.
Takeaways & Limitations
The approach provides an efficient alternative to semidefinite-programming-based phase retrieval while retaining a stable performance guarantee in the noisy setting.
Takeaways & Limitations
The authors leave average-case analysis for stochastic noise and believe the noisy-case logarithmic measurement factor is an artifact of the current analysis.
Abstract
from arXiv · showhide
In many areas of imaging science, it is difficult to measure the phase of linear measurements. As such, one often wishes to reconstruct a signal from intensity measurements, that is, perform phase retrieval. In this paper, we provide a novel measurement design which is inspired by interferometry and exploits certain properties of expander graphs. We also give an efficient phase retrieval procedure, and use recent results in spectral graph theory to produce a stable performance guarantee which rivals the guarantee for PhaseLift in [Candes et al. 2011]. We use numerical simulations to illustrate the performance of our phase retrieval procedure, and we compare reconstruction error and runtime with a common alternating-projections-type procedure.
1. Introduction.
Phase retrieval reconstructs signals from intensity-only measurements, but global-phase ambiguity, noninjective designs, and inefficient or unstable algorithms complicate the task. The paper proposes interferometry-inspired measurements and a faster reconstruction approach with stable guarantees, using additional O(M log M) measurements.
- Intensity measurements determine a signal only up to a global phase, so the target is the equivalence class [x].
- Noninjective measurement designs can prevent unique reconstruction, while practical alternating-projections methods are sensitive to their initial phases.
- The central questions are which designs make intensity measurements injective and which permit stable, efficient reconstruction.
- Existing stable reconstruction with Gaussian-random measurements uses semidefinite programming and O(M log M) measurements, whereas earlier guarantees could require Ω(M^2).
- Interferometry extracts additional information by combining the unknown signal with a known reference, motivating the paper’s measurement design.
- The paper trades O(M log M) additional nonadaptive measurements for faster reconstruction with a stable performance guarantee, focusing on one-dimensional signals.
2. The noiseless case.
The noiseless procedure recovers relative phases from polarization measurements placed on the edges of a sparse expander graph. Spectral connectivity guarantees allow recovery with O(M) measurements, while the noiseless method remains unstable to noise and conditioning.
- The algorithm deletes zero-measurement vertices, finds a connected component of at least M vertices, propagates relative phases, and applies a Moore–Penrose pseudoinverse.
- Polarization measurements of ϕ_i + ζ_kϕ_j recover products of coefficients and thereby determine relative phases between vertex measurements.
- A spectral-gap connectivity lemma ensures that removing sufficiently few vertices leaves a connected component large enough for recovery.
- Using a sparse d-regular graph makes the total measurement count N = |V| + 3|E| proportional to the number of graph vertices, unlike the complete-graph construction.
- Ramanujan-style expander constructions yield phase retrieval with N ≤ 236M measurements in the stated cases, achieving O(M) scaling.
- The noiseless method is fast but lacks stability because the frame may be poorly conditioned and sequential phase propagation accumulates error.
3. The noisy case.
The noisy procedure prunes unreliable vertices and weakly connected regions, then reconstructs phases through graph-based synchronization. Its design yields a stable performance guarantee under a noise-to-signal condition, with stability improving as the signal dimension grows.
- Procedure: The procedure first removes vertices with unreliable measurements, prunes for connectivity, estimates vertex phases by angular synchronization, and reconstructs the signal by least squares.The pipeline uses reliability pruning, connectivity pruning, angular synchronization, measurement-based vertex selection, and a Moore–Penrose pseudoinverse.
- Reliability pruning: Projective uniformity limits the number of small vertices by guaranteeing many measurements exceed a signal-dependent threshold for every unit-norm signal.This controls the instability caused by normalizing small noisy products used for relative phase estimation.
- Connectivity pruning: Spectral clustering iteratively removes poorly connected vertex sets until the remaining graph has spectral gap at least τ.The stated purpose is to restore connectivity lost during reliability pruning while removing only a small proportion of vertices.
- Angular synchronization: The connection Laplacian converts noisy relative-phase estimates on graph edges into an eigenvector-based estimate of the vertex phases.The smallest-eigenvalue eigenvector is normalized coordinatewise to enforce unit-modulus phase estimates.
- Guarantee: For N ∼ C M log M measurements and sufficiently large C, the procedure provides a high-probability stable reconstruction guarantee when the noise-to-signal ratio meets the stated bound.The analysis further states that the resulting NSR = O(1/√log M), indicating greater stability as M grows.
4. Numerical results.
Simulations show that noiseless reconstruction undergoes a graph-connectivity phase transition, while the noisy procedure achieves low error with modest runtime costs and compares favorably with alternating projections in runtime.
- 4.1. The noiseless case.: The success rate approaches 0 or 1 according to whether the Erdős-Rényi graph has a component of size at least M, producing the predicted phase transition.Across 12,870 trials, only four vertices were deleted for tiny measurements, so graph connectivity dominated reconstruction success.
- 4.1. The noiseless case.: The transition curve is c = r log(r/(r −1)), derived by requiring the giant component to contain at least M vertices.The simulations used M ∈ {16, 32, 64}, n = rM, and edge probability p = c/n.
- 4.1. The noiseless case.: At r ≈ 1.28, the measurement redundancy is approximately N/M ≈ 5.02, far below 236, but this almost-everywhere reconstruction setting does not ensure injectivity.The authors emphasize that the simulations therefore do not capture the hardest measurement-design requirement: reconstructing every signal uniquely.
- 4.2. The noisy case.: Phase Retrieval Procedure B produces relative errors similar to least-squares estimation from noisy vertex measurements and returns an estimate in less than one second.The procedure is slower than phase oracles because angular synchronization estimates vertex phases, but the runtime difference is described as modest.
- 4.2. The noisy case.: The noisy simulations note that replacing spectral pruning with the largest surviving component worked because that component always had spectral gap larger than τ = 0.1 in these trials.The authors suspect this behavior is an artifact of the random graph and state that it need not hold generally.
- 4.2. The noisy case.: With noise added after the modulus square, alternating projections consistently achieves slightly lower relative error than Procedure B but takes substantially longer to terminate.Alternating projections using only the 3M vertex vectors instead stalled with relative errors on the order of 1.
- 4.2. The noisy case.: The stability theorem remains insufficient for application-driven specifications because it does not prescribe a measurement design for a given noise level and target error.The paper identifies this as an open gap in known phase-retrieval stability guarantees.
5. Concluding remarks.
The paper identifies remaining gaps between its theory and practical phase retrieval. It assumes known measurement designs, uses hard thresholding for simpler analysis, and leaves average-case noise analysis and removal of a noisy-case log factor for future work.
- 5. Concluding remarks.: The analysis assumes complete knowledge of the measurement design, whereas practical settings may include measurement-design mismatch error.The paper notes that stability results accounting for this noise could partly address the gap.
- 5. Concluding remarks.: Hard thresholds remove vertices based on measurement size, simplifying projective-uniformity analysis but leaving smoother confidence weighting as a possible alternative.The paper connects such smooth weighting to angular-synchronization theory.
- 5. Concluding remarks.: The paper leaves average-case analysis for stochastic noise open and suspects the noisy-case logarithmic measurement factor is an artifact of the current analysis.The worst-case analysis supports comparison with worst-case stability results, while stochastic noise may better fit some applications.
6. Appendix.
The appendix develops graph-theoretic and phase-synchronization guarantees underlying the proposed phase retrieval method. It combines Cheeger-type spectral bounds, noisy projective uniformity for Gaussian measurements, and least-squares reconstruction to obtain a high-probability stability guarantee.
- Graph guarantees: Cheeger-type graph bounds show that after vertex removal, Algorithm 3 retains at least q|V| vertices when the original spectral gap exceeds the stated threshold.The condition uses λ2 > g(p, q) and τ = 1/8(λ2 − g(p, q))^2.
- Graph guarantees: The constructive Cheeger inequality supplies a set S whose conductance satisfies h(S) ≤ √2λ2, supporting the graph-pruning analysis.The appendix derives incompatible edge-bound estimates to establish the retention guarantee.
- Angular synchronization: Theorem 6.3 bounds phase-estimation error using the graph spectral gap and the minimum edge reliability quantity P.The proof relates unit-modulus phase errors to angular distance and controls the resulting graph energy.
- Angular synchronization: For connected graphs, minimizing the angular-synchronization objective recovers the target phases exactly in the noiseless case and yields a constant-factor optimality guarantee for Algorithm 4.The guarantee is based on a connection-Laplacian Cheeger inequality and spectral gap τ > 0.
- Projective uniformity: With |V| ∼ C M log M Gaussian measurement vectors, Theorem 6.8 establishes noisy projective uniformity with overwhelming probability for proportions α < 1 − 1/(2C).The guarantee applies uniformly over every noise vector ε in the stated setting.
- Main result: The main noisy-case theorem uses N ∼ C M log M measurements and guarantees reconstruction stability for all x with overwhelming probability when the noise-to-signal ratio is at most C′/√M.The estimate is formed from the measurement design ΦV ∪ ΦE and has a reconstruction-error bound with universal constants.