Adaptive Denoising of Signals with Shift-Invariant Structure
share
We study the problem of discrete-time signal denoising, following the line of research initiated by [Nem91] and further developed in [JN09, JN10, HJNO15, OHJN16]. Previous papers considered the following setup: the signal is assumed to admit a convolution-type linear oracle -- an unknown linear estimator in the form of the convolution of the observations with an unknown time-invariant filter with small ℓ_2-norm. It was shown that such an oracle can be "mimicked" by an efficiently computable non-linear convolution-type estimator, in which the filter minimizes the Fourier-domain ℓ_∞-norm of the residual, regularized by the Fourier-domain ℓ_1-norm of the filter. Following [OHJN16], here we study an alternative family of estimators, replacing the ℓ_∞-norm of the residual with the ℓ_2-norm. Such estimators are found to have better statistical properties, in particular, we prove sharp oracle inequalities for their ℓ_2-loss. Our guarantees require an extra assumption of approximate shift-invariance: the signal must be -close, in ℓ_2-metric, to some shift-invariant linear subspace with bounded dimension s. However, this subspace can be completely unknown, and the remainder terms in the oracle inequalities scale at most polynomially with s and . In conclusion, we show that the new assumption implies the previously considered one, providing explicit constructions of the convolution-type linear oracles with ℓ_2-norm bounded in terms of parameters s and .
READ FULL TEXT