CS Paper Radar

The Minimum Number of Measurements for Almost-Everywhere Complex Phase Retrieval

Zhiqiang Xu

cs.IT math.NA ·submitted 2026-08-15 03:20 UTC · v3
theory

Abstract

Let $d\geq 2$ and let $\bf{f}_1,\ldots,\bf{f}_m\in\mathbb C^d$. We prove that if $m\leq 2d-1$, then the intensity measurement map \[ \bf{x}\longmapsto \bigl( |\langle \bf{x},\bf{f}_1\rangle|^2, \ldots, |\langle \bf{x},\bf{f}_m\rangle|^2 \bigr) \] fails to recover almost every signal in $\mathbb C^d$ uniquely up to a global phase factor. Combined with the known generic sufficiency of $2d$ measurements, our result establishes that the minimum number of measurements required for almost-everywhere phase retrieval in $\mathbb C^d$ is exactly $2d$. This resolves an open problem in phase retrieval by determining the exact measurement threshold for almost-everywhere phase retrieval in ${\mathbb C}^d$.

Comment
7 pages

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.IT ·2026-09-25 ·Jian-Feng Cai, Zhibo Jin, Tong Wu, Ruizhe Xia
theory similarity 0.66
Abstract · 38 pages

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.

0.19

A Mathematical Theory of Near-Field Super-Resolution

cs.IT math.NT ·2026-09-25 ·Sajad Daei, Gabor Fodor, Mikael Skoglund
similarity 0.60
Abstract

Finite-aperture near-field sensing leads to a super-resolution geometry fundamentally different from the translation-invariant Fourier setting. In the Fresnel regime, wavefront curvature introduces a range-dependent quadratic aperture phase, so distinguishability is governed by incomplete quadratic exponential sums of the form \( \sum_{n=0}^{N_r-1} a_n e^{i(ω_1 n+ω_2 n^2)} \), rather than by angular separation alone. We develop a deterministic recovery theory for sparse measures with ranges on a finite grid and continuous angles, and introduce a support-uniform quadratic-phase aperture criterion replacing classical minimum separation. Under this criterion, total-variation minimization exactly recovers every sparse measure in the admissible support class, uniformly over all nonzero complex amplitudes. The proof develops nonasymptotic support-uniform bounds for finite quadratic sums and combines them with a gauged Hermite dual certificate controlling interpolation, local curvature, and off-support leakage. We further construct a finite-harmonic Bessel-Vandermonde lift with explicit truncation error. In the far-field limit, the quadratic phase disappears and the theory reduces to Fourier-type angular super-resolution.

0.27

The Fusion Frame Phase Retrieval

cs.IT ·2026-09-08 ·Haixia Liu, Bing Gao, Yang Wang
similarity 0.60
Abstract · 32 pages, 2 figures

The phase retrieval problem involves reconstructing a function or signal solely from the magnitude of linear measurements. Most theoretical analyses of phase retrieval algorithms rely on i.i.d. Gaussian random measurements or sub-Gaussian random measurements. In this paper, our focus is on the fusion frame phase retrieval problem, where the sampling matrices are i.i.d. rank-$r$ orthogonal projections drawn from the Haar measure. We present concentration inequalities for functions on the set of rank-$r$ orthogonal projection matrices. These inequalities are crucial for the theoretical analysis of the fusion frame phase retrieval problem. Based on these inequalities, we demonstrate that gradient descent, combined with a two-stage initialization, achieves linear convergence to the target signal up to a global phase with a measurement complexity of $O(d\log^2 d)$ when the rank $r = O(1)$. We verify this convergence through numerical results.

0.16

A Nonadaptive Sparse Fourier Transform in Every Dimension

cs.DS cs.ITmath.NA ·2026-11-19 ·Mahdi Cheraghchi, Jingyi Lyu
similarity 0.55
Abstract

Let $G=(\mathbb{Z}/2^a\mathbb{Z})^d$, of order $N=2^{ad}$. Given point-query access to any complex signal $X$ with Fourier transform $\hat{X}$ over $G$, we provide a randomized algorithm that constructs a $k$-sparse estimate $\widetilde{X}$ via non-adaptive queries such that, with large probability, $\|\widetilde{X}-\hat{X}\|_2^2 \leq C \cdot \|H_k(\hat{X})-\hat{X}\|_2^2$, for an absolute constant $C>0$, where $H_k(\cdot)$ denotes the best $k$-sparse approximation. The constant $C$ can be improved to any desired $1+\varepsilon$ by either supplying a constant-factor estimate on the $k$-sparse tail norm or allowing an arbitrarily small additive error term $δ\|\hat{X}\|_2^2$ on the right-hand side. With a supplied tail estimate, we can also satisfy an $\ell_\infty/\ell_2$ heavy hitters guarantee. For fixed $δ$, the number of samples is $O((k/\varepsilon^2)(\log N)\log(k/\varepsilon))$, and the recovery algorithm requires a polynomial in $(k/\varepsilon)\log N$ exact operations. The algorithm naturally extends to $G=(\mathbb{Z}/b^a\mathbb{Z})^d$ for any fixed integer $b>1$.

0.32

Optimal Low-Rank Quantum State Tomography with Bounded-Sample Joint Measurements

cs.DS quant-phcs.ITcs.LG ·2026-09-09 ·Ashwin Nayak, Xingyu Zhou
theoryhighly cited similarity 0.55
Abstract · 70 pages; v2: minor revisions

We determine the optimal sample complexity of low-rank quantum state tomography when each measurement may act jointly on at most $t$ samples. For sufficiently small $\varepsilon$, estimating an unknown state on $\mathbb{C}^d$ of rank at most $r$ to trace norm error $\varepsilon$ with constant success probability requires, and is achievable with, $$Θ\left(\frac{dr}{\varepsilon^2}\mathop{\mathrm{max}}\left\{1,\frac{r}{\sqrt{t}}\right\}\right)$$ samples. The lower bound allows the protocol to choose each joint measurement adaptively using all previous classical outcomes; the matching upper bound is nonadaptive. Thus joint measurements on at most $t$ samples improve the complexity of algorithms making single-sample measurements by at most a factor $\sqrt{t}$. Further, measuring order $r^2$ samples jointly is necessary and sufficient to attain the unrestricted collective rate. For the lower bound, we vary the support of a state with fixed uniform spectrum and bound the Fisher information trace of every joint measurement on $t$ samples. The adaptive Fisher chain rule and the van Trees inequality then give the trace norm lower bound. For the upper bound, we construct and analyze a nonadaptive tomography protocol based on a Gaussian joint measurement. An explicit second moment identity and a conditional Gaussian law outside the state's support give a rank-dependent error analysis, yielding the matching rate.

0.51

Exponential Quantum Advantage in Testing Fourier Dimensionality

cs.CC quant-phcs.DS ·2026-09-22 ·Kenny Chen
theory similarity 0.53
Abstract · 38 pages; small fixes to existing sections, adding new sections on the tolerant version of the problem

A boolean function $f$ has Fourier dimension $k$ if its strings with nonzero Fourier coefficients span a subspace of dimension $k$. We first consider the property testing task of determining whether a function has Fourier dimension at most $k$, or is $ε$-far from being so. We show that there is an $O(k/\sqrtε)$-query quantum property tester for this problem, which we show to be almost optimal. Combined with Gopalan \etal's classical lower bound of $Ω(2^{k/2})$, this demonstrates an exponential quantum advantage for this task. We complement this result with a $\tilde{O}(2^{k/2}/ε)$ classical tester, giving a quadratic improvement over the previous best tester, and essentially settling the classical query complexity. We then introduce and study the tolerant version of this problem. That is, determining whether a function is $αε$-close to having Fourier dimension at most $k$, or is $ε$-far from being so. Perhaps surprisingly, we show that this tolerant version of the problem is essentially just as hard as the standard version of the problem. That is, we show this problem has a $\tilde{O}(k/ε)$ quantum tester, and a $\tilde{O}(2^{k/2}/ε)$ classical tester.

0.25

The Generalized Twin Image: Understanding Regularized Phase Retrieval

eess.IV physics.optics ·2026-10-30 ·Zhiyuan Hu, Michael Unser, Jonathan Dong
similarity 0.53
Abstract

Image priors can dramatically improve phase retrieval reconstruction, but their effectiveness strongly varies between imaging modalities. We introduce the generalized twin image, which extends the classical twin-image ambiguity from Fourier phase retrieval to any invertible sensing operator, to understand this effectiveness. The ambiguity extends to undersampled and oversampled measurements, remaining exact under undersampling and for oversampled coded Fourier measurements. We show that it provides a simple criterion to assess regularization effectiveness: the image prior should favor the ground truth over its generalized twin image. We propose the total-variation ratio as a simple measure of this preference, and derive closed-form estimates for structured random phase retrieval models. Experiments with a pretrained denoiser demonstrate that the ratio predicts regularized reconstruction performance across different sensing models.

0.30

The Gauss--Newton Method for Phase Retrieval from Coded Diffraction Patterns

cs.IT ·2026-10-13 ·Meng Huang, Tianjiao Wang
similarity 0.53
Abstract

We study the minimum-norm Gauss--Newton method for phase retrieval from random coded diffraction patterns with additive intensity noise. For bounded symmetric masks satisfying the standard complex moment conditions, we establish convergence guarantees with quadratic error recursions in both the resampled and fixed-data settings. In the resampled setting, $O(\log^2 n)$ masks per independent block suffice to obtain a spectral initializer within a constant-relative-radius neighborhood and to establish a local quadratic error recursion with an additive noise term. Consequently, in the noiseless case, the method achieves relative accuracy $ε$ using $O(\log\log(1/ε)\log^2 n)$ masks. In the fixed-data setting, $O(\log^6(en))$ masks suffice for spectral initialization within a neighborhood whose relative radius is proportional to $\log^{-5/2}(nL)$. Within this neighborhood, the method satisfies a linear contraction bound and eventually a quadratic error recursion. In particular, in the noiseless case, the method initially converges linearly and enters a quadratic convergence phase after $O(\log n)$ iterations, without acquiring additional masks. Numerical experiments on synthetic signals and a natural image demonstrate the method's efficiency relative to state-of-the-art algorithms.

0.15