One-Bin Fourier Challenges for Dimension-Free Reconstruction Certification

Abstract

Partial-Fourier measurement underlies computational imaging, and its reconstructions increasingly come from iterative or learned solvers whose recovery guarantees are conditional on a signal model, a sampling law, and solver accuracy. None of those guarantees transfers to a particular committed output: it can satisfy every acquired coefficient while remaining badly wrong in the unmeasured nullspace. Native Fourier holdout does not repair this, since a spectrally concentrated error is missed unless its bin is drawn, so uniform worst-case risk needs a number of hidden bins proportional to the dimension. We propose a post-commit acceptance test: secret finite-phase masks turn one fixed Fourier readout into dense randomized residual checks, and a median-of-means threshold handles calibrated readout noise. We prove that errors above $E_{\mathrm{rej}}$ are rejected and errors below $E_{\mathrm{acc}}$ are accepted with confidence $1-\delta$ once $q\ge C(1+N{\sigma }^2/E_{\mathrm{rej}}{)}^2\log (1/\delta )$, explicitly exposing the one-bin resolution floor $N{\sigma }^2/\sqrt{q}$; in the zero-noise limit, QPSK gives $4^{-q}$ soundness versus $97.9\%$ minimax false acceptance for a worst-case ordinary-bin error. At a fixed noise-to-threshold ratio, measured screening false acceptance fell from about $21\%$ at 16 checks to $5\%$ at 64; a data-consistent learned nullspace failure with NMSE $0.200$ was rejected by $96.9\%$ of challenge banks while 16 ordinary bins missed it $98.9\%$ of the time; and error statistics at 16 checks stayed stable from 128 through $65,536$ dimensions. The test supports solver acceptance, model selection, and stopping certification, with a certified fresh-bank error interval.

arXiv commentThe author withdraws this paper because the coded-diffraction implementation claimed in Section 3.3 is not established. The certification procedure requires complex-valued linear Fourier measurements, whereas intensity-only acquisition does not directly provide them. The manuscript does not establish the additional acquisition procedure needed to bridge this gap