Cheap Twins: Why Simplicity Priors Cannot Stabilize Phase Retrieval

Phase retrieval means recovering a signal when a sensor records only the magnitudes of its measurements and loses the phases, as in lensless imaging, ptychography, and spectrogram inversion. A standing hope is that a strong enough prior on what signals look like will make recovery stable. The prior can be "the signal is simple", in the sense of short description length, or "the signal is in the range of a trained generator". This proposal argues that the hope is misplaced in one important class of problems: localized measurements, where each measurement sees only part of the signal. There, the ambiguities that make recovery fail are produced by maps that are themselves algorithmically trivial. One example is rotating the phase of one part of the signal relative to the other. Because the map is cheap to describe, a signal and its "twin" have essentially the same complexity, and no complexity budget can tell them apart. What does tell them apart is how the measurements are spread: specifically, how much measurement energy sees both parts of the signal at once.

The note makes three contributions. The first is a theorem showing that complexity-regularized recovery inherits a "price of symmetry" in phaseless problems. The second is a computable, per-signal certificate, the mixed local redundancy, that predicts when recovery will fail. The third is an experimental program on spectrogram-style phase retrieval and generator-prior benchmarks that tests whether this certificate predicts failure better than the signal's compressibility or the usual global count of measurements per dimension. Tight dual frames enter as an attribution tool. A dual frame is a set of reconstruction vectors that inverts the linear measurement map. When a tight dual, one whose singular values are all equal, is used for the linear reconstruction stage, errors pass through that stage equally in all directions. Any remaining failure can then be blamed on the phase-recovery stage.

Core Claim

Two results frame the claim. The Simplest Solution to an Underdetermined System of Linear Equations shows that choosing the lowest-Kolmogorov-complexity solution recovers signals with $K(x)=O(d)$ from $d$ random linear measurements. Kolmogorov complexity is the length of the shortest program that prints the signal. Minimum Complexity Pursuit: Stability Analysis makes this stable under noise with $d \approx 8r\kappa\log n$ measurements for complexity budget $\kappa$.

The same paper by Donoho and coauthors also identifies a "price of structure". When the sensing matrix is algorithmically simple, as Walsh matrices are, simple vectors sit in its null space and the recovery threshold collapses to $O(\log n)$. Our claim is that phaseless measurement carries an analogous and unavoidable price. The analogue of a simple null-space vector is a cheap symmetry of the signal.

Concretely, write $x = u + v$, where $u$ and $v$ are two pieces of the signal with disjoint supports. Its twin is $x_\theta = u + e^{i\theta}v$. The twin is computable from $x$ given the split point and $\theta$. In the quantized complexity of Minimum Complexity Pursuit for Universal Compressed Sensing at resolution $m$, this gives $K(x_\theta) \le K(x) + O(\log n + \log m)$. So any solver that ranks candidates by complexity sees the twin as equally plausible.

What separates $x$ from $x_\theta$ is the geometry of the measurement vectors $\phi_1,\dots,\phi_N$. A direct computation gives the bound

$$\big\|\,|\Phi^* x|^2 - |\Phi^* x_\theta|^2\big\| \;\le\; 2\,|1-e^{i\theta}|\,\|u\|\,\|v\|\,\sqrt{M_\Phi(u,v)}, \qquad M_\Phi(u,v)=\frac{\sum_{i=1}^N |\langle u,\phi_i\rangle|^2\,|\langle v,\phi_i\rangle|^2}{\|u\|^2\|v\|^2}.$$

Here $\Phi^*x$ is the vector of measurements $\langle x,\phi_i\rangle$, and $M_\Phi(u,v)$ is the mixed local redundancy. It is the cross-term analogue of the point-wise redundancy $R_\Phi(x)=\sum_i\|P_{\phi_i}x\|^2$ of A quantitative notion of redundancy for finite frames, where $P_{\phi_i}$ projects onto the line spanned by $\phi_i$. That paper's point-wise redundancy measures how much measurement energy sees a single direction. $M_\Phi$ measures how much sees two pieces of the signal simultaneously.

The proposition to be proved has two parts. First, the lower stability constant of any complexity-constrained phaseless estimator, including an idealized phaseless version of Minimum Complexity Pursuit, is bounded above by $\min_{\text{splits}} \sqrt{M_\Phi(u,v)}$, up to the $O(\log n)$ complexity slack, independently of $\kappa$. Second, for Gaussian measurement vectors this minimum is bounded away from zero with high probability. That would explain why the generator-prior landscape results of Phase Retrieval Under a Generative Prior find only the trivial sign ambiguity. For localized frames such as short-window discrete short-time Fourier transforms (STFT), it can be arbitrarily small.

This is the finite-dimensional, computable counterpart of the "Calabi dumbbell" mechanism in On the connection between uniqueness from samples and stability in Gabor phase retrieval. In that paper, signals whose time-frequency energy forms two islands joined by a thin neck have tiny eigenvalues of a magnetic Laplacian, and counterexamples to uniqueness are dense. Our hypothesis is that small $M_\Phi$ is the discrete, design-level signature of a thin neck.

Research Program

The theoretical part has two goals. It first proves the price-of-symmetry proposition for real signals (sign flips, $\theta=\pi$) and complex signals (relative phase rotations). It then relates $\min_{\text{splits}} M_\Phi$ to two existing quantities. One is the quantitative stability constants of Invertibility and robustness of phaseless reconstruction, which shows that injectivity at $m=2n-1$ does not give stability. The other is the complement property behind the $N=2M-1$ transition in Phase Transitions in Phase Retrieval. The expected result is that $\min_{\text{splits}} M_\Phi > 0$ is a signal-dependent, quantitative refinement of the complement property. It applies to a signal's actual decomposition rather than to all index partitions.

The design part asks how many "bridging" measurements are needed to lift $\min M_\Phi$ above a target value under a fixed budget. A bridging measurement is a longer window or a global vector that sees both islands. Candidates are chosen in one of two ways: greedily by the certificate, or at random. The multi-window idea of Multi-window STFT phase retrieval: Lattice uniqueness, which adds windows to restore uniqueness, supplies the candidate pool. We differ from that work in targeting stability rather than uniqueness and in allocating windows by a per-signal-class certificate.

The reconstruction pipeline has two stages, following Fast Compressive Phase Retrieval from Fourier Measurements. That paper recovers measurement phases algebraically and then solves a linear problem. In our pipeline, stage 1 recovers the phases with a standard solver. Stage 2 rebuilds the signal from the phase-completed coefficients through a dual frame. Sparsity and spectral properties of dual frames proves that once redundancy reaches $m \ge 2n$, a tight dual almost always exists with spectrum decoupled from the primal frame. Below $2n$, dual singular values are trapped by interlacing inequalities.

We use the tight dual in stage 2 so that coefficient errors are transferred to signal errors with equal gain in every direction. Directional structure in the final error, such as concentration on $u - e^{i\theta}v$, is then attributable to stage 1. We do not claim the tight dual beats the canonical dual for white noise. The canonical dual minimizes noise gain in that case, and we test this explicitly. Its role is attribution, and possibly robustness to the uneven, magnitude-dependent errors that stage-1 phase estimates produce.

Baselines

The naive reference point is a uniform-lattice discrete STFT at a fixed measurement count, solved with re-weighted Amplitude Flow and Wirtinger Flow as implemented in PhasePack: A phase retrieval library. That library's user guide reports these methods as competitive. Each solver gets the same spectral initialization, the same iteration cap, and a matched step-size grid.

The strongest competitor on the "does a prior fix it" question is Deep Phase Retrieval, from Phase Retrieval Under a Generative Prior and Compressive Phase Retrieval: Optimal Sample Complexity with Deep Generative Priors. It minimizes the magnitude mismatch over the latent code of a pretrained generator. With Gaussian measurements on MNIST (VAE latent dimension 20, $n=1024$), it reports "reasonable recovery with only 200 measurements", while SPARTA "needed 500". We run it with the same generator family, latent dimension, number of random restarts, and optimizer budget across all measurement designs. It counts as beaten if, at a matched measurement count on localized measurements, our bridged design reaches lower error and a lower rate of converging to the twin.

The strongest competitor on the design question is uniform densification. We add the same number of extra measurements by refining the lattice instead of placing bridging windows. Two ablations isolate the key ingredients. The first compares bridging windows chosen by the certificate against bridging windows chosen at random, at an equal count. The second compares tight-dual against canonical-dual reconstruction in stage 2, with stage 1 held fixed. As a predictor baseline, we compare $\min M_\Phi$ against three quantities: the global ratio $N/n$, a Lempel–Ziv compressed length used as a stand-in for $K(x)$, and the smallest non-trivial singular value of the measurement Jacobian at $x$.

For spectrogram phase retrieval on separated-island signals, and for multi-window STFT, no reported result was found on Lacuna. Those baselines will be established here.

Why not just…?

Why not just use a stronger learned prior? This is the real threat, and it splits in two. A generator trained on data where the relative phase between islands is fixed has learned the symmetry away, so it may resolve the twin. That would not contradict the theorem, which concerns universal simplicity rather than distribution-specific memorization, but it would limit the theorem's practical reach. The experiments therefore train generators on canvases with fixed and with random relative phase. They then evaluate both in distribution and under shifted relative phase. Our prediction is that the prior helps only in the fixed-phase, in-distribution case and fails under shift. If the prior helps robustly, the practical claim shrinks to "priors work only when the training data pins the symmetry".

Why not just add a few random global measurements? Generic Gaussian vectors see both islands, so they plausibly raise $M_\Phi$ as well as optimized windows do. We do not argue around this. Random bridging is a first-class arm of the design study. If it matches certificate-chosen windows, the contribution becomes the certificate as a budget rule: it predicts how many bridging measurements are needed. It is not a superior placement. The price-of-structure result of The Simplest Solution to an Underdetermined System of Linear Equations suggests some randomness will be needed in any case.

Why not just oversample the lattice? Non-uniqueness theory in sampled STFT phase retrieval proves that no rectangular-lattice density guarantees uniqueness for all signals. Our bound shows that densifying short windows does not create cross-island measurements, so $M_\Phi$ stays small. The matched-budget densification baseline tests this directly.

Why not just use the Jacobian's smallest singular value as the certificate? It is computable and is the ground truth for infinitesimal perturbations. However, it misses finite twins such as the $\theta=\pi$ flip, which is exactly the ambiguity that traps solvers. It also gives no direct guidance on where to add measurements. We include it as a predictor baseline. If it predicts finite-flip failures as well as $M_\Phi$ does, we report that and keep $M_\Phi$ only as a design objective.

Proposed Experiments

The first experiment is a synthetic 1D study at $n=512$, the dimension used in Fast Compressive Phase Retrieval from Fourier Measurements. The signal is two complex Gaussian bumps separated by a gap $g$. Measurements come from a discrete STFT with a short Gaussian window. We sweep $g$ and the noise level from 0 to 60 dB signal-to-noise ratio.

For each configuration we record three quantities. The first is the relative error after removing the global phase. The second is the fraction of runs that converge to the twin, detected by projecting the error onto $u-e^{i\theta}v$. The third is the anisotropy of the error after tight-dual reconstruction.

The decisive check is a rank correlation between $\min M_\Phi$ and recovery error across all configurations, compared against $N/n$, compressed length, and the Jacobian singular value. If compressed length or $N/n$ predicts failure as well as $M_\Phi$, the core claim fails.

The second experiment uses a two-digit MNIST canvas: two digits placed far apart, each with an independent phase. Measurements are either Gaussian or a localized 2D windowed Fourier transform, at matched counts from 200 to 1000. Deep Phase Retrieval should succeed with Gaussian measurements near its reported 200-measurement level. The theorem predicts it fails with localized measurements, through twin convergence, until bridging measurements are added. The theorem also predicts that the number of bridging measurements needed tracks the certificate's threshold. The fixed- and random-relative-phase generator variants described above settle the learned-prior question.

The third experiment is exploratory and run on the empirical transmission-matrix data in PhasePack. PhasePack User Guide reports that methods converging at a sampling ratio of 3 on Gaussian data need "ratios of 10 or higher" on this data. We ask whether the empirical matrix's lower redundancy $R_\Phi^-$ and its $\min M_\Phi$ on the resolution-chart targets account for that gap better than global conditioning does. A negative result here would mark the boundary of the theory's reach. It would not refute the theory, because these measurements are not localized.