Source-linked AI summary
Stable phase retrieval with low-redundancy frames
Bernhard G. Bodmann, Nathaniel Hammen
TL;DR
Phase retrieval asks whether signals can be recovered from magnitude-only measurements, including measurements arising in applications such as X-ray crystallography and quantum communication. This paper develops recovery procedures for complex polynomials and proves uniqueness and noise stability under stated assumptions.
Problem
The paper studies how many evaluations of squared magnitudes are needed to determine a signal up to a unimodular constant, and whether noisy measurements permit accurate recovery.
Method
The approach reconstructs complex polynomials from magnitude data by comparing extensions across intersecting lines and selecting compatible root configurations.
Results
Perturbing the measured quantities by sufficiently small noise yields approximate recovery with error O(ε), while numerical experiments find the linear error regime extends beyond the provable threshold.
Takeaways & Limitations
Magnitude measurements on two suitably angled lines can determine a polynomial up to a unimodular constant, and the recovery procedure remains proportionally accurate under sufficiently small perturbations.
Takeaways & Limitations
The recovery procedure assumes the signal is a complex polynomial of degree d−1 and, in a stability lemma, imposes lower and upper bounds on the signal and its derivative on the unit circle.
Abstract
from arXiv · showhide
We investigate the recovery of vectors from magnitudes of frame coefficients when the frames have a low redundancy, meaning a small number of frame vectors compared to the dimension of the Hilbert space. We first show that for vectors in d dimensions, 4d-4 suitably chosen frame vectors are sufficient to uniquely determine each signal, up to an overall unimodular constant, from the magnitudes of its frame coefficients. Then we discuss the effect of noise and show that 8d-4 frame vectors provide a stable recovery if part of the frame coefficients is bounded away from zero. In this regime, perturbing the magnitudes of the frame coefficients by noise that is sufficiently small results in a recovery error that is at most proportional to the noise level.
1. Introduction
The paper studies phase retrieval with few linear measurements, seeking both uniqueness up to a unimodular constant and resilience to noise. It develops a polynomial-based recovery procedure and analyzes its stability under small perturbations.
- Motivation: The paper targets low-redundancy phase retrieval by finding few linear measurements whose magnitudes characterize finite-dimensional vectors up to a unimodular constant.It also seeks recovery procedures resilient to noise in the magnitude measurements.
- Related work: Existing approaches use rank-one Hermitian reformulations, compressed sensing, tensor powers, expander graphs, and polarization constructions, but do not reach the necessary measurement count.The paper positions its explicit redundancy bounds relative to projective-embedding theory.
- Recovery procedure: The recovery procedure represents the signal as a complex polynomial and uses magnitude and derivative-related measurements to recover values on the unit circle.Dirichlet-kernel interpolation and the polarization identity provide the extrapolated quantities used in later recovery steps.
- Stability: 8d-4 frame vectors provide stable recovery under suitable conditions, with sufficiently small magnitude perturbations producing recovery error of order the noise level.The paper states that this provable linear error bound holds only up to a certain noise level, while simulations find a wider empirical regime.
- Contributions: 4d-4 suitably chosen measurements determine a vector up to a unimodular constant, while later sections establish stability criteria and numerical verification.The paper organizes these results into injectivity and noisy-recovery analyses.
2. Injectivity of the magnitude map
The magnitude map can be made injective with carefully chosen samples on two intersecting circles or their mapped lines. The proof combines interpolation with a root-selection argument based on an irrational-angle reflection composition.
- Problem setup: The first problem is to determine how many evaluations of A(f)=|f|2 identify f up to a unimodular constant, alongside the question of noisy recovery.Here Pn is the analytic-polynomial subspace of the trigonometric-polynomial space Tn.
- Injectivity result: 4n-4 magnitude samples suffice to determine a polynomial of degree at most n−1 up to a unimodular constant.The theorem uses a specific sampling construction and an auxiliary result concerning magnitudes on two lines.
- Two-line argument: Magnitudes on two lines intersecting at an angle α not in πQ determine a degree-at-most-d−1 polynomial up to a unimodular constant.The proof extends the magnitude data across each line and selects roots common to the resulting symmetry patterns.
- Proof mechanism: Dirichlet-kernel interpolation extends samples from each circle to the full circles, enabling the two-line uniqueness argument after conformal mapping.The circles intersect at two points, and additional unit-circle magnitudes complete the data needed on their union.
3. Stable recovery in the presence of noise
The recovery procedure propagates sufficiently small measurement perturbations into coefficient errors proportional to the noise level, under a nonvanishing-magnitude condition. It combines perturbed moment recovery, polynomial factor reconstruction, and finite sampling; simulations show the linear regime extends beyond the proven stability radius.
- Perturbed moments: Perturbed moments determine the coefficients of the inner-root polynomial factor with error O(γ), where γ bounds moment perturbations.Newton’s identities provide the coefficient recurrence used with perturbed moments.
- Stability conditions: If the polynomial stays bounded away from zero on the unit circle and measurement noise is sufficiently small, the inner factor coefficients have error O(ǫ).The condition includes a lower magnitude bound and a noise restriction proportional to m^2.
- Polynomial reconstruction: The outer-root factor is obtained by reversing the inner-factor coefficients, preserving O(ǫ) coefficient accuracy.Combining the inner and outer factors yields a polynomial whose coefficients also have error O(ǫ).
- Finite measurements: Finite measurements are obtained by discretizing and interpolating with the Dirichlet kernel.The construction recovers approximations to |f(z)|^2 and f′(z) from sampled perturbed values.
- Recovery guarantee: Using 3 sets of perturbed measurements with errors at most ǫ determines the polynomial up to a unimodular constant with accuracy O(ǫ).The recovered coefficient approximation is likewise O(ǫ).