Improved Recovery Guarantees for Phase Retrieval from Coded Diffraction Patterns

1.1. The problem of phase retrieval.

• Phase retrieval seeks an unknown complex vector from amplitude measurements, with recovery defined only up to a global phase.Source: §1.1 · p. 1
• Generic injectivity results establish when a unique signal exists, but alone do not indicate how to recover it or directly generalize to noisy measurements.The cited generic measurement bounds are 4d + o(1) sufficient and 4d − O(log d) necessary.Source: §1.1 · p. 1
• PhaseLift uses the rank-one structure of X = xx* with convex relaxation to recover signals from fewer measurements than direct linear solving requires.The introduction cites Gaussian-measurement guarantees scaling linearly with dimension.Source: §1.1 · p. 2
• Earlier partial derandomization used spherical designs, but the introduction characterizes such setups as mainly theoretical in interest.Source: §1.1 · p. 2
• Structured measurements closer to applications include coded diffraction patterns, modeled by diagonal masks composed with the Fourier transform.Earlier polarization-based recovery used O(log d) masks, or O(d log d) measurements.Source: §1.1 · p. 2
• O(d log^2 d) measurements improve the PhaseLift recovery bound for the coded-diffraction setup adopted from.The introduction contrasts this with the earlier O(d log^4 d) bound for random masks.Source: §1.1 · pp. 2–3

2.1. Coded diffraction patterns.

• Each coded-diffraction measurement takes the squared magnitude of a Fourier coefficient after random diagonal modulation, with mask entries drawn from a bounded real distribution satisfying stated moment conditions.Under condition (5), the measurement ensemble forms a spherical 2-design.Source: §2.1 · p. 3

2.2. Convex Relaxation.

• Lifting expresses measurements as linear constraints on a matrix, and PhaseLift replaces rank minimization with a nuclear-norm convex relaxation.When signal intensity is known, positivity and a trace constraint make nuclear-norm minimization redundant.Source: §2.2 · p. 4

2.3. Our contribution.

• Theorem 1 guarantees recovery up to global phase with probability at least 1−e^−ω under its stated pattern condition, improving by O(log^2 d) and leaving one log-factor over the O(log d) lower bound.The guarantee assumes a unit-norm signal, odd d≥3, and independent complete Fourier measurements; the lower bound applies to Rademacher masks with random erasures.Source: §2.3 · pp. 4–5

2.4. More general bases and outlook.

• Theorem 1 extends to k-dimensional Fourier transforms when the dimensions are mutually coprime odd numbers greater than 3.For more general bases, Lemma 7 can be abstracted, but Lemma 9 currently blocks extending the main result beyond the Fourier setting.Source: §2.4 · p. 6
• Odd dimension is used only for Lemma 7, and the authors consider the result plausibly valid for even dimensions as well.The current proof also leaves generalization to broader bases open because of Lemma 9's coordinate-based argument.Source: §2.4 · p. 6

3.1. Vectors, Matrices, and matrix valued Operators.

• Hermitian matrices form a Hilbert space under the Hilbert-Schmidt (Frobenius) inner product, and the paper uses several operator norms.It also defines positive semidefiniteness and highlights rank-1 projectors, including X = xx* and F_k,l = D_l f_k(D_l f_k)*.Source: §3.1 · pp. 6–7
• The paper treats matrix-valued operators on the Hermitian-matrix space as self-adjoint under the Hilbert-Schmidt inner product, including identity and projector maps.The identity map is presented as a normalized projection.Source: §3.1 · p. 7

3.2. Tools from Probability Theory.

• The probability toolkit includes a Hoeffding extension for independent bounded centered real variables applied to complex-vector expressions.The proof approach splits vectors and sums into real and imaginary parts, then uses Hoeffding bounds and a union bound.Source: §3.2 · p. 8
• The section also recalls matrix Bernstein inequalities for independent random self-adjoint matrices and a vector Bernstein inequality applicable to sums of Hermitian matrices.The matrix bounds include uniform-operator and smallest-eigenvalue forms.Source: §3.2 · p. 8

4.1. Near-isotropicity.

• The measurement operator R is near-isotropic, with E[R(Z)] = Z + tr(Z)1 for every Z in the Hermitian-matrix space.The section notes that a proof of Lemma 7 appears in and also supplies a proof in the appendix.Source: §4.1 · p. 9
• Near-isotropy of R is equivalent to the realizations of D_l f_k forming a 2-design.The passage connects this characterization to [35, Lemma 1] and higher-order spherical designs in.Source: §4.1 · p. 9
• For symmetric ǫ, permutation and sign-change symmetries yield an abstract route to near-isotropy when the basis satisfies two fourth-order polynomial equations.The passage sketches a representation-theoretic argument and refers to for details.Source: §4.1 · p. 9

Z 7→ XZ + ZX −XZX (23)

• The projection onto T’s orthogonal complement is introduced alongside the tangent-space projection associated with the rank-one signal matrix.The supplied passages identify T as the tangent space at X = xx* and denote the complementary projection by P_perp.Source: Z 7→ XZ + ZX −XZX (23) · pp. 9–10

4.2. Well-posedness/Injectivity.

• The single-sided Bernstein inequality removes the O(log^2 d) factor in the failure-probability exponent present in the analogous Lemma 3.7 of.The passage contrasts this with the symmetric Hoeffding inequality used there.Source: §4.2 · p. 10
• Proposition 8 establishes a robust-injectivity lower bound with failure probability smaller than d^2 exp(...), as stated in the proposition.The supplied statement does not include the full exponent or bound.Source: §4.2 · p. 10
• The proof strategy obtains the lower bound by centering R around its expectation and applying an operator Bernstein inequality to control the smallest eigenvalue.It uses near-isotropy and variance bounds for the relevant summands.Source: §4.2 · p. 13
• Lemma 10 gives a robust-injectivity upper bound that holds with probability 1 for all Hermitian matrices.The stated bound also holds simultaneously for all Z in T, with b, ν, and an absolute constant C1 as parameters.Source: §4.2 · pp. 10, 14

• An approximate dual certificate guarantees recovery of x up to a global phase when condition (26) holds.The certificate lies in the range of the measurement operator’s adjoint.Source: §5 · p. 14
• Unlike ’s Hoeffding-based golfing scheme, the authors use Bernstein’s inequality for sharper bounds, at the cost of estimating an additional variance parameter.A direct concentration bound around the exact certificate would require too many measurements, motivating the refined golfing construction.Source: §5 · pp. 15, 20
• To control worst-case operator norms, the proof conditions on measurements whose maximal value is not too large and uses a truncated measurement operator.The unconditioned summands can scale with |⟨f_k, D_l x⟩|^2, motivating this truncation.Source: §5 · pp. 15–16
• The proof bounds truncated-operator deviations using operator Bernstein for an operator-norm estimate and vector Bernstein for a tangent-space estimate.These concentration tools support the golfing scheme’s successive updates.Source: §5 · pp. 17–19
• For d ≥ 3 and ω ≥ 1, the golfing scheme constructs an approximate dual certificate with probability greater than 1 − 5/6e^−ω when the total pattern count satisfies Proposition 18’s bound.The supplied passage does not include the bound’s formula.Source: §5 · p. 20

Proof of the Main Theorem

• The two failure probabilities combine to at most e^-ω, yielding the main result through Proposition 12 and a union bound.The certificate construction fails with probability at most 5/6e^-ω, while condition (26) fails with probability at most 1/6e^-ω.Source: §5 · p. 24
• With probability at least 1 − 5/6e^-ω, Proposition 18 constructs an approximate dual certificate when the total number of masks L meets the stated bound.The bound uses a sufficiently large constant C̄; its formula is not present in the supplied passage.Source: §5 · p. 24
• By Proposition 8, condition (26) holds with probability at least 1 − 1/6e^-ω, potentially after increasing C̄.The proof combines this event with the approximate-certificate event using a union bound.Source: §5 · p. 24

6. APPENDIX

• For L < c log^2 d random masked Fourier measurements of e1, another signal produces identical measurements with probability at least 1 − δ, so no algorithm can distinguish them.The proof reduces equality of measurements to repeated absolute-value mask patterns and applies the coupon collector argument.Source: §6 · p. 26
• The proof of Lemma 7 derives a second-moment identity by evaluating the operator on tensor-product basis vectors, yielding near-isotropy of R.It treats the cases i = j and i ≠ j separately and identifies the result with the action of 2P_Sym2.Source: §6 · pp. 26–27
• The proof of Proposition 12 shows that feasibility and the dual-certificate properties imply the optimality criterion needed for X to minimize (9).It writes a feasible point as X′ = X + ∆ and uses A(∆) = 0 and (Y, ∆) = 0.Source: §6 · pp. 27–28