Source-linked AI summary
Phase Retrieval: Stability and Recovery Guarantees
Yonina C. Eldar, Shahar Mendelson
TL;DR
The paper asks when unknown vectors in general sets can be stably recovered from noisy quadratic measurements despite missing phase information. It analyzes complexity-dependent stability and approximate empirical minimization, obtaining sparse and unrestricted-vector guarantees while matching the order of linear-measurement stability. The noisy bounds become arbitrarily small with appropriate measurement counts.
Problem
The paper studies fundamental limits for stable recovery from quadratic measurements when the unknown input lies in an arbitrary set T.
Method
The paper derives complexity-parameter-based stability conditions and uses bounded empirical risk to certify approximate recovery without requiring an exact nonconvex minimizer.
Results
O(k log(n/k)) noise-free measurements suffice for k-sparse vectors, while noisy recovery requires O(k log(n/k) log k); arbitrary vectors require O(n) and O(n log n), respectively.
Takeaways & Limitations
The quadratic problem has the same complexity parameter as linear stability analysis, indicating no substantial stability cost from unknown measurement phase.
Takeaways & Limitations
Optimality in the quadratic setting is not proved, although the bounds are optimal in the linear case and are expected to be optimal here.
Abstract
from arXiv · showhide
We consider stability and uniqueness in real phase retrieval problems over general input sets. Specifically, we assume the data consists of noisy quadratic measurements of an unknown input x in R^n that lies in a general set T and study conditions under which x can be stably recovered from the measurements. In the noise-free setting we derive a general expression on the number of measurements needed to ensure that a unique solution can be found in a stable way, that depends on the set T through a natural complexity parameter. This parameter can be computed explicitly for many sets T of interest. For example, for k-sparse inputs we show that O(k\log(n/k)) measurements are needed, and when x can be any vector in R^n, O(n) measurements suffice. In the noisy case, we show that if one can find a value for which the empirical risk is bounded by a given, computable constant (that depends on the set T), then the error with respect to the true input is bounded above by an another, closely related complexity parameter of the set. By choosing an appropriate number N of measurements, this bound can be made arbitrarily small, and it decays at a rate faster than N^{-1/2+δ} for any δ>0. In particular, for k-sparse vectors stable recovery is possible from O(k\log(n/k)\log k) noisy measurements, and when x can be any vector in R^n, O(n \log n) noisy measurements suffice. We also show that the complexity parameter for the quadratic problem is the same as the one used for analyzing stability in linear measurements under very general conditions. Thus, no substantial price has to be paid in terms of stability if there is no knowledge of the phase.
1 Introduction
The paper studies stable phase retrieval from real quadratic measurements over general input sets, addressing fundamental recovery limits in both noise-free and noisy settings. It develops complexity-dependent guarantees, including sparse and unrestricted-vector cases, and relates quadratic stability to linear-measurement stability.
- Problem setting: Phase retrieval recovers an unknown vector from quadratic measurements that reveal magnitudes but not signs or phases.The model uses yi = |⟨ai, x⟩|2 + wi, with known measurement vectors and noise.
- Noise-free guarantees: O(k log(n/k)) measurements ensure stable recovery for k-sparse vectors, improving the prior semidefinite-relaxation estimate by a factor of k.For unrestricted x ∈ R^n, O(n) measurements suffice.
- Noise-free guarantees: The required measurement count depends on a natural complexity parameter of the input set T, covering both sparse vectors and T = R^n.The resulting estimate is sharp for stable recovery and sharp up to logarithmic factors in the noisy problem.
- Connection to linear estimation: The quadratic problem uses the same natural complexity parameter as linear measurements, so unknown phase incurs no substantial stability penalty.The comparison applies to very general input sets T.
- Noisy recovery: If an empirical-risk value is found below a computable set-dependent constant, the estimate is guaranteed close to the true input up to sign.The squared-error bound converges to zero faster than N^{-1/2+δ} for every δ > 0.
- Noisy recovery: O(k log(n/k) log k) noisy measurements suffice for stable recovery of k-sparse vectors, while O(n log n) suffice for arbitrary vectors in R^n.The algorithm may be run from multiple initializations, checking whether a candidate satisfies the empirical-risk bound.
2 Problem Formulation and Main Results
The paper studies stable, sign-ambiguous recovery from quadratic measurements for arbitrary signal sets under isotropic, L-subgaussian measurements. It characterizes measurement requirements through complexity parameters and gives noise-free and noisy guarantees.
- Problem Formulation: The goal is stable recovery of x from φ(Ax), both without noise and with noise, regardless of the specific recovery method.
- Assumptions on x and a: The signal set T may be arbitrary, and the required measurement count is governed by a natural complexity parameter of T.The resulting estimate is sharp for stable recovery and sharp up to logarithmic factors for noisy recovery.
- Assumptions on x and a: The measurement vectors are independent and distributed according to an isotropic, L-subgaussian probability measure.Examples include Gaussian and uniform {−1, 1}^n measurements.
- Stability Results: Uniqueness is necessarily only up to sign, and stability compares quadratic measurements in ℓ1 for pairs s,t with s ≠ t and s ≠ −t.Stability is stronger than invertibility because it supplies a quantitative separation bound.
- Stability Results: For k-sparse signals, ρT,N is bounded by k log(en/k)/N, yielding a sufficient measurement condition of N ≥ c2u3k log(en/k) under the small-ball assumption.The guarantee holds with probability at least 1 − 2 exp(−c3u2k log(en/k)).
- Stability Results: Stable recovery for linear and quadratic measurements requires the same order N ∼ k log(en/k) for suitable measurement ensembles.The paper interprets this as no substantial stability price for not knowing measurement phases.
- Noisy Recovery Results: In the noisy setting, an approximate empirical-risk solution can be certified through a computable bound, after which it is close to x0 or −x0 with high probability.The paper suggests repeated initialization with a greedy method until an acceptable solution is found.
- Noisy Recovery Results: O(k log(n/k) log k) noisy measurements suffice for k-sparse vectors, while O(n log n) suffice when x0 may be any vector in R^n.
3 Stability Results
The paper begins the stability analysis by reducing the noise-free problem to estimates for the complexity and separation quantities appearing in its main theorem.
- The proof of the noise-free stability theorem is followed by estimates of κ(v,w) and ρT,N.
3.1 Proof of Theorem 2.4
The proof establishes stability by controlling the empirical quadratic-measurement process and requiring a uniform lower bound on the relevant separation quantity κ.
- A stability result requires infs≠±t, s,t∈T κ(s−t,s+t) to be bounded away from zero.If κ is very small, random measurement vectors are unlikely to provide the needed separation.
- Under the isotropic, L-subgaussian assumptions, the main uniform estimate holds with probability at least 1−2 exp(−c2u2 min{N,E2}).
- Once N is sufficiently large relative to E2, the desired uniform bound follows from the definition of zs,t and κ(s−t,s+t).
3.2 Computing κ and ρT,N
This section develops complexity estimates and lower bounds for κ using covering-number methods, small-ball arguments, and moment assumptions on the measurement distribution.
- The complexity estimates relate ℓ(T) to Euclidean covering numbers, with an upper bound from Dudley and a lower bound from Sudakov.The gap between the bounds is at most approximately √log n, and the resulting estimate is sharp in the examples studied.
- For Gaussian measurements, the small-ball property follows from the bounded density of a one-dimensional Gaussian.
- The small-ball framework also covers isotropic, symmetric, log-concave measures, including volume measures on convex symmetric bodies and suitable product measures.
- A Paley–Zygmund argument provides a second method for deriving the needed lower bound from moment comparisons.
- For symmetric variance-one coordinates with a finite L2q moment, the resulting κ bound depends on moment control beyond the variance.
- For {−1,1}-valued coordinates, the relevant expectation can vanish for specific pairs, so the fourth-moment assumption cannot be relaxed for a uniform bound.
3.3 Examples
The examples show that stable phase retrieval requires measurement counts governed by the geometry and complexity of the signal set. For the full sphere, sparse vectors, finite sets, and block-sparse vectors, the resulting orders are explicit.
- General Measurement Conditions: The general corollaries impose measurement conditions proportional to u^3 times the relevant complexity divided by κ^2.For the full sphere, sparse, finite, and block-sparse settings, these complexities are n, k log(en/k), log |T|, and k log(en/(dk)) + dk, respectively.
- Entire Space T = Rn: N ∼ n measurements suffice for stable recovery over the full sphere when κ is constant.The guarantee holds with high probability.
- Sparse Vectors: N ∼ k log(en/k) measurements suffice for stable recovery of k-sparse vectors when κ is constant.The result holds with high probability.
- Finite Sets: N ∼ log |T| measurements suffice for stable recovery over finite sets when κ is constant.The guarantee holds with high probability.
- Block-Sparse Vectors: N ∼ k(log(en/(kd)) + d) measurements are needed for stability with k blocks of size d.This matches the order required for a random Gaussian matrix to satisfy the block restricted isometry constant.
4 Noisy Measurements
The noisy phase retrieval analysis studies recovery up to sign from quadratic measurements under subgaussian sensing and noise assumptions. It shows that an approximately feasible empirical-risk solution has a controlled error, yielding explicit noisy-measurement rates for several signal classes.
- Problem Setting: Recovery targets an estimate close to x0 or −x0 because quadratic measurements cannot distinguish the two signs.The error is measured by ∥x̂ − x0∥2∥x̂ + x0∥2.
- Problem Setting: The model uses noisy quadratic measurements yi = |⟨ai, x0⟩|2 + wi with isotropic subgaussian sensing vectors and independent symmetric noise.The noise is assumed to have suitable decay, formalized through ψα conditions.
- Recovery Algorithm: Because empirical risk is nonconvex, it is sufficient to find a feasible point whose empirical risk is bounded rather than an exact minimizer.The resulting candidate can be checked against the required bound, and initialization-dependent algorithms can be rerun from different starting points.
- Recovery Guarantee: A bounded empirical excess risk implies a bounded squared-error product ∥x̂ − x0∥2∥x̂ + x0∥2.Proposition 4.7 supplies a probabilistic empirical-risk bound, while Theorem 4.8 converts it into recovery control under a lower bound on κT.
- Sparse Vectors: N ≳ k log(en/k) log k measurements ensure k-sparse recovery error at most ε with probability at least 1 − δ.This is within a logarithmic factor of the optimal linear-measurement estimate.
- Entire Space T = Rn: N ≳ n log n measurements ensure recovery error at most ε over the sphere with probability at least 1 − δ.The result applies when the number of measurements is bounded by a suitable polynomial in n.
- Block-Sparse Vectors: For k-block sparse vectors of length d, N ≳ (k log(en/(kd)) + dk)(log k + log d) measurements ensure error at most ε with probability at least 1 − δ.The guarantee is stated under isotropic subgaussian sensing, subgaussian noise, and a lower bound on κT.
5 Connection with Results on Linear Estimation
The paper connects quadratic phase-retrieval stability to linear estimation through the same Gaussian-complexity parameter, while comparing stability through typical random operators. Its resulting bounds match the linear case in order, although quadratic optimality is not proved here.
- Linear stability: The linear stability notion requires all pairwise differences in T to remain controlled after applying the measurement operator.The paper characterizes stability through inequalities over s,t ∈ T and relates the constant to the smallest singular value of a typical random operator.
- Linear stability: Isotropy makes the expected squared measurement of every unit direction equal to 1, reducing stability to a lower-bound estimate for the empirical process.The analysis seeks a uniform lower bound over normalized differences z=(t−s)/∥t−s∥_2.
- Complexity bounds: N ≳L u^6ℓ^2(T−) measurements yield a high-probability stability estimate for isotropic, L-subgaussian measurements.Theorem 5.1 provides probability at least 1−2 exp(−c u^2ℓ(T−)) in the stated setting, with the relevant constants depending only on L.
- Connection to linear estimation: The quadratic and linear problems use the same Gaussian complexity of the projection of T−T onto the sphere, while the T+T component does not appear.For sets where T+T and T−T have essentially the same complexity, the stability estimates coincide in order and no substantial stability penalty follows from unknown measurement phases.
- Connection to linear estimation: The quadratic bounds are expected to be optimal because they match sharp linear-regression bounds, but this paper does not prove quadratic optimality.The authors defer the more involved optimality argument to prior work on the linear case.