Thresholding with Sub-Gaussian Regression Noise

Why the Noise Distribution Changes Thresholding

A wavelet coefficient is estimated by averaging the regression errors against a basis function. Under Gaussian noise, its error is Gaussian, so exact tail probabilities and some Gaussian risk identities are available. With sub-Gaussian errors, the coefficient error still has an exponential tail, but it need not be Gaussian, and its variance need not equal the proxy used to control that tail. The useful replacement is to carry the proxy variance through the threshold calculation.

We work with fixed design points \(x_1,\ldots,x_n\) and the regression model \(Y_i=f(x_i)+\varepsilon_i\). Assume the errors are independent, centered, and sub-Gaussian: for known nonnegative numbers \(\sigma_i^2\), \(E[\exp(t\varepsilon_i)]\leq \exp(t^2\sigma_i^2/2)\) for every real \(t\). The \(\sigma_i^2\) are proxy variances; the assumption does not assert that \(\operatorname{Var}(\varepsilon_i)=\sigma_i^2\).

Let \(\psi_k(x_i)\) be the sampled basis function for coefficient \(k\). Use the empirical normalization \(n^{-1}\sum_{i=1}^n\psi_j(x_i)\psi_k(x_i)=1\) when \(j=k\) and \(0\) otherwise. Define the true and estimated coefficients by \(\beta_k=n^{-1}\sum_i f(x_i)\psi_k(x_i)\) and \(\widehat\beta_k=n^{-1}\sum_iY_i\psi_k(x_i)\). Thus \(\widehat\beta_k=\beta_k+\eta_k\), where \(\eta_k=n^{-1}\sum_i\psi_k(x_i)\varepsilon_i\). Independence gives a coefficient-specific proxy \(v_k^2=n^{-2}\sum_i\psi_k(x_i)^2\sigma_i^2\).

Tail Bounds and Threshold Calibration

The coefficient proxy yields a two-sided tail bound without requiring a Gaussian distribution. For \(t>0\), Markov’s inequality applied to \(\exp(s\eta_k)\), followed by minimization over \(s>0\), bounds the upper tail. Applying the same argument to \(-\eta_k\) bounds the lower tail.

To verify the moment bound, independence factors the expectation into a product: \(E[\exp(t\eta_k)]=\prod_i E[\exp(t\psi_k(x_i)\varepsilon_i/n)]\). Each factor is at most \(\exp(t^2\psi_k(x_i)^2\sigma_i^2/(2n^2))\), so their product is at most \(\exp(t^2v_k^2/2)\). For the upper tail, for any \(s>0\), \(P(\eta_k>u)\leq \exp(-su)E[\exp(s\eta_k)]\leq\exp(-su+s^2v_k^2/2)\). Taking \(s=u/v_k^2\) gives \(\exp(-u^2/(2v_k^2))\); the lower tail follows by applying the same argument to \(-\eta_k\). Adding the two bounds proves the result.

For \(M\) coefficients, a union bound gives \(P(\max_{1\leq k\leq M}|\eta_k|>u)\leq2M\exp(-u^2/(2v_{\max}^2))\), where \(v_{\max}=\max_k v_k\). No independence between coefficient errors is needed for this step. A common threshold that makes this probability at most \(\delta\), for \(0<\delta<1\), is \(u=v_{\max}\sqrt{2\log(2M/\delta)}\). If proxies differ substantially, the coefficient-specific choice \(u_k=v_k\sqrt{2\log(2M/\delta)}\) gives the same simultaneous probability guarantee by applying the union bound to the individual tails.

What the Tail Event Guarantees for Hard Thresholding

For a threshold \(\lambda>0\), hard thresholding keeps an observed coefficient when its magnitude exceeds \(\lambda\): \(\delta_H(z)=z\,\mathbf{1}\{|z|>\lambda\}\). The following deterministic bound explains how a simultaneous noise event transfers into coefficient error. It applies coefficient by coefficient and does not require Gaussianity.

To prove it, consider three ranges. If \(|\beta|\leq\lambda/2\), then \(|\beta+\eta|\leq\lambda\), so the estimate is zero and the absolute error is \(|\beta|\). If \(\lambda/2<|\beta|\leq\lambda\), a discarded coefficient again has error \(|\beta|\); a retained coefficient has error \(|\eta|\leq\lambda/2<|\beta|\). In both ranges the error is at most \(\min(|\beta|,\lambda)\). Finally, if \(|\beta|>\lambda\), a retained coefficient has error \(|\eta|\leq\lambda/2\). If it is discarded, then \(|\beta|\leq|\beta+\eta|+|\eta|\leq3\lambda/2\). Thus in this last range the absolute error is at most \(3\lambda/2\). Combining the cases gives the uniform absolute-error bound \((3/2)\min(|\beta|,\lambda)\); squaring proves the stated result because \((3/2)^2=9/4\). \(\square\)

Consequently, if \(\lambda_k\) are chosen so that \(P(\text{some }|\eta_k|>\lambda_k/2)\leq\delta\), then with probability at least \(1-\delta\), the sum of squared hard-thresholding errors over those coefficients is at most \((9/4)\sum_k\min(\beta_k^2,\lambda_k^2)\). For example, using the common proxy bound above, take \(\lambda_k=2v_{\max}\sqrt{2\log(2M/\delta)}\). The factor of two is needed because the deterministic result assumes noise at most half the threshold.

An Expected-Risk Bound and Its Limits

A separate finite-sample bound is useful when considering one coefficient without conditioning on a simultaneous event. Write \(D=\{|\beta+\eta|\leq\lambda\}\) for the event that hard thresholding discards it. The exact squared error is \(\beta^2\) on \(D\) and \(\eta^2\) on its complement. Therefore

If \(|\beta|>\lambda\), discarding implies \(|\eta|\geq|\beta|-\lambda\), by the triangle inequality. Hence the sub-Gaussian tail bound gives

Here \(E[\eta^2]\leq v^2\), which follows from the sub-Gaussian moment-generating-function bound (equivalently, its standard variance consequence). When \(|\beta|\leq\lambda\), the safe bound \(P(D)\leq1\) gives risk at most \(\beta^2+v^2\). These bounds are intentionally different from the simultaneous-event inequality: the expected-risk statement does not claim a sharp oracle inequality for every coefficient or every signal size.

Which Gaussian Guarantees Need Modification?

Threshold calibration based only on exponential tails survives with sub-Gaussian errors: replace the Gaussian standard deviation by a valid proxy upper bound, account for the number of coefficients, and use a union bound. Several other familiar Gaussian statements do not follow from the sub-Gaussian assumption alone.

• Exact tail probabilities. A Gaussian threshold may be calibrated from a normal quantile. A sub-Gaussian proxy yields an upper bound, generally not that exact quantile.
• Variance substitution. The proxy controls tails but need not equal the error variance. A threshold based on an estimated standard deviation is justified only if that estimate reliably upper-bounds, or otherwise appropriately accounts for, the needed scale.
• Gaussian risk identities. Identities that use normal density calculations or Gaussian integration by parts do not automatically hold for non-Gaussian errors. They require separate assumptions and derivations.
• Coefficient independence. Orthogonal design does not by itself imply independent coefficient errors for non-Gaussian regression errors. The union-bound guarantees above avoid needing that independence.

A common mistake is to use a Gaussian threshold formula with a quantity called “the variance” and conclude that the Gaussian false-retention probability remains exact. The correction is to identify the coefficient proxy \(v_k^2\), verify the sub-Gaussian moment bound, and state the result as a tail inequality. Another mistake is to infer a global expected-risk oracle bound from a high-probability coefficient inequality. The latter holds on a specified event; converting it into an unconditional expectation requires controlling the loss on the complementary event as well.