Deriving the Universal Wavelet Threshold

Why a Threshold Must Grow With the Number of Coefficients

A wavelet transform can represent a signal using many coefficients. Even if a particular coefficient is zero, its noisy estimate will usually not be exactly zero. Thresholding is intended to suppress coefficients that look like noise, but a small noise fluctuation becomes more likely when there are many coordinates to inspect. A cutoff chosen for one coefficient therefore cannot be assessed without considering the size of the whole collection.

The universal threshold addresses this multiplicity by scaling the cutoff with the number of coefficients. Its defining scale comes from the maximum of many standard Gaussian variables. The resulting rule is deliberately cautious: it makes noise-only coordinates unlikely to cross the cutoff, but that caution can also discard real signal and incur risk.

Gaussian Sequence Setup and the Universal Threshold

Consider $m$ estimated coefficients in a Gaussian sequence model:

Y_i=\theta_i+\sigma Z_i,\qquad i=1,\ldots,m,

where $\theta_i$ is the true coefficient, $\sigma>0$ is the noise standard deviation, and the $Z_i$ are independent $N(0,1)$ variables. In an orthonormal wavelet transform of a Gaussian white-noise model, this is the standard coefficient-noise representation. The maximum-probability bound below only needs each noise variable to have a standard normal marginal distribution; independence is not required for that bound.

Definition: For $m\geq 2$ Gaussian coefficient estimates with common noise standard deviation $\sigma$, the universal threshold is $$ \lambda_{\mathrm{univ}}=\sigma\sqrt{2\log m}. $$ Hard thresholding retains $Y_i$ when $|Y_i|>\lambda_{\mathrm{univ}}$ and sets it to zero otherwise. A coordinate is a null coordinate when $\theta_i=0$; retaining such a coordinate is a false retention.

The name reflects the scale of the largest noise fluctuation in a collection of $m$ Gaussian coordinates. It does not mean that the rule is optimal for every signal, loss, or desired error probability. In particular, it is useful to distinguish controlling the chance of any false retention from minimizing expected estimation error.

Worked Example: The Cutoff for 1,024 Coefficients

Suppose $m=1024$ and $\sigma=2$. Since $\log(1024)=10\log 2\approx 6.93147$, the universal threshold is

\lambda_{\mathrm{univ}} =2\sqrt{2\log(1024)} =2\sqrt{13.86294} \approx 7.4466.

A coefficient estimate is retained only if its absolute value exceeds approximately $7.45$. In standard-deviation units the cutoff is about $3.7233$, since $7.4466/2\approx3.7233$. This threshold is not the same as applying a fixed $3$-standard-deviation rule to every coefficient: its value has been set using the total number of coordinates.

Bounding the Chance of Any False Retention

Let $I_0=\{i:\theta_i=0\}$ be the set of null coordinates, and let $q$ be its size. The event of at least one false retention is that some null-coordinate noise exceeds the cutoff in absolute value. A union bound reduces this maximum event to a sum of marginal tail probabilities.

Theorem: Suppose each $Z_i$ is standard normal and $q\leq m$. For any $u>0$, thresholding at $\lambda=\sigma u$ satisfies $$ P\!\left(\text{at least one null coordinate is retained}\right) \leq 2q\,\overline{\Phi}(u) \leq \frac{2q\,\phi(u)}{u}, $$ where $\phi(u)=(2\pi)^{-1/2}e^{-u^2/2}$ is the standard normal density and $\overline{\Phi}(u)=P(Z>u)$ for $Z\sim N(0,1)$. In particular, at the universal threshold, $$ P\!\left(\text{at least one null coordinate is retained}\right) \leq \frac{2}{\sqrt{2\pi}\sqrt{2\log m}}. $$

The first inequality is valid whether or not the coefficient noises are independent. The second uses the Gaussian Mills bound $\overline{\Phi}(u)\leq\phi(u)/u$, which follows directly by comparing the tail integral with an integral whose integrand has a convenient antiderivative.

Proof. For a null coordinate, $Y_i=\sigma Z_i$. Thus the event that coordinate $i$ is retained at threshold $\sigma u$ is $\{|Z_i|>u\}$. The probability of a union is no larger than the sum of the probabilities, so

P\!\left(\bigcup_{i\in I_0}\{|Z_i|>u\}\right) \leq \sum_{i\in I_0}P(|Z_i|>u) =2q\,\overline{\Phi}(u).

For $u>0$, since $z/u\geq1$ for $z\geq u$, and since $\phi'(z)=-z\phi(z)$,

\overline{\Phi}(u) =\int_u^\infty \phi(z)\,dz \leq \frac{1}{u}\int_u^\infty z\phi(z)\,dz =\frac{\phi(u)}{u}.

Substituting gives the second inequality. For $u=\sqrt{2\log m}$, we have $e^{-u^2/2}=1/m$, hence $\phi(u)=1/(\sqrt{2\pi}m)$. Using $q\leq m$ yields the stated universal-threshold bound. $\square$

The Gaussian tail prefactor matters. Replacing the normal tail by the looser exponential bound can obscure why this particular threshold gives a useful asymptotic maximum bound. The displayed bound tends to zero at the rate $1/\sqrt{\log m}$. It is an upper bound, not an exact probability, and it does not promise a chosen finite-sample level such as $0.05$ for every $m$.

Worked Example: A Familywise Bound at 1,024 Coordinates

Suppose all $m=1024$ coordinates are null. Here $u=\sqrt{2\log(1024)}\approx3.7233$. Applying the theorem with $q=m$ gives

P(\text{at least one false retention}) \leq \frac{2}{\sqrt{2\pi}(3.7233)} \approx 0.214.

Thus this bound limits the probability to about $21.4\%$; it does not assert that the probability equals $21.4\%$. If only 100 of the 1,024 coefficients are null, the same calculation with $q=100$ gives the sharper bound $0.214(100/1024)\approx0.0209$. The number of null coordinates, not just the total number available, enters the first bound.

Choosing a Threshold for a Prespecified Error Probability

If a specific familywise error target is required, the universal threshold need not be the desired finite-sample choice. A simple, more conservative alternative follows from the Gaussian exponential tail bound. For $x>0$, Markov's inequality applied to $e^{xZ}$, together with $E[e^{xZ}]=e^{x^2/2}$, gives $P(Z>x)\leq e^{-x^2/2}$. Symmetry then gives $P(|Z|>x)\leq2e^{-x^2/2}$.

Result: For $q\leq m$ null coordinates and a target $0<\alpha<1$, the threshold $$ \lambda_\alpha=\sigma\sqrt{2\log(2m/\alpha)} $$ ensures that the probability of at least one false retention is at most $\alpha$.

Indeed, the union bound and the two-sided exponential tail bound give

P(\text{at least one false retention}) \leq 2q e^{-u^2/2} \leq 2m e^{-u^2/2}.

Setting $u=\sqrt{2\log(2m/\alpha)}$ makes the right-hand side $2m e^{-\log(2m/\alpha)}=\alpha$. This is a sufficient bound and may be conservative. It is a finite-sample guarantee of a different form from the universal threshold’s asymptotic maximum scale.

Worked Example: Calibrating a 5% Bound

For $m=1000$ and target $\alpha=0.05$, the exponential-tail calibration uses

u_\alpha=\sqrt{2\log(2(1000)/0.05)} =\sqrt{2\log(40000)} \approx \sqrt{21.1933} \approx 4.6036.

The resulting threshold is $4.6036\sigma$. The universal threshold for the same $m$ is $\sigma\sqrt{2\log(1000)}\approx3.7169\sigma$. The calibrated threshold is larger because this particular union-bound calculation is designed to ensure a $5\%$ upper bound. The comparison does not establish that one threshold is uniformly better: a larger cutoff protects more strongly against false retention but can remove more signal.

The Conservative Null-Risk Cost

The false-retention probability describes whether any noise coefficient crosses the threshold. Integrated squared-error risk asks a different question: how much squared error is contributed by the retained noise values? Under the global null, every true coefficient is zero, so hard thresholding has risk equal to the expected squared size of the noise values that survive.

Result: Under the global null $Y_i=\sigma Z_i$, with independent standard normal $Z_i$, hard thresholding at $\lambda=\sigma u$, $u>0$, has total risk $$ R_0=m\sigma^2\,2\{u\phi(u)+\overline{\Phi}(u)\}. $$ It is bounded above by $$ R_0\leq 2m\sigma^2\phi(u)\left(u+\frac{1}{u}\right). $$

Derivation. Under the null, the thresholded estimate is $Y_i\mathbf{1}\{|Y_i|>\sigma u\}$, and its squared error is its square. Consequently,

R_0 =m\sigma^2 E\!\left[Z^2\mathbf{1}\{|Z|>u\}\right] =2m\sigma^2\int_u^\infty z^2\phi(z)\,dz.

Using $\phi'(z)=-z\phi(z)$, integration by parts gives

\int_u^\infty z^2\phi(z)\,dz =u\phi(u)+\int_u^\infty\phi(z)\,dz =u\phi(u)+\overline{\Phi}(u).

The boundary term at infinity vanishes because $z\phi(z)\to0$. This proves the exact formula. Applying $\overline{\Phi}(u)\leq\phi(u)/u$ proves the upper bound. At the universal threshold, $\phi(u)=1/(\sqrt{2\pi}m)$, so

R_0\leq \frac{2\sigma^2}{\sqrt{2\pi}} \left(\sqrt{2\log m}+\frac{1}{\sqrt{2\log m}}\right).

Although there are $m$ coordinates, this upper bound grows only on the order of $\sigma^2\sqrt{\log m}$. It is nevertheless positive: an oracle that knows every coefficient is zero would estimate all of them as zero and have zero risk. The bound quantifies one cost of using a data-independent cutoff that guards against large noise fluctuations across a large collection.

Worked Example: Total and Per-Coordinate Null Risk

Take $m=1024$, $\sigma=2$, and the universal threshold. Then $u\approx3.7233$ and $1/u\approx0.2686$. Using $\phi(u)=1/(\sqrt{2\pi}m)$, the total-risk upper bound is

R_0 \leq \frac{2(2^2)}{\sqrt{2\pi}}(3.7233+0.2686) \approx 12.7402.

Dividing the total bound by $m=1024$ gives a per-coordinate bound of

\frac{12.7402}{1024}\approx 0.0124416,

or approximately $0.01244$. Dividing instead by $m\sigma^2=4096$ gives the variance-normalized bound $12.7402/4096\approx0.00311$. These are different quantities: $0.01244$ is per-coordinate risk in squared coefficient units, while $0.00311$ is per-coordinate risk divided by $\sigma^2$.

Interpretation and Common Pitfall

The universal threshold links a maximum-noise calculation to a practical coefficient rule. Raising the threshold reduces the chance of retaining a noise-only coordinate and reduces the null risk from retained noise. But a nonzero coefficient can also fall below the threshold and be set to zero, creating estimation error. Thus the null-risk calculation is not a claim that the universal threshold minimizes total risk for every signal; it isolates a particular conservative cost.

Mistake: treating the universal threshold as a fixed-level guarantee. The formula $\sigma\sqrt{2\log m}$ does not, by itself, promise that the probability of any false retention is at most a chosen $\alpha$. Use an explicit finite-sample calibration when that guarantee is required.
Mistake: confusing a familywise probability with risk. The probability that at least one null coefficient is retained is not the expected sum of squared retained noise. The latter requires the tail second-moment calculation.
Mistake: dividing risk by the wrong quantity. Total risk divided by $m$ is per-coordinate squared-error risk; division by $m\sigma^2$ gives variance-normalized per-coordinate risk.
Mistake: assuming the maximum bound requires independent coordinates. The union bound and its marginal Gaussian tail calculation do not require independence, though exact maximum probabilities generally depend on the joint distribution.

Key takeaway: The universal threshold has the Gaussian maximum scale $\sigma\sqrt{2\log m}$. A Gaussian tail bound controls false retention, while integrating the squared tail quantifies the null-risk price. These are related calculations, but they answer different questions.

Check Your Understanding

Use the definitions and derivations above to answer the following.

Why does the universal threshold increase when the number of coefficient estimates increases?
Which step in the familywise false-retention bound uses a union bound, and which step uses the Gaussian Mills bound?
For $m$ null coefficients, explain why the probability of at least one false retention and the total squared-error risk are not the same quantity.
If the total null-risk upper bound is $R$, what are the per-coordinate risk and the variance-normalized per-coordinate risk?
Why might a threshold calibrated to guarantee a small false-retention probability have greater risk when some true coefficients are nonzero?