The Fusion Frame Phase Retrieval

• Structured non-Gaussian measurement ensembles have comparatively fewer phase retrieval guarantees than Gaussian models.The introduction notes that recent work has focused on sub-Gaussian measurements.Source: §1 · p. 2
• The fusion frame problem asks whether x can be recovered up to a unimodular scalar from measurements x*Ajx, where Aj are i.i.d. Haar-drawn rank-r orthogonal projections.Source: §1 · p. 2
• Gradient descent with two-stage initialization achieves linear convergence with O(d log^2 d) measurements when r = O(1).Source: §1 · p. 2
• The paper provides concentration inequalities for rank-r orthogonal projections as part of its convergence analysis.Source: §1 · p. 2

2 Convergence Analysis

• Gradient descent converges locally linearly when initialized in S(x, ε0), under the theorem’s stated conditions.Source: §2 · p. 3

2.1 Two-Stage Initialization

• The initializer scales a leading eigenvector using ρ, then regularized descent removes isotropic population curvature and enlarges the region with a descent estimate.Source: §2 · p. 4, §2.1 · p. 4
• With the stated probability, spectral initialization starts in S(x, ε1), and B regularized steps move it into S(x, ε0), the local convergence region.Source: §2.1 · p. 5
• For r = O(1), the overall method achieves linear convergence with O(d log^2 d) measurements.Source: §2.1 · p. 5

3.1 Experimental Setup

• The experiments use Gaussian-generated target signals and random rank-r orthogonal projection matrices as measurements.Source: §3.1 · p. 5

3.2 Numerical Results

• At d=128, the experiments vary N/d from 2 to 5 and test ranks 1, 5, 7, and 9.Relative error is defined as the distance between the numerical and true solutions divided by the true solution's norm.Source: §3.2 · p. 6, §3.1 · p. 6
• Across 50 repetitions, averaged initialization relative error did not improve as rank increased.Figure 1's left panel plots averaged relative error against N/d for different ranks.Source: §3.2 · p. 6, Figure 1 · p. 6
• At d=128, empirical success generally improves for r>1 at fixed N/d, while r=1 requires the most measurements across the tested range 1 ≤ r ≤ 9.The right panel of Figure 1 plots success rates against N/d.Source: §3.2 · p. 6, Figure 1 · p. 6

• The section states local curvature and local smoothness conditions under the assumptions of Theorem 2.2.The curvature lemma gives probability bounds, while the smoothness lemma states inequalities for points in the local region.Source: §4 · pp. 7, 9
• The regularized local bounds use the estimate for ∥x∥² − ρ² together with bounds on ∥z∥ and the distance from z to x.Source: §4 · pp. 8, 11
• The proof treats the result for E and then eE; in the E argument, h := e−iθ(z)z − x satisfies ∥h∥ ≤ ε0∥x∥.For eE, the stated bound is ε0∥x∥/2 ≤ ∥h∥ ≤ ε1∥x∥.Source: §4 · pp. 9, 11

5.1 Proof of Theorem 2.2.

• Induction using the local curvature and smoothness bounds gives contraction and keeps iterates in the local region, provided the initialization begins there.Source: §5.1 · pp. 11–12

5.2 Proof of Theorem 2.3.

• Theorem 2.3's proof concludes that the distance contracts by a factor in [1/2, 1).Source: §5.2 · p. 13

5.3 Proof of Theorem 2.4

• Theorem 2.4's proof establishes invariance of the regularized inner ball by showing the updated iterate remains in S(x, ε0) in both cases.Source: §5.3 · pp. 13–14

5.4 Proof of Theorem 2.5

• The initializer proof combines spectral and norm estimates to place the initial point in S(x, ε1), then shows the prescribed regularized steps reach S(x, ε0).The argument uses concentration estimates and the iteration bound B(eξ).Source: §5.4 · pp. 14–15

Lemmas 6.1 and 6.4

• For Haar-distributed rank-r A and nonzero x, the scalar x*Ax/∥x∥^2 follows a Beta(r, d − r) distribution.Lemma 6.4 supplies a Bernstein-type tail bound for a Beta(r, d − r) variable.Source: §6 · pp. 15, 18

Lemmas 6.2 and 6.3

• Unitary invariance makes off-diagonal entry second moments equal, gives E(A) = (r/d)I, and makes the matrix-valued expectation E(x) transform equivariantly.For every unitary P, the stated relation is E(x) = P*E(Px)P.Source: §6 · pp. 16–17

Theorem 6.5

• N ≥ C4d/(rρ^2) suffices for the empirical projection average to concentrate around (r/d)I with probability at least 1 − exp(−c4d).The theorem gives absolute constants C4 and c4; its proof uses a beta-tail bound and a net argument.Source: §6 · pp. 19–20

Theorem 6.6

• For a fixed x, Theorem 6.6 provides simultaneous estimates under a sample-size condition involving λ and ζ, with exponentially high probability.The supplied passage omits the displayed estimates and probability expression, so their specific bounds cannot be stated here.Source: §6 · p. 21

6 Concentration Inequalities

• N ≥ C d (λ/ζ)^2 log^2 d suffices for the inequalities to hold with probability at least 1 − exp(−γ d log^2 d).Here C and γ are positive constants.Source: §6 · p. 26
• The inequalities apply to S1 and S2, where Im(h*x) = 0 and the perturbation norms lie in (0, ε0||x||] and [ε0||x||/2, ε1||x||], respectively.These regions cover small and intermediate perturbations subject to the phase-orthogonality condition.Source: §6 · pp. 26–27
• The proof extends fixed-perturbation bounds uniformly over unit phase-orthogonal directions and the corresponding perturbation-scale ranges using η-nets and covering arguments.The uniform bounds are obtained over both the small-scale and intermediate-scale ranges.Source: §6 · pp. 28–30

A Definitions and Lemmas

• An η-net approximates every point in a metric space within η, and the covering number is the minimal cardinality of such a net.The appendix denotes the covering number at scale η by N(X, η).Source: A Definitions and Lemmas · p. 30
• Lemma A.2 gives a covering-number result for η-nets of the complex unit sphere.The supplied passage does not include the stated cardinality bound.Source: A Definitions and Lemmas · p. 30
• Lemma A.3 concerns computing the spectral norm of a Hermitian matrix using a net of the complex unit sphere.It specifies η in [0, 1/2), but the supplied passage omits the lemma's conclusion.Source: A Definitions and Lemmas · p. 30
• Lemma A.4 presents a one-sided Bentkus tail bound for i.i.d. real-valued variables; Φ denotes the standard-normal distribution function and c0 is set to 1.The supplied passages omit the bound and the full variable assumptions.Source: A Definitions and Lemmas · p. 30