Literature
Display
← All papers

Robust Uncertainty Principles: Exact Signal Reconstruction from Highly Incomplete Frequency Information

Emmanuel Candès · Justin Romberg · Terence Tao

· IEEE Transactions on Information Theory 52(2 (489–509 ↗

Contents

Overview

This edition follows the September 2004 arXiv v1 manuscript, including its proofs and appendix. The DOI identifies the later February 2006 journal publication; version-specific wording and formulas here follow the reviewed manuscript. Author affiliations are Caltech and UCLA. The source’s acknowledgments credit supporting institutions and earlier discussions; they are not experimental results.

At a glance

Intuition. A Fourier coefficient describes one frequency component of a signal. This paper asks whether observing a randomly selected subset of those components can still identify the original signal. Sparsity supplies the missing information: the decoder searches among signals with very few nonzero entries rather than among all possible signals.

Reading the math. N is the full signal length, T is its nonzero support, and Ω is the set of measured frequencies. The recovery program matches the observed frequencies while minimizing the sum of absolute signal values. Think of the measurements as clues that must uniquely distinguish the sparse answer. The stated guarantee is probabilistic and noiseless; image extensions instead exploit sparse changes between pixels.

For a fixed sparse signal, randomly sampled Fourier coefficients can determine its exact ℓ1 reconstruction with high probability once the expected measurement count is sufficiently large relative to support size and log signal length. The proof constructs a dual trigonometric polynomial and controls random-matrix moments. Sparse differences motivate total-variation extensions and phantom-image demonstrations. Exact noiseless recovery, random sampling, and fixed-signal probability are central assumptions; “robust” in the title does not mean that this manuscript proves a complete arbitrary-noise recovery theorem.

Equations
#⁡{t,f⁡(t)≠0}≤α⁡(M)⋅(log⁡N)−1⋅#​Ω,\#\{t,\,\,f(t)\neq 0\}\leq\alpha(M)\cdot(\log N)^{-1}\cdot\#\Omega,
min⁡∑t=0N−1g⁡|g⁡(t)|,s.t. ​g^​(ω)=f^​(ω)​ for all ​ω∈Ω.\min_{g}\sum_{t=0}^{N-1}|g(t)|,\quad\text{s.t. }\,\hat{g}(\omega)=\hat{f}(\omega)\text{ for all }\,\,\omega\in\Omega.

1 Introduction

Incomplete Fourier data leave an underdetermined inverse problem. Sparsity supplies additional structure, while convex minimization chooses a low-complexity feasible signal without knowing its support in advance. The paper separates information-theoretic uniqueness, computational recovery, and probabilistic sampling guarantees.

Equation
f^(ω)=∑t∈ℤNdf(t)e−iω⋅t.\hat{f}(\omega)=\sum_{t\in\mathbb{Z}^{d}_{N}}f(t)e^{-i\omega\cdot t}.

1.1 A puzzling numerical experiment

A 512×512 phantom is sampled along 22 approximately radial Fourier lines. Setting unseen Fourier values to zero produces strong artifacts; minimizing discrete isotropic total variation recovers the displayed piecewise-constant phantom exactly in the reported numerical experiment. Figure 1 retains the original, sampling mask, minimum-energy reconstruction, and TV reconstruction. Radial sampling in this illustration is different from the independent Bernoulli Fourier sampling of the main theorem, and a successful synthetic phantom is not a general medical-imaging validation.

Complete original Figure1, including every scientific panel and label, from the exact-version PDF.
Figure 1: Example of a simple recovery problem. (a) The Logan-Shepp phantom test image. (b) Sampling ’domain’ in the frequency plane; Fourier coefficients are sampled along 22 approximately radial lines. (c) Minimum energy reconstruction obtained by setting unobserved Fourier coefficients to zero. (d) Reconstruction obtained by minimizing the total-variation, as in (1.1). The reconstruction is an exact replica of the image in (a).
Equations 1.1
‖g‖B​V=∑t1,t2|D1​g​(t1,t2)|2+|D2​g​(t1,t2)|2,\|g\|_{BV}=\sum_{t_{1},t_{2}}\sqrt{|D_{1}g(t_{1},t_{2})|^{2}+|D_{2}g(t_{1},t_{2})|^{2}},
min⁡‖g‖B​Vsubject tog^​(ω)=f^​(ω)​ for all ​ω∈Ω.\min\|g\|_{BV}\qquad\text{subject to}\qquad\hat{g}(\mathbf{\omega})=\hat{f}(\mathbf{\omega})\text{ for all }\omega\in\Omega. (1.1)

1.2 Main Results

For prime signal length, Theorem 1.1 gives uniqueness among sufficiently sparse signals from an arbitrary frequency subset, with a sharp support-count obstruction beyond that threshold. It relies on injectivity of square Fourier minors and does not itself give an efficient reconstruction algorithm. The ℓ0 search is combinatorial; the proposed ℓ1 program is convex. Theorem 1.3 instead fixes a signal and draws each frequency independently with probability τ: support size is at most α(M)τN/logN, and recovery succeeds with probability 1−O(N^−M). This is not an assertion that one draw simultaneously recovers every signal of that sparsity. The proof’s explicit constants are conservative and carry the sampling-parameter conditions shown later.

Equations 1.2
f^(k):=∑t=0N−1f(t)e−i​ωk​t,ωk=2​π​kN,k=0,1,…,N−1.\hat{f}(k):=\sum_{t=0}^{N-1}f(t)\,e^{-i\omega_{k}t},\quad\omega_{k}=\frac{2\pi k}{N},\,k=0,1,\ldots,N-1. (1.2)
f⁡(t)=1N​∑k=0N−1f^​(k)​ei​ωk​t.f(t)=\frac{1}{N}\sum_{k=0}^{N-1}\hat{f}(k)\,e^{i\omega_{k}t}.
f=∑t∈Tαtδt,δt(t′)=1{t′=t}.f=\sum_{t\in T}\alpha_{t}\delta_{t},\qquad\delta_{t}(t^{\prime})=1_{\{t^{\prime}=t\}}.
Theorem 1.1

Suppose that the signal length NN is a prime integer. Let Ω\Omega be a subset of {0,…,N−1}\{0,\ldots,N-1\}, and let ff be a vector supported on TT such that

Equation 1.3
|T|≤12​|Ω|.|T|\leq\frac{1}{2}|\Omega|. (1.3)

Then ff can be reconstructed uniquely from Ω\Omega and f^|Ω\hat{f}|_{\Omega}. Conversely, if Ω\Omega is not the set of all NN frequencies, then there exist distinct vectors f,gf,g such that |supp​(f)|,|supp​(g)|≤12​|Ω|+1|{\hbox{\rm supp}}(f)|,|{\hbox{\rm supp}}(g)|\leq\frac{1}{2}|\Omega|+1 and such that f^|Ω=g^|Ω\hat{f}|_{\Omega}=\hat{g}|_{\Omega}.

Lemma 1.2

([18], Corollary 1.4) Let NN be a prime integer and T,ΩT,\Omega be subsets of ℤN\mathbb{Z}_{N}. Put ℓ2​(T)\ell_{2}(T) (resp. ℓ2​(Ω)\ell_{2}(\Omega)) to be the space of signals that are zero outside of TT (resp. Ω\Omega). The restricted Fourier transform ℱT→Ω:ℓ2​(T)→ℓ2​(Ω){\cal F}_{T\to\Omega}:\ell_{2}(T)\to\ell_{2}(\Omega) is defined as

Equation
ℱT→Ω​f:=f^|Ω​ for all ​f∈ℓ2​(T),{\cal F}_{T\to\Omega}f:=\hat{f}|_{\Omega}\hbox{ for all }f\in\ell_{2}(T),

If |T|=|Ω||T|=|\Omega|, then ℱT→Ω{\cal F}_{T\to\Omega} is a bijection; as a consequence, we thus see that ℱT→Ω{\cal F}_{T\to\Omega} is injective for |T|≤|Ω||T|\leq|\Omega| and surjective for |T|≥|Ω||T|\geq|\Omega|. Clearly, the same claims hold if the Fourier transform ℱ{\cal F} is replaced by the inverse Fourier transform ℱ−1{\cal F}^{-1}.

Equations 1.4–1.8
(P0)ming∈CN⁡‖g‖ℓ0,g^|Ω=f^|Ω,(P_{0})\quad\quad\min_{g\in{\hbox{\bf C}}^{N}}\|g\|_{\ell_{0}},\quad\hat{g}|_{\Omega}=\hat{f}|_{\Omega}, (1.4)
(P1)ming∈CN⁡‖g‖ℓ1:=∑t∈ℤN|g⁡(t)|,g^|Ω=f^|Ω.(P_{1})\quad\quad\min_{g\in{\hbox{\bf C}}^{N}}\|g\|_{\ell_{1}}:=\sum_{t\in\mathbb{Z}_{N}}|g(t)|,\quad\hat{g}|_{\Omega}=\hat{f}|_{\Omega}. (1.5)
Ik={0with prob. ​1−τ,1with prob. ​τ.I_{k}=\begin{cases}0&\text{with prob. }1-\tau,\\ 1&\text{with prob. }\tau.\end{cases} (1.6)
Ω:={k:Ik=1}.\Omega:=\{k:I_{k}=1\}. (1.7)
E​(|Ω|)=τ​N.{\hbox{\bf E}}(|\Omega|)=\tau N. (1.8)
Theorem 1.3

Let f∈CNf\in{\hbox{\bf C}}^{N} be a discrete signal and Ω\Omega be the random set defined in (1.7). For a given accuracy parameter MM, if ff is supported on TT and

Equation 1.9
|T|≤α⁡(M)⋅(log⁡N)−1⋅τ​N,|T|\leq\alpha(M)\cdot(\log N)^{-1}\cdot\tau N, (1.9)

then with probability at least 1−O⁡(N−M)1-O(N^{-M}), the minimizer to the problem (1.5) is unique and is equal to ff.

1.3 For Almost Every Ω

Two counterexamples explain why the sampling assumptions matter. A Dirac comb can have all its informative Fourier coefficients omitted, making recovery impossible even before choosing an algorithm. A carefully placed box signal and a Fourier-invisible perturbation can also defeat ℓ1 minimization. Such structured bad subsets do not contradict a high-probability result over random subsets. Sparsity alone does not make every undersampled Fourier system recoverable.

1.4 Extensions

A piecewise-constant signal has sparse first differences, so recovery can be expressed by total-variation minimization, with its mean fixed separately. Higher-dimensional sparse recovery uses the same strategy; detailed proofs of some extensions are omitted in the source. The printed one-dimensional conversion contains a multiplier inconsistency: after deriving δ̂=(1−e^−iω)ĝ, it defines υ as the reciprocal but writes υf̂ in the equivalent constraint. The original formulas remain unchanged; a direct implementation should use the multiplier implied by the displayed difference identity.

Equations 1.10
min⁡∑t∈ℤNg⁡|g⁡(t)−g⁡(t−1)|g^|Ω=f^|Ω,\min_{g}\,\,\,\sum_{t\in\mathbb{Z}_{N}}|g(t)-g(t-1)|\qquad\hat{g}|_{\Omega}=\hat{f}|_{\Omega}, (1.10)
δ^​(ω)=(1−e−i​ω)​g^​(ω),for all ​ω≠0\hat{\delta}(\omega)=(1-e^{-i\omega})\hat{g}(\omega),\quad\text{for all }\omega\neq 0
minδ⁡‖δ‖ℓ1δ^|Ω∖{0}=(υ​f^)|Ω∖{0},δ^​(0)=0,\min_{\delta}\,\,\|\delta\|_{\ell_{1}}\qquad\hat{\delta}|_{\Omega\setminus\{0\}}=(\upsilon\hat{f})|_{\Omega\setminus\{0\}},\,\,\hat{\delta}(0)=0,
Corollary 1.4

Put T={t,f⁡(t)≠f⁡(t−1)}T=\{t,\,f(t)\neq f(t-1)\}. Under the assumptions of Theorem 1.3, the minimizer to the problem (1.10) is unique and is equal ff with probability at least 1−O⁡(N−M)1-O(N^{-M})—provided, of course, that ff be adjusted so that ∑f​(t)=f^​(0)\sum f(t)=\hat{f}(0).

Theorem 1.5

Put N=n2N=n^{2}. We let f⁡(t1,t2),1≤t1,t2≤nf(t_{1},t_{2}),1\leq t_{1},t_{2}\leq n be a discrete signal and Ω\Omega be the random set defined as in (1.7). Assume that for a given accuracy parameter MM, ff is supported on TT obeying (1.9). Then with probability at least 1−O⁡(N−M)1-O(N^{-M}), the minimizer to the problem (1.5) is unique and is equal to ff.

1.5 Relationship to Uncertainty Principles

A sufficient nullspace condition says that no nonzero Fourier-invisible perturbation can place half its ℓ1 mass on the signal support. The triangle inequality then makes every feasible perturbation increase the objective. Classical deterministic uncertainty bounds imply only much more restrictive support sizes in the regime of interest. The paper therefore pursues dual certificates and random sampling rather than relying only on that deterministic estimate.

Equations
∑t∈ℤN|f⁡(t)+h⁡(t)|>∑t∈ℤN|f⁡(t)|,∀h≠0,h^|Ω=0\sum_{t\in\mathbb{Z}_{N}}|f(t)+h(t)|>\sum_{t\in\mathbb{Z}_{N}}|f(t)|,\quad\forall h\neq 0,\,\hat{h}|_{\Omega}=0
∑ℤN|f⁡(t)+h⁡(t)|=∑T|f⁡(t)+h⁡(t)|+∑Tc|h⁡(t)|≥∑T|f⁡(t)|−|h⁡(t)|+∑Tc|h⁡(t)|.\sum_{\mathbb{Z}_{N}}|f(t)+h(t)|=\sum_{T}|f(t)+h(t)|+\sum_{T^{c}}|h(t)|\geq\sum_{T}|f(t)|-|h(t)|+\sum_{T^{c}}|h(t)|.
∑T|h⁡(t)|<∑Tc|h⁡(t)|∀h≠0,h^|Ω=0.\sum_{T}|h(t)|<\sum_{T^{c}}|h(t)|\qquad\forall h\neq 0,\,\hat{h}|_{\Omega}=0.
2​|T|⋅(N−|Ω|)<N.2|T|\cdot(N-|\Omega|)<N.

1.6 Robust Uncertainty Principles

The proposed robust uncertainty principle concerns typical support pairs, contrasting them with special extremal configurations such as combs. Its stronger scale is probabilistic, with a failure level controlled by the chosen accuracy parameter. The source sketches this broader interpretation rather than developing all its consequences; its title should not be read as a uniform bound for every support pair or a theorem about measurement-noise robustness.

Equations 1.11–1.12
|T|+|Ω|≥2​N.|T|+|\Omega|\geq 2\sqrt{N}. (1.11)
|T|+|Ω|≥γ(M)⋅(logN)−1/2⋅N,|T|+|\Omega|\geq\gamma(M)\cdot(\log N)^{-1/2}\cdot N, (1.12)

1.7 Connections with existing work

The work builds on Basis Pursuit and sparse dictionary-representation results, but recovers an incompletely observed signal rather than merely choosing a sparse expansion of a fully known vector. Random-matrix estimates permit substantially different sampling regimes. Connections to spectral estimation and sublinear Fourier approximation are discussed with care: here the frequency observations are externally specified, and producing a complete length-N reconstruction itself precludes a sublinear output algorithm. [3, 7]

Equation 1.13
f=D​α.f=D\alpha. (1.13)

2 Strategy

The recovery proof needs both injectivity on the true support and a dual polynomial with the correct signs on that support and magnitude strictly below one elsewhere. These conditions make the feasible optimum unique. The remaining argument shows they hold with high probability for the proposed random-frequency model.

2.1 Duality

For a real signal the program can be written using nonnegative positive and negative parts; its dual motivates the certificate. Lemma 2.1 states the corresponding complex-valued result. A certificate supported in the observed Fourier set, together with injectivity on the signal support, proves uniqueness by an ℓ1 inequality and Parseval orthogonality. The proof checks the equality case: a competing optimum must vanish off the support and then injectivity forces it to coincide with the signal. The original statement is retained with its exact assumptions.

Equations 2.1–2.7
min⁡∑t=0N−1g+,g−∈ℝNg+,g−≥0⁡(g+​(t)+g−​(t)),ℱΩ​(g+−g−)=f^|Ω\min_{\begin{subarray}{c}g^{+},g^{-}\in\mathbb{R}^{N}\\ g^{+},g^{-}\geq 0\end{subarray}}~\sum_{t=0}^{N-1}(g^{+}(t)+g^{-}(t)),\quad\mathcal{F}_{\Omega}(g^{+}-g^{-})=\hat{f}|_{\Omega} (2.1)
L⁡(g+,g−,λ,μ+,μ−)=∑t=0N−1(g+​(t)+g−​(t))+λH​(f^|Ω−ℱΩ​(g+−g−))+μ+⁣∗​g++(μ−)∗​g−L(g^{+},g^{-};\lambda,\mu^{+},\mu^{-})=\sum_{t=0}^{N-1}(g^{+}(t)+g^{-}(t))~+~\lambda^{H}(\hat{f}|_{\Omega}-\mathcal{F}_{\Omega}(g^{+}-g^{-}))~+~\mu^{+*}g^{+}~+~(\mu^{-})^{*}g^{-} (2.2)
ℱΩ​(g~+−g~−)\displaystyle\mathcal{F}_{\Omega}(\tilde{g}^{+}-\tilde{g}^{-}) =\displaystyle= f^|Ω\displaystyle\hat{f}|_{\Omega}
(μ+)∗​g~+\displaystyle(\mu^{+})^{*}\tilde{g}^{+} =\displaystyle= 0\displaystyle 0
(μ−)∗​g~−\displaystyle(\mu^{-})^{*}\tilde{g}^{-} =\displaystyle= 0\displaystyle 0
∂L∂g~+​(t)=I{g~+(t)>0}−ℱ∗Ωλ+μ+\displaystyle\frac{\partial L}{\partial\tilde{g}^{+}(t)}~=~I_{\{\tilde{g}^{+}(t)>0\}}~-~\mathcal{F}^{*}_{\Omega}\lambda~+~\mu^{+} =\displaystyle= 0\displaystyle 0
∂L∂g~t−=I{g~−(t)>0}+ℱ∗Ωλ+μ−\displaystyle\frac{\partial L}{\partial\tilde{g}^{-}_{t}}~=~I_{\{\tilde{g}^{-}(t)>0\}}~+~\mathcal{F}^{*}_{\Omega}\lambda~+~\mu^{-} =\displaystyle= 0.\displaystyle 0.
(ℱΩ∗​λ)​(t)\displaystyle(\mathcal{F}^{*}_{\Omega}\lambda)(t) =\displaystyle= sgn​(f)​(t)t∈T\displaystyle{\hbox{sgn}}(f)(t)\quad\quad t\in T (2.3)
1−(ℱΩ∗​λ)​(t)−μ+\displaystyle 1-(\mathcal{F}^{*}_{\Omega}\lambda)(t)-\mu^{+} =\displaystyle= 0t∈Tc\displaystyle 0~\quad\quad\quad\quad\quad t\in T^{c} (2.4)
1+(ℱΩ∗​λ)​(t)−μ−\displaystyle 1+(\mathcal{F}^{*}_{\Omega}\lambda)(t)-\mu^{-} =\displaystyle= 0t∈Tc\displaystyle 0~\quad\quad\quad\quad\quad t\in T^{c} (2.5)
P⁡(t)\displaystyle P(t) =\displaystyle= sgn​(f)​(t)t∈T\displaystyle{\hbox{sgn}}(f)(t)\quad\quad t\in T (2.6)
|P⁡(t)|\displaystyle|P(t)| <\displaystyle< 1t∉T.\displaystyle 1~\quad\quad\quad\quad\quad t\not\in T. (2.7)
Lemma 2.1

Let Ω⊂ℤN\Omega\subset\mathbb{Z}_{N}. For a vector f∈CNf\in{\hbox{\bf C}}^{N}, define the ’sign’ vector sgn​(f){\hbox{sgn}}(f) by sgn​(f)​(t):=f⁡(t)/|f⁡(t)|{\hbox{sgn}}(f)(t):=f(t)/|f(t)| when t∈supp​(f)t\in{\hbox{\rm supp}}(f) and sgn​(f)=0{\hbox{sgn}}(f)=0 otherwise. Suppose there exists a vector PP whose Fourier transform P^\hat{P} is supported in Ω\Omega such that

Equation
P⁡(t)=sgn​(f)​(t)​ for all ​t∈supp​(f)P(t)={\hbox{sgn}}(f)(t)\hbox{ for all }t\in{\hbox{\rm supp}}(f)

and

Equation
|P⁡(t)|<1​ for all ​t∉supp​(f).|P(t)|<1\hbox{ for all }t\not\in{\hbox{\rm supp}}(f).
  • •

    Then if ℱsupp​(f)→Ω{\cal F}_{{\hbox{\rm supp}}(f)\to\Omega} is injective, the minimizer f♯f^{\sharp} to the problem (P1)(P_{1}) (1.5) is unique and is equal to ff.

  • •

    Conversely, if ff is the unique minimizer of (P1)(P_{1}), then there exists a vector PP with the above properties.

Equations
|g⁡(t)|\displaystyle|g(t)| =|f⁡(t)+h⁡(t)|\displaystyle=|f(t)+h(t)|
=||f⁡(t)|+h⁡(t)​sgn​(f)​(t)¯|\displaystyle=||f(t)|+h(t)\,\overline{{\hbox{sgn}}(f)(t)}|
≥|f⁡(t)|+Re​(h⁡(t)​sgn​(f)​(t)¯)\displaystyle\geq|f(t)|+{\hbox{Re}}(h(t)\,\overline{{\hbox{sgn}}(f)(t)})
=|f⁡(t)|+Re​(h⁡(t)​P⁡(t)¯)\displaystyle=|f(t)|+{\hbox{Re}}(h(t)\,\overline{P(t)})
‖g‖ℓ1≥‖f‖ℓ1+∑t=0N−1Re​(h⁡(t)​P⁡(t)¯).\|g\|_{\ell_{1}}\geq\|f\|_{\ell_{1}}+\sum_{t=0}^{N-1}{\hbox{Re}}(h(t)\,\overline{P(t)}).
∑t=0N−1Re​(h⁡(t)​P⁡(t)¯)=1N​∑k=0N−1Re​(h^​(k)​P^​(k)¯)=0\sum_{t=0}^{N-1}{\hbox{Re}}(h(t)\overline{P(t)})=\frac{1}{N}\sum_{k=0}^{N-1}{\hbox{Re}}(\hat{h}(k)\,\overline{\hat{P}(k)})=0

2.2 Architecture of the Argument

Fix the signal and its support T. Concentration first controls the random sample count. An off-diagonal operatorH removes the deterministic diagonal of the restricted Fourier Gram matrix. Inverting its support restriction yields the polynomial in Eq 2.11, which automatically has the required Fourier support and interpolates the signal signs. The two remaining tasks are bounding that inverse and controlling the polynomial outside T. Degree-of-freedom intuition alone does not establish the strict off-support inequality.

Equations 2.8–2.11
P(|Ω|<E|Ω|−t)≤exp(−t2/2E|Ω|).{\hbox{\bf P}}(|\Omega|<{\hbox{\bf E}}|\Omega|-t)\leq\exp(-t^{2}/2{\hbox{\bf E}}|\Omega|). (2.8)
P​(|Ω|<(1−ϵM)​|τ​N|)≤N−M,ϵM:=2​M​log⁡N|τ​N|.{\hbox{\bf P}}(|\Omega|<(1-\epsilon_{M})|\tau N|)\leq N^{-M},\qquad\epsilon_{M}:=\sqrt{\frac{2M\log N}{|\tau N|}}. (2.9)
Hf(t):=−∑ω∈Ω∑t′∈T:t′≠tei​ω​(t−t′)f(t′).Hf(t):=-\sum_{\omega\in\Omega}\,\,\,\sum_{t^{\prime}\in T:t^{\prime}\neq t}e^{i\omega(t-t^{\prime})}\,f(t^{\prime}). (2.10)
(ι−1|Ω|​H)​f​(t)=1|Ω|​∑ω∈Ω∑t′∈Tei​ω​(t−t′)​f​(t′)=1|Ω|​∑ω∈Ωf^​(ω)​ei​ω​t,(\iota-\frac{1}{|\Omega|}H)f(t)=\frac{1}{|\Omega|}\sum_{\omega\in\Omega}\sum_{t^{\prime}\in T}e^{i\omega(t-t^{\prime})}f(t^{\prime})=\frac{1}{|\Omega|}\sum_{\omega\in\Omega}\hat{f}(\omega)\,e^{i\omega t},
P:=(ι−1|Ω|​H)​(ι∗​ι−1|Ω|​ι∗​H)−1​ι∗​sgn​(f).P:=(\iota-\frac{1}{|\Omega|}H)(\iota^{*}\iota-\frac{1}{|\Omega|}\iota^{*}H)^{-1}\iota^{*}{\hbox{sgn}}(f). (2.11)
ι∗​P=(ι∗​ι−1|Ω|​ι∗​H)​(ι∗​ι−1|Ω|​ι∗​H)−1​ι∗​sgn​(f)=ι∗​sgn​(f),\iota^{*}P=(\iota^{*}\iota-\frac{1}{|\Omega|}\iota^{*}H)(\iota^{*}\iota-\frac{1}{|\Omega|}\iota^{*}H)^{-1}\iota^{*}{\hbox{sgn}}(f)=\iota^{*}{\hbox{sgn}}(f),
ι∗​ι−1|Ω|​ι∗​H=1|Ω|​[ℱT→Ω]∗​ℱT→Ω.\iota^{*}\iota-\frac{1}{|\Omega|}\iota^{*}H=\frac{1}{|\Omega|}[{\cal F}_{T\to\Omega}]^{*}{\cal F}_{T\to\Omega}.

3 Construction of the Dual Polynomial

The construction uses high moments of a random matrix to obtain invertibility and high moments of a truncated Neumann series to control the off-support certificate. The source keeps the numerical constants explicit, sacrificing sharpness for a quantitative failure bound.

3.1 Invertibility

A direct Frobenius-norm estimate only handles very small supports. Raising the self-adjoint matrix to a high power exposes cancellations from random frequency selection. Theorem 3.1 bounds the expected trace of an even power; Markov’s inequality then controls the operator norm and hence invertibility of the restricted Gram matrix. Theorem 3.3 supplies a technical estimate for τ≤0.44 and moment order at least4, and Corollary 3.4 converts it to a polynomially small failure probability. Printed inequalities and parameter restrictions are retained rather than simplified into a universal constant.

Equation
‖M‖F2:=Tr​(M​M∗)=∑i,j|M⁡(i,j)|2,\|M\|^{2}_{F}:={\hbox{\rm Tr}}(MM^{*})=\sum_{i,j}|M(i,j)|^{2},
Theorem 3.1

Put H0=ι∗​HH_{0}=\iota^{*}H for short, where HH is the operator defined by (2.10). Set cτ:=e​log⁡((1−τ)/τ)c_{\tau}:=e\log((1-\tau)/\tau) and let

Equation
an=(2​n−1)2​n​cτ−(2​n−1)​N​|T|2​n,bn=(2​n)!n!​ 2n​(τ1−τ)n​Nn​|T|n+1.a_{n}=(2n-1)^{2n}\,c_{\tau}^{-(2n-1)}\,N\,|T|^{2n},\quad b_{n}=\frac{(2n)!}{n!\,2^{n}}\,\left(\frac{\tau}{1-\tau}\right)^{n}\,N^{n}\,|T|^{n+1}.

Then

Equation 3.1
E​[Tr​(H02​n)]≤n​(1+52)2​n​max⁡(an,bn).{\hbox{\bf E}}[{\hbox{\rm Tr}}(H_{0}^{2n})]\leq n\,\left(\frac{1+\sqrt{5}}{2}\right)^{2n}\,\max(a_{n},b_{n}). (3.1)
Equations 3.2–3.3
(2​n)!n!​ 2n∼2n+1/2​e−n​nn≤2n+1​e−n​nn\frac{(2n)!}{n!\,2^{n}}\sim 2^{n+1/2}\,e^{-n}\,n^{n}\leq 2^{n+1}\,e^{-n}\,n^{n}
E​(Tr​(H02​n))≤2​e−n​γ2​n​nn+1⋅|τ​N|n​|T|n+1,γ2=2​ϕ21−τ,{\hbox{\bf E}}({\hbox{\rm Tr}}(H_{0}^{2n}))\leq 2\,e^{-n}\,\gamma^{2n}\,n^{n+1}\cdot|\tau N|^{n}\,|T|^{n+1},\quad\gamma^{2}=\frac{2\phi^{2}}{1-\tau}, (3.2)
an≤2n+1​e−n​nn​(τ1−τ)n​Nn​|T|n.a_{n}\leq 2^{n+1}\,e^{-n}\,n^{n}\,\left(\frac{\tau}{1-\tau}\right)^{n}\,N^{n}\,|T|^{n}. (3.3)
‖H0‖2​n=‖H0n‖2≤‖H0n‖F2=Tr​(H02​n)\|H_{0}\|^{2n}=\|H_{0}^{n}\|^{2}\leq\|H_{0}^{n}\|^{2}_{F}={\hbox{\rm Tr}}(H_{0}^{2n})
(E​‖H0‖)2​n≤E​‖H0‖2​n≤(2​n)​γ2​n​e−n​nn​|T|n+1​|τ​N|n.\left({\hbox{\bf E}}\|H_{0}\|\right)^{2n}\leq{\hbox{\bf E}}\|H_{0}\|^{2n}\leq(2n)\,\gamma^{2n}\,e^{-n}\,n^{n}\,|T|^{n+1}\,|\tau N|^{n}.
e−n​nn​|T|≤⌈log⁡|T|⌉ne^{-n}\,n^{n}\,|T|\leq\lceil\log|T|\rceil^{n}
E​‖H0‖≤γ⋅log⁡(|T|)⋅|T|​|τ​N|⋅(1+o⁡(1)), as ​|T|→∞.{\hbox{\bf E}}\|H_{0}\|\leq\gamma\cdot\sqrt{\log(|T|)}\cdot\sqrt{|T|\,|\tau N|}\cdot(1+o(1)),\quad\text{ as }|T|\rightarrow\infty.
Corollary 3.2

Suppose |T|≤(log⁡|τ​N|)−1​|τ​N||T|\leq(\log|\tau N|)^{-1}|\tau N|. Then for any ϵ>0\epsilon>0, we have

Equation
P​(‖H0‖>(1+ϵ)​γ​log⁡|T|​|T|​|τ​N|)→0 as ​|T|,|τ​N|→∞.{\hbox{\bf P}}\left(\|H_{0}\|>(1+\epsilon)\,\gamma\,\sqrt{\log|T|}\,\sqrt{|T|\,|\tau N|}\right)\,\rightarrow 0\quad\text{ as }|T|,|\tau N|\rightarrow\infty.
Equations 3.4–3.5
P​(‖H0n‖F≥αn⋅|τ​N|n)=E​‖H0n‖F2α2​n​|τ​N|2​n.\displaystyle{\hbox{\bf P}}(\|H_{0}^{n}\|_{F}\geq\alpha^{n}\cdot|\tau N|^{n})=\frac{{\hbox{\bf E}}\|H_{0}^{n}\|^{2}_{F}}{\alpha^{2n}\,|\tau N|^{2n}}.
P​(‖H0n‖F≥αn⋅|τ​N|n)≤(2​n)​e−n​(n​γ2α2)n​(|T||τ​N|)n​|T|.{\hbox{\bf P}}(\|H_{0}^{n}\|_{F}\geq\alpha^{n}\cdot|\tau N|^{n})\leq(2n)\,e^{-n}\,\left(\frac{n\,\gamma^{2}}{\alpha^{2}}\right)^{n}\,\left(\frac{|T|}{|\tau N|}\right)^{n}\ \,|T|. (3.4)
|T|≤αM2γ2​|τ​N|n<|T|+1,for some ​αM≤α.|T|\leq\frac{\alpha_{M}^{2}}{\gamma^{2}}\,\frac{|\tau N|}{n}<|T|+1,\quad\text{for some }\alpha_{M}\leq\alpha. (3.5)
P​(‖H0n‖F≥αn⋅|τ​N|n)≤2​(α2/γ2)​e−n​|τ​N|.{\hbox{\bf P}}(\|H_{0}^{n}\|_{F}\geq\alpha^{n}\cdot|\tau N|^{n})\leq 2(\alpha^{2}/\gamma^{2})\,e^{-n}\,|\tau N|.
Theorem 3.3

Assume that τ≤.44\tau\leq.44, say, and suppose that TT obeys (3.5). Then (3.3) holds for any n≥4n\geq 4, and therefore

Equation 3.6
P​(‖H0n‖F≥αn⋅|τ​N|n)≤2​(α/γ)2​e−n​|τ​N|.{\hbox{\bf P}}(\|H_{0}^{n}\|_{F}\geq\alpha^{n}\cdot|\tau N|^{n})\leq 2(\alpha/\gamma)^{2}\,e^{-n}\,|\tau N|. (3.6)
Equations
P​(‖H0‖≥α⋅|Ω|)≤P​(‖H0‖≥α⁡(1−ϵM)​|τ​N|)+P​(|Ω|<(1−ϵM)​|τ​N|),{\hbox{\bf P}}(\|H_{0}\|\geq\alpha\cdot|\Omega|)\leq{\hbox{\bf P}}(\|H_{0}\|\geq\alpha\,(1-\epsilon_{M})|\tau N|)+{\hbox{\bf P}}(|\Omega|<(1-\epsilon_{M})|\tau N|),
P​(‖H0‖≥α⁡(1−ϵM)⋅|τ​N|)≤2​(α/γ)2​e−n​|τ​N|.{\hbox{\bf P}}(\|H_{0}\|\geq\alpha\,(1-\epsilon_{M})\cdot|\tau N|)\leq 2(\alpha/\gamma)^{2}\,e^{-n}\,|\tau N|.
Corollary 3.4

Take n=(M+1)​log⁡Nn=(M+1)\log N. We see from the Neumann series that the operator ι∗​ι−1|Ω|​ι∗​H\iota^{*}\iota-\frac{1}{|\Omega|}\iota^{*}H is invertible with probability at least 1−(1+2/γ2)​N−M1-(1+2/\gamma^{2})N^{-M} since ι∗​ι\iota^{*}\iota is the identity on vectors supported on TT.

3.2 Magnitude of the polynomial on the complement of T

A finite geometric-series identity separates the inverse into a truncated Neumann sum and a small remainder. An operator-norm or high-power bound controls the remainder; a dimension-dependent conversion then bounds its infinity norm. This reduction leaves the truncated series as the principal obstacle. The displayed Frobenius-norm assumptions are part of the source’s chosen sufficient events, not a free consequence of matrix invertibility alone.

Equations 3.7–3.8
(1−M)−1=(1−Mn)−1​(1+M+…+Mn−1).(1-M)^{-1}=(1-M^{n})^{-1}(1+M+\ldots+M^{n-1}).
(ι∗​ι−1|Ω|n​(ι∗​H)n)−1=ι∗​ι+R(\iota^{*}\iota-\frac{1}{|\Omega|^{n}}(\iota^{*}H)^{n})^{-1}=\iota^{*}\iota+R
(ι∗​ι−1|Ω|​ι∗​H)−1=(ι∗​ι+R)​∑m=0n−11|Ω|m​(ι∗​H)m.(\iota^{*}\iota-\frac{1}{|\Omega|}\iota^{*}H)^{-1}=(\iota^{*}\iota+R)\sum_{m=0}^{n-1}\frac{1}{|\Omega|^{m}}(\iota^{*}H)^{m}. (3.7)
‖R‖F≤αn1−αn.\|R\|_{F}\leq\frac{\alpha^{n}}{1-\alpha^{n}}.
‖M‖∞=supi∑j|M⁡(i,j)|.\|M\|_{\infty}=\sup_{i}\sum_{j}|M(i,j)|.
‖M‖∞2≤supi#​M​(col)​∑j|M⁡(i,j)|2≤#​M​(col)⋅‖M‖F2,\|M\|^{2}_{\infty}\leq\sup_{i}\,\#M(\text{col})\,\sum_{j}|M(i,j)|^{2}\leq\#M(\text{col})\cdot\|M\|^{2}_{F},
‖R‖∞≤|T|1/2⋅αn1−αn.\|R\|_{\infty}\leq|T|^{1/2}\cdot\frac{\alpha^{n}}{1-\alpha^{n}}. (3.8)

3.3 Estimating the truncated Neumann series

The off-support polynomial splits into a main truncated term P0 and a remainder P1. Lemma 3.5 bounds moments of individual series terms using the same combinatorial machinery as the matrix moment theorem. Lemma 3.6 groups term orders and applies probability bounds so that the main contribution stays below 0.91; Lemma 3.7 controls the remainder by 0.09 under its additional parameter condition. Their combination gives strict certificate control with high probability. The numerical split is one proof choice, not an empirical phase transition.

Equations
P=1|Ω|​H​(ι∗​ι−1|Ω|​ι∗​H)−1​ι∗​sgn​(f),P=\frac{1}{|\Omega|}H(\iota^{*}\iota-\frac{1}{|\Omega|}\iota^{*}H)^{-1}\iota^{*}{\hbox{sgn}}(f),
P⁡(t)=P0​(t)+P1​(t),∀t∈Tc,P(t)=P_{0}(t)+P_{1}(t),\qquad\forall t\in T^{c},
P0=Sn​sgn​(f),P1=1|Ω|​H​R​ι∗​(I+Sn−1)​sgn​(f)P_{0}=S_{n}{\hbox{sgn}}(f),\quad P_{1}=\frac{1}{|\Omega|}HR\iota^{*}(I+S_{n-1}){\hbox{sgn}}(f)
Sn=∑m=1n|Ω|−m​(H​ι∗)m.S_{n}=\sum_{m=1}^{n}|\Omega|^{-m}(H\iota^{*})^{m}.
P​(supt∈Tc|P⁡(t)|>1)≤P​(‖P0‖∞>a0)+P​(‖P1‖∞>a1),{\hbox{\bf P}}\left(\sup_{t\in T^{c}}|P(t)|>1\right)\leq{\hbox{\bf P}}(\|P_{0}\|_{\infty}>a_{0})+{\hbox{\bf P}}(\|P_{1}\|_{\infty}>a_{1}),
‖P1‖∞≤1|Ω|​‖H​R‖∞​(1+‖ι∗​Q0‖∞).\|P_{1}\|_{\infty}\leq\frac{1}{|\Omega|}\|HR\|_{\infty}(1+\|\iota^{*}Q_{0}\|_{\infty}).
P0​(t)=∑m=1n|Ω|−m​Xm​(t),Xm=(H​ι∗)m​sgn​(f)P_{0}(t)=\sum_{m=1}^{n}|\Omega|^{-m}X_{m}(t),\qquad X_{m}=(H\iota^{*})^{m}\,{\hbox{sgn}}(f)
Lemma 3.5

Set n=k​mn=km. Then E​|Xm​(t0)|2​k{\hbox{\bf E}}|X_{m}(t_{0})|^{2k} obeys the same estimate as that in Theorem 3.1 (up to a multiplicative factor |T|−1|T|^{-1}), namely,

Equation 3.9
E​|Xm​(t0)|2​k≤1|T|⋅n​ϕ2​n​max⁡(an,bn).{\hbox{\bf E}}|X_{m}(t_{0})|^{2k}\leq\frac{1}{|T|}\cdot n\,\phi^{2n}\,\max(a_{n},b_{n}). (3.9)

In particular, following (3.2)

Equation 3.10
E​|Xm​(t0)|2​k≤2​e−n​γ2​n​nn+1⋅|T|n​|τ​N|n,{\hbox{\bf E}}|X_{m}(t_{0})|^{2k}\leq 2\,e^{-n}\,\gamma^{2n}\,n^{n+1}\cdot|T|^{n}|\tau N|^{n}, (3.10)

where γ\gamma is as before.

Lemma 3.6

Fix a0=.91a_{0}=.91. Suppose that |T||T| obeys (3.5) and let BMB_{M} be the set where |Ω|<(1−ϵM)⋅|τ​N||\Omega|<(1-\epsilon_{M})\cdot|\tau N| with ϵM\epsilon_{M} as in (2.9). For each t∈ℤNt\in\mathbb{Z}_{N}, there is a set AtA_{t} with the property

Equation
P​(At)>1−ϵn,ϵn=2​(1−ϵM)−2​n⋅n2​e−n​α2​n⋅(0.42)−2​n,{\hbox{\bf P}}(A_{t})>1-\epsilon_{n},\qquad\epsilon_{n}=2(1-\epsilon_{M})^{-2n}\cdot n^{2}\,e^{-n}\alpha^{2n}\cdot(0.42)^{-2n},

and

Equation
|P0​(t)|<.91,|Q0​(t)|<.91​ on ​At∩BMc.|P_{0}(t)|<.91,\quad|Q_{0}(t)|<.91\text{ on }A_{t}\cap B_{M}^{c}.

As a consequence,

Equation
P​(supt|P0​(t)|>a0)≤N−M+N​ϵn,{\hbox{\bf P}}(\sup_{t}|P_{0}(t)|>a_{0})\leq N^{-M}+N\epsilon_{n},

and similarly for Q0Q_{0}.

Equations 3.11–3.12
E​|Xm​(t)|2​k≤2​n​e−n​α2​n⋅|τ​N|2​n.{\hbox{\bf E}}|X_{m}(t)|^{2k}\leq 2n\,e^{-n}\alpha^{2n}\cdot|\tau N|^{2n}. (3.11)
|P0​(t)|≤∑m=1nYm,Ym=1(1−ϵM)m​|τ​N|m​|Xm​(t)|.|P_{0}(t)|\leq\sum_{m=1}^{n}Y_{m},\qquad Y_{m}=\frac{1}{(1-\epsilon_{M})^{m}\,|\tau N|^{m}}\,|X_{m}(t)|.
P​(∑m=1nYm>a0)≤∑j=0J−1∑m=2j2j+1−1P​(Ym>βj)≤∑j=0J−1∑m=2j2j+1−1βj−2​Kj​E​|Ym|2​Kj.{\hbox{\bf P}}(\sum_{m=1}^{n}Y_{m}>a_{0})\leq\sum_{j=0}^{J-1}\,\,\sum_{m=2^{j}}^{2^{j+1}-1}{\hbox{\bf P}}(Y_{m}>\beta_{j})\leq\sum_{j=0}^{J-1}\,\,\sum_{m=2^{j}}^{2^{j+1}-1}\beta_{j}^{-2K_{j}}\,{\hbox{\bf E}}|Y_{m}|^{2K_{j}}.
E​|Ym|2​Kj≤(1−ϵM)−2​n⋅(2​n​e−n​α2​n).{\hbox{\bf E}}|Y_{m}|^{2K_{j}}\leq(1-\epsilon_{M})^{-2n}\cdot(2n\,e^{-n}\alpha^{2n}).
P​(∑m=1nYm>a0)≤2​(1−ϵM)−2​n⋅n2​e−n​α2​n⋅β0−2​n,{\hbox{\bf P}}(\sum_{m=1}^{n}Y_{m}>a_{0})\leq 2(1-\epsilon_{M})^{-2n}\cdot n^{2}\,e^{-n}\alpha^{2n}\cdot\beta_{0}^{-2n},
P​(∑m=1nYm>.91)≤2​(1−ϵM)−2​n⋅n2​e−n​α2​n⋅(0.42)−2​n.{\hbox{\bf P}}(\sum_{m=1}^{n}Y_{m}>.91)\leq 2(1-\epsilon_{M})^{-2n}\cdot n^{2}\,e^{-n}\alpha^{2n}\cdot(0.42)^{-2n}. (3.12)
Lemma 3.7

Fix a1=.09a_{1}=.09. Suppose that the pair (α,N)(\alpha,N) obeys |τ​N|3/2​αn1−αn≤a1/2|\tau N|^{3/2}\frac{\alpha^{n}}{1-\alpha^{n}}\leq a_{1}/2. Then

Equation
‖P1‖∞≤a1\|P_{1}\|_{\infty}\leq a_{1}

on the event A∩{∥ι∗H∥F≤α|Ω|}A\cap\{\|\iota^{*}H\|_{F}\leq\alpha|\Omega|\}, for some AA obeying P​(A)≥1−O⁡(N−M){\hbox{\bf P}}(A)\geq 1-O(N^{-M}).

Equation
‖H‖∞⋅‖R‖∞≤|T|3/2⋅αn1−αn,\|H\|_{\infty}\cdot\|R\|_{\infty}\leq|T|^{3/2}\cdot\frac{\alpha^{n}}{1-\alpha^{n}},

3.4 Proof of Theorem 1.3

The proof chooses a moment order proportional to(M+1)logN and a numerical parameter 0.42, combines invertibility and certificate events, and derives a conservative support constant of order 1/[29.6(M+1)]. Intermediate failure estimates include logarithmic factors, and several printed narrative sentences write a small failure probability where the surrounding argument requires a large success probability. The reading claim is the stated high-probability recovery theorem with its full assumptions, not those isolated wording slips.

Equations 3.13
(1.5−.87​(M+1))​log⁡N≤−3.10.(1.5-.87(M+1))\log N\leq-3.10.
|T|≤α⁡(M)⋅|τ​N|log⁡N,α⁡(M)=.422γ2​(M+1)​(1+o⁡(1))|T|\leq\alpha(M)\cdot\frac{|\tau N|}{\log N},\qquad\alpha(M)=\frac{.42^{2}}{\gamma^{2}(M+1)}(1+o(1))
α⁡(M)=129.6​(M+1)​(1+o⁡(1)).\alpha(M)=\frac{1}{29.6(M+1)}(1+o(1)). (3.13)

4 Moments of Random Matrices

The technical core expands expected traces by grouping repeated sampled frequencies. Dependence caused by repeated indices prevents treating every factor as independent. Set partitions, inclusion–exclusion, Stirling numbers, and convex bounds organize the surviving terms.

4.1 A First Formula for the Expected Value of the Trace of ( H 0 ) 2 ​ n

Expand the trace into closed index walks and products of Fourier coefficients. A partition records which frequency indices coincide. Bernoulli sampling contributes a power ofτ equal to the number of distinct frequency classes. Keeping that collision pattern is essential: multiplying independent expectations for every occurrence would give the wrong moment. The two-index example illustrates why sums with distinctness exclusions are awkward.

Equations 4.1–4.2
H0​(t,t′)={0t=t′,c⁡(t−t′)t≠t′,c⁡(u)=∑ω∈Ωei​ω​u.H_{0}(t,t^{\prime})=\begin{cases}0&t=t^{\prime},\\ c(t-t^{\prime})&t\neq t^{\prime},\end{cases}\quad c(u)=\sum_{\omega\in\Omega}e^{i\omega u}. (4.1)
H02​n(t1,t1)=∑t2,…,t2​n:tj≠tj+1c(t1−t2)…c(t2​n−t1),H_{0}^{2n}(t_{1},t_{1})=\sum_{t_{2},\ldots,t_{2n}:\,t_{j}\neq t_{j+1}}\,c(t_{1}-t_{2})\ldots c(t_{2n}-t_{1}),
E(Tr(H02​n))=∑t1,…,t2​n:tj≠tj+1E[∑ω1,…,ω2​n∈Ωei​∑j=12​nωj​(tj−tj+1)].{\hbox{\bf E}}({\hbox{\rm Tr}}(H_{0}^{2n}))=\sum_{t_{1},\ldots,t_{2n}:\,t_{j}\neq t_{j+1}}\,\,\,{\hbox{\bf E}}\left[\sum_{\omega_{1},\ldots,\omega_{2n}\in\Omega}\,\,\,e^{i\sum_{j=1}^{2n}\omega_{j}(t_{j}-t_{j+1})}\right].
∑t1,…,t2​n:tj≠tj+1∑0≤ω1,…,ω2​n≤N−1ei​∑j=12​nωj​(tj−tj+1)E[∏j=12​nI{ωj∈Ω}].\sum_{t_{1},\ldots,t_{2n}:\,t_{j}\neq t_{j+1}}\,\,\,\sum_{0\leq\omega_{1},\ldots,\omega_{2n}\leq N-1}\,\,\,e^{i\sum_{j=1}^{2n}\omega_{j}(t_{j}-t_{j+1})}\,{\hbox{\bf E}}\left[\prod_{j=1}^{2n}I_{\{\omega_{j}\in\Omega\}}\right].
Ω(∼):={𝝎∈ℤN2​n:∼𝝎=∼}\Omega(\sim):=\{{\mbox{\boldmath{$\omega$}}}\in\mathbb{Z}_{N}^{2n}:\sim_{\mbox{\boldmath{$\omega$}}}=\sim\}
Ω≤(∼):=⋃∼′∈𝒫:∼′≤∼Ω(∼′)={𝝎∈ℤN2​n:∼𝝎≤∼}.\Omega_{\leq}(\sim):=\bigcup_{\sim^{\prime}\in{\cal P}:\sim^{\prime}\leq\sim}\Omega(\sim^{\prime})=\{{\mbox{\boldmath{$\omega$}}}\in\mathbb{Z}_{N}^{2n}:\sim_{\mbox{\boldmath{$\omega$}}}\leq\sim\}.
Ω≤​(∼):={𝝎∈ℤN2​n:ωa=ωb​ whenever ​a∼b}.\Omega_{\leq}(\sim):=\{{\mbox{\boldmath{$\omega$}}}\in\mathbb{Z}_{N}^{2n}:\omega_{a}=\omega_{b}\hbox{ whenever }a\sim b\}.
Ω(∼):={𝝎∈ℤN2​n:ωa=ωb whenever a∼b, and ωa≠ωb whenever a≁b}.\Omega(\sim):=\{{\mbox{\boldmath{$\omega$}}}\in\mathbb{Z}_{N}^{2n}:\omega_{a}=\omega_{b}\hbox{ whenever }a\sim b,\hbox{ and }\omega_{a}\neq\omega_{b}\hbox{ whenever }a\not\sim b\}.
E(∏j=12​nIωj)=τ|A/∼|,{\hbox{\bf E}}(\prod_{j=1}^{2n}I_{\omega_{j}})=\tau^{|A/\sim|},
E(Tr(H02​n))=∑t1,…,t2​n:tj≠tj+1∑∼∈𝒫(A)τ|A/∼|∑𝝎∈Ω⁡(∼)ei​∑j=12​nωj​(tj−tj+1){\hbox{\bf E}}({\hbox{\rm Tr}}(H_{0}^{2n}))=\sum_{t_{1},\ldots,t_{2n}:\,t_{j}\neq t_{j+1}}\,\,\,\sum_{\sim\in{\cal P}(A)}\,\,\tau^{|A/\sim|}\sum_{{\mbox{\boldmath{$\omega$}}}\in\Omega(\sim)}\,\,\,e^{i\sum_{j=1}^{2n}\omega_{j}(t_{j}-t_{j+1})} (4.2)
∑t1,t2:t1≠t2[τ∑(ω1,ω2)∈ℤN2:ω1=ω2ei​ω1​(t1−t1)+τ2∑(ω1,ω2)∈ℤN2:ω1≠ω2ei​ω1​(t1−t2)+i​ω2​(t2−t1)].\sum_{t_{1},t_{2}:\,t_{1}\neq t_{2}}\,\,\,\left[\tau\sum_{(\omega_{1},\omega_{2})\in\mathbb{Z}_{N}^{2}:\omega_{1}=\omega_{2}}e^{i\omega_{1}(t_{1}-t_{1})}+\tau^{2}\sum_{(\omega_{1},\omega_{2})\in\mathbb{Z}_{N}^{2}:\omega_{1}\neq\omega_{2}}e^{i\omega_{1}(t_{1}-t_{2})+i\omega_{2}(t_{2}-t_{1})}\right].
∑𝝎∈ℤN2:ω1≠ω2=∑𝝎∈ℤN2−∑𝝎∈ℤN2:ω1=ω2\sum_{{\mbox{\boldmath{$\omega$}}}\in\mathbb{Z}_{N}^{2}:\omega_{1}\neq\omega_{2}}=\sum_{{\mbox{\boldmath{$\omega$}}}\in\mathbb{Z}_{N}^{2}}-\sum_{{\mbox{\boldmath{$\omega$}}}\in\mathbb{Z}_{N}^{2}:\omega_{1}=\omega_{2}}
∑𝝎∈ℤN2=∑ω1ei​ω1​(t1−t2)⋅∑ω2ei​ω2​(t2−t1);\sum_{{\mbox{\boldmath{$\omega$}}}\in\mathbb{Z}_{N}^{2}}=\sum_{\omega_{1}}e^{i\omega_{1}(t_{1}-t_{2})}\cdot\sum_{\omega_{2}}e^{i\omega_{2}(t_{2}-t_{1})};

4.2 Inclusion-Exclusion formulae

Lemma 4.1 rewrites sums over exactly specified frequency-collision patterns as signed sums over coarser equality constraints. Its factorial coefficients account for ways classes can merge. The inductive proof adds the final index either as a singleton or into an existing class, weighting repeated descriptions correctly. Removing inequality exclusions lets the Fourier sums factor and subsequently vanish unless linear constraints on signal indices hold.

Lemma 4.1 (Inclusion-Exclusion principle for equivalence classes)

Let AA and GG be non-empty finite sets. For any equivalence class ∼∈𝒫(A)\sim\in{\cal P}(A) on 𝛚∈G|A|{\mbox{\boldmath{$\omega$}}}\in G^{|A|}, we have

Equation 4.3
∑𝝎∈Ω⁡(∼)f(𝝎)=∑∼1∈𝒫:∼1≤∼(−1)|A/∼|−|A/∼1|(∏A′∈A/∼1(|A′/∼|−1)!)∑𝝎∈Ω≤(∼1)f(𝝎).\sum_{{\mbox{\boldmath{$\omega$}}}\in\Omega(\sim)}f({\mbox{\boldmath{$\omega$}}})=\sum_{\sim_{1}\in{\cal P}:\sim_{1}\leq\sim}(-1)^{|A/\sim|-|A/\sim_{1}|}\left(\prod_{A^{\prime}\in A/\sim_{1}}(|A^{\prime}/\sim|-1)!\right)\sum_{{\mbox{\boldmath{$\omega$}}}\in\Omega_{\leq}(\sim_{1})}f({\mbox{\boldmath{$\omega$}}}). (4.3)
Equations 4.4–4.5
∑ω1,ω2,ω3∈G:ω1,ω2,ω3​ distinct=∑ω1,ω2,ω3∈G−∑ω1,ω2,ω3:ω1=ω2−∑ω1,ω2,ω3∈G:ω2=ω3−∑ω1,ω2,ω3∈G:ω3=ω1+2∑ω1,ω2,ω3∈G:ω1=ω2=ω3\sum_{\omega_{1},\omega_{2},\omega_{3}\in G:\omega_{1},\omega_{2},\omega_{3}\text{ distinct}}=\sum_{\omega_{1},\omega_{2},\omega_{3}\in G}\\ -\sum_{\omega_{1},\omega_{2},\omega_{3}:\omega_{1}=\omega_{2}}-\sum_{\omega_{1},\omega_{2},\omega_{3}\in G:\omega_{2}=\omega_{3}}-\sum_{\omega_{1},\omega_{2},\omega_{3}\in G:\omega_{3}=\omega_{1}}+2\sum_{\omega_{1},\omega_{2},\omega_{3}\in G:\omega_{1}=\omega_{2}=\omega_{3}}
∑𝝎∈Gn:ω1,…,ωn​ distinctf(𝝎)=∑∼∈𝒫({1,…,n})(−1)n−|{1,…,n}/∼|[∏A∈{1,…,n}/∼(|A|−1)!]∑𝝎∈Ω≤​(∼)f(𝝎).\sum_{{\mbox{\boldmath{$\omega$}}}\in G^{n}:\omega_{1},\ldots,\omega_{n}\hbox{ distinct}}f({\mbox{\boldmath{$\omega$}}})=\\ \sum_{\sim\in{\cal P}(\{1,\ldots,n\})}(-1)^{n-|\{1,\ldots,n\}/\sim|}\left[\prod_{A\in\{1,\ldots,n\}/\sim}(|A|-1)!\right]\sum_{{\mbox{\boldmath{$\omega$}}}\in\Omega_{\leq}(\sim)}f({\mbox{\boldmath{$\omega$}}}). (4.4)
∑𝝎′∈Gn−1:ω1,…,ωn−1​ distinct(∑ωn∈Gf(𝝎′,ωn)−∑j=1n−1f(𝝎′,ωj)),\sum_{{\mbox{\boldmath{$\omega$}}}^{\prime}\in G^{n-1}:\omega_{1},\ldots,\omega_{n-1}\hbox{ distinct}}\left(\sum_{\omega_{n}\in G}f({\mbox{\boldmath{$\omega$}}}^{\prime},\omega_{n})-\sum_{j=1}^{n-1}f({\mbox{\boldmath{$\omega$}}}^{\prime},\omega_{j})\right),
∑∼′∈𝒫({1,…,n−1})(−1)n−1−|{1,…,n−1}/∼′|∏A′∈{1,…,n−1}/∼(|A′|−1)!∑𝝎′∈Ω≤(∼′)(∑ωn∈Gf(𝝎′,ωn)−∑1≤j≤nf(𝝎′,ωj)).\sum_{\sim^{\prime}\in{\cal P}(\{1,\ldots,n-1\})}(-1)^{n-1-|\{1,\ldots,n-1\}/\sim^{\prime}|}\,\prod_{A^{\prime}\in\{1,\ldots,n-1\}/\sim}(|A^{\prime}|-1)!\\ \sum_{{\mbox{\boldmath{$\omega$}}}^{\prime}\in\Omega_{\leq}(\sim^{\prime})}\left(\sum_{\omega_{n}\in G}f({\mbox{\boldmath{$\omega$}}}^{\prime},\omega_{n})-\sum_{1\leq j\leq n}f({\mbox{\boldmath{$\omega$}}}^{\prime},\omega_{j})\right). (4.5)
∑∼∈𝒫({1,…,n})F(∼)=∑∼′∈𝒫({1,…,n−1})F({∼′,{n}})+∑∼′∈𝒫({1,…,n−1})∑j=1n−11|[j]∼′|F({∼′,{n}}/(j=n))\sum_{\sim\in{\cal P}(\{1,\ldots,n\})}F(\sim)=\sum_{\sim^{\prime}\in{\cal P}(\{1,\ldots,n-1\})}F(\{\sim^{\prime},\{n\}\})\\ +\sum_{\sim^{\prime}\in{\cal P}(\{1,\ldots,n-1\})}\sum_{j=1}^{n-1}\frac{1}{|[j]_{\sim^{\prime}}|}F(\{\sim^{\prime},\{n\}\}/(j=n))
∑∼′∈𝒫({1,…,n−1})(−1)n−(|{1,…,n−1}/∼′|+1)[∏A∈{1,…,n−1}/∼′(|A|−1)!]∑𝝎′∈Ω≤(∼′)f(𝝎′,ωn)\sum_{\sim^{\prime}\in{\cal P}(\{1,\ldots,n-1\})}(-1)^{n-(|\{1,\ldots,n-1\}/\sim^{\prime}|+1)}\left[\prod_{A\in\{1,\ldots,n-1\}/\sim^{\prime}}(|A|-1)!\right]\sum_{{\mbox{\boldmath{$\omega$}}}^{\prime}\in\Omega_{\leq}(\sim^{\prime})}f({\mbox{\boldmath{$\omega$}}}^{\prime},\omega_{n})
∑∼′∈𝒫({1,…,n−1})(−1)n−|{1,…,n−1}/∼′|∑j=1n−1T(j)∑𝝎′∈Ω≤(∼′)f(𝝎′,ωj),\sum_{\sim^{\prime}\in{\cal P}(\{1,\ldots,n-1\})}(-1)^{n-|\{1,\ldots,n-1\}/\sim^{\prime}|}\,\,\,\sum_{j=1}^{n-1}T(j)\sum_{{\mbox{\boldmath{$\omega$}}}^{\prime}\in\Omega_{\leq}(\sim^{\prime})}f({\mbox{\boldmath{$\omega$}}}^{\prime},\omega_{j}),
T(j):=1|[j]∼′|∏A∈{1,…,n}/({∼′,{n}}/(j=n))(|A|−1)!=∏A′∈{1,…,n−1}/∼′(|A′|−1)!T(j):=\frac{1}{|[j]_{\sim^{\prime}}|}\prod_{A\in\{1,\ldots,n\}/(\{\sim^{\prime},\{n\}\}/(j=n))}(|A|-1)!=\prod_{A^{\prime}\in\{1,\ldots,n-1\}/\sim^{\prime}}(|A^{\prime}|-1)!

4.3 Stirling Numbers

Stirling numbers count partitions with a specified number of classes. Their recurrence leads to a generating identity for the auxiliary functionsFn(τ), valid in the statedτ<1/2 range. Lemma 4.3 bounds the alternating series using the location of its largest term. These functions retain the repeated-frequency contribution after inclusion–exclusion; treating them as independent entries of a generic random matrix would miss the Fourier structure.

Equations 4.6
S(n,k):=#{∼∈𝒫(A):|A/∼|=k}.S(n,k):=\#\,\{\sim\in{\cal P}(A):|A/\sim|=k\}.
S⁡(n+1,k)=S⁡(n,k−1)+k​S​(n,k)​ for all ​k,n≥0.S(n+1,k)=S(n,k-1)+kS(n,k)\text{ for all }k,n\geq 0. (4.6)
Lemma 4.2

For any n≥1n\geq 1 and 0≤τ<1/20\leq\tau<1/2, we have the identity

Equation 4.7
∑k=1n(k−1)!​S​(n,k)​(−1)n−k​τk=∑k=1∞(−1)n−k​τk​kn−1(1−τ)k.\sum_{k=1}^{n}(k-1)!S(n,k)(-1)^{n-k}\tau^{k}=\sum_{k=1}^{\infty}(-1)^{n-k}\frac{\tau^{k}k^{n-1}}{(1-\tau)^{k}}. (4.7)

Note that the condition 0≤τ<1/20\leq\tau<1/2 ensures that the right-hand side is convergent.

Equations 4.8
∑k=1∞(−1)k+1τk(1−τ)k=−∑k=0∞(ττ−1)k+1=−11−ττ−1+1=τ\sum_{k=1}^{\infty}(-1)^{k+1}\frac{\tau^{k}}{(1-\tau)^{k}}=-\sum_{k=0}^{\infty}\left(\frac{\tau}{\tau-1}\right)^{k}+1=\frac{-1}{1-\frac{\tau}{\tau-1}}+1=\tau
∑k=1n+1(k−1)!​(S⁡(n,k−1)+k​S​(n,k))​(−1)n+1−k​τk=∑k=0∞(−1)n+1−k​τk​kn(1−τ)k,\sum_{k=1}^{n+1}(k-1)!(S(n,k-1)+kS(n,k))(-1)^{n+1-k}\tau^{k}=\sum_{k=0}^{\infty}(-1)^{n+1-k}\frac{\tau^{k}k^{n}}{(1-\tau)^{k}},
Fn​(τ)=∑k=1n(k−1)!​S​(n,k)​(−1)n−k​τk=∑k=1∞(−1)n+k​τk​kn−1(1−τ)k.F_{n}(\tau)=\sum_{k=1}^{n}(k-1)!S(n,k)(-1)^{n-k}\tau^{k}=\sum_{k=1}^{\infty}(-1)^{n+k}\frac{\tau^{k}k^{n-1}}{(1-\tau)^{k}}. (4.8)
F1​(τ)=τ,F2​(τ)=−τ+τ2,F3​(τ)=τ−3​τ2+2​τ3,F_{1}(\tau)=\tau,\quad F_{2}(\tau)=-\tau+\tau^{2},\quad F_{3}(\tau)=\tau-3\tau^{2}+2\tau^{3},
Lemma 4.3

Let n≥1n\geq 1 and 0≤τ<1/20\leq\tau<1/2. If τ1−τ≤e1−n\frac{\tau}{1-\tau}\leq e^{1-n}, then we have |Fn​(τ)|≤τ1−τ|F_{n}(\tau)|\leq\frac{\tau}{1-\tau}. If instead τ1−τ>e1−n\frac{\tau}{1-\tau}>e^{1-n}, then

Equation
|Fn​(τ)|≤exp⁡((n−1)​(log⁡(n−1)−log⁡log⁡1−ττ−1)).|F_{n}(\tau)|\leq\exp((n-1)(\log(n-1)-\log\log\frac{1-\tau}{\tau}-1)).
Equation
g⁡(x∗)=exp⁡((n−1)​(log⁡(n−1)−log⁡log⁡1−ττ−1))g(x_{*})=\exp((n-1)(\log(n-1)-\log\log\frac{1-\tau}{\tau}-1))

4.4 A Second Formula for the Expected Value of the Trace of H 0 2 ​ n

The weighted partition identity factors each contribution into one auxiliary function per class. Summing frequencies then enforces a linear constraint for each class: a Fourier sum is eitherN or zero. Singleton classes contribute nothing because adjacent signal indices are required to differ. Lemma 4.5 is the resulting exact combinatorial trace formula and serves as the basis of the later estimates.

Equation
∑∼∈𝒫(A)τ|A/∼|∑𝝎∈Ω⁡(∼)f(𝝎)\sum_{\sim\in{\cal P}(A)}\tau^{|A/\sim|}\sum_{{\mbox{\boldmath{$\omega$}}}\in\Omega(\sim)}f({\mbox{\boldmath{$\omega$}}})
Lemma 4.4
Equation 4.9
∑∼∈𝒫(A)τ|A/∼|∑𝝎∈Ω⁡(∼)f(𝝎)=∑∼1∈𝒫(A)[∑𝝎∈Ω≤(∼1)f(𝝎)]∏A′∈A/∼1F|A′|(τ).\sum_{\sim\in{\cal P}(A)}\tau^{|A/\sim|}\sum_{{\mbox{\boldmath{$\omega$}}}\in\Omega(\sim)}f({\mbox{\boldmath{$\omega$}}})=\sum_{\sim_{1}\in{\cal P}(A)}\left[\sum_{{\mbox{\boldmath{$\omega$}}}\in\Omega_{\leq}(\sim_{1})}f({\mbox{\boldmath{$\omega$}}})\right]\prod_{A^{\prime}\in A/\sim_{1}}F_{|A^{\prime}|}(\tau). (4.9)
Equations 4.10
∑∼1∈𝒫(A)T(∼1)∑𝝎∈Ω≤(∼1)f(𝝎),\sum_{\sim_{1}\in{\cal P}(A)}T(\sim_{1})\,\sum_{{\mbox{\boldmath{$\omega$}}}\in\Omega_{\leq}(\sim_{1})}f({\mbox{\boldmath{$\omega$}}}),
T(∼1)=∑∼∈𝒫(A):∼≥∼1τ|A/∼|(−1)|A/∼|−|A/∼1|∏A′∈A/∼1(|A′/∼|−1)!.T(\sim_{1})=\sum_{\sim\in{\cal P}(A):\sim\geq\sim_{1}}\tau^{|A/\sim|}(-1)^{|A/\sim|-|A/\sim_{1}|}\prod_{A^{\prime}\in A/\sim_{1}}(|A^{\prime}/\sim|-1)!.
T(∼1)=∏A′∈A/∼1∑∼′∈𝒫(A′)τ|A′/∼′|(−1)|A′/∼′|−|A′|(|A′/∼′|−1)!;T(\sim_{1})=\prod_{A^{\prime}\in A/\sim_{1}}\sum_{\sim^{\prime}\in{\cal P}(A^{\prime})}\tau^{|A^{\prime}/\sim^{\prime}|}(-1)^{|A^{\prime}/\sim^{\prime}|-|A^{\prime}|}(|A^{\prime}/\sim^{\prime}|-1)!;
∏A′∈A/∼1∑k=1|A′|S(|A′|,k)τk(−1)|A′|−k(k−1)!=∏A′∈A/∼1F|A′|(τ)\prod_{A^{\prime}\in A/\sim_{1}}\sum_{k=1}^{|A^{\prime}|}S(|A^{\prime}|,k)\tau^{k}(-1)^{|A^{\prime}|-k}(k-1)!=\prod_{A^{\prime}\in A/\sim_{1}}F_{|A^{\prime}|}(\tau)
E[Tr(H02​n)]=∑∼∈𝒫(A)∑t1,…,t2​n∈T:tj≠tj+1∑𝝎∈Ω≤​(∼)ei​∑j=12​nωj​(tj−tj+1)∏A′∈A/∼F|A′|(τ).{\hbox{\bf E}}[{\hbox{\rm Tr}}(H_{0}^{2n})]=\sum_{\sim\in{\cal P}(A)}\,\,\sum_{t_{1},\ldots,t_{2n}\in T:\,t_{j}\neq t_{j+1}}\,\,\sum_{{\mbox{\boldmath{$\omega$}}}\in\Omega_{\leq}(\sim)}e^{i\sum_{j=1}^{2n}\omega_{j}(t_{j}-t_{j+1})}\,\prod_{A^{\prime}\in A/\sim}F_{|A^{\prime}|}(\tau). (4.10)
I⁡(∼)=∑𝝎∈Ω≤​(∼)ei​∑1≤j≤2​nωj​(tj−tj+1).I(\sim)=\sum_{{\mbox{\boldmath{$\omega$}}}\in\Omega_{\leq}(\sim)}e^{i\sum_{1\leq j\leq 2n}\omega_{j}(t_{j}-t_{j+1})}.
I(∼)=∑(ωA′)A′∈A/∼∈ℤN|A/∼|e∑A′∈A/∼iωA′tA′=∏A′∈A/∼∑ωA′∈ℤNei​ωA′​tA′.I(\sim)=\sum_{(\omega_{A^{\prime}})_{A^{\prime}\in A/\sim}\in\mathbb{Z}_{N}^{|A/\sim|}}e^{\sum_{A^{\prime}\in A/\sim}i\omega_{A^{\prime}}t_{A^{\prime}}}=\prod_{A^{\prime}\in A/\sim}\,\,\,\sum_{\omega_{A^{\prime}}\in\mathbb{Z}_{N}}e^{i\omega_{A^{\prime}}t_{A^{\prime}}}.
Lemma 4.5

For every equivalence class A′∈A/∼A^{\prime}\in A/\sim, let tA′:=∑a∈A′(ta−ta+1)t_{A^{\prime}}:=\sum_{a\in A^{\prime}}(t_{a}-t_{a+1}). Then

Equation 4.11
E[Tr(H02​n)]=∑∼∈𝒫(A)∑t∈T2​n:tj≠tj+1​ and ​tA′=0​ for all ​A′N|A/∼|∏A′∈A/∼F|A′|(τ).{\hbox{\bf E}}[{\hbox{\rm Tr}}(H_{0}^{2n})]=\sum_{\sim\in{\cal P}(A)}\,\,\sum_{t\in T^{2n}:\,t_{j}\neq t_{j+1}\text{ and }t_{A^{\prime}}=0\text{ for all }A^{\prime}}N^{|A/\sim|}\prod_{A^{\prime}\in A/\sim}F_{|A^{\prime}|}(\tau). (4.11)

4.5 A First Bound on E ​ [ Tr ​ ( H 0 2 ​ n ) ]

The proof bounds how many signal-index tuples satisfy the partition constraints and counts partitions without singleton classes. Lemma 4.6 supplies a factorial-type upper bound involving the golden ratio. The manuscript’s printed recurrence Eq 4.12 omits the factork multiplyingP(n−1,k) for partitions into k nonsingleton blocks; for example P(5,2)=10 while the printed right side gives7. The original equation is preserved, and the prose should be read as the intended counting strategy rather than a line-by-line verification of that printed recurrence.

Equations 4.12–4.13
#{t∈T2​n:tA′=0 for all A′∈A/∼}≤|T|2n−|A/∼|+1.\#\,\,\{t\in T^{2n}:\,t_{A^{\prime}}=0\text{ for all }A^{\prime}\in{A/\sim}\}\leq|T|^{2n-|A/\sim|+1}.
P(n,k):=#{∼∈𝒫(A):|A/∼|=k and |A′|≥2,∀A′∈A/∼}.P(n,k):=\#\,\{\sim\in{\cal P}(A):\,|A/\sim|=k\text{ and }|A^{\prime}|\geq 2,\,\forall A^{\prime}\in A/\sim\}.
P⁡(n,k)=P⁡(n−1,k)+(n−1)​P​(n−2,k−1),P(n,k)=P(n-1,k)+(n-1)P(n-2,k-1), (4.12)
ETr(H02​n)≤∑k=1nNk|T|2​n−k+1P(2n,k)sup∼:|A/∼|=k∏A′∈A/∼F|A′|(τ).{\hbox{\bf E}}{\hbox{\rm Tr}}(H^{2n}_{0})\leq\sum_{k=1}^{n}N^{k}\,|T|^{2n-k+1}\,P(2n,k)\,\sup_{\sim:|A/\sim|=k}\,\,\prod_{A^{\prime}\in A/\sim}F_{|A^{\prime}|}(\tau). (4.13)
Lemma 4.6

The numbers P⁡(n,k)P(n,k) obey

Equation 4.14
P⁡(n,k)≤λn​(n−1)​…​(n−2​k+1),∀λ≥ϕ:=1+52.P(n,k)\leq\lambda^{n}\,(n-1)\ldots(n-2k+1),\quad\forall\lambda\geq\phi:=\frac{1+\sqrt{5}}{2}. (4.14)
Equation
P⁡(n+1,k)\displaystyle P(n+1,k) =\displaystyle= P⁡(n−1,k)+(n−1)​P​(n−2,k−1)\displaystyle P(n-1,k)+(n-1)P(n-2,k-1)
≤\displaystyle\leq λn−1​(n−2)​…​(n−2​k+2)+λn−2​(n−1)​…​(n−2​k+1)\displaystyle\lambda^{n-1}\,(n-2)\ldots(n-2k+2)+\lambda^{n-2}\,(n-1)\ldots(n-2k+1)
≤\displaystyle\leq (λn−1+λn−2)​(n−1)​…​(n−2​k+1).\displaystyle(\lambda^{n-1}+\lambda^{n-2})\,(n-1)\ldots(n-2k+1).

4.6 Convex analysis

A convex function attains the displayed simplex maximum at a vertex; the log-convex version bounds products. Applying that principle to the class-size factors reduces their worst configuration to extreme class sizes. A further discrete-convexity argument reduces the remaining partition-count sum to its endpoint terms. The source leaves one elementary inequality verification to the reader; the original formulas preserve its exact parameter and index conventions.

Lemma 4.7

Let ff be a convex function on [0,1][0,1], say. Consider the problem

Equation 4.15
f∗=max∑j=1kf(xj),subject to xj≥0 and ∑j=1kxj=1.f^{*}=\max\sum_{j=1}^{k}f(x_{j}),\quad\text{subject to }x_{j}\geq 0\text{ and }\sum_{j=1}^{k}x_{j}=1. (4.15)

Then the maximum value f∗f^{*} is obtained by allocating one xjx_{j} to 1 and all the others to 0, i.e. f∗=(k−1)​f​(0)+f⁡(1)f^{*}=(k-1)f(0)+f(1).

Equations
f⁡(xj)≤(1−xj)​f​(0)+xj​f​(1).f(x_{j})\leq(1-x_{j})f(0)+x_{j}f(1).
∑j=1kf⁡(xj)≤(k−1)​f​(0)+f⁡(1),\sum_{j=1}^{k}f(x_{j})\leq(k-1)f(0)+f(1),
Corollary 4.8

Suppose that f=log⁡Ff=\log F is a convex function on [0,1][0,1], say, and consider

Equation 4.16
F∗=max∏j=1kF(xj),subject to xj≥0 and ∑j=1kxj=1.F^{*}=\max\prod_{j=1}^{k}F(x_{j}),\quad\text{subject to }x_{j}\geq 0\text{ and }\sum_{j=1}^{k}x_{j}=1. (4.16)

Then the maximum value F∗F^{*} is obtained by allocating one xjx_{j} to 1 and all the others to 0, i.e. F∗=(F⁡(0))k−1​F​(1)F^{*}=(F(0))^{k-1}F(1).

Equations 4.17–4.20
f(j+1)−f(j)≥f(j)−f(j−1),j=0,1,2,….f(j+1)-f(j)\geq f(j)-f(j-1),\quad j=0,1,2,\ldots. (4.17)
Fn​(τ)≤Gτ/(1−τ)​(n)F_{n}(\tau)\leq G_{\tau/(1-\tau)}(n)
Gu​(n)={u,log⁡u≤1−n,exp⁡((n−1)​(log⁡(n−1)−log⁡log⁡(1/u)−1)),log⁡u>1−n..G_{u}(n)=\begin{cases}u,&\text{$\log u\leq 1-n$},\\ \exp((n-1)(\log(n-1)-\log\log(1/u)-1)),&\text{$\log u>1-n$}.\end{cases}. (4.18)
Gu∗=max∏j=1kGu(nj),subject to nj≥2 and ∑j=1knj=2nG_{u}^{*}=\max\prod_{j=1}^{k}G_{u}(n_{j}),\quad\text{subject to }n_{j}\geq 2\text{ and }\sum_{j=1}^{k}n_{j}=2n
Gu∗=(Gu​(2))k−1​Gu​(2​n−2​k+2).G_{u}^{*}=(G_{u}(2))^{k-1}G_{u}(2n-2k+2).
∏A′∈A/∼F|A′|(τ)≤∏A′∈A/∼G(|A′|)≤[G(2)]k−1G(2n−2k+2),\prod_{A^{\prime}\in A/\sim}F_{|A^{\prime}|}(\tau)\leq\prod_{A^{\prime}\in A/\sim}G(|A^{\prime}|)\leq[G(2)]^{k-1}\,G(2n-2k+2),
ETr​(H02​n)≤∑k=1nNk​|T|2​n−k+1​P​(2​n,k)​[G⁡(2)]k−1​G​(2​n−2​k+2).{\hbox{\bf E}}{\hbox{\rm Tr}}(H^{2n}_{0})\leq\sum_{k=1}^{n}N^{k}\,|T|^{2n-k+1}\,P(2n,k)\,[G(2)]^{k-1}\,G(2n-2k+2).
ETr​(H02​n)≤|T|​λ2​n​∑k=1nf⁡(k),{\hbox{\bf E}}{\hbox{\rm Tr}}(H^{2n}_{0})\leq|T|\,\lambda^{2n}\,\sum_{k=1}^{n}f(k), (4.19)
f⁡(k):=Nk​|T|2​n−k​[(2​n−1)​…​(2​n−2​k+1)]​[G⁡(2)]k−1​G​(2​n−2​k+2)f(k):=N^{k}\,|T|^{2n-k}\,[(2n-1)\ldots(2n-2k+1)]\,[G(2)]^{k-1}\,G(2n-2k+2) (4.20)
Lemma 4.9

For each k≤n−1k\leq n-1, ff obeys

Equation
f⁡(k+1)−f⁡(k)≥f⁡(k)−f⁡(k−1).f(k+1)-f(k)\geq f(k)-f(k-1).
Equations
f⁡(k)≤max⁡(f⁡(1),f⁡(n)),∀1≤k≤n.f(k)\leq\max(f(1),f(n)),\quad\forall 1\leq k\leq n.
f⁡(k+1)f⁡(k)+f⁡(k−1)f⁡(k)≥2.\frac{f(k+1)}{f(k)}+\frac{f(k-1)}{f(k)}\geq 2.
f⁡(k+1)f⁡(k)=α​ρk+1,f⁡(k)f⁡(k−1)=α−1​ρk−1,\frac{f(k+1)}{f(k)}=\alpha\rho_{k+1},\quad\frac{f(k)}{f(k-1)}=\alpha^{-1}\rho_{k-1},
ρk+1=(2​n−2​k−1)⋅G⁡(2​n−2​k)G⁡(2​n−2​k+2),ρk−1=1(2​n−2​k+1)⋅G⁡(2​n−2​k+4)G⁡(2​n−2​k+2).\rho_{k+1}=(2n-2k-1)\cdot\frac{G(2n-2k)}{G(2n-2k+2)},\quad\rho_{k-1}=\frac{1}{(2n-2k+1)}\cdot\frac{G(2n-2k+4)}{G(2n-2k+2)}.
α​ρk+1+α−1​ρk−1≥2​ρk+1​ρk−1\alpha\rho_{k+1}+\alpha^{-1}\rho_{k-1}\geq 2\,\sqrt{\rho_{k+1}\,\rho_{k-1}}
ρk+1​ρk−1\displaystyle\rho_{k+1}\,\rho_{k-1} =\displaystyle= m−1m+1⋅G⁡(m)​G​(m+4)[G⁡(m+2)]2\displaystyle\frac{m-1}{m+1}\cdot\frac{G(m)\,G(m+4)}{[G(m+2)]^{2}}
=\displaystyle= m−1m+1⋅(m−1)m−1​(m+3)m+3(m+1)2​(m+1).\displaystyle\frac{m-1}{m+1}\cdot\frac{(m-1)^{m-1}\,(m+3)^{m+3}}{(m+1)^{2(m+1)}}.
m​log⁡(m−1)+(m+3)​log⁡(m+3)−(2​m+3)​log⁡(m+1)≥0.m\log(m-1)+(m+3)\log(m+3)-(2m+3)\log(m+1)\geq 0.

4.7 Proof of Theorem 3.1

The endpoint estimates yield the two termsan andbn in Theorem 3.1. Combining them with the partition count completes the stated moment bound. This closes the random-matrix component used earlier for invertibility and certificate construction, subject to the source’s printed technical formulas and the qualifications noted alongside them.

Equations
ETr​(H02​n)≤|T|​ϕ2​n⋅n⋅max⁡(f⁡(1),f⁡(n)){\hbox{\bf E}}{\hbox{\rm Tr}}(H^{2n}_{0})\leq|T|\,\phi^{2n}\cdot n\cdot\max(f(1),f(n))
f⁡(1)=(2​n−1)​G​(2​n)​N​|T|2​n−1=(2​n−1)2​n​cτ−(2​n−1)​N​|T|2​n−1.f(1)=(2n-1)\,G(2n)\,N\,|T|^{2n-1}=(2n-1)^{2n}\,c_{\tau}^{-(2n-1)}\,N\,|T|^{2n-1}.
f⁡(n)=[(2​n−1)×(2​n−3)​…×1]⋅(τ1−τ)n​Nn​|T|n.f(n)=[(2n-1)\times(2n-3)\ldots\times 1]\cdot\left(\frac{\tau}{1-\tau}\right)^{n}\,N^{n}\,|T|^{n}.

5 Numerical Experiments

The experiment chooses a support and Fourier sample set uniformly without replacement, assigns random complex Gaussian amplitudes on the support, and solves the convex program. For N=512, each support/sample-size pair is tested 100 times. Figure 2 shows the empirical recovery map and its|Ω|=64cross-section; Figure 3 tests the specific certificate and has a different horizontal scale. The chosen certificate succeeds over a narrower region than the optimization itself, illustrating slack in that sufficient proof construction. Figure 4 retains both additional phantoms and all minimum-energy and TV reconstructions. Reported iteration counts and runtimes describe the authors’ implementation and historical hardware, not a current performance benchmark.

Complete original Figure2, including every scientific panel and label, from the exact-version PDF.
Figure 2: Recovery experiment for N=512N=512. (a) The image intensity represents the percentage of the time solving (P1)(P_{1}) recovered the signal ff exactly as a function of |Ω||\Omega| (vertical axis) and |T|/|Ω||T|/|\Omega| (horizontal axis); in white regions, the signal is recovered approximately 100%100\% of the time, in black regions, the signal is never recovered. For each |T|,|Ω||T|,|\Omega| pair, 100100 experiments were run. (b) Cross-section of the image in (a) at |Ω|=64|\Omega|=64. We can see that we have perfect recovery with very high probability for |T|≤16|T|\leq 16.
Complete original Figure3, including every scientific panel and label, from the exact-version PDF.
Figure 3: Sufficient condition test for N=512N=512. (a) The image intensity represents the percentage of the time P⁡(t)P(t) chosen as in (2.11) meets the condition |P⁡(t)|<1,t∈Tc|P(t)|<1,t\in T^{c}. (b) A cross-section of the image in (a) at |Ω|=64|\Omega|=64. Note that the axes are scaled differently than in Figure 2.
Complete original Figure4, including every scientific panel and label, from the exact-version PDF.
Figure 4: Two more phantom examples for the recovery problem discussed in Section 1.1. On the left is the original phantom ((d) was created by drawing ten ellipses at random), in the center is the minimum energy reconstruction, and on the right is the minimum total-variation reconstruction. The minimum total-variation reconstructions are exact.

6 Discussion

The discussion separates conditioning with a known support, reconstruction with noisy observations, and other synthesis/measurement pairs. Only the first is directly connected to a developed estimate in this manuscript; the others are described as preliminary or future work.

6.1 Stability

The same restricted Gram-matrix bound controls the condition of least-squares recovery when the support is known. A norm sufficiently below the diagonal scale keeps the inverse away from singularity. This supports local conditioning of that oracle problem under the stated sparsity and random-sampling regime. It is distinct from proving an error bound for the complete unknown-support convex recovery algorithm under arbitrary noise.

Equations
f=(ℱT→Ω∗​ℱT→Ω)−1​ℱT→Ω∗​f^|Ω.f=({\cal F}_{T\rightarrow\Omega}^{*}{\cal F}_{T\rightarrow\Omega})^{-1}\,{\cal F}_{T\rightarrow\Omega}^{*}\,\hat{f}|_{\Omega}.
ℱT→Ω∗​ℱT→Ω∝IT−1|Ω|​H0.{\cal F}_{T\rightarrow\Omega}^{*}{\cal F}_{T\rightarrow\Omega}\propto I_{T}-\frac{1}{|\Omega|}H_{0}.

6.2 Robustness

With perturbed Fourier observations, exact recovery is no longer expected. The authors describe preliminary calculations suggesting small ℓ1 error for a small ℓ1 perturbation and explicitly defer detailed robustness results. The title’s terminology and this discussion therefore do not license a general noise-stability theorem beyond what the manuscript actually establishes.

Equation
f♯=argmin ​‖g‖ℓ1,g^​(ω)=f^​(ω)+h^​(ω),∀ω∈Ω.f^{\sharp}=\text{argmin }\|g\|_{\ell_{1}},\qquad\hat{g}(\omega)=\hat{f}(\omega)+\hat{h}(\omega),\quad\forall\omega\in\Omega.

6.3 Extensions

The proposed extension replaces the canonical/Fourier pair by other synthesis and measurement bases. Their incoherence would govern how many coefficients are required. The source reports this as work in progress and does not prove a uniform theorem for every pair of bases. Sparsity in one basis must be paired with a compatible measurement system.

7 Appendix

The appendix supplies the technical constant estimate for Theorem 3.3 and the scalar high-moment estimate used for the truncated certificate series. Both complete components invoked in the main proof; they are included here with all their original equations.

7.1 Proof of Theorem 3.3

The proof reduces the technical comparison betweenan andbn to a scalar logarithmic inequality under τ≤0.44 and n≥4. Figure 5 plots its two sides for n=4 and 5. The source invokes simple numerical calculations for the stated constant range; the plot is an illustration, not independent proof for every parameter. Its original formulas and both plots are retained.

Equations 7.1
(2​n−1)2​n​(cτ)−(2​n−1)​N​|T|2​n−1≤nn​ 2n+1​e−n​(τ1−τ)n​Nn​|T|n;(2n-1)^{2n}\,(c_{\tau})^{-(2n-1)}\,N\,|T|^{2n-1}\leq n^{n}\,2^{n+1}\,e^{-n}\,\left(\frac{\tau}{1-\tau}\right)^{n}\,N^{n}\,|T|^{n};
ϵn​(2​e)n−1​nn​(cτ)−2​(n−1)​(1−τ)n−1​|T|n−1≤|Ω|n−1​sτ\epsilon_{n}\,(2e)^{n-1}\,n^{n}(c_{\tau})^{-2(n-1)}\,(1-\tau)^{n-1}|T|^{n-1}\leq|\Omega|^{n-1}\,s_{\tau}
ϵn​n​rτn−1≤sτ,rτ=2​α2​e​(1−τ)γ2​cτ2.\epsilon_{n}\,n\,r_{\tau}^{n-1}\leq s_{\tau},\quad r_{\tau}=\frac{2\alpha^{2}e(1-\tau)}{\gamma^{2}\,c_{\tau}^{2}}.
(n−1)​log⁡rτ+log⁡n+12​n≤log⁡sτ.(n-1)\log r_{\tau}+\log n+\frac{1}{2n}\leq\log s_{\tau}. (7.1)
Complete original Figure5, including every scientific panel and label, from the exact-version PDF.
Figure 5: Behavior of the left and right-hand side of (7.1) for two values of nn

7.2 Proof of Lemma 3.5

Expand a high even moment of a series term into multiple index paths, including the unit-modulus signal phases. Group repeated frequencies and apply the same partition identity as in Section 4. Because the starting point is fixed, the count has one fewer free signal index than the trace calculation, producing the additional support-size factor in Lemma 3.5. The final estimate parallels the matrix-moment argument while preserving that distinction.

Equations 7.2–7.4
[(Hι∗)n+1ei​ϕ](t0)=∑t1,…,tn+1∈T:tj≠tj+1​ for ​j=0,…,n∑ω0,…,ωn∈Ωei​∑j=0nωj​(tj−tj+1)ei​ϕ​(tn+1),[(H\iota^{*})^{n+1}e^{i\phi}](t_{0})=\sum_{t_{1},\ldots,t_{n+1}\in T:\,t_{j}\neq t_{j+1}\text{ for }j=0,\ldots,n}\,\,\,\sum_{\omega_{0},\ldots,\omega_{n}\in\Omega}\,\,\,e^{i\sum_{j=0}^{n}\omega_{j}(t_{j}-t_{j+1})}\,\,e^{i\phi(t_{n+1})},
|[(Hι∗)n+1ei​ϕ](t0)|2=∑t1,…,tn+1∈T:tj≠tj+1​ for ​j=0,…,nt1′,…,t2​n′∈T:tj′≠tj+1′​ for ​j=0,…,nei​ϕ​(tn+1)e−i​ϕ​(tn+1′)∑ω0,…,ωn∈Ωω0′,…,ωn′∈Ωei​∑j=0nωj​(tj−tj+1)e−i∑j=0nω′j(t′j−t′j+1).|[(H\iota^{*})^{n+1}e^{i\phi}](t_{0})|^{2}=\sum_{t_{1},\ldots,t_{n+1}\in T:\,t_{j}\neq t_{j+1}\text{ for }j=0,\ldots,n\atop t^{\prime}_{1},\ldots,t^{\prime}_{2n}\in T:\,t^{\prime}_{j}\neq t^{\prime}_{j+1}\text{ for }j=0,\ldots,n}\,\,e^{i\phi(t_{n+1})}\,e^{-i\phi(t^{\prime}_{n+1})}\\ \sum_{\omega_{0},\ldots,\omega_{n}\in\Omega\atop\omega^{\prime}_{0},\ldots,\omega^{\prime}_{n}\in\Omega}\,\,e^{i\sum_{j=0}^{n}\omega_{j}(t_{j}-t_{j+1})}\,e^{-i\sum_{j=0}^{n}\omega^{\prime}_{j}(t^{\prime}_{j}-t^{\prime}_{j+1})}.
𝝎:=(ωj(k))k,j,𝐭=(tj(k))k,j∈T2​K​(n+1),1≤j≤n+1​ and ​1≤k≤2​K{\mbox{\boldmath{$\omega$}}}:=(\omega^{(k)}_{j})_{k,j},\quad\mathbf{t}=(t^{(k)}_{j})_{k,j}\in T^{2K(n+1)},\quad 1\leq j\leq n+1\text{ and }1\leq k\leq 2K
|[(Hι∗)n+1g](t0)|2​K=∑𝐭∈T2​m:tj(k)≠tj+1(k)∑𝝎∈Ω2​mei​∑k=12​K(−1)k​ϕ​(tn+1(k))ei​∑k=12​K∑j=0n(−1)k​ωj(k)​(tj(k)−tj+1(k)),|[(H\iota^{*})^{n+1}g](t_{0})|^{2K}=\sum_{\mathbf{t}\in T^{2m}:t^{(k)}_{j}\neq t^{(k)}_{j+1}}\sum_{{\mbox{\boldmath{$\omega$}}}\in\Omega^{2m}}\,\,e^{i\sum_{k=1}^{2K}(-1)^{k}\phi(t^{(k)}_{n+1})}\,\,e^{i\sum_{k=1}^{2K}\sum_{j=0}^{n}(-1)^{k}\omega^{(k)}_{j}(t^{(k)}_{j}-t^{(k)}_{j+1})},
E[∏j,kIωj(k)]=τ|A/∼|;{\hbox{\bf E}}\left[\prod_{j,k}I_{\omega_{j}^{(k)}}\right]=\tau^{|A/\sim|};
m(n;K)=∑𝐭∈T2​m:tj(k)≠tj+1(k)ei​∑k=12​K(−1)k​ϕ​(tn+1(k))∑∼∈𝒫(A)τ|A/∼|∑𝝎∈Ω(∼)ei​∑k=12​K∑j=0n(−1)k​ωj(k)​(tj(k)−tj+1(k))m(n;K)=\sum_{\mathbf{t}\in T^{2m}:t^{(k)}_{j}\neq t^{(k)}_{j+1}}\,\,\,\,e^{i\sum_{k=1}^{2K}(-1)^{k}\phi(t^{(k)}_{n+1})}\,\sum_{\sim\in{\cal P}(A)}\,\,\tau^{|A/\sim|}\\ \sum_{{\mbox{\boldmath{$\omega$}}}\in\Omega^{(}\sim)}\,\,\,e^{i\sum_{k=1}^{2K}\sum_{j=0}^{n}(-1)^{k}\omega^{(k)}_{j}(t^{(k)}_{j}-t^{(k)}_{j+1})}
m(n;K)=∑∼∈𝒫(A)∑𝐭∈T2​m:tj(k)≠tj+1(k)ei​∑k=12​K(−1)k​ϕ​(tn+1(k))∏A′∈A/∼F|A′|(τ)∑𝝎∈Ω(∼)ei​∑k=12​K∑j=0n(−1)k​ωj(k)​(tj(k)−tj+1(k))m(n;K)=\sum_{\sim\in{\cal P}(A)}\,\,\sum_{\mathbf{t}\in T^{2m}:t^{(k)}_{j}\neq t^{(k)}_{j+1}}\,\,e^{i\sum_{k=1}^{2K}(-1)^{k}\phi(t^{(k)}_{n+1})}\,\prod_{A^{\prime}\in A/\sim}F_{|A^{\prime}|}(\tau)\\ \sum_{{\mbox{\boldmath{$\omega$}}}\in\Omega^{(}\sim)}\,\,e^{i\sum_{k=1}^{2K}\sum_{j=0}^{n}(-1)^{k}\omega^{(k)}_{j}(t^{(k)}_{j}-t^{(k)}_{j+1})}
|A/∼|≤K(n+1)=m.|A/\sim|\leq K(n+1)=m. (7.2)
m⁡(n,K)\displaystyle m(n,K) =\displaystyle= ∑∼∈𝒫(A)∑𝐭∈T2​m:tj(k)≠tj+1(k)​ and ​tA′=0​ for all ​A′ei​∑k=12​K(−1)k​ϕ​(tn+1(k))N|A/∼|∏A′∈A/∼F|A′|(τ)\displaystyle\sum_{\sim\in{\cal P}(A)}\,\,\sum_{\mathbf{t}\in T^{2m}:t^{(k)}_{j}\neq t^{(k)}_{j+1}\text{ and }t_{A^{\prime}}=0\text{ for all }A^{\prime}}e^{i\sum_{k=1}^{2K}(-1)^{k}\phi(t^{(k)}_{n+1})}N^{|A/\sim|}\prod_{A^{\prime}\in A/\sim}F_{|A^{\prime}|}(\tau) (7.3)
≤\displaystyle\leq ∑∼∈𝒫(A)∑𝐭∈T2​K​(n+1):tj(k)≠tj+1(k)​ and ​tA′=0​ for all ​A′N|A/∼|∏A′∈A/∼F|A′|(τ),\displaystyle\sum_{\sim\in{\cal P}(A)}\,\,\sum_{\mathbf{t}\in T^{2K(n+1)}:t^{(k)}_{j}\neq t^{(k)}_{j+1}\text{ and }t_{A^{\prime}}=0\text{ for all }A^{\prime}}N^{|A/\sim|}\prod_{A^{\prime}\in A/\sim}F_{|A^{\prime}|}(\tau),
#{𝐭∈T2​K​(n+1):tA′=0, for all A′∈A/∼}≤|T|2K(n+1)−|A/∼|.\#\,\,\{\mathbf{t}\in T^{2K(n+1)}:t_{A^{\prime}}=0,\text{ for all }A^{\prime}\in{A/\sim}\}\leq|T|^{2K(n+1)-|A/\sim|}.
m(n,K)≤∑k=1mNk|T|2​m−kP(2m,k)sup∼:|A/∼|=k∏A′∈A/∼F|A′|(τ).m(n,K)\leq\sum_{k=1}^{m}N^{k}\,|T|^{2m-k}\,P(2m,k)\,\sup_{\sim:|A/\sim|=k}\,\,\prod_{A^{\prime}\in A/\sim}F_{|A^{\prime}|}(\tau). (7.4)
Concept demonstration

Open image ↗