Source-linked AI summary
Sparse Phase Retrieval via Truncated Amplitude Flow
Gang Wang, Liang Zhang, Georgios B. Giannakis, Mehmet Akcakaya, Jie Chen
TL;DR
Sparse phase retrieval asks how to reconstruct sparse signals from magnitude-only measurements despite a generally NP-hard nonconvex formulation. SPARTA uses support recovery, support-restricted power iterations, and hard-thresholded truncated-gradient refinement, and the paper reports exact recovery with about k^2 log n Gaussian measurements alongside lower computational complexity and noise robustness. The authors also identify extensions involving alternative sparsity regularization, stochastic optimization, and robustness to outliers as future directions.
Problem
Sparse phase retrieval reconstructs sparse signals from magnitude-only measurements, but its amplitude-based objective and ℓ0 constraint are nonconvex and NP-hard in general.
Method
SPARTA estimates the support, forms a support-restricted power-iteration initialization, and successively refines it using truncated gradient iterations with hard thresholding.
Results
SPARTA exactly recovers eligible k-sparse signals from O(k^2 log n) measurements, with computational complexity O(k^2n log n log(1/ϵ)) and robustness to bounded-support additive noise.
Takeaways & Limitations
SPARTA provides a simple and scalable sparse phase-retrieval solver with reported recovery, noise-robustness, and runtime improvements over existing alternatives.
Takeaways & Limitations
The analysis assumes minimum nonzero entries on the order of (1/√k)∥x∥2, while robust sparse recovery with outliers and alternative sparsity regularization remain future directions.
Abstract
from arXiv · showhide
This paper develops a novel algorithm, termed \emph{SPARse Truncated Amplitude flow} (SPARTA), to reconstruct a sparse signal from a small number of magnitude-only measurements. It deals with what is also known as sparse phase retrieval (PR), which is \emph{NP-hard} in general and emerges in many science and engineering applications. Upon formulating sparse PR as an amplitude-based nonconvex optimization task, SPARTA works iteratively in two stages: In stage one, the support of the underlying sparse signal is recovered using an analytically well-justified rule, and subsequently, a sparse orthogonality-promoting initialization is obtained via power iterations restricted on the support; and, in the second stage, the initialization is successively refined by means of hard thresholding based gradient-type iterations. SPARTA is a simple yet effective, scalable, and fast sparse PR solver. On the theoretical side, for any $n$-dimensional $k$-sparse ($k\ll n$) signal $\bm{x}$ with minimum (in modulus) nonzero entries on the order of $(1/\sqrt{k})\|\bm{x}\|_2$, SPARTA recovers the signal exactly (up to a global unimodular constant) from about $k^2\log n$ random Gaussian measurements with high probability. Furthermore, SPARTA incurs computational complexity on the order of $k^2n\log n$ with total runtime proportional to the time required to read the data, which improves upon the state-of-the-art by at least a factor of $k$. Finally, SPARTA is robust against additive noise of bounded support. Extensive numerical tests corroborate markedly improved recovery performance and speedups of SPARTA relative to existing alternatives.
1 Introduction
Sparse phase retrieval reconstructs signals from magnitude-only measurements and is important in imaging and other engineering applications. SPARTA addresses sparse phase retrieval with a two-stage solver that combines support recovery, support-restricted initialization, and hard-thresholded truncated-gradient refinement.
- Motivation: Phase retrieval reconstructs signals from squared transform magnitudes, supporting applications including crystallography, microscopy, astronomy, optics, and imaging.Sensors record intensity but not phase.
- Sparse phase retrieval: Sparse signals arise naturally in imaging, including sparsely distributed stars and atoms or molecules.
- SPARTA: SPARTA estimates the signal support, obtains a support-restricted power-iteration initialization, and refines it with hard-thresholded truncated-gradient iterations.The algorithm is formulated as an amplitude-based nonconvex solver.
- Guarantees and evaluation: O(k^2 log n) measurements suffice for exact recovery under a minimum-entry condition, while the computational cost is O(k^2n log n log(1/ϵ)).The minimum nonzero entries must be on the order of (1/√k)∥x∥2; the stated complexity improves on the state of the art by at least a factor of k.
- Guarantees and evaluation: Numerical tests report improved exact recovery, noise robustness, and runtime relative to state-of-the-art alternatives.The paper also states robustness to additive noise of bounded support.
2 Sparse Phase Retrieval
Sparse phase retrieval seeks a sparse signal from phaseless quadratic measurements, but its amplitude-based formulation is generally nonconvex and NP-hard. The paper proposes a two-stage solver that initializes on an estimated support and then performs truncated gradient refinement with hard thresholding.
- Problem formulation: The measurements may be represented as amplitudes ψ_i = |⟨a_i, x⟩| or as squared magnitudes y_i = |⟨a_i, x⟩|^2, with sparsity level k assumed known for theoretical analysis.
- Problem formulation: Stable sparse phase retrieval requires at least O(k log(n/k)) measurements in the noisy setting, matching the corresponding compressive-sensing order.The passage also gives uniqueness thresholds of 2k real measurements and at least 4k−2 complex measurements for generic systems.
- Problem formulation: Sparse phase retrieval reconstructs a k-sparse signal from a small number of phaseless quadratic equations.The objective assumes a unique k-sparse solution up to a global sign.
- Problem formulation: The amplitude-based objective and ℓ0 constraint are nonconvex, making the optimization problem NP-hard in general.The resulting problem is computationally intractable in general.
- Proposed solver: SPARTA first obtains a sparse orthogonality-promoting initialization by power iterations on an estimated support, then applies truncated gradients and hard thresholding.Hard thresholding retains the k entries with largest magnitudes.
3 Algorithm: Sparse Truncated Amplitude Flow
SPARTA estimates the sparse support, constructs a support-restricted orthogonality-promoting initialization, and refines it with hard-thresholded truncated-gradient iterations. Its support rule exploits separable measurement statistics, while power iterations reduce initialization cost.
- Sparse orthogonality-promoting initialization: The initialization approximates a smallest-eigenvector problem through a principal-eigenvector computation and a few power iterations, reducing complexity from O(n^3) to O(n|I_0|).The sparse version performs these iterations after restricting the data to the estimated support.
- Sparse orthogonality-promoting initialization: SPARTA first estimates the signal support, then applies power iterations on that support to obtain a sparse orthogonality-promoting initialization.The initialization is zero-padded outside the estimated support and scaled using a norm estimate.
- Exact support recovery: O(k^2 log n) measurements suffice for exact support recovery with high probability when the minimum nonzero entry is on the order of (1/sqrt(k))||x||_2.This condition creates the separation needed to distinguish supported from nonsupported coordinates.
- Thresholded truncated gradient stage: The refinement stage applies truncated gradient updates followed by H_k, which retains only the k entries with largest magnitudes.The method can still recover the signal when the estimated support is imperfect, provided the initialization is sufficiently close.
4 Main Results
The paper establishes exact recovery and linear convergence for SPARTA under Gaussian measurements, with sample and computational complexity scaling polynomially in sparsity rather than ambient dimension. It also reports robustness to bounded additive noise.
- Exact recovery: Under Gaussian measurements, SPARTA exactly recovers any k-sparse signal with minimum nonzero entries on the order of (1/sqrt(k))||x||_2 when m ≥ C_0k^2 log(mn).The support is recovered exactly with probability at least 1 − 6/m under the theorem’s assumptions.
- Sample complexity: The sample complexity can be expressed as about k^2 log n measurements, matching the measurement count of cited sparse PR alternatives.The paper contrasts this with nonsparse TAF, whose guarantee requires m ≳ n.
- Convergence: The SPARTA iterates converge linearly to the global solution, with a convergence rate independent of the signal dimension n.For accuracy epsilon, at most T = log(1/epsilon) iterations are required according to the stated remark.
- Computational complexity: O(k^2n log n) computational complexity is required, and an epsilon-accurate solution takes O(k^2n log n log(1/epsilon)) runtime.The total runtime is proportional to the O(k^2n log n) time needed to read the data, up to the accuracy-dependent iteration factor.
- Noise robustness: SPARTA is robust to additive noise, particularly when the noise has bounded values.Numerical results for noisy sparse phase retrieval are reported as part of the paper’s evaluation.
5 Numerical Experiments
Numerical experiments compare SPARTA with TAF and TWF on exact recovery, sparsity scaling, noisy measurements, and computational speed. Across these tests, SPARTA shows improved recovery, noise robustness, and faster convergence, including when the exact sparsity level is unknown.
- Exact recovery: Using k = ⌈√n⌉ = 32 as an upper limit, SPARTA0 performs well even when the exact number of nonzeros is unknown.This setting is included alongside SPARTA with the known value k = 10.
- Exact recovery: SPARTA markedly improves empirical exact-recovery performance over TAF and TWF for real-valued signals with n = 1,000 and k = 10.Success is measured over 100 Monte Carlo trials using a relative mean-square error threshold below 10^-5.
- Sparsity scaling: With m = n = 1,000 measurements, SPARTA significantly outperforms TWF and achieves exact recovery for signals with up to about 25 nonzero entries.The reported threshold is below √n ≈ 32 because of polylogarithmic factors in the sample complexity.
- Noisy recovery: Under Gaussian additive noise, SPARTA requires about m = 6k^2 = 600 measurements for exact recovery, compared with about 3n = 3,000 for TAF and more than 3,000 for TWF.The experiment uses n = 1,000, k = 10, and noise η_i ∼ N(0, 0.1^2).
- Noisy recovery: For the AWGN model, SPARTA’s relative MSE scales inversely with SNR across the tested m/n values, supporting stability under additive noise.The result averages 100 Monte Carlo realizations over SNR values from 5 dB to 55 dB.
- Complex-valued recovery: SPARTA recovers a 20,000-dimensional complex-valued signal from 1,000 magnitude-only measurements in a few seconds.The complex-valued experiment uses a 10-sparse signal and evaluates relative MSE against iteration count.
- Computational performance: SPARTA converges faster than TAF and TWF both in runtime and in iterations needed to reach a given solution accuracy.The experiments use 100 power iterations followed by 1,000 gradient iterations for each scheme.
6 Proof of Theorem 1
The proof establishes SPARTA’s theoretical pipeline: exact support recovery, a sufficiently accurate initialization, and linear convergence of hard-thresholded iterations under Gaussian measurements and sparsity conditions.
- Support recovery: O(k^2 log(mn)) measurements suffice for exact support recovery with probability at least 1 − 6/m.This enables the subsequent initialization to operate on dimension-reduced data.
- Initialization: The sparse orthogonality-promoting initialization lies within (1/10)∥x∥_2 of the signal with high probability under sufficiently large m/k and k.The initialization is formed after support recovery using power iterations restricted to the recovered support.
- Linear convergence: Starting within this neighborhood, SPARTA’s successive estimates contract geometrically as dist(z_t, x) ≤ (1/10)(1 − ν)^t∥x∥_2.The result holds with high probability for an appropriate constant learning parameter and γ = +∞.
- Linear convergence: Step 5 guarantees linear convergence to the globally optimal solution whenever the initial estimate is sufficiently close, even without exact support recovery.Thus, exact support recovery is sufficient for the proof’s initialization route but is not required by the refinement step itself.
- RIP analysis: Gaussian sensing matrices satisfy the required RIP bounds with high probability when the measurement count scales with sparsity and ambient dimension.These RIP properties control the hard-thresholding analysis over supports of size up to 3k.
7 Concluding Remarks
The paper concludes that SPARTA combines support recovery, sparse initialization, and truncated hard-thresholding refinement into a simple, scalable solver with exact-recovery guarantees and improved computational efficiency.
- Contributions: SPARTA first recovers the support, then computes a support-restricted orthogonality-promoting initialization, and finally applies truncated hard-thresholding gradient iterations.The three-stage description emphasizes the algorithm’s simplicity and scalability.
- Theoretical guarantees: SPARTA achieves provably exact recovery once noiseless Gaussian measurements exceed a specified bound.The conclusion contrasts its lower computational complexity with state-of-the-art methods at the same sample size.
- Empirical results: Simulated tests report improved recovery performance and computational efficiency relative to existing alternatives.The stated comparisons include methods such as AltMinPhase and TWF.
- Future directions: Future work includes sparsity-promoting regularization, stochastic large-scale optimization, and extensions to robust sparse phase retrieval and matrix recovery with outliers.These are presented as extensions rather than established capabilities of the current method.
Appendix: Supporting Lemmas
The appendix collects probabilistic concentration, Gaussian tail, and local regularity results used to support SPARTA’s support-recovery and convergence analysis.
- Concentration tools: Bernstein-type concentration bounds control sums of independent bounded or variance-limited random variables.The stated lemma introduces conditions involving a uniform bound and variance parameters.
- Gaussian bounds: A Gaussian tail inequality bounds weighted sums of independent standard Gaussian variables for arbitrary positive thresholds.This result supports probabilistic control of Gaussian measurement-related quantities.
- Local regularity: For Gaussian measurements, a local regularity result controls the relevant quantities for vectors near the true sparse signal.The guarantee applies within a radius ρ_0 = 1/10 and requires a measurement count scaling with sparsity and ambient dimension.
- Supporting results: The appendix identifies the local regularity lemma as a generalization of an earlier result.Its proof is cited rather than reproduced in the supplied passage.