CS Paper Radar

Sharp Minimax Limits and Compatibility Spectra for Critical Near-DFT Index-Only Frequency Estimation

Armon Rasooli, Mohammad Sadegh Narimani

eess.SP ·submitted 2026-09-01 08:42 UTC · v1

Abstract

An $M$-channel discrete Fourier transform (DFT) channelizer routes an on-grid sinusoid to a single output. When each frame reports only one energy-proportional channel index, signed sub-bin frequency estimation becomes nonregular: dark-channel probability is quadratic in the offset, whereas orientation enters cubically. We study $N$ independent labeled reports under a known uniform-replacement probability $ε_N$ and a single deterministic unitary shared by all frequencies and frames, constrained to routing defect $τ/N$. If $\sqrt{N}ε_N \to λ< \infty$, we establish an attained global-in-frequency minimax limit at the critical scales $N^{-1/4}$ for frequency offset, $N^{-1/2}$ for unitary perturbation and replacement, and $N^{-1}$ for routing defect. The effective unitary tangent is a symmetric complete-graph edge field modulo one centering nuisance, and its first variation is a radius-dependent weighted divergence. For $λ>0$, evaluation at $k$ distinct normalized offset magnitudes yields an exact Fourier-Cauchy nullity spectrum: $\lfloor(M-1)/2\rfloor$ evaluations are necessary and sufficient, for every choice of distinct magnitudes, to certify neutrality at all magnitudes. The terminal nullspace has a greatest-common-divisor dimension formula and positive-definite aggregate curvature. Consequently, exact DFT routing is uniquely minimax within the complete critical tangent class for $M=3$, whereas every positive critical defect budget strictly improves the minimax constant for $M\geq4$. The analysis also yields a smallest-prime curvature-visibility law and, for $M\geq5$, discontinuous compatibility geometry but a continuous minimax value at the zero critical replacement floor $λ=0$.

Closest papers

Nearest neighbours by meaning across the whole index.

A Nonadaptive Sparse Fourier Transform in Every Dimension

cs.DS cs.ITmath.NA ·2026-11-19 ·Mahdi Cheraghchi, Jingyi Lyu
similarity 0.58
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

High Probability Streaming Lower Bounds for $F_2$ Estimation

cs.DS ·2026-09-15 ·William Swartworth, David P. Woodruff, Samson Zhou
theory similarity 0.58
Abstract · RANDOM 2026

Estimating the second frequency moment ($F_2$) of an underlying frequency vector is a fundamental problem in the streaming model. While recent work by Braverman and Zamir [STOC 2025] resolved the space complexity for constant failure probability in the insertion-only model, the optimal dependence on the failure parameter $δ$ remained open. We close this gap by proving a tight high-probability lower bound of $Ω\left(\frac{1}{\varepsilon^2}\log\frac{1}δ\,\log\frac{\varepsilon\sqrt{n}}{\log(1/δ)}\right)$ for $(1\pm\varepsilon)$-approximate $F_2$ estimation. The key challenge is the failure of prior multi-scale direct sum arguments under noise sensitivity. We introduce a noise-robust communication primitive, Exam Mostly Set Disjointness, and prove an $Ω\left(\frac{m}{t}\log\frac{1}δ\right)$ one-way lower bound. Embedding this into a multi-scale reduction yields the correct $\log(1/δ)$ dependence. We also give two complementary algorithms under natural structure assumptions. For streams with frequency bound $B$, we design a subsampling method using continuous $F_0$ tracking that replaces a $\log(n)$ factor with $\text{polylog}(B)$. For $k$-sparse streams, we develop a two-stage sketch using approximate Morris counters, replacing $\log n$ with $\log k$ and achieving a further $\log\log m$ dependence on stream length.

0.35

Fourier Ratio and Restricted Isometry via Entropic Descent

cs.IT math.CA ·2026-09-18 ·Will Burstein, Alex Iosevich, Ben Krause
theory similarity 0.57
Abstract

In this second paper on descent methods as proof mechanisms in harmonic analysis (the first treated Bourgain's $Λ(p)$ selection theorem), entropic mirror descent gives an improved restricted isometry bound, improving sampling and recovery bounds in the Fourier Ratio program. Let $H$ be a complex $n\times n$ matrix with $H^*H=nI$ and $|H_{ij}|=1$. For fixed $0<\varepsilon<\frac14$ and $A_0>0$, independent Bernoulli row selection with expected cardinality $C_{\varepsilon,A_0}r\log\frac{2en}{r}\log(2r)\leq m\leq n/2$ preserves, after normalization by $\sqrt m$, the squared norm of every complex vector $y$ with $\|y\|_1\leq\sqrt r\|y\|_2$ within a factor $1\pm\varepsilon$, with failure probability at most $Cn^{-A_0}$. This includes every $r$-sparse vector and also fully supported ones; support size enters only through this inequality. For $y=\widehat f$ the condition is exactly $\operatorname{FR}(f)^2\leq r$, where $\operatorname{FR}(f)=\|\widehat f\|_1/\|\widehat f\|_2$, giving uniform energy sampling and approximate recovery even for signals with full Fourier support. The same holds for a uniform subset of prescribed cardinality, and for discrete Fourier and real Hadamard matrices. At fixed accuracy the bound removes one sparsity logarithm from the earlier count and replaces $\log n$ by $\log\frac{2en}{r}$; for Walsh matrices it matches, up to constants, the lower bound of Błasiok et al.\ in their range. One relative-entropy potential controls the corrections of an amplitude predictor at every scale; counting them on the symmetric difference of two samples gives the uniform estimate. We also prove the sufficient bound $C_{A_0}\varepsilon^{-5}r\log\frac{2en}{r}\log\frac{2r}{\varepsilon}$, and stable sparse recovery from $Cs\log\frac{2en}{s}\log(2s)$ measurements, with error controlled by the noise and the best $s$-term approximation.

0.42

Sharp Rates for Optimal Recovery of Bandlimited Functions from Localized Oversampling

cs.IT math.CA ·2026-11-08 ·Wentao Huang, Haizhang Zhang
similarity 0.56
Abstract

It is well-known that one can recover a function $f$ bandlimited to $[-δ,δ]$ ( $0<δ<π$) from its finite sample data $f(j),-n\le j\le n$, with an approximation error exponentially decaying to zero as $n$ tends to infinity. Various regularized Shannon sampling formula have been proposed to achieve such exponential approximation. So far the best rate has been $$ O\biggl(\frac1{\sqrt{n}}\exp(-(π-δ)n)\biggr). $$ We establish that the optimal recovery algorithm in the worst-case scenario achieves an approximation error $ρ_{n,δ}$ satisfying $$ c_* \frac1{\sqrt{n}}(\tan\fracδ4)^{2n+1/2}\le ρ_{n,δ}\le C^* \frac1{\sqrt{n}}(\tan\fracδ4)^{2n+1/2}, \quad 0<δ\leqπ,\quad n\geq1, $$ where $c_*,C^*$ are positive constants independent of $n$ and $δ$. This result identifies the best possible exponential rate to reconstruct bandlimited functions from two-sided finite oversampling data. In other words, $$ ρ_{n,δ} \asymp \frac{\tan\fracδ4}{\sqrt{n}}\exp\bigl(-c_δ(π-δ)n\bigr), $$ where $c_δ$ is strictly decreasing on $(0,π]$ and $$ \lim_{δ\toπ^-}c_δ=1,\ \lim_{δ\to 0^+}c_δ=+\infty. $$ We also make the new finding that one can also reconstruct $f$ bandlimited to $[-δ,δ]$ with exponentially decaying error from one-sided sample data $f(j)$, $1\le j\le n$, and the sharp rate of approximation error $ρ_{n,δ}'$ of the optimal algorithm is $$ ρ_{n,δ}' \asymp \sqrt{δ/π}\sin^n(δ/2). $$

0.23

Unbounded Holevo additivity gaps in finite dimensions

cs.IT quant-phmath-ph ·2026-09-16 ·Jinzhao Wang
code/data similarity 0.55
Abstract · 22+8pp; v2:added a short discussion of concurrent works; corrected estimates in Appendix B; added a Lean certificate: https://github.com/JWa…

We establish unbounded two-use Holevo additivity gaps in finite dimensions. For each sufficiently large fixed integer $K$ and all sufficiently large $n$, we construct channels $T_n$ with output dimension $K^n$, input dimension $\exp(Θ_K(n^2))$, and \[ χ(T_n^{\otimes2})-2χ(T_n) \ge n\left[\frac{\log_2K}{K}-2\log_2(1+9/K)\right]-O(1/n). \] The gap is linear in output qubits, with an explicit quadratic input-qubit cost and an explicit threshold on $n$. We also obtain channels whose single-use Holevo quantity tends to zero while their two-use Holevo information, and hence classical capacity, diverges. The channels arise from structured tensor products of the complementary mixed-unitary channels used in Collins's free-probabilistic proof. We establish minimum-output-entropy gaps by combining Collins--Youn's product-group Haagerup inequality with Bordenave--Collins's quantitative strong-convergence estimates. We also provide a Lean certificate for our proofs.

0.51

A Tight Second-Order Converse Bound for Variable-Length Feedback Codes

cs.IT ·2026-09-10 ·Recep Can Yavas
similarity 0.54
Abstract · 26 pages, submitted to Information Theory Transactions

We study variable-length feedback (VLF) codes over a discrete memoryless channel under average decoding-time and error-probability constraints. In the non-vanishing error probability regime, Polyanskiy, Poor, and Verdú (2011) derive achievability and converse bounds on the logarithm of the maximum achievable codebook size. These bounds establish the $ε$-capacity but leave an order-$\log N$ gap in the second-order expansion, where $N$ is the average decoding time. Yavas and Tan (2025) improve the coefficient of $\log N$ in the achievability bound from $-1$ to $-\frac{C}{C_1}$, where $C$ is the channel capacity and $C_1$ is the largest Kullback--Leibler divergence between two conditional output distributions. We derive a converse with the same coefficient, establishing the second-order fundamental limit for every positive-capacity discrete memoryless channel with finite $C_1$. The result also covers the moderate-deviations and error-exponent regimes, including polynomially decaying error probabilities. The converse uses Rényi entropy and the extrinsic Jensen--Shannon divergence. We also derive necessary properties of asymptotically optimal VLF codes. First-order-optimal codes must have an early-stopping branch, and second-order-optimal codes must additionally exhibit communication and confirmation behavior. Finally, for the binary erasure channel, we determine the exact minimum expected decoding time for every message-set size and admissible error probability.

0.11

Minimax Quantum State Tomography in a Known Trace-Distance Ball

cs.IT quant-ph ·2026-10-04 ·Yonglong Li
theory similarity 0.53
Abstract

We study quantum state tomography when the unknown state lies in a trace-distance ball of radius $R$ around a known reference state $ρ$. For arbitrary collective measurements, we determine the minimax expected risk and confidence radius up to universal constants, uniformly over the dimension, center spectrum, radius, and sample size. Write $Γ=d(\mathrm{Tr}\sqrtρ)^2+d^2R$. For $d\ge2$, $0<R\le1$, and $n\ge1$ copies, the expected risk is $Θ(\min\{R,\sqrt{Γ/n}\})$. At failure probability $0<δ\le1/3$, the minimax confidence radius is \[ Θ\!\left(\min\left\{R,\sqrt{\frac{Γ+\log(1/δ)}{n}}\right\}\right). \] For $\varepsilon\le c_0R$ with a universal $c_0>0$, the copy complexity is $Θ((Γ+\log(1/δ))/\varepsilon^2)$. For the lower bound we use a weighted trace-norm witness to retain all spectral scales in a square-root perturbation family. For the upper bound, we give a direct spectral and concentration analysis of a modified existing purification-based procedure.

0.21

Monotonicity of the Rényi channel capacity under non-signaling assisted channel simulation

cs.IT quant-ph ·2026-09-28 ·Tina Shariat, Matt Hoogsteder-Riera, Marco Tomamichel
similarity 0.53
Abstract · 25 pages, 1 figure

We give an alternative variational proof that non-signaling correlations shared between the sender and receiver cannot increase the Rényi capacity of a classical channel. This monotonicity follows from the data-processing inequality for channel divergences established by Oufkir, Yao and Berta. Our approach works directly with the information-radius representation of the capacity. The constraints defining non-signaling boxes are linear in the box, while the Rényi capacity depends on the channel nonlinearly. We use a Legendre transform to express the capacity as an extremum over a family of affine functionals in which the channel appears linearly. Combining this method with separate arguments for the Shannon capacity and endpoint orders, we recover monotonicity at every order from zero to infinity. We then derive consequences for standard coding exponent functions: non-signaling simulation cannot increase the random-coding or sphere-packing exponent below capacity, or decrease the strong-converse exponent above capacity.

0.35