PaperlayerView exact revision on arXiv

Source-linked AI summary

Stable Recovery and Benign Overparameterized Landscapes for Phase Retrieval from Coded Diffraction Patterns

Jian-Feng Cai, Zhibo Jin, Tong Wu, Ruizhe Xia

arXiv:2609.30825v1cs.ITmath.IT

TL;DR

Coded diffraction patterns are structured phase-retrieval measurements, but dependence among measurements from a shared mask complicates stability analysis. The paper proves a uniform lower isometry using a row-subset operator-norm bound, then derives stable convex recovery and a benign noiseless overparameterized landscape.

  • Problem

    Existing stable-recovery guarantees for convex CDP programs do not attain Gaussian-type noise scaling, and a global benign-landscape guarantee for the CDP model had not been established.

    Source: §I · pp. 2, 4

  • Method

    The paper proves a uniform lower isometry for the lifted CDP operator and uses a uniform operator-norm bound over row subsets to handle dependent measurements.

    Source: §I · p. 4, §V · p. 19, §VIII · p. 35

  • Results

    With L ≍ log n masks, the paper establishes stable convex recovery and a benign noiseless landscape under factor width r = O(log^5(2n)).

    Source: §I · p. 4, §VIII · p. 35

  • Takeaways & Limitations

    The row-subset operator-norm bound is a key ingredient for stability analysis of CDP measurements and may be useful for other structured measurement models.

    Source: §VIII · p. 35

Abstract

from arXiv · show

Coded diffraction patterns (CDPs) provide a structured and physically relevant model for phase retrieval, but the dependence among Fourier measurements generated by a common mask makes sharp stability analysis challenging. For a fixed unit-norm signal $\boldsymbol{x}_\star \in \mathbb{C}^n$, let $\boldsymbol{X}_\star=\boldsymbol{x}_\star\boldsymbol{x}_\star^*$, and let $\mathcal A$ be the lifted CDP measurement operator. We prove that, with $L=O(\log n)$ random masks, the following uniform lower isometry holds with high probability: $\|\boldsymbol{X}-\boldsymbol{X}_\star\|_F \lesssim \log^2(2n) \frac{\|\mathcal A(\boldsymbol{X}-\boldsymbol{X}_\star)\|_2}{\sqrt{nL}}, \boldsymbol{X}\succeq\boldsymbol{0},$ from which we derive two consequences. First, for $\boldsymbol{y}=\mathcal A(\boldsymbol{X}_\star)+\boldsymbol{e}$, PhaseLift-type convex programs achieve the Gaussian-type stable recovery bound $\|\widehat{\boldsymbol{X}}-\boldsymbol{X}_\star\|_F \lesssim \frac{\log^2(2n)}{\sqrt{nL}}\|\boldsymbol{e}\|_2.$ Second, in the noiseless case, the nonconvex factorized loss has a benign landscape when the factor width satisfies $r = O(\log^5(2n))$: every second-order critical point $\boldsymbol{V}\in\mathbb C^{n\times r}$ satisfies $\boldsymbol{V}\boldsymbol{V}^*=\boldsymbol{X}_\star$. The key ingredient is a uniform operator-norm bound over row subsets of the dependent CDP measurement matrix, which permits the removal of a controlled set of adaptively selected rows while preserving tangent injectivity.

I. INTRODUCTION

The introduction identifies a gap in stable convex recovery and global landscape guarantees for coded diffraction patterns, whose Fourier measurements are dependent within each mask. It presents a uniform lower isometry as the basis for convex and nonconvex recovery results, and introduces the random-mask Fourier measurement model.

A. Coded Diffraction Model

  • Each CDP mask produces a Fourier-intensity pattern whose measurements are generally correlated within that pattern; L masks give m = nL measurements.The model uses Fourier measurements of the signal modulated by masks.Source: §I · p. 2

I. INTRODUCTION

  • The lower isometry yields stable recovery for PhaseLift-type convex programs, addressing the lack of Gaussian-type noise scaling guarantees for convex CDP recovery.The introduction describes the resulting scaling as Gaussian-type up to logarithmic factors.Source: §I · pp. 3–4
  • A uniform operator-norm bound over row subsets lets the analysis remove adaptively selected rows with large normal-component measurements while preserving tangent injectivity.This addresses within-pattern dependence and gives a matching ℓ2 normal bound outside the erased rows.Source: §I · p. 4
  • With L ≍ log n masks, the paper establishes a uniform lower isometry simultaneously for every PSD candidate.This stability result underlies the paper’s convex and nonconvex recovery consequences.Source: §I · p. 4
  • In the noiseless case, the factorized least-squares loss has a benign landscape under mild overparameterization, with factor width r = O(log^5(2n)).Source: §I · p. 4

B. Notation

The section fixes notation and presents a uniform lower isometry for the PSD secant set, followed by stable convex recovery and a benign landscape guarantee for overparameterized optimization.

B. Notation

  • The notation defines tangent-space projections at X⋆ and specifies comparison, logarithm, and vector and matrix norm conventions used in the analysis.The tangent-normal decomposition uses H_T⋆ = P_T⋆H and H_T⊥⋆ = P_T⊥⋆X ⪰ 0.Source: B. Notation · p. 6

A. Uniform Lower Isometry

  • With L ≍ log n masks, the lower isometry controls Frobenius error by measurement discrepancy for every PSD candidate, including candidates of unrestricted rank.The result concerns the structured secant set {X − X⋆: X ⪰ 0}, not an RIP over all matrices.Source: A. Uniform Lower Isometry · pp. 6–7

B. Stable Recovery of Convex Programs

  • For PSD convex estimators with controlled measurement fit, the lower isometry yields stable recovery from noisy measurements without requiring a rank restriction.The section identifies feasibility and least-squares programs as ways to ensure the required fit condition.Source: B. Stable Recovery of Convex Programs · pp. 7–8

C. Application to Overparameterized Optimization

  • In the noiseless case, factor width r = O(log^5(2n)) suffices for every second-order critical point to recover X⋆, while nonglobal critical points have a direction of strictly negative curvature.The guarantee combines the lower isometry with a spectral upper bound in the landscape framework.Source: C. Application to Overparameterized… · p. 9

IV. PROOF OF THE UNIFORM LOWER ISOMETRY THEOREM

The proof decomposes PSD errors into tangent and normal components, then controls their measurement effects using row erasure and a uniform bound for subsets of dependent CDP rows.

IV. PROOF OF THE UNIFORM LOWER ISOMETRY THEOREM

  • The proof uses m = nL and studies the measurement matrix and lifted operator restricted to selected row sets.It fixes a failure probability parameter before establishing the uniform lower isometry.Source: §IV · p. 10

A. Proof Overview

  • The tangent-normal decomposition combines tangent injectivity with controlled row erasure and certificate-based bounds to control both error components by the measurement discrepancy.Erasing the selected rows removes only a controlled fraction of tangent measurement energy, so tangent injectivity survives on the remaining rows.Source: A. Proof Overview · pp. 10–11

B. Key Ingredient: A Uniform Row-Subset Bound

  • A uniform row-subset estimate controls dependent CDP measurements for every row set of size at most s; its stated range is s ≤ n, with an extension to s ≤ m costing extra logarithmic factors in s.The estimate supplies an analogous row-subset bound for structured, dependent coded-diffraction measurements.Source: B. Key Ingredient: A Uniform… · p. 12

C. PSD Measurements Outside the Erased Rows

The section bounds PSD measurements outside adaptively erased rows and shows that removing a controlled number of rows preserves tangent injectivity. The erased set is chosen by measurement size, while the tangent bound applies uniformly over row subsets.

C. PSD Measurements Outside the Erased Rows

  • E_P collects the s largest measurements of P, with ζ_P tr(P) equal to the smallest among those selected values.The PSD measurement bound outside the erased rows allows P to have arbitrary rank and depend on all masks.Source: C. PSD Measurements Outside the Erased… · pp. 12–13

D. Tangent Energy on the Erased Rows and Erasure-Robust Tangent Injectivity

  • A fixed-target coherence estimate and a uniform row-subset bound control tangent energy on erased rows before that energy is subtracted from the full tangent lower bound.The argument combines the coherence estimate with the row-subset bound and compares the erased-row energy with full-measurement injectivity.Source: D. Tangent Energy on the Erased Rows… · pp. 13, 15
  • Erasing any set of at most s rows preserves a uniform tangent-energy bound, yielding erasure-robust tangent injectivity.The bound holds simultaneously for every tangent direction on the stated event.Source: D. Tangent Energy on the Erased Rows… · pp. 13–14

E. PSD ℓ2 Bound Outside the Erased Rows

The section establishes a uniform PSD ℓ2 bound outside erased rows and combines it with tangent estimates and a pure-range certificate in the proof of the main theorem. The certificate construction uses O(log n) masks; that upper bound is used mainly to match its normalization, not as an intrinsic CDP limitation.

E. PSD ℓ2 Bound Outside the Erased Rows

  • A uniform ℓ2 bound outside erased rows holds for every PSD matrix when the bound from Proposition 9 holds.The section obtains this bound by combining an infinity-norm bound with an existing ℓ1 bound on PSD matrices.Source: E. PSD ℓ2 Bound Outside the Erased Rows · p. 15

F. Proof of the Main Theorem

  • The proof combines erasure-robust tangent estimates, the PSD bound outside erased rows, and a pure-range certificate to establish the main estimate.The certificate relates the PSD normal component to the measurement residual and tangent component.Source: F. Proof of the Main Theorem · pp. 16, 18
  • The O(log n) upper bound on mask count mainly matches certificate normalization and is not an intrinsic limitation of the CDP model.Candès et al. constructed a similar pure-range certificate using L ≳ log^4 n masks.Source: F. Proof of the Main Theorem · p. 16

V. PROOF OF THE UNIFORM ROW-SUBSET BOUND

The proof recasts the uniform row-subset operator-norm problem as a sparse-vector supremum of a quadratic chaos process. This reformulation isolates dependence among measurements from one mask in a matrix class, leaving independent mask entries as the process coordinates.

V. PROOF OF THE UNIFORM ROW-SUBSET BOUND

  • Dependence among Fourier measurements from one mask is encoded in the matrix class, while the mask-entry coordinates remain independent.The row-subset operator norm is represented through a quadratic chaos process in those independent entries.Source: §V · p. 19, A. The Row-subset Bound as a Chaos… · p. 20

A. The Row-subset Bound as a Chaos Process

  • Uniformly bounding row-subset operator norms is equivalent to bounding ||Φ* z||2 over s-sparse unit vectors z.Coordinate restriction and zero-padding identify row subsets with sparse vectors.Source: A. The Row-subset Bound as a Chaos… · p. 19
  • The vector ξ is defined as (d1,0, …, dL,n−1)ᵀ; Φ*z depends linearly on ξ and therefore can be expressed as the matrix-vector product Azξ.The displayed matrix components include diag(F z1), …, diag(F zL).Source: A. The Row-subset Bound as a Chaos… · pp. 19–20

B. A Uniform Chaos Estimate

The section bounds a quadratic chaos process using a generic-chaining theorem and entropy estimates for its matrix class. It combines direct sparse-set coverings at small scales with Maurey’s empirical method at larger scales.

B. A Uniform Chaos Estimate

  • The Krahmer–Mendelson–Rauhut chaos bound supplies the tool for controlling the row-subset operator norm through a one-sided sparse-vector estimate.The authors apply it to the matrix class generated by sparse vectors, with bounded mask entries providing the required sub-Gaussian condition.Source: B. A Uniform Chaos Estimate · pp. 20–21
  • Direct nets cover the sparse-vector class at small scales, while Maurey’s empirical method controls covering numbers at larger scales.Integrating the entropy estimates bounds the γ2-functional used by the chaos theorem.Source: B. A Uniform Chaos Estimate · pp. 20, 22, 23
  • The operator-norm estimate uses four-phase coordinate atoms and a Rademacher-sum bound to verify Maurey’s empirical-method hypothesis.The atom set contains ±U_ℓk and ±iU_ℓk, with 4m elements.Source: B. A Uniform Chaos Estimate · pp. 22–23

VI. CONSTRUCTION OF A DUAL CERTIFICATE

The construction produces a pure-range dual certificate with explicit control of its coefficient vector. An empirical identity initializes adaptive golfing updates while keeping the certificate in range(A∗).

  • Replacing I with an empirical identity in range(A∗) incurs only a small perturbation, preserving the estimates needed for the golfing construction.Source: §VI · pp. 24, 26
  • The certificate lies exactly in range(A∗), with explicit control of its coefficient vector and L = O(log n + log(1/ϵ)) masks.Source: §VI · pp. 25, 31
  • Adaptive golfing updates use fresh batches to geometrically contract the tangent residual while keeping the certificate components in range(A∗).Source: §VI · pp. 25, 27
  • With the stated mask budget, the empirical-identity event and all successful golfing updates occur with probability at least 1 − n^-ω.Source: §VI · p. 29

VII. FROM STABILITY TO A BENIGN LANDSCAPE

The section combines the deterministic landscape framework with Theorem 2 to establish noisy recovery bounds and a benign noiseless landscape. In the noiseless case, it also establishes a strict-saddle guarantee.

  • The deterministic landscape framework combined with Theorem 2 yields a recovery bound for every real second-order critical point under noise.Source: §VII · p. 31
  • In the noiseless case, every second-order critical point is a global minimizer, and every nonglobal critical point has negative real-Hessian curvature.Source: §VII · p. 31
  • The analysis applies to the factorized nonconvex loss in (17).Source: §VII · p. 31

A. First- and Second-Order Critical Conditions for the Nonconvex Loss

The section defines real second-order criticality through gradient and Hessian conditions, then treats the complex problem by embedding it in real variables. The complex critical points are defined through their real embeddings.

A. First- and Second-Order Critical Conditions for the Nonconvex Loss

B. The Consequence of the Critical Conditions and its Relationship to Stability

The section uses the second-order conditions to bound the measurement residual, then combines stable injectivity with a spectral upper bound. For a fixed target, the spectral bound holds with high probability when L is logarithmic in n.

B. The Consequence of the Critical Conditions and its Relationship to Stability

C. Noisy Error Bound and the Benign Noiseless Landscape

The section connects CDP stability to stable convex recovery and an exact noiseless landscape under logarithmic-power overparameterization. It also identifies open questions about scaling, width, and algorithmic convergence.

C. Noisy Error Bound and the Benign Noiseless Landscape

VIII. DISCUSSION AND CONCLUSION

  • For a fixed signal chosen independently of the masks, L ≍ log n yields a uniform lower isometry over the PSD secant set, supporting stable PhaseLift-type recovery.The conclusion describes the resulting recovery scaling as near-optimal.Source: §VIII · p. 35
  • A uniform operator-norm bound over row subsets is the key ingredient and may inform analyses of CDP or more structured measurements.Source: §VIII · p. 35
  • Open questions include whether logarithmic factors are intrinsic, whether the landscape remains benign at r=1, and how to obtain iteration-complexity guarantees for practical algorithms.Source: §VIII · p. 36
Loading 2609.30825v1…