Source-linked AI summary
Optimal Rates of Convergence for Noisy Sparse Phase Retrieval via Thresholded Wirtinger Flow
T. Tony Cai, Xiaodong Li, Zongming Ma
TL;DR
The paper asks how sparsity affects estimation precision in noisy sparse phase retrieval and how to attain optimal rates computationally. It develops Thresholded Wirtinger Flow with a theoretically justified initializer and shows minimax-optimal performance under Gaussian sensing and sub-exponential noise, subject to sufficient sample size.
Problem
The paper studies sparse signal recovery from noisy quadratic measurements and the unresolved dependence of optimal convergence rates on sparsity and sample size.
Method
The paper combines a diagonal-thresholding initializer with thresholded gradient descent for sparse estimation in a nonconvex empirical-risk problem.
Results
Thresholded Wirtinger Flow achieves minimax-optimal convergence rates under Gaussian design and sub-exponential noise when the sample size is sufficiently large.
Takeaways & Limitations
Thresholded gradient methods can attain optimal statistical precision for sparse phase retrieval even when the empirical risk lacks restricted strong convexity.
Takeaways & Limitations
The computational guarantee requires a sample size condition of m ≳ k^2 up to polylogarithmic factors, and whether this condition can be relaxed remains open.
Abstract
from arXiv · showhide
This paper considers the noisy sparse phase retrieval problem: recovering a sparse signal $x \in \mathbb{R}^p$ from noisy quadratic measurements $y_j = (a_j' x )^2 + ε_j$, $j=1, \ldots, m$, with independent sub-exponential noise $ε_j$. The goals are to understand the effect of the sparsity of $x$ on the estimation precision and to construct a computationally feasible estimator to achieve the optimal rates. Inspired by the Wirtinger Flow [12] proposed for noiseless and non-sparse phase retrieval, a novel thresholded gradient descent algorithm is proposed and it is shown to adaptively achieve the minimax optimal rates of convergence over a wide range of sparsity levels when the $a_j$'s are independent standard Gaussian random vectors, provided that the sample size is sufficiently large compared to the sparsity of $x$.
1 Introduction
The paper studies recovery of sparse signals from noisy quadratic measurements, focusing on how sparsity and sub-exponential noise affect estimation precision. It establishes minimax-optimal convergence rates and proposes a computationally efficient thresholded gradient method under Gaussian sensing.
- Problem: Sparse phase retrieval recovers a p-dimensional signal from noisy measurements of squared sensing-vector magnitudes.The model uses measurements of |a_j′x|^2 contaminated by stochastic noise; sparsity is assumed after any known linear transformation.
- Research gap: Existing noisy sparse phase retrieval results did not fully characterize optimal dependence on sparsity and sample size.Prior work included stability results and nearly minimax rates under Gaussian noise, but the paper identifies a gap in optimal rate dependence.
- Contributions: The paper establishes minimax-optimal convergence rates under sub-exponential noise and proposes a thresholded gradient descent estimator.The analysis examines the effects of signal sparsity and noise on ℓ2 estimation.
- Results: Under independent standard Gaussian sensing vectors, the proposed procedure achieves the paper’s optimal estimation rate.The rate is described in terms of sparsity, signal norm, noise level, and sample size.
- Results: The thresholded gradient method is both rate-optimal and computationally efficient when the sample size meets the stated requirements.Its sample-size requirement matches the state-of-the-art computational result for structureless Gaussian designs.
2 Methodology
The methodology minimizes a nonconvex empirical risk with thresholded gradient updates and uses a specialized initializer. Thresholding incorporates sparsity, while initialization addresses the risks of nonconvex optimization.
- Thresholded Wirtinger flow: The core estimator uses thresholded gradient descent to obtain a sparse solution to a nonconvex empirical risk problem.The methodology assumes standard Gaussian entries in the sensing matrix.
- Thresholded Wirtinger flow: The empirical risk uses least squares, enabling computationally convenient closed-form gradient updates.The paper selects least squares despite noting that LAD can be more robust for heavy-tailed noise in low-dimensional settings.
- Thresholded Wirtinger flow: Each gradient step is followed by thresholding to preserve sparsity and reduce noise contamination in updated coordinates.The thresholding step is intended to mimic restricting updates to the unknown support.
- Algorithm structure: Thresholded Wirtinger Flow combines an initialization step with iterative thresholding for sparse recovery.The algorithm is named after Wirtinger flow for noiseless phase retrieval.
- Initialization: Initialization is crucial because the empirical risk is nonconvex and may have multiple local minimizers.An accurate initializer can also reduce the required number of iterations.
- Initialization: The initializer identifies coordinates with strong marginal signals and estimates the signal using those selected coordinates.This diagonal-thresholding strategy is motivated by sparse PCA.
3 Theory
Under independent Gaussian sensing vectors and centered sub-exponential noise, the paper establishes minimax-optimal ℓ2 convergence rates and analyzes thresholded Wirtinger flow. The method is rate-optimal and computationally efficient, but its guarantees rely on a sparsity-dependent sample-size condition.
- Method and analysis: The thresholded Wirtinger flow analysis establishes convergence under Gaussian design and uses thresholding for initialization and iterative recovery.The proof attributes initialization efficacy to Lemma 6.3 and estimation accuracy to Lemmas 6.4 and 6.5.
- Assumptions: The analysis assumes k-sparse x, independent standard Gaussian sensing vectors, and independent centered sub-exponential errors with norm σ.
- Noiseless case: With high probability, the noiseless method achieves linear convergence to the original signal up to a global sign.
- Noisy case: In the noisy case, choosing t ≍ log(1/δ) yields the stated high-probability estimation guarantee, while t = O(log p) works without knowledge of δ.The supplied passages state the iteration choices and associated probability scaling, but fragmentary theorem text omits the complete bound.
- Optimality: The convergence rate σ∥x∥2√(k log(ep/k)/m) is attainable by a fast algorithm and improves on the cited intractable sparsity-constrained empirical-risk bound.
- Computational boundary: Ignoring polylogarithmic factors, the method’s guarantees require m ≳ k^2, and the paper leaves relaxation of this condition as an open question.When m ≳ p, spectral methods can obtain a consistent initializer regardless of sparsity.
4 Numerical Simulation
Numerical simulations examine how relative estimation error changes with thresholding, noise, sample size, and sparsity under Gaussian designs. The method performs poorly at small sample sizes, while error rises with noise and sparsity.
- Thresholding effect: 0.2365 to 0.1151: average relative error decreases as β increases from 0 to 0.75, then rises slowly to 0.1684.The comparison uses p = 1000, m = 7000, k = 100, and noise-to-signal ratio 1.
- Thresholding effect: Average relative-error performance is very close for initialization parameters α = 0.1 and α = 0.5.The two curves are compared in Figure 1 under otherwise matched settings.
- Noise effect: 0.0000 to 0.1219: average relative error increases strictly as the noise-to-signal ratio rises from 0 to 1.The experiment fixes m = 7000, k = 100, and β = 1.
- Sample size effect: 0.8444 and 0.3651: average relative errors at sample sizes m = 2000 and 3000 indicate poor recovery.When m increases from 4000 to 11000, the average relative error decreases steadily from 0.1692 to 0.0956.
- Sparsity effect: 0.1059 to 0.1666: average relative error increases as sparsity rises from k = 25 to 200.This experiment fixes m = 7000, noise-to-signal ratio 1, and β = 1.
5 Discussion
The discussion emphasizes the method’s optimality under Gaussian design and sub-exponential noise, while identifying analytical and methodological boundaries. It also highlights that the result does not rely on restricted strong convexity.
- Main conclusions: Thresholded Wirtinger Flow achieves the optimal rates for noisy sparse phase retrieval under Gaussian design and sub-exponential noise when the sample size is sufficiently large.The paper introduces this method and establishes its rate-optimality.
- Analytical novelty: Existing high-dimensional M-estimation analyses rely on RSC and RSS, but the phase-retrieval empirical risk generally lacks RSC.The paper instead establishes optimal statistical precision for thresholded gradient methods without that common assumption.
- Open questions: Whether a globally minimized penalized empirical risk is rate-optimal for the original sparse signal is left for future research.The discussion identifies this as an unresolved question for alternative regularized methods.
6 Proof of Theorem 3.1
The proof establishes the theorem by combining a support-preserving initialization, local gradient control, and an induction showing that thresholded iterations retain accuracy and sparsity.
- Initialization: The initialization constructs an estimator supported on the true support and proves a small relative error with high probability.The stated initialization guarantee is min(∥x(0) − x∥2, ∥x(0) + x∥2) ≤ ∥x∥2/6.
- Local control: The proof decomposes the local gradient analysis into terms T1, T2, and τ(z), then bounds these terms under sample-size and tuning conditions.The bounds require conditions including m ≥ Ck^2 log p and sufficiently small µ.
- Induction: The induction begins from the initialization lemma and extends the estimation guarantee across iterations, yielding Theorem 3.1.The theorem follows directly from Lemma 6.5 after the initial condition is established.
- Induction: Thresholding preserves the true support because off-support coordinates remain below the threshold with high probability.The induction constructs events on which supp(x(n+1)) ⊂ S and the algorithmic iterate equals the constructed vector.
A Preliminaries and supporting lemmas
The preliminaries collect concentration tools for Gaussian designs and sub-exponential variables. These lemmas provide the high-probability bounds used in the initialization and gradient analyses.
- Gaussian design bounds: The restricted design analysis applies to vectors supported on S and uses covering arguments over sparse directions.The index set explicitly constrains u to have support contained in S.
- Gaussian design bounds: Gaussian concentration controls operator-type quantities for the restricted design matrix A_S.The supporting lemmas use Lipschitz concentration and Gaussian-process comparisons.
- Conditions: The lemmas impose sample-size conditions such as m ≥ C(δ)k log k and m ≥ m0 for the stated probability bounds.These conditions support concentration results for the design and noise components.
- Noise concentration: Sub-exponential noise lemmas provide tail and moment controls needed for the noisy measurement terms.The results include bounds on individual errors and aggregated quantities with high probability.