PaperlayerView exact revision on arXiv

Source-linked AI summary

Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow

Gang Wang, Georgios B. Giannakis, Yonina C. Eldar

arXiv:1605.08285v5stat.MLcs.ITmath.OC

TL;DR

The paper addresses recovery of an unknown vector from random phaseless quadratic measurements, a generally NP-hard nonconvex problem. It proposes truncated amplitude flow, combining orthogonality-promoting initialization with truncated generalized-gradient refinement, and proves exact recovery with near-optimal measurement counts and linear computational scaling. Experiments report strong performance, including 100% success at m/n = 3 in the real Gaussian model and improved results over related methods.

  • Problem

    Recovering x from phaseless quadratic measurements requires reconstructing missing signs or phases, while the resulting nonconvex optimization problem is generally NP-hard.

  • Method

    TAF uses an orthogonality-promoting initialization followed by truncated generalized-gradient iterations to minimize an amplitude-based cost function.

  • Results

    TAF exactly recovers the signal from a near-optimal number of noiseless random measurements with linear-time complexity, and achieves 100% success at m/n = 3 in the real Gaussian model.

  • Takeaways & Limitations

    TAF reduces the empirical sample-complexity ratio relative to TWF and WF while outperforming amplitude-flow and Wirtinger-flow alternatives in reported experiments.

Abstract

from arXiv · show

This paper presents a new algorithm, termed \emph{truncated amplitude flow} (TAF), to recover an unknown vector $\bm{x}$ from a system of quadratic equations of the form $y_i=|\langle\bm{a}_i,\bm{x}\rangle|^2$, where $\bm{a}_i$'s are given random measurement vectors. This problem is known to be \emph{NP-hard} in general. We prove that as soon as the number of equations is on the order of the number of unknowns, TAF recovers the solution exactly (up to a global unimodular constant) with high probability and complexity growing linearly with both the number of unknowns and the number of equations. Our TAF approach adopts the \emph{amplitude-based} empirical loss function, and proceeds in two stages. In the first stage, we introduce an \emph{orthogonality-promoting} initialization that can be obtained with a few power iterations. Stage two refines the initial estimate by successive updates of scalable \emph{truncated generalized gradient iterations}, which are able to handle the rather challenging nonconvex and nonsmooth amplitude-based objective function. In particular, when vectors $\bm{x}$ and $\bm{a}_i$'s are real-valued, our gradient truncation rule provably eliminates erroneously estimated signs with high probability to markedly improve upon its untruncated version. Numerical tests using synthetic data and real images demonstrate that our initialization returns more accurate and robust estimates relative to spectral initializations. Furthermore, even under the same initialization, the proposed amplitude-based refinement outperforms existing Wirtinger flow variants, corroborating the superior performance of TAF over state-of-the-art algorithms.

I. INTRODUCTION

Phase retrieval seeks to reconstruct an unknown real- or complex-valued vector from quadratic measurements that reveal magnitudes but omit signs or phases. The task has applications across physical sciences and engineering, while its general nonconvex formulation is computationally difficult.

  • The problem recovers an unknown vector x from m quadratic equations with known measurement vectors a_i and observed data y_i.
  • Missing measurement phases leave real-valued inner products with unknown signs and complex-valued inner products with unknown phases.
  • Uniqueness requires at least m ≥ 2n − 1 generic measurements for real signals and m ≥ 4n − 4 for complex signals.
  • The real-valued formulation can be viewed as selecting signs from 2^m combinations, with only two producing x up to a global sign.
  • Phase retrieval arises in X-ray crystallography, optics, coherent imaging, astronomy, and microscopy because physical sensors record only squared magnitudes.

A. Prior art

Prior work includes nonconvex and convex approaches to phase retrieval, but near-optimal measurement regimes remain challenging for scalable iterative methods. Amplitude-based and truncated-gradient ideas motivate the paper’s approach.

  • The amplitude-based formulation is nonconvex and nonsmooth, while gradient regularization is proposed as a route to improved refinement performance.
  • One-dimensional Fourier phase retrieval can lack uniqueness even after trivial ambiguities are removed, motivating additional constraints or measurement redundancy.
  • Phase-retrieval solvers include alternating projections, AltMinPhase, Wirtinger-flow variants, Kaczmarz methods, trust-region methods, and convex approaches.
  • Convex methods achieve exact recovery with O(n) noiseless Gaussian measurements but require semidefinite programs with worst-case complexity O(n^4.5).
  • WF requires O(n log n) measurements and O(mn^2 log(1/ϵ)) time, whereas TWF reaches O(n) measurements and O(mn log(1/ϵ)) time.
  • TWF still needs at least 4n ∼5n equations for stable empirical success rates of at least 99% in the noiseless real Gaussian model, exceeding the information limit m = 2n − 1.

B. This paper

The paper develops truncated amplitude flow, a linear-time two-stage algorithm combining orthogonality-promoting initialization with truncated generalized-gradient refinement. It targets exact recovery from near-optimal random measurements and reports advantages over related methods.

  • TAF minimizes an amplitude-based cost function with computational time linear in both the number of measurements m and dimension n.
  • Its first stage computes an orthogonality-promoting initialization using a few power iterations, followed by truncated generalized-gradient updates.
  • The initialization exploits hidden orthogonality in high-dimensional random vectors rather than the strong-law basis of spectral alternatives.
  • Gradient truncation is designed to eliminate erroneously estimated signs or phases, and experiments report more accurate initialization and better performance than competing alternatives.
  • TAF outperforms the independently developed RWF/AF method especially when the number of equations approaches the real information-theoretic limit 2n − 1.

II. TRUNCATED AMPLITUDE FLOW

The TAF method addresses the nonconvex and nonsmooth amplitude-based objective through gradient regularization and uses an orthogonality-promoting initialization motivated by near-orthogonality in high-dimensional random vectors.

  • The method analyzes and regularizes the nonconvex, nonsmooth amplitude-based cost function with a carefully designed gradient rule.
  • Distance to the solution set accounts for the real global-sign ambiguity and the complex global-phase ambiguity.
  • The presentation fixes a representative solution phase by replacing estimates with a phase-adjusted version when needed.

A. Truncated generalized gradient stage

TAF refines an initial estimate with truncated generalized-gradient iterations for a nonconvex, nonsmooth amplitude-based objective. Its truncation rule targets gradient components associated with sign errors, preserving a well-behaved search direction with high probability.

  • Objective and generalized gradients: The amplitude-based objective is nonconvex and nondifferentiable, motivating generalized gradients for the refinement stage.Generalized gradients extend gradient-like analysis to almost-everywhere differentiable functions in nonconvex nonsmooth settings.
  • Truncated generalized gradient iterations: TAF iteratively refines the orthogonality-promoting initial estimate using truncated generalized-gradient updates.The iterations use a step size and a selected index set of retained gradient components.
  • Sign-error mechanism: Undesirable stationary points require sign differences between the measurements generated by an iterate and those generated by the true signal.This observation motivates detecting and separating gradient components associated with mistakenly estimated signs.
  • Truncation rule: TAF truncates components whose iterates lie sufficiently away from the watershed hyperplane, where most spurious components concentrate.The rule can reject some good gradients or miss some bad ones, but the paper states that both probabilities are very small.
  • Truncation rule: The truncation rule removes most corrupted generalized-gradient components with high probability while maintaining a well-behaved search direction.The rule also excludes relatively large components and makes the truncated objective smooth at the iterate.
  • Numerical comparison: In noiseless real-valued Gaussian experiments, TAF refinement outperforms TWF and WF under the same truncated spectral initialization and also outperforms untruncated AF.These comparisons are presented as evidence for the proposed gradient update and truncation rule.

B. Orthogonality-promoting initialization stage

The initialization exploits near-orthogonality in high-dimensional Gaussian vectors by finding a vector orthogonal to selected measurements, yielding a scalable alternative to spectral initialization. Its performance is consistently superior under noiseless and noisy Gaussian models.

  • Motivation: High-dimensional Gaussian measurement vectors are nearly orthogonal to the signal, motivating initialization through orthogonality to selected vectors.Almost all squared normalized inner-products are below 10^-2, and half are below 10^-3.
  • Construction: The orthogonality-promoting initializer forms a matrix from normalized measurement vectors after selecting indices with the smallest squared normalized inner-products.The resulting smallest-eigenvalue problem can be converted into a largest-eigenvalue problem and solved with power iterations.
  • Advantages: Unlike spectral initialization, the constructed matrix depends on observed amplitudes only through the selected index set and avoids heavy-tailed fourth-order moments.The paper also identifies reduced sensitivity to noisy data as an advantage.
  • Numerical evaluation: The orthogonality-promoting initializer consistently outperforms spectral alternatives, while spectral and truncated spectral methods become similar at sufficiently large m/n.Their performance becomes similar at m/n ≥14 in the noiseless setup and m/n ≥16 in the noisy setup.
  • Numerical evaluation: Figure 4 evaluates relative initial-estimate error against m/n from 2 to 20 under noiseless and noisy real-valued Gaussian models.It compares spectral, truncated spectral, and orthogonality-promoting initialization for n = 1,000.

III. MAIN RESULTS

TAF combines orthogonality-promoting initialization with truncated amplitude-based generalized-gradient refinement for random Gaussian phase retrieval. It achieves exact recovery with about as many equations as unknowns, exponential convergence, and stability under bounded additive noise.

  • Exact recovery: TAF exactly recovers arbitrary real signals from noiseless Gaussian measurements with high probability when the measurement count is proportional to the dimension.The initialization enters a basin enabling the subsequent geometric convergence guarantee.
  • Convergence and complexity: TAF converges exponentially at a dimension-independent rate, requiring O(log(1/ϵ)) iterations to reach relative accuracy ϵ.Each iteration costs O(mn), and total runtime is O(mn log(1/ϵ)).
  • Sample complexity: Numerically, TAF reaches 100% success at m/n = 3, compared with ratios of 5 for TWF and 7 for WF.TAF also exceeds 50% success at the information-limit ratio m/n = 2.
  • Noisy recovery: Under bounded additive amplitude noise, TAF’s error contracts geometrically toward a noise-dependent floor proportional to ∥η∥/√m.The guarantee assumes m ≥ c1|I0| ≥ c2n and ∥η∥∞ ≤ c3∥x∥.

IV. SIMULATED TESTS

Simulated tests compare TAF with WF, TWF, and AF across initialization quality, measurement ratios, noise levels, and a real coded-diffraction image. TAF shows strong recovery, noise stability, scalability, and timing performance in the reported experiments.

  • Experimental setup: TAF uses 50 power iterations for initialization and 1,000 gradient-type iterations for refinement in the comparative experiments.The implementations were evaluated against WF, TWF, and AF, with Matlab code provided for reproducibility.
  • Initialization: The orthogonality-promoting initialization returns more accurate and robust estimates than spectral alternatives across the tested Gaussian settings.The comparison covers noise-free and noisy real- and complex-valued instances.
  • Noiseless recovery: TAF converges slowly during roughly the first 200 iterations at m = 2n −1, then converges exponentially fast after entering a small neighborhood of x.The early slowdown is attributed to eliminating generalized-gradient components corrupted by mistakenly estimated signs.
  • Success rates: TAF exceeds 50% success at m/n = 2 and achieves perfect real recovery from about 3n measurements; complex recovery reaches 95% at m/n = 3.4 and becomes perfect around 4.5n.Success is defined as relative error below 10^-5.
  • Noise stability: Relative MSE scales inversely with SNR for m/n values tested from 6 to 10, supporting TAF stability under bounded additive noise.The result averages 100 independent trials under the amplitude-based noisy data model.
  • Comparative and image tests: TAF with orthogonality-promoting initialization outperforms the simulated alternatives, while TAF converges slightly faster than TWF and both are markedly faster than WF.The initialization comparison uses both truncated spectral and orthogonality-promoting initial estimates; the image experiment uses six masks and 100 gradient iterations.

V. PROOFS

The proofs establish the two ingredients of Theorem 1: an orthogonality-promoting initialization with constant relative error at m ≍ n, and geometric convergence of TAF from such an initialization.

  • V. PROOFS: The analysis addresses the nonsmooth, nonconvex objective and uses proof tools distinct from those for spectral initialization.Some proof components are adapted from earlier WF, TWF, and related analyses.
  • V. PROOFS: The experimental section includes recovered Milky Way Galaxy images after initialization and 100 TAF gradient iterations.The figure compares truncated spectral initialization, orthogonality-promoting initialization, and subsequent TAF refinement.
  • V. PROOFS: The proof of Theorem 1 separates initialization guarantees from convergence guarantees for the TAF refinement stage.The initialization achieves a constant relative error when m is orderwise equivalent to n; convergence then requires a sufficiently small initial error.

A. Constant relative error by orthogonality-promoting initialization

The orthogonality-promoting initialization is proved to achieve a constant relative error with high probability using a number of measurements proportional to the signal dimension.

  • Probability: The proposition’s probability guarantee includes exponentially decaying terms in n and m together with an inverse-polynomial term.The stated guarantee holds for sufficiently large n under the specified proportional measurement conditions.
  • Parameter regime: The meaningfulness of the angular bound requires m/|I0| > 4, with ⌊m/|I0|⌋ = 6 reported to work well when m/n is relatively small.This corresponds to selecting |I0| = ⌈m/6⌉ in the algorithm.
  • Proof strategy: The proof controls the initialization angle by bounding sin^2 θ and then converts this angular control into distance from x.The bound can be made arbitrarily small by increasing m/|I0|; the analysis takes κ = 0.001.
  • Guarantee: The initialization satisfies dist(z0, x)/∥x∥ ≤ 1/10 with high probability when m ≥ c1|I0| ≥ c2n and n is sufficiently large.The constants are universal, and the guarantee applies to arbitrary real-valued x in the noiseless Gaussian model.

B. Exact recovery from noiseless data

The exact-recovery proof shows that truncated generalized-gradient updates are locally contractive and converge geometrically once initialization enters a sufficiently small basin around x.

  • Exact recovery: With an initialization satisfying Proposition 1, TAF reconstructs x exactly in linear time by establishing local contractivity of its update rule.The contractivity argument is formulated through a local regularity condition for the truncated gradient.
  • Local convergence: Inside the basin ∥z − x∥ ≤ ϵ∥x∥, the local regularity condition implies geometric decrease of the iterate distance to x.The basin is invariant under the updates, and the iterates are attracted to x exponentially fast.
  • Regularity analysis: The proof bounds the truncated gradient norm and establishes sufficient descent along h = z − x.Gaussian matrix concentration controls the sensing matrix norm, while additional lemmas control retained and discarded gradient components.
  • Gradient truncation: The truncation analysis treats components with erroneously estimated signs through symmetric spherical-cap events around the sensing vectors.The resulting bounds require m proportional to n and a sufficiently small relative error, with fixed γ and an appropriately chosen step size.
  • Parameters: For default parameters, the admissible step-size analysis gives µ0 = 0.8388 and λ0 = 1.22.These values conclude the proof of Theorem 1 under the stated regularity conditions.

VI. CONCLUSION

TAF is presented as a linear-time solver for generally unstructured random quadratic systems, combining orthogonality-promoting initialization, gradient truncation, and scalable gradient-like iterations. Numerical tests corroborate its superior performance over state-of-the-art solvers, while several extensions remain open.

  • TAF combines orthogonality-promoting initialization, gradient truncation, and scalable gradient-like iterations for random quadratic equations.
  • Future work includes applying the initialization to semidefinite optimization, matrix completion, and blind deconvolution, and extending theory to generalized measurement vectors.
  • The initialization is obtained from a leading eigenvector and is analyzed through its angle with the unknown vector.The proof uses a maximum-eigenvalue formulation and bounds the resulting angle via concentration properties of the selected measurements.
  • The initialization selects measurements using a threshold based on y_i/∥a_i∥2, then analyzes the resulting conditional random rows.The selected rows are treated as independent conditional random vectors, enabling concentration bounds for the initialization matrix.

C. Proof of Lemma 3

The proof of Lemma 3 derives a lower bound for the energy captured by the largest selected coordinates of random measurement vectors. It combines order-statistics arguments with truncation and concentration inequalities to establish the bound with high probability.

  • The proof reduces the lower-bound problem to summing the largest |I0| entries among squared first coordinates of the measurement vectors.The selected coordinates arise after ordering measurements by their normalized quadratic observations.
  • The simpler sample-average lower bound is generally too loose and produces a relatively large upper bound for the target term.
  • The maximum squared coordinate reaches 2 log n with high probability when m/n exceeds a sufficiently large constant.This yields a tighter lower-bound scale than the sample-average estimate under a constant |I0|/m ratio.
  • Grouping squared Gaussian coordinates in pairs converts the analysis to chi-square variables with two degrees of freedom.This provides a tractable complementary distribution for analyzing the relevant order statistics.
  • An upper truncation is introduced because chi-square summands are unbounded, allowing Bernstein-type concentration to be applied.After truncation and mean subtraction, the variables are bounded and centered; the resulting bound holds with high probability under sufficient sampling.
Loading 1605.08285v5…