# Adaptive Denoising of Signals with Local Shift-Invariant Structure

Zaid Harchaoui, Anatoli B. Juditsky, Arkadi Nemirovski, Dmitrii M. Ostrovskii

► To cite this version:

Zaid Harchaoui, Anatoli B. Juditsky, Arkadi Nemirovski, Dmitrii M. Ostrovskii. Adaptive Denoising of Signals with Local Shift-Invariant Structure. Festschrift in Honor of Vladimir Spokoiny, Nov 2019, Berlin, Germany. hal-04037260

HAL Id: hal-04037260

https://hal.science/hal-04037260

Submitted on 22 Mar 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Adaptive Denoising of Signals with Local Shift-Invariant Structure

Zaid Harchaoui<fnref n="1" />, Anatoli Juditsky<fnref n="2" />, Arkadi Nemirovski<fnref n="3" />, and Dmitrii Ostrovskii<fnref n="4" />

**Abstract.** We discuss the problem of adaptive discrete-time signal denoising in the situation where the signal to be recovered admits a “linear oracle”—an unknown linear estimate that takes the form of convolution of observations with a time-invariant filter. It was shown by Juditsky and Nemirovski (2009) [20] that when the $l_2$-norm of the oracle filter is small enough, such oracle can be “mimicked” by an efficiently computable adaptive estimate of the same structure with the observation-driven filter. The filter in question was obtained as a solution to the optimization problem in which the $l_\infty$-norm of the Discrete Fourier Transform (DFT) of the estimation residual is minimized under constraint on the $l_1$-norm of the filter DFT. In this paper, we discuss a new family of adaptive estimates which rely upon minimizing the $l_2$-norm of the estimation residual. We show that such estimators possess better statistical properties than those based on $l_\infty$-fit; in particular, under the assumption of approximate shift-invariance we prove oracle inequalities for their $l_2$-loss and improved bounds for $l_2$- and pointwise losses. We also study the relationship of the approximate shift-invariance assumption with the signal simplicity introduced in [20] and discuss the application of the proposed approach to harmonic oscillation denoising.

# 1 Introduction

The problem we consider in this paper is that of signal denoising: given noisy observations

$$y_{\tau} = x_{\tau} + \sigma \zeta_{\tau}, \quad \tau \in \mathbb{Z} \qquad (1)$$

we aim at recovering a signal $(x_t)_{t \in \mathbb{Z}}$. It is convenient for us to assume that signal and noises are complex-valued. Observation noises $\zeta_\tau$ are assumed to be independent of $x$ i.i.d. standard complex-valued Gaussian random variables (denoted $\zeta_\tau \sim \mathcal{CN}(0, 1)$), meaning that $\zeta_\tau = \zeta_\tau^1 + i\zeta_\tau^2$ with i.i.d. $\zeta_\tau^1, \zeta_\tau^2 \sim \mathcal{N}(0, 1)$.

<footnote n="1">¹ University of Washington, Seattle, WA 98195, USA, zaid@uw.edu,</footnote>

<footnote n="2">² LJK, Université Grenoble Alpes, 700 Avenue Centrale, 38401 Saint-Martin-d'Hères, France, anatoli.juditsky@univ-grenoble-alpes.fr</footnote>

<footnote n="3">³ Georgia Institute of Technology, Atlanta, GA 30332, USA, nemirovs@isye.gatech.edu</footnote>

<footnote n="4">⁴ University of Southern California, Los Angeles, CA 90089, USA, emaildostrovs@usc.edu</footnote>
Our goal may be, for instance, to recover the value $x_t$ of the signal at time $t$ given observations $(y_\tau), |\tau - t| \le m$ for some $m \in \mathbb{Z}_+$ (problem referred to as signal interpolation in signal processing literature), or to estimate the value $x_{t+h}$ given observations $(y_\tau), t - m \le \tau \le t$ (signal prediction or extrapolation), etc.

The above problem is classical in statistics and signal processing. In particular, linear estimates of the form

$$ \hat{x}_t = \sum_{\tau \in \mathbb{Z}} \phi_{\tau} y_{t-\tau} $$

are ubiquitous in nonparametric estimation; for instance, classical kernel estimators are of this type. More generally, linear estimates are considered both theoretically attractive and easy to use in practice [17, 9, 6, 25, 39, 41]. When the set $\mathcal{X}$ of signals is well-specified, one can usually compute a (nearly) minimax on $\mathcal{X}$ linear estimator in closed form. In particular, if $\mathcal{X}$ is a class of “smooth signals,” such as a Hölder or a Sobolev ball, then the corresponding estimator is given by the kernel estimator with properly selected bandwidth [39], and is minimax among all possible estimators. Moreover, linear estimators are known to be nearly minimax optimal with respect to the pointwise loss [16, 6] and the $l_2$-loss [8, 34, 24, 23] under rather general assumptions about the set $\mathcal{X}$ of possible signals. Besides this, if the set $\mathcal{X}$ of signals is specified in a computationally tractable way, then a near-minimax linear estimator can be efficiently computed by solving a convex optimization problem [24], [23].

The strength of this approach, however, comes at a price: in order to implement the estimate the set $\mathcal{X}$ must be known to the statistician. Such knowledge is crucial: near-minimax estimator for one signal set can be of poor quality for another one. Thus, linear estimation approach cannot be directly implemented when no prior knowledge of $\mathcal{X}$ is available. In the statistical literature this difficulty is usually addressed via adaptive model selection [3, 12, 18, 27, 29, 28, 30, 39]. However, model selection procedures usually impose strong structural assumptions on the signal set, assuming it to be known up to a few hyper-parameters.<fnref n="5" />

An alternative approach to the denoising problem with unknown $\mathcal{X}$ was proposed in [32]. There, instead of directly restricting the class of signals and requiring a specification of $\mathcal{X}$, one restricts the class of possible estimators. Namely, let us denote $C(\mathbb{Z})$ the space of complex-valued functions on $\mathbb{Z}$, and let, for $m \in \mathbb{Z}_+$, $C_m(\mathbb{Z})$ be the space of complex-valued sequences that vanish outside the set $\{-m, \dots, m\}$. We consider linear convolution-type estimators, associated with filters $\phi \in C_m(\mathbb{Z})$ of the form

$$ \hat{x}_t = [y * \phi]_t := \sum_{\tau \in \mathbb{Z}} \phi_{\tau} y_{t-\tau} = \sum_{|\tau| \le m} \phi_{\tau} y_{t-\tau}. \quad (2) $$

<footnote n="5">⁵ More general adaptation schemes have been recently introduced, e.g., routines from [13, 28] which can handle, for example, adaptation to inhomogeneous and anisotropic smoothness of the signal. However, the proposed schemes cannot be implemented in a numerically efficient fashion, and therefore are not practical.</footnote>
Informally, the problem we are interested in here is as follows:

If we fix the structure (2) of the estimate and consider the form of the fil-
ter $\phi$ as a "free parameter," is it possible to build an estimation procedure
which is adaptive with respect to this parameter?

In other words, suppose that a “good” filter $\phi^o$ with small estimation error “exists in nature.” Is it then possible to construct a data-driven estimation routine which has (almost) the same accuracy as the “oracle”—a hypothetic optimal estimation method utilizing $\phi^o$?

The above question was first answered positively in [20] using the estimation machinery from [32]. To present the ideas underlying the approach of [20] we need to define the class of “well-filtered” or “simple” signals [15, 20].

**Definition 1 (Simple signals).** Given parameters $m, n \in \mathbb{Z}_+$, $\rho \ge 1$, and $\theta \ge 0$, signal $x \in C(\mathbb{Z})$ is called $(m, n, \rho, \theta)$-simple if there exists $\phi^o \in C_m(\mathbb{Z})$ satisfying

$$
\|\phi^o\|_2 \le \frac{\rho}{\sqrt{2m+1}}, \qquad (3)
$$

and such that

$$
|x_{\tau} - [\phi^{o} * x]_{\tau}| \le \frac{\sigma \theta \rho}{\sqrt{2m+1}}, \quad \text{for all } |\tau| \le m+n. \quad (4)
$$

Decomposing the pointwise mean-squared error of the estimate (2) with $\phi = \phi^o$
as

$$
\mathbf{E}|x_{\tau} - [\phi^{o} * y]_{\tau}|^2 = \sigma^2 \mathbf{E}|[\phi^{o} * \zeta]_{\tau}|^2 + |x_{\tau} - [\phi^{o} * x]_{\tau}|^2,
$$

we immediately arrive at the following bound on the pointwise expected error:

$$
[\mathbf{E}|x_{\tau} - [\phi^o * y]_{\tau}|^2]^{1/2} \le \frac{\sigma\sqrt{1 + \theta^2}\rho}{\sqrt{2m+1}}, \quad |\tau| \le m+n. \quad (5)
$$

In other words, simple signals are those for which there exists a linear estimator
(i) utilizing observations in the *m*-neighbourhood of a point, (ii) invariant in the
(*m* + *n*)-vicinity of the origin, and (iii) attaining pointwise risk of order *m*⁻¹/²
in that vicinity. (For brevity, here we refer to the quantity *E*[|*x*_t - *x̂*t|²]¹/² as the
pointwise risk (at *t* ∈ Z) of estimate *x̂*.) Parameters *ρ*, *θ* allow for refined control
of the risk and specify the bias-variance balance.

Now, assume that the only prior information about the signal to be recovered
is that it is (m, n, ρ, θ)-simple with some known (m, n, ρ, θ). As we have just seen,
this implies existence of a convolution-type linear estimator x̂ = φ° * y with a
good statistical performance. The question is whether we can use this informa-
tion to “mimic” x̂°—i.e., construct an estimator of (x_τ)|_τ≤n with comparable
statistical performance when only using available observations. Answering this
question is not straightforward. In order to build such an adaptive estimator,
one could implement the cross-validation procedure by minimizing some observ-
able proxy of the quadratic loss of the estimate, say, the l₂-norm of the residual
([y - ϕ * y]τ)|τ|≤m+n, over the set of filters ϕ satisfying (3). However, it is well known that the set of filters satisfying (3) is too “massive” to allow for construction of adaptive estimate with the risk bound similar to (5) even when ρ = 1.<fnref n="6" /> As a result, all known to us approaches to adaptive estimation in this case impose some extra constraints on the class of filters such as regularity [11] or sparsity in a certain basis [7], etc.

Nevertheless, surprisingly, adaptive convolution-type estimators with favorable statistical performance guarantees can be constructed. The key idea, going back to [20], is to pass to a “new oracle” with a characterization which better suits the goal of adaptive estimation. Namely, one can easily verify (cf., e.g., [15, Proposition 3]) that if a filter $\phi^o \in C_m(\mathbb{Z})$ satisfies relations (3) and (4), then its auto-convolution $\phi^o = \phi^o * \phi^o \in C_{2m}(\mathbb{Z})$ (with twice larger support) satisfies their analogues

$$ \begin{gathered} \|F_{2m}[\phi^o]\|_1 \le \frac{2\rho^2}{\sqrt{4m+1}}, \qquad (6) \\ |x_{\tau} - [\phi^o * x]_{\tau}| \le \frac{2\sqrt{2\sigma\theta\rho^2}}{\sqrt{4m+1}}, \quad |\tau| \le n; \end{gathered} $$

here $F_n$ is the unitary Discrete Fourier Transform (DFT) $F_n : C_n(\mathbb{Z}) \to \mathbb{C}^{2n+1}$,

$$ (F_n[x])_k = \frac{1}{\sqrt{2n+1}} \sum_{|\tau| \le n} \exp\left(\frac{2\pi i k \tau}{2n+1}\right) x_{\tau}, \quad 1 \le k \le 2n+1. $$

While the new bounds are inflated (the additional factor $\rho$ is present in both bounds), the bound (6) is essentially stronger than its counterpart $\|F_m[\phi^o]\|_1 \le \rho$ one could extract from (3).

Based on this observation, the authors studied in [14, 20, 15] a class of adaptive convolution-type “uniform-fit” estimators which correspond to filters obtained by minimizing the uniform norm of the Fourier-domain residual $F_n[y - y * \phi]$ constrained (or penalized) by the $l_1$-norm of the DFT of the filter. Such estimators can be efficiently computed since the corresponding filters are given as optimal solutions to well-structured convex optimization problems.

As it is common in adaptive nonparametric estimation, one can measure the quality of an adaptive estimator with the factor—the “cost of adaptation”—by which the risk of such an estimator is greater than that of the corresponding “oracle” estimator which the adaptive one is trying to “mimic”. As it turns out, “uniform-fit” estimators studied in [14, 20, 15] admit the pointwise risk bounds similar to (5), with extra factor $C\rho^3\sqrt{\log(m+n)}$ as compared to (5) (see [15, Theorem 5]). On the other hand, there is a lower bound stating that the adaptation factor cannot be less than $c\rho\sqrt{\log m}$ when $m \ge c'n$ (cf. [15, Theorem 2]), leaving the gap between these two bounds which may be quite significant when

<footnote n="6">⁶ While this statement appears self-evident to statisticians of older generations, younger researchers may expect an explanation. This is why we provide a brief discussion of the “naive estimate” in Section D of the appendix.</footnote>
$\rho$ is large. Furthermore, the choice of optimization objective (uniform fit of the Fourier-domain residual) in such estimators was dictated by the technical consideration allowing simpler control of the pointwise risk and seems artificial when the estimation performance is measured by the $l_2$-loss.

**Contributions.** In this paper, we propose a new family of adaptive convolution-type estimators. These estimators utilize an adaptive filter which is obtained by minimizing the $l_2$-norm of the residual constrained or penalized by the $l_1$-norm of the DFT of the filter. Similarly to uniform-fit estimators, new estimators can be efficiently computed via convex optimization routines. We prove oracle inequalities for the $l_2$-loss of these estimators, which lead to the improved risk bounds compared to the case of uniform-fit estimators. Note that signal simplicity, as per Definition 1, involves a special sort of time-invariance of the oracle estimate: filter $\phi^o \in C_m(Z)$ in Definition 1 is assumed to be “good” (cf. (4)) uniformly over $|t| \le m + n$, what can be understood as some kind of “approximate local shift-invariance” of the signal to be recovered. In fact, this property of the signal is operational when deriving corresponding risk bounds for adaptive recoveries. In the present paper, in order to derive the oracle inequalities we replace the assumption of signal simplicity, as per Definition 1, with an explicit approximate (local) shift-invariance (ASI) assumption. In a nutshell, the new assumption states that the unknown signal admits (locally) a decomposition $x = x^S + \varepsilon$ where $x^S$ belongs to an unknown shift-invariant linear subspace $S \subset C(Z)$ of a small dimension, and the residual component $\varepsilon$ is small in $l_2$-norm or $l_\infty$-norm. The remainder terms in the established oracle inequalities explicitly depend on the subspace dimension $s = \dim(S)$ and the magnitude $\kappa$ of the residual.<fnref n="7" /> We also study the relationship between our ASI assumption and the notion of signal simplicity introduced in [20]:

- On one hand, approximately shift-invariant signals constitute a subclass of simple signals (in fact, the widest known to us such subclass to date). In particular, a “uniform” version of ASI assumption, in which the residual component $\varepsilon$ is bounded in $l_\infty$-norm, implies signal simplicity (cf. Definition 1) with simple dependence of parameters $\rho$ and $\theta$ of the class on the ASI parameters $s$ and $\kappa$. This, in turn, allows to derive improved bounds for the pointwise and $l_2$-loss of novel adaptive estimators over the class of signals satisfying the “uniform” version of ASI assumption.

<footnote n="7">⁷ In hindsight, ASI is a natural generalization of the classical “regularity assumption” for signals on the regular grid. Indeed, consider signals which are discretizations of smooth functions; such signals have a very simple structure—they are “locally close” to a given small-dimensional subspace, that of small degree polynomials. Here we extend the notion of regularity allowing for signals to be (locally) close to an unknown subspace of moderate dimension; we refer to [14, 21] for the detailed discussion of the relationship of the developed framework with the nonparametric estimation of regular functions. Our standing (technical) assumption about (local) shift invariance of the approximating subspace is operational, it allows for successful application of the machinery of linear filtering and Fourier transform.</footnote>
- On the other hand, all known to us examples of simple signals in $C(\mathbb{Z})$ are those of signals close to solutions of low-order linear homogeneous difference equations, see [21]; such signals are close to small-dimensional shift-invariant subspaces. New bounds on the $l_2$- and pointwise risk for such signals established in this work improve significantly over the analogous bounds for such signals obtained in [21, 15].

As an illustration, we consider an application of the proposed approach to the problem of denoising a harmonic oscillation—a sum of complex sinusoids with arbitrary (unknown) frequencies. The known approaches [1, 37] to this problem are based on the ideas from sparse recovery [10] and impose frequency separation conditions to obtain sharp statistical guarantees (see Section 4.3 for more details). In contrast, deriving near-optimal statistical guarantees for adaptive convolution-type estimators in this problem does not require this type of assumptions.

Preliminary versions of some results presented in this paper were announced in [33].

*Manuscript organization.* We present the problem of adaptive interpolation and prediction and introduce necessary notation in Section 2. In Section 3 we introduce adaptive estimators and present oracle inequalities for their $l_2$-loss. Then we use these inequalities to derive guarantees for $l_2$- and pointwise risks of adaptive estimates in Section 4. In particular, in Section 4.2 we discuss the structure of the classes of approximately shift-invariant signals over $\mathbb{Z}$ and show that such signals are close, in certain sense, to complex exponential polynomials—solutions to linear homogeneous difference equations. We then specify statistical guarantees for adaptive interpolation and prediction of such signals; in particular, we establish new bounds for adaptive prediction of generalized harmonic oscillations which are sums of complex sinusoids modulated by polynomials. Finally, in Section 4.3 we consider an application of the proposed estimates to the problem of full recovery of a generalized (or usual) harmonic oscillation, and compare our approach against the state of the art for this problem. To streamline the presentation we defer technical proofs to appendix.

# 2 Problem description

## 2.1 Notation

We follow the “Matlab convention” for matrices: $[A, B]$ and $[A; B]$ denote, respectively, the horizontal and vertical concatenations of two matrices of compatible dimensions. Unless explicitly stated otherwise, all vectors are column vectors. Given a signal $x \in C(\mathbb{Z})$ and $n_1, n_2 \in \mathbb{Z}$ such that $n_1 \le n_2$, we define the “slicing” map

$$x_{n_1}^{n_2} := [x_{n_1}; \dots; x_{n_2}]. \qquad (7)$$

In what follows, when it is unambiguous, we use the shorthand notation $\tau \le n$ ($\tau < n, |\tau| \le n$, etc.) for the set of integers satisfying the inequality in question.
*Convolution and filters.* Recall that $C(\mathbb{Z})$ is the linear space of all two-sided complex sequences, and $C_n(\mathbb{Z})$ denotes the space of such sequences which vanish outside $[-n, ..., n]$. We call the smallest $m \in \mathbb{Z}_+$ such that $\phi \in C_m(\mathbb{Z})$ the width of $\phi$ and denote it $w(\phi)$. Note that (7) allows to identify $C_n(\mathbb{Z})$, with complex vector space $C^{2n+1}$. It is also convenient to identify $x \in C(\mathbb{Z})$ with its Laurent series $x(z) = \sum_j x_j z^j$. The (discrete) convolution of $\varphi * \psi \in C(\mathbb{Z})$ of $\varphi, \psi \in C(\mathbb{Z})$ is defined as

$$[\varphi * \psi]_t := \sum_{\tau \in \mathbb{Z}} \varphi_{\tau} \psi_{t-\tau}$$

and is, clearly, a commutative operation. One has $[\varphi * \psi](z) = \varphi(z)\psi(z)$ with

$$w(\varphi * \psi) \le w(\varphi) + w(\psi).$$

In what follows, $\Delta$ stands for the forward shift operator on $C(\mathbb{Z})$:

$$[\Delta x]_t = x_{t-1},$$

and $\Delta^{-1}$ for its inverse, the backward shift. Then

$$\varphi * \psi = \varphi(\Delta)\psi.$$

Given $\varphi \in C(\mathbb{Z})$ with $w(\varphi) < \infty$ and observations $y = (y_\tau)$, we can associate with $\varphi$ the linear estimate $\hat{x}$ of $x \in C(\mathbb{Z})$ of the form

$$\hat{x} = \varphi * y = \varphi(\Delta)y \quad (8)$$

($\hat{x}$ is simply a kernel estimate over the grid $\mathbb{Z}$ corresponding to a finitely supported discrete kernel $\varphi$). The just defined “convolution” (kernel) estimates are referred to as linear filters in signal processing; with some terminology abuse, we also call *filters* elements of $C(\mathbb{Z})$ with finitely many nonzero entries.

*Norms.* For $x, y \in C(\mathbb{Z})$ we denote $\langle x, y \rangle$ the Hermitian inner product $\langle x, y \rangle = \sum_{\tau \in \mathbb{Z}} \bar{x}_{\tau} y_{\tau}$, $\bar{x}_{\tau}$ being the complex conjugate of $x_{\tau}$; for $n \in \mathbb{Z}_+$ we put

$$\langle x, y \rangle_n = \sum_{|\tau| \le n} \bar{x}_{\tau} y_{\tau}.$$

Given $p \ge 1$ and $n \in \mathbb{Z}_+$ we define semi-norms on $C(\mathbb{Z})$ as follows:

$$\|x\|_{n,p} := \left( \sum_{|\tau| \le n} |x_{\tau}|^p \right)^{1/p}$$

with $\|x\|_{n,\infty} = \max_{|\tau| \le n} |x_{\tau}|$. When such notation is unambiguous, we also use $\| \cdot \|_p$ to denote the “usual” $l_p$-norm on $C(\mathbb{Z})$, e.g., $\|x\|_p = \|x\|_{n,p}$ whenever $w(x) \le n$.
We define the (unitary) Discrete Fourier Transform (DFT) operator $F_n : \mathbb{C}_n(\mathbb{Z}) \to \mathbb{C}^{2n+1}$ by

$$ (F_n[x])_k = \frac{1}{\sqrt{2n+1}} \sum_{|\tau| \le n} \exp\left(-\frac{i2\pi k \tau}{2n+1}\right) x_{\tau}, \quad 1 \le k \le 2n+1. $$

The unitarity of DFT implies the Parseval identities: for any $x, y \in \mathbb{C}(\mathbb{Z})$ and $n \in \mathbb{Z}_+$ one has

$$ \langle x, x \rangle_n = \langle F_n[x], F_n[x] \rangle, \quad \|x\|_{n,2} = \|F_n[x]\|_2. \qquad (9) $$

In what follows, $c$, $C$, $C'$, etc., stand for absolute constants whose exact values can be recovered from the proofs. We use the $O(\cdot)$ notation: for two functions $f, g$ of the same argument $t$, $f = O(g)$ means that there exists $C < \infty$ such that $|f(t)| \le C|g(t)|$ for all $t$ in the domain of $f$.

## 2.2 Problem statement

We consider the problem of estimating the signal $x \in \mathbb{C}(\mathbb{Z})$ given noisy observations $y_{\tau} := x_{\tau} + \sigma\zeta_{\tau}$ on the segment $-L \le \tau \le L$ (cf. (1)); here $\zeta_t \sim \mathbb{CN}(0, 1)$ are i.i.d. standard complex-valued Gaussian random variables. Here we discuss different settings of this problem:

- *Signal interpolation* in which, when computing the estimate of $x_t$, one can use observations both on the left and on the right of $t$. For the sake of simplicity, we consider the “symmetric” version of this problem where the objective is, given $|m| \le L$, to build an estimate $\hat{x}_t = [\hat{\varphi} * y]_t$ of $x_t$ for $|t| \le L - m$, with $\hat{\varphi} \in \mathbb{C}_m(\mathbb{Z})$ depending on observations.

- *Signal prediction* in which, when computing the estimate of $x_t$, we are allowed to use observations only on one side of $t$, e.g., observations for $\tau \le t-h$ where $h \in \mathbb{Z}_+$ is a given prediction horizon. For the sake of clarity, in this paper we only consider the version of this problem with $h = 0$ (often referred as filtering in signal processing literature); the general situation can be treated in the same way at the expense of more involved notation. In other words, we are looking to build a data-driven filter $\hat{\varphi} \in \mathbb{C}_m(\mathbb{Z})$ and the “left” estimate of $x_t$, $-L + 2m \le t \le L$ (utilizing observations $y_{\tau}$, $\tau \le t$),

$$ \hat{x}_t = \sum_{\tau=0}^{2m} \varphi_{\tau-m} y_{t-\tau} = \sum_{s=-m}^{m} \varphi_s y_{t-s-m} = [\varphi * (\Delta^m y)]_t. $$

The corresponding “right” estimate of $x_t$, $-L \le t \le L - 2m$ (utilizing observations $y_{\tau}$, $\tau \ge t$) writes

$$ \hat{x}_t = \sum_{\tau=0}^{2m} \varphi_{m-\tau} y_{t+\tau} = \sum_{s=-m}^{m} \varphi_s y_{t-s+m} = [\varphi * (\Delta^{-m} y)]_t. $$
Given a set $\mathcal{X}$ of signals, $m, n \in \mathbb{Z}_+$, observations $y_\tau$ for $|\tau| \le L = m + n$, and the target estimation domain $D_n$ of length $2n + 1$ (e.g., $D_n = \{-n, ..., n\}$ in the case of signal interpolation, or $D_n = \{-n+m, ..., n+m\}$ in the case of filtering), we quantify the accuracy of estimate $\hat{x}$ using two types of risks:

- maximal over $\mathcal{X}$ $\ell_2$ (integral) $\alpha$-risk: the smallest maximal over $x \in \mathcal{X}$ radius of $(1 - \alpha)$-confidence ball of $\| \cdot \|_{2}$-norm on $D_n$ centered at $\hat{x}$:

$$ \text{Risk}_{D_{n,2,\alpha}}(\hat{x}|\mathcal{X}) = \inf \left\{ r : \sup_{x \in \mathcal{X}} \text{Prob} \left\{ \left( \sum_{t \in D_n} |[\hat{x} - x]_t|^2 \right)^{1/2} \ge r \right\} \le \alpha \right\}; $$

- maximal over $\mathcal{X}$ pointwise $\alpha$-risk: the smallest maximal over $x \in \mathcal{X}$ and $t \in D_n$ $(1 - \alpha)$-confidence interval for $x_t$ centered at $\hat{x}_t$:

$$ \text{Risk}_{D_{n,\alpha}}(\hat{x}|\mathcal{X}) = \inf \left\{ r : \sup_{x \in \mathcal{X}} \text{Prob} \{ \|[\hat{x} - x]_t\| \ge r \} \le \alpha \quad \forall t \in D_n \right\}. $$

When $n = 0$ the estimation interval $D_n = \{t\}$ is a singleton, and the latter definition becomes that of the “usual” worst-case over $\mathcal{X}$ $(1 - \alpha)$-confidence interval for $x_t$:

$$ \text{Risk}_{\alpha}(\hat{x}_t|\mathcal{X}) = \inf \left\{ r : \sup_{x \in \mathcal{X}} \text{Prob} \{ \|[\hat{x} - x]_t\| \ge r \} \le \alpha \right\}. $$

# 3 Oracle inequalities for $\ell_2$-loss of adaptive estimators

## 3.1 Adaptive signal interpolation

**Adaptive recoveries** Given $m, n \in \mathbb{Z}_+$, $L = m + n$, and $\bar{\rho} > 0$, consider the optimization problem

$$ \min_{\varphi \in C_m(\mathbb{Z})} \|y - \varphi * y\|_{n,2}^2 \quad \text{subject to} \quad \|F_m[\varphi]\|_1 \le \frac{\bar{\rho}}{\sqrt{2m+1}}. \quad (\text{Con}) $$

Note that (Con) is clearly solvable; we denote $\hat{\varphi}_{\text{con}}$ its optimal solution and refer to

$$ \hat{x}_{\text{con}} = \hat{\varphi}_{\text{con}} * y $$

as the constrained (least-squares) estimate of $x$. Computing $\hat{\varphi}_{\text{con}}$ requires setting the problem parameter $\bar{\rho}$ which, ideally, would be set proportional to the $\ell_1$-norm of the DFT of some ideal (oracle) filter, or a non-trivial upper bound on it. Because this is not often possible in practice, we also consider the penalized estimator

$$ \hat{x}_{\text{pen}} = \hat{\varphi}_{\text{pen}} * y, $$

where, for $\lambda > 0$, $\hat{\varphi}_{\text{pen}} \in C_m(\mathbb{Z})$ is selected as an optimal solution to the (solvable) problem

$$ \min_{\varphi \in C_m(\mathbb{Z})} \|y - \varphi * y\|_{n,2}^2 + \sigma^2 \lambda^2 (2m + 1) \|F_m[\varphi]\|_1^2. \quad (\text{Pen}) $$
Instead of knowing $\bar{\sigma}$, some knowledge of noise variance $\sigma^2$ is required to tune this estimator. Hence, the practical recommendation is to use (Pen) when $\sigma^2$ is known or can be estimated.

**Oracle inequalities for $\ell_2$-loss** Despite striking similarity with Lasso estimators [38, 5, 2], the proposed estimates are of quite different nature. First of all, solving optimization problems (Con) and (Pen) allows to recover a filter but not the signal itself, and this filter is generally not sparse neither in time nor in Fourier domain (unless the signal to recover is a sum of harmonic oscillations with frequencies on the “DFT grid”). Second, the equivalent of “regression matrices” involved in these procedures cannot be assumed to satisfy any kind of “restricted incoherence” conditions usually imposed to prove statistical properties of “classical” $\ell_1$-recovery routines (see [4, Chapter 6] for a comprehensive overview of such conditions). Moreover, being constructed from noisy observations, these matrices depend on the noise, which poses some extra difficulties in the analysis of the adaptive estimates, in particular, leading to the necessity of imposing some restrictions on the signal class.

In what follows, when analyzing adaptive estimators we constrain the unknown signal $x$ on the interval $|\tau| \le L$ to be “close” to some shift-invariant linear subspace $S$. Specifically, consider the following assumption:

**Assumption 31 (Approximate local shift-invariance)** We suppose that $x \in C(Z)$ admits a decomposition

$$x = x^S + \varepsilon.$$

Here, $x^S \in S$ where $S$ is some (unknown) shift-invariant linear subspace of $C(Z)$ with $s := \dim(S) \le 2n + 1$, and $\varepsilon$ is bounded in the $\ell_2$-norm: for some $\varkappa \ge 0$ one has

$$\|\Delta^{-\tau}\varepsilon\|_{n,2} \le \varkappa\sigma, \quad |\tau| \le m. \qquad (10)$$

We denote $\mathcal{X}_{m,n}(s, \varkappa)$ the class of such signals.

**Remarks.** Assumption 31 merits some comments.

Observe that $\mathcal{X}_{m,n}(s, \varkappa)$ is in fact the subset of $C(Z)$ comprising sequences which are close, in the sense of (10), to all $s$-dimensional shift-invariant subspaces of $C(Z)$. Similarly to Assumption 31, signal “simplicity” as set by Definition 1 also postulates a kind of “local time-invariance” of the signal: it states that there exists a linear time-invariant filter which reproduces the signal “well” on a certain interval. However, the actual relationship between the two notions is rather intricate and will be discussed in Section 4.

Letting the signal to be close, in $\ell_2$-norm, to a shift-invariant subspace—instead of simply belonging to the subspace—extends the set of signals and allows to address nonparametric situations. As an example, consider discretizations over a uniform grid in $[0, 1]$ of functions from the Sobolev ball. Locally, such signals are close in $\ell_2$-norm to polynomials on the grid which satisfy a linear
homogeneous difference equation and hence belong to a shift-invariant subspace of small dimension [21]. Other classes of signals for which Assumption 31 holds are discretizations of complex sinusoids modulated with smooth functions and signals satisfying linear difference inequalities [21].

We now present oracle inequalities which relate the $l_2$-loss of adaptive filter $\hat{\varphi}$ with the best loss of any feasible solution $\varphi$ to the corresponding optimization problem. These inequalities, interesting for their own sake, are also operational when deriving bounds for the pointwise and $l_2$-losses of the proposed estimators. We first state the result for the constrained estimator.

**Theorem 1.** Let $s, m, n \in \mathbb{Z}_+$, $\varkappa \ge 0$. Suppose that $x \in \mathcal{X}_{m,n}(s, \varkappa)$ and $\varphi$ is feasible for (Con). Let $\hat{\varphi}_{\text{con}}$ be an optimal solution to (Con) with some $\bar{\varrho} > 1$, and let $\hat{x}_{\text{con}} = \hat{\varphi}_{\text{con}} * y$. Then for any $\alpha \in ]0, 1[$ it holds with probability at least $1 - \alpha$:

$$ \|x - \hat{x}_{\text{con}}\|_{n,2} \le \|x - \varphi * y\|_{n,2} + C\sigma \left( \bar{\varrho}(\kappa_{m,n}^2 + 1) \log\left[\frac{(m+n)/\alpha}{\bar{\varrho}\varkappa\sqrt{\log[1/\alpha]}} + s\right] \right)^{1/2} \quad (11) $$

where

$$ \kappa_{m,n} := \sqrt{\frac{2n+1}{2m+1}}. $$

The counterpart of Theorem 1 for the penalized estimator is as follows.

**Theorem 2.** Let $s, m, n \in \mathbb{Z}_+$, $\varkappa, \lambda > 0$. Suppose that $x \in \mathcal{X}_{m,n}(s, \varkappa)$ and $\varphi \in C_m(\mathbb{Z})$ with $\varrho(\varphi) = \sqrt{2m+1}\|F_m[\varphi]\|_1$. Let $\hat{\varphi}_{\text{pen}}$ be an optimal solution to (Pen). Then for any $\alpha \in ]0, 1[$ the estimate $\hat{x}_{\text{pen}} = \hat{\varphi}_{\text{pen}} * y$ satisfies with probability at least $1 - \alpha$:

$$ \|x - \hat{x}_{\text{pen}}\|_{n,2} \le \|x - \varphi * y\|_{n,2} + \sigma \left( \lambda \varrho(\varphi) + C_1 Q_1/\lambda + C_2 Q_2^{1/2}(\varphi) \right) \quad (12) $$

where

$$ Q_1 = Q_1(\varkappa, \kappa_{m,n}, \alpha) = (\kappa_{m,n}^2 + 1) \log\left[\frac{(m+n)/\alpha}{\varkappa\sqrt{\log[1/\alpha]}} + 1\right], \quad (13) $$

$$ Q_2(\varphi) = Q_2(\varphi, s, \varkappa, \alpha) = \varrho(\varphi) \log[1/\alpha] + \varkappa\sqrt{\log[1/\alpha]} + s. $$

In particular, when setting $\lambda = Q_1^{1/2}$ we obtain

$$ \|x - \hat{x}_{\text{pen}}\|_{n,2} \le \|x - \varphi * y\|_{n,2} + C\sigma \left( Q_1^{1/2} \varrho(\varphi) + Q_2^{1/2}(\varphi) \right). $$

One may observe that, ideally, $\bar{\varrho}$ in (Con) should be selected as

$$ \varrho(\varphi^o) = \sqrt{2m+1} \|F_m[\varphi^o]\|_1 $$

where $\varphi^o$ is an ideal “oracle filter,” while the penalty parameter in (Pen) would be set to $\lambda = [C_1Q_1/\varrho(\varphi^o)]^{1/2}$. These choices would result in the same remainder terms in (11) and (12) (order of $\sigma(\varrho(\varphi^o)(1+\varkappa)+s)^{1/2}$ up to logarithmic factors). Obviously, this choice cannot be implemented since the value $\varrho(\varphi^o)$ is unknown. Nevertheless, Theorem 2 provides us with an implementable choice of $\lambda$ that still results in an oracle inequality, at the expense of a larger remainder term which now scales as $\sigma[\varrho(\varphi^o)\sqrt{1+\varkappa} + \sqrt{s}]$.
## 3.2 Adaptive signal filtering

Here we consider the “left” version of the problem in which we are given observations ($y_\tau$) on the interval $-L \le \tau \le L$, and our objective is to build a (left) convolution estimate $\hat{x}_t = [\hat{\varphi} * (\Delta^m y)]_t$ of $x_t$, $t \in \{-L + 2m \le t \le L\}$, using an observation-driven filter $\hat{\varphi} \in C_m(\mathbb{Z})$. Clearly, the treatment of the “right” version of the problem is completely analogous up to obvious modifications. Let us consider the following counterparts of (Con) and (Pen):

$$ \min_{\varphi \in C_m(\mathbb{Z})} \|\Delta^{-m}(y - \varphi * \Delta^m y)\|_{n,2}^2 \quad \text{subject to} \quad \|F_m[\varphi]\|_1 \le \frac{\bar{\varrho}}{\sqrt{2m+1}}, \quad (\text{Con}^+) $$

$$ \min_{\varphi \in C_m(\mathbb{Z})} \|\Delta^{-m}(y - \varphi * \Delta^m y)\|_{n,2}^2 + \sigma^2 \lambda^2(m+1) \|F_m[\varphi]\|_1^2. \quad (\text{Pen}^+) $$

Same as in the interpolation setting, both problems are clearly solvable, so their respective optimal solutions $\hat{\varphi}_{\text{con}}$ and $\hat{\varphi}_{\text{pen}}$ are well-defined. A close inspection of the proofs of Theorems 1 and 2 shows that their results remain valid, with obvious adjustments, in the setting of this section. Namely, we have the following analog of those statements.

**Proposition 1** Let $s, m, n \in \mathbb{Z}_+$, $\varkappa \ge 0$, and $x \in \mathcal{X}_{m,n}(s, \varkappa)$; let $\alpha \in ]0, 1[$.

1. Let $\bar{\varrho} > 1$ be fixed, $\varphi$ be feasible to (Con$^+$), and let $\hat{x}_{\text{con}} = \hat{\varphi}_{\text{con}} * \Delta^m y$ where $\hat{\varphi}_{\text{con}}$ is an optimal solution to (Con$^+$); then with probability at least $1 - \alpha$ estimate $\hat{x}_{\text{con}}$ satisfies

$$ \|\Delta^{-m}(x - \hat{x}_{\text{con}})\|_{n,2} \le \|\Delta^{-m}(x - \varphi * \Delta^m y)\|_{n,2} \\ + C\sigma \left( \bar{\varrho}(\kappa_{m,n}^2 + 1) \log[(m+n)/\alpha] + \bar{\varrho}\varkappa\sqrt{\log[1/\alpha]} + s \right)^{1/2}. $$

2. Let $\varphi \in C_m(\mathbb{Z})$ with $\varrho(\varphi) = \sqrt{2m+1}\|F_m[\varphi]\|_1$, and let $\hat{x}_{\text{pen}} = \hat{\varphi}_{\text{pen}} * \Delta^m y$ where $\hat{\varphi}_{\text{pen}}$ is an optimal solution to (Pen$^+$) with $\lambda > 0$; then $\hat{x}_{\text{pen}}$ satisfies with probability at least $1 - \alpha$

$$ \|\Delta^{-m}(x - \hat{x}_{\text{pen}})\|_{n,2} \le \|\Delta^{-m}(x - \varphi * \Delta^m y)\|_{n,2} \\ + \sigma \left( \lambda \varrho(\varphi) + C_1 Q_1 / \lambda + C_2 Q_2^{1/2}(\varphi) \right) $$

where $Q_1$ and $Q_2(\varphi)$ are defined in (13).

## 4 Risk bounds for adaptive recovery under ASI

In order to transform the oracle inequalities of Theorems 1, 2 and Proposition 1 into risk bounds for adaptive recoveries, we need to establish bounds for oracle risks on the classes of approximately shift-invariant signals. We start with the interpolation setting.
## 4.1 Risk bounds for adaptive signal interpolation

Results of this section are direct corollaries of the following statement which may be of independent interest.

**Proposition 2** Let $\mathcal{S}$ be a shift-invariant subspace of $\mathbb{C}(\mathbb{Z})$ of dimension $s \le m + 1$. Then there exists a filter $\phi^o \in \mathbb{C}_m(\mathbb{Z})$ such that for all $x \in \mathcal{S}$ one has $x = \phi^o * x$ and

$$ \|\phi^o\|_2 \le \sqrt{\frac{2s}{2m+1}}. $$

In other words, signals $x \in \mathcal{S}$ are $(m, n, \rho, 0)$-simple in the sense of Definition 1, for any $n \in \mathbb{Z}_+$ and $m \ge s - 1$, with $\rho = \sqrt{2s}$ and $\theta = 0$.

When combined with Theorems 1 and 2, Proposition 2 implies the following bound on the integral risk of adaptive recovery.

**Proposition 3** Let $s, m, n \in \mathbb{Z}_+$, $m \ge 2s - 1$, $\varkappa \ge 0$, and let $D_n = \{-n, ..., n\}$.

(i) Assume that $\hat{x}_{\text{con}} = \hat{\varphi}_{\text{con}} * y$ where $\hat{\varphi}_{\text{con}}$ is an optimal solution to (Con) with some $\bar{\varrho} \ge 4s$. Then for any $\alpha \in ]0, 1/2]$

$$ \text{Risk}_{D_n, 2, \alpha}(\hat{x}_{\text{con}}|\mathcal{X}_{m,n}(s, \varkappa)) \le C \psi_{m,n}^{\alpha}(\sigma, s, \varkappa; \bar{\varrho}) $$

where

$$ \psi_{m,n}^{\alpha}(\sigma, s, \varkappa; \bar{\varrho}) = \sigma s(\kappa_{m,n} \sqrt{\log[1/\alpha]} + \varkappa) + \sigma(\bar{\varrho}(\kappa_{m,n}^2 + 1) \log[(m+n)/\alpha] + \bar{\varrho}\varkappa \sqrt{\log[1/\alpha]} + s)^{1/2}. $$

In particular, when $\bar{\varrho} \le C'$s is chosen in (Con) one obtains

$$ \text{Risk}_{D_n, 2, \alpha}(\hat{x}_{\text{con}}|\mathcal{X}_{m,n}(s, \varkappa)) \le C \bar{\psi}_{m,n}^{\alpha}(\sigma, s, \varkappa) \quad (14) $$

with

$$ \bar{\psi}_{m,n}^{\alpha}(\sigma, s, \varkappa) = \sigma s(\kappa_{m,n} \sqrt{\log[1/\alpha]} + \varkappa) + \sigma(s(\kappa_{m,n}^2 + 1) \log[(m+n)/\alpha] + s\varkappa\sqrt{\log[1/\alpha]} + s)^{1/2}. $$

(ii) Let $\lambda = Q_1^{1/2}$ with $Q_1$ as defined in (13), and let $\hat{x}_{\text{pen}} = \hat{\varphi}_{\text{pen}} * y$ where $\hat{\varphi}_{\text{pen}}$ is an optimal solution to (Pen). Then for any $\alpha \in (0, 1/2]$

$$ \text{Risk}_{D_n, 2, \alpha}(\hat{x}_{\text{pen}}|\mathcal{X}_{m,n}(s, \varkappa)) \le C \tilde{\psi}_{m,n}^{\alpha}(\sigma, s, \varkappa) $$

where

$$ \tilde{\psi}_{m,n}^{\alpha}(\sigma, s, \varkappa) = \sigma s(\kappa_{m,n} \sqrt{\log[1/\alpha]} + \varkappa) + \sigma s(\kappa_{m,n} + 1) \sqrt{\log[(m+n)/\alpha]}. $$

We are now ready to derive bounds for the pointwise risk of adaptive estimates described in the previous section. To establish such bounds we need to replace Assumption 31 with a somewhat stronger uniform analog.
**Assumption 41 (Approximate locally uniform shift-invariance)** Let $n \ge m \in \mathbb{Z}_+$. We suppose that $x \in \mathbb{C}(\mathbb{Z})$ admits a decomposition

$$x = x^S + \varepsilon.$$

Here $x^S \in S$ where $S$ is some (unknown) shift-invariant linear subspace of $\mathbb{C}(\mathbb{Z})$ with $s := \dim(S) \le 2n+1$, and $\varepsilon$ is uniformly bounded: for some $\varkappa \ge 0$ one has

$$|\varepsilon_{\tau}| \le \frac{\varkappa\sigma}{\sqrt{2n+1}}, \quad |\tau| \le n+m. \qquad (15)$$

We denote $\bar{\mathcal{X}}_{m,n}(s, \varkappa)$ the class of such signals.

Observe that if $x \in \bar{\mathcal{X}}_{m,n}(s, \varkappa)$ then also $x \in \mathcal{X}_{m,n}(s, \varkappa)$. Therefore, the bounds of Proposition 2 also hold true for the risk of adaptive recovery on $\bar{\mathcal{X}}_{m,n}(s, \varkappa)$. Furthermore, bound (15) of Assumption 41 now leads to the following bounds for pointwise risk of recoveries $\hat{x}_{\text{con}}$ and $\hat{x}_{\text{pen}}$.

**Proposition 4** Let $s, m, n \in \mathbb{Z}_+$ with $m \ge 2s-1$ and $n \ge \lfloor m/2 \rfloor$ (here $\lfloor \cdot \rfloor$ stands for the integer part), $\varkappa \ge 0$; let also $D_{n,m} = \{-n+\lfloor m/2 \rfloor, \dots, n-\lfloor m/2 \rfloor\}$.

(i) Let $\hat{x}_{\text{con}} = \hat{\varphi}_{\text{con}}*y$ where $\hat{\varphi}_{\text{con}}$ is an optimal solution to (Con) with $\bar{\varrho} \in [4s, Cs]$ for some $C \ge 4$.<fnref n="8" /> Then for any $\alpha \in [0, 1/2]$

$$\text{Risk}_{D_{n,m}, \alpha}(\hat{x}_{\text{con}}|\bar{\mathcal{X}}_{m,n}(s, \varkappa)) \le C' \bar{\zeta}_{m,n}^{\alpha}(\sigma, s, \varkappa) \qquad (16)$$

where

$$\begin{aligned} \bar{\zeta}_{m,n}^{\alpha}(\sigma, s, \varkappa) &= \sqrt{\frac{s}{2m+1}} \bar{\psi}_{m,n}^{\alpha}(\sigma, s, \varkappa) \\ &\quad + \frac{s\sigma}{\sqrt{2m+1}} \left( \sqrt{s\varkappa} + \sqrt{\log\left[\left(2m+1\right)/\alpha\right]} + \sqrt{s\log\left[1/\alpha\right]} \right) \\ &\le C'' \frac{s\sigma}{\sqrt{2m+1}} \left( \kappa_{m,n}\sqrt{s\log\left[1/\alpha\right]} + \varkappa + \kappa_{m,n}\sqrt{\log\left[(m+n)/\alpha\right]} \right). \end{aligned}$$

(ii) Let $\hat{x}_{\text{pen}} = \hat{\varphi}_{\text{pen}}*y$ where $\hat{\varphi}_{\text{pen}}$ is an optimal solution to (Pen) with $\lambda = Q_1^{1/2}$, $Q_1$ being defined in (13). Then for any $\alpha \in (0, 1/2]$

$$\text{Risk}_{D_{n,m}, \alpha}(\hat{x}_{\text{pen}}|\bar{\mathcal{X}}_{m,n}(s, \varkappa)) \le C \bar{\zeta}_{m,n}^{\alpha}(\sigma, s, \varkappa)$$

where

$$\begin{aligned} \bar{\zeta}_{m,n}^{\alpha}(\sigma, s, \varkappa) &= \sqrt{\frac{s}{2m+1}} \tilde{\psi}_{m,n}^{\alpha}(\sigma, s, \varkappa) \\ &\quad + \frac{s\sigma}{\sqrt{2m+1}} \left( \sqrt{s\varkappa} + \sqrt{\log\left[\left(2m+1\right)/\alpha\right]} + \sqrt{s\log\left[1/\alpha\right]} \right) \\ &\le \frac{C's\sigma}{\sqrt{2m+1}} \left( \sqrt{s} \left( \kappa_{m,n}\sqrt{\log\left[1/\alpha\right]} \right. \right. \\ &\qquad \left. \left. + \varkappa + \sqrt{\varkappa \log\left[1/\alpha\right]} \right) + \kappa_{m,n}\sqrt{\log\left[(m+n)/\alpha\right]} \right). \end{aligned}$$

<footnote n="8">⁸ For the sake of conciseness, here we only present the result for the constrained recovery with $\bar{\varrho} \asymp s$.</footnote>
Remark. The above bounds for the pointwise risk of adaptive estimates may be compared against available lower bound and bounds for the risk of the uniform-fit adaptive estimate in the case where the signal to recover is a sum of s complex sinusoids. In this situation, [15, Theorem 2] states the lower bound $c\sigma s\sqrt{\frac{\log m}{m}}$ for the pointwise risk of estimation with the upper bound

$$O\left(\sigma s^3 \log[s] \sqrt{\frac{\log m}{m}}\right)$$

up to a logarithmic in $\alpha$ factor (cf. [15, Section 4]). Because the signal in question belongs to a 2s-dimensional shift-invariant subspace of $C(\mathbb{Z})$, the bound on the pointwise risk in Proposition 4 results (recall that we are in the situation of $\varkappa = 0$) in the bound

$$O\left(\sigma s \sqrt{\frac{s + \log m}{m}}\right)$$

for adaptive estimates $\hat{x}_{\text{con}}$ and $\hat{x}_{\text{pen}}$ with significantly improved dependence on s.

## 4.2 Risk bounds for adaptive signal filtering

Our next goal is to bound the risk of the constrained and penalized adaptive filters. Recall that in order to obtain the corresponding bounds in the interpolation setting we first established the result of Proposition 2 which allows to bound the error of the oracle filter on any s-dimensional shift-invariant subspace of $C(\mathbb{Z})$. This result, along with oracle inequalities of Theorems 1 and 2, directly led us to the bounds for the risk of adaptive interpolation estimates. In order to reproduce the derivation in the previous section we first need to establish a fact similar to Proposition 2 which would guarantee existence of a predictive filter of small $\ell_2$-norm exactly reproducing all signals from any shift-invariant subspace of $C(\mathbb{Z})$. However, as we will see in an instant, the prediction case is rather different from the interpolation case: generally, a “good predictive filter” one may look for—a reproducing predictive filter of small norm—simply does not exist in the case of prediction. And analysis of situations where such filter does exist is quite different from the simple proof of Proposition 2. This is why, before returning to our original problem, it is useful to get a better understanding of the structure of shift-invariant subspaces of $C(\mathbb{Z})$.

**Characterizing shift-invariant subspaces of $C(\mathbb{Z})$** We start with the following

**Proposition 5** *Solution set of a homogeneous linear difference equation*

$$[p(\Delta)x]_t = \sum_{\tau=0}^{s} p_{\tau} x_{t-\tau} = 0, \quad t \in \mathbb{Z}, \qquad (17)$$
with a characteristic polynomial $p(z) = 1 + p_1 z + \dots + p_s z^s$ is a shift-invariant subspace of $C(\mathbb{Z})$ of dimension at most $s$.

Conversely, any shift-invariant subspace of $C(\mathbb{Z})$ of dimension $s$ is the solution set of a difference equation of the form (17) with $\deg(p) = s$; such polynomial is unique if normalized by $p(0) = 1$.

Recall that the set of solutions of equation (17) is spanned by exponential polynomials. Namely, let $z_k$, for $k = 1, \dots, r \le s$, be the distinct roots of $p(z)$ with corresponding multiplicities $m_k$, and let $\omega_k \in \mathbb{C}$ be such that $z_k = e^{-i\omega_k}$. Then solutions to (17) are exactly sequences of the form

$$x_t = \sum_{k=1}^{r} q_k(t) e^{i\omega_k t}$$

where $q_k(\cdot)$ are arbitrary polynomials of $\deg(q_k) = m_k - 1$. For instance, discrete-time polynomials of degree $s-1$ satisfy (17) with $p(z) = (1-z)^s$; another example is that of harmonic oscillations with given (all distinct) $\omega_1, \dots, \omega_s \in [0, 2\pi[$,

$$x_t = \sum_{k=1}^{s} q_k e^{i\omega_k t}, \quad q \in \mathbb{C}^s, \qquad (18)$$

which satisfy (17) with $p(z) = \prod_{k=1}^{s} (1 - e^{i\omega_k z})$. Thus, the set of complex harmonic oscillations with fixed frequencies $\omega_1, \dots, \omega_s$ is an $s$-dimensional shift-invariant subspace.

In view of the above, it is now clear that simply belonging to a shift-invariant subspace does not guarantee that a signal $x$ can be reproduced by a predictive filter of small $\ell_2$-norm. For instance, given $r \in \mathbb{C}$, $|r| > 1$, consider signals from the parametric family

$$\mathcal{X}_r = \{x \in \mathbb{C}(\mathbb{Z}) : x_{\tau} = \beta r^{\tau}, \beta \in \mathbb{C}\}.$$

Here $\mathcal{X}_r$ is a one-dimensional shift-invariant subspace of $C(\mathbb{Z})$—solution set of the equation $(1 - r\Delta)x = 0$. Clearly, for $x \in \mathcal{X}_r$, $x_t$ cannot be estimated consistently using noisy observations on the left of $t$ (cf. [35]), and we cannot expect a “good” predictive filter to exist for all $x \in \mathcal{X}_r$.

The above example is representative of the difficulties arising when predicting signals from shift-invariant subspaces of $C(\mathbb{Z})$: the characteristic polynomial of the associated difference equation is unstable—its root $z = 1/r$ lies inside the (open) unit disk. Therefore, to be able to build good “left” predictive filters, we need to reduce the class of signals to solutions of equations (17) with stable polynomials, with all roots lying outside the (open) unit disk—decaying exponents, harmonic oscillations, and their products. Note that if we are interested in estimating $x_t$ using only observations on the right of $t$, similar difficulties will arise when $x$ is a solution of a homogeneous linear difference equation with roots outside the closed unit disc—this situation is completely similar to the above, up to the inversion of the time axis.
**Adaptive prediction of generalized harmonic oscillations** The above discussion motivates our interest in a special family of shift-invariant subspaces which allow for constructing good “left” and “right” prediction filters—that of sets of solutions to linear homogeneous difference equations (17) with all roots $z_k$ on the unit circle, i.e., $z_k = e^{-i\omega_k}$ with real $\omega_k \in [0, 2\pi[, k = 1, ..., s$. In other words, we are interested in the class of solutions to equation (17) with $p(z) = \prod_{k=1}^{s}(1 - e^{i\omega_k}z)$ comprised of signals of the form

$$x_t = \sum_{k=1}^{r} q_k(t) e^{i\omega_k t}$$

where $\omega_1, ..., \omega_r \in [0, 2\pi[$ are distinct oscillation frequencies and $q_k(\cdot), k = 1, ..., r$, are (arbitrary) polynomials of degree $m_k - 1$, $m_k$ being the multiplicity of the root $z_k = e^{-i\omega_k}$ (i.e., $\sum_{k=1}^{r} m_k = s$). We call such signals generalized harmonic oscillations; we denote $\mathcal{H}_s[\omega]$ the space of such signals with fixed spectrum $\omega \in [0, 2\pi[^s$ and denote $\mathcal{H}_s$ the set of generalized harmonic oscillations with at most $s$ (unknown) frequencies.

The problem of constructing a predictive filter for signals from $\mathcal{H}_s[\omega]$ has already been studied in [22], where the authors proved (cf. [22, Lemma 6.1]) that for any $s \ge 1$, vector of frequencies $\omega_1, ..., \omega_s$, and $m$ large enough there is $\phi^o \in C_m(\mathbb{Z})$ such that $x = \phi^o * \Delta^m x$ and

$$\|\phi^o\|_2 \le C s^{3/2} \sqrt{\frac{\log[s+1]}{m}}. \qquad (19)$$

Here we utilize an improved version of that result.

**Proposition 6** Let $s \ge 1$ and $\omega \in [0, 2\pi[^s$. Then for any $m \ge cs^2 \log s$ there is a filter $\phi^o \in C_m(\mathbb{Z})$ which only depend on $\omega$ such that $x = \phi^o * \Delta^m x$ for all $x \in \mathcal{H}_s[\omega]$ and

$$\|\phi^o\|_2 \le C s \sqrt{\frac{\log m}{m}}. \qquad (20)$$

Let now $\mathcal{H}_{m,n}(s, \varkappa)$ be the set of signals $x \in C(\mathbb{Z})$ (locally) close to $\mathcal{H}_s$ in $l_2$-norm, i.e., which can be decomposed (cf. Assumption (31)) as

$$x = x^{\mathcal{H}} + \varepsilon$$

where $x^{\mathcal{H}} \in \mathcal{H}_s$ and

$$\|\Delta^{-\tau}\varepsilon\|_{n,2} \le \varkappa\sigma, \quad |\tau| \le m.$$

Equipped with the bound of Proposition 6, we can now derive risk bounds for adaptive predictive estimates on $\mathcal{H}_{m,n}(s, \varkappa)$. Specifically, following the proof of Propositions 3 and 4 we obtain the following corollaries of the oracle inequalities of Proposition 1.

**Proposition 7** Let $s, m, n \in \mathbb{Z}_+$, $m \ge cs^2 \log s$ with large enough $c$, and let $\varkappa \ge 0$.
(i) Let $\bar{\rho} = Cs^2 \log m$ with $C$ large enough, and let $\hat{x}_{\text{con}} = \hat{\varphi}_{\text{con}} * \Delta^m y$ where $\hat{\varphi}_{\text{con}}$ is an optimal solution to (Con$^+$); let also $D_n = \{-n+m, \dots, n+m\}$. Then for any $\alpha \in ]0, 1/2]$

$$ \text{Risk}_{D_n, 2, \alpha}(\hat{x}_{\text{con}} | \mathcal{H}_{m,n}(s, \varkappa)) \le C' \chi_{m,n}^{\alpha}(\sigma, s, \varkappa) $$

where

$$ \chi_{m,n}^{\alpha}(\sigma, s, \varkappa) = \sigma s^2 \log[m] (\kappa_{m,n} \sqrt{\log[1/\alpha]} + \varkappa) + \sigma s(\kappa_{m,n} + 1) \sqrt{\log[m] \log[(m+n)/\alpha]} $$

(ii) Let $\lambda = Q_1^{1/2}$ with $Q_1$ as in (13), and let $\hat{x}_{\text{pen}} = \hat{\varphi}_{\text{pen}} * \Delta^m y$ where $\hat{\varphi}_{\text{pen}}$ is an optimal solution to (Pen$^+$). Then for any $\alpha \in ]0, 1/2]$

$$ \text{Risk}_{D_n, 2, \alpha}(\hat{x}_{\text{pen}} | \mathcal{H}_{m,n}(s, \varkappa)) \le C \tilde{\chi}_{m,n}^{\alpha}(\sigma, s, \varkappa) $$

where

$$ \tilde{\chi}_{m,n}^{\alpha}(\sigma, s, \varkappa) = \sigma s^2 \log[m] \left( (\kappa_{m,n} + 1) \sqrt{\log[(m+n)/\alpha]} + \varkappa \right). $$

Next, in order to state the result describing pointwise risks of the proposed estimate we need to replace the class $\mathcal{H}_{m,n}(s, \varkappa)$ with the class of signals which are (locally) “uniformly” close to $\mathcal{H}_s$. Namely, let $\overline{\mathcal{H}}_{m,n}(s, \varkappa)$ be the set of signals $x \in \mathbb{C}(\mathbb{Z})$ which can be decomposed (cf. Assumption 41) as

$$ x = x^{\mathcal{H}} + \varepsilon $$

with $x^{\mathcal{H}} \in \mathcal{H}_s$ and

$$ |\varepsilon_{\tau}| \le \frac{\varkappa \sigma}{\sqrt{2n+1}}, \quad |\tau| \le n+m. $$

**Proposition 8** Let $s, m, n \in \mathbb{Z}_+$, $m \ge cs^2 \log s$ with large enough $c$, $n \ge m/2$, and let $\varkappa \ge 0$. We set $D_{n,m} = \{-n+2m, \dots, n+m\}$.

(i) Let $\hat{x}_{\text{con}} = \hat{\varphi}_{\text{con}} * \Delta^m y$ where $\hat{\varphi}_{\text{con}}$ is an optimal solution to (Con$^+$) where $\bar{\rho} = Cs^2 \log m$ with $C$ large enough. Then for any $\alpha \in ]0, 1/2]$

$$ \text{Risk}_{D_{n,m}, \alpha}(\hat{x}_{\text{con}} | \overline{\mathcal{H}}_{m,n}(s, \varkappa)) \le C' \nu_{m,n}^{\alpha}(\sigma, s, \varkappa) $$

where

$$ \nu_{m,n}^{\alpha}(\sigma, s, \varkappa) = s \sqrt{\frac{\log m}{m}} \chi_{m,n}^{\alpha}(\sigma, s, \varkappa) + \frac{\sigma s^3 (\log m)^{3/2}}{\sqrt{m}} (\varkappa + \log[1/\alpha]) \\ \le C'' \frac{\sigma s^3 (\log m)^{3/2}}{\sqrt{m}} (\varkappa + \log[1/\alpha]). $$

(ii) Let $\hat{x}_{\text{pen}} = \hat{\varphi}_{\text{pen}} * \Delta^m y$ where $\hat{\varphi}_{\text{pen}}$ is an optimal solution to (Pen$^+$) with $\lambda = Q_1^{1/2}$, $Q_1$ being defined in (13). Then for any $\alpha \in ]0, 1/2]$

$$ \text{Risk}_{D_{n,m}, \alpha}(\hat{x}_{\text{pen}} | \overline{\mathcal{H}}_{m,n}(s, \varkappa)) \le C \tilde{\nu}_{m,n}^{\alpha}(\sigma, s, \varkappa) $$
where

$$
\begin{align*}
\tilde{v}_{m,n}^{\alpha}(\sigma, s, \varkappa) &= s \sqrt{\frac{\log m}{m}} \tilde{\chi}_{m,n}^{\alpha}(\sigma, s, \varkappa) + \frac{\sigma s^3 (\log m)^{3/2}}{\sqrt{m}} (\varkappa + \log[1/\alpha]) \\
&\le C' \frac{\sigma s^3 (\log m)^{3/2}}{\sqrt{m}} (\varkappa + \log[(m+n)/\alpha]).
\end{align*}
$$

4.3 Harmonic oscillation denoising

To illustrate the results of the previous section, let us consider the problem
of recovery of generalized harmonic oscillations. Specifically, given observations
$y_{\tau} = x_{\tau} + \sigma \zeta_{\tau}, |\tau| \le L \in \mathbb{Z}_{+}$ we are to estimate the signal $x \in \mathcal{H}_s$. We measure
the statistical performance of the adaptive estimate $\hat{x}$ by the maximal over $\mathcal{H}_s$
integral $\alpha$-risk

$$
\text{Risk}_{D_L, 2, \alpha}(\hat{x}|\mathcal{H}_s) = \inf \left\{ r : \sup_{x \in \mathcal{H}_s} \text{Prob} \{ \|\hat{x} - x\|_{L,2} \ge r \} \le \alpha \right\}
$$

on the entire observation domain $D_L = \{-L, \dots, L\}$.

Note that if the frequencies were known, the ordinary least-squares estimate
would attain the risk $O(\sigma\sqrt{s})$ (up to a logarithmic factor in $\alpha$). When the
frequencies are unknown, the lower bound (see, e.g., [37, Theorem 2]) states
that

$$
\text{Risk}_{D_L, 2, \frac{1}{2}} (\hat{x} | \mathcal{H}_s) \ge c\sigma \sqrt{s \log L}. \quad (21)
$$

In the case where all frequencies are different, this bound is attained asymp-
totically by the maximum likelihood estimate [40, 36]. However, implementing
that estimate involves computing maximal likelihood estimate of $\omega$—a global
minimizer in the optimization problem

$$
\min_{\alpha \in \mathbb{C}^s, \omega \in \mathbb{R}^s} \left( \sum_{|\tau| \le L} \left| y_{\tau} - \sum_{k=1}^{s} \alpha_k e^{i\omega_k \tau} \right|^2 \right)^{1/2}
$$

and becomes numerically challenging already for very moderate values of s.
Moreover, the lower bound (21) is in fact attained by the *Atomic Soft Thresholding* (AST) estimate [1, 37]—which can be implemented efficiently—but only under the assumption that the frequencies {$\omega_1, \dots, \omega_s$} are well separated—precisely, when the *minimal frequency separation* in the wrap-around distance

$$
\delta_{\min} := \min_{1 \le j \ne k \le s} \min \{|\omega_j - \omega_k|, 2\pi - |\omega_j - \omega_k|\} \quad (22)
$$

satisfies $\delta_{\min} > \frac{2\pi}{2L+1}$ (cf. [37, Theorem 1]). To the best of our knowledge, the question whether there exists an efficiently implementable estimate matching the lower bound (21) in the general case is open.
A new approach to the problem was suggested in [15] where a uniform-fit adaptive estimate was used for estimation and prediction of (generalized) harmonic oscillations. That approach, using the bound (19) along with the estimate for the risk of the uniform-fit recovery, resulted in the final risk bound $O(\sigma s^3 \log[s] \log[L/\alpha])$.

Using the results in the preceding section we can now build an improved adaptive estimate. Here we assume that the number $s$ of frequencies (counting with their multiplicities) is known in advance, and utilize constrained recoveries (Con) and (Con$^+$) with the parameter $\bar{\varrho}$ selected using this information;<fnref n="9" /> note that $s$ is precisely the dimension of the shift-invariant subspace to which $x$ belongs, cf. Proposition 5. Let us consider the following procedure.

Choose $K \le L$, and divide the observation interval $D_L$ into the central segment $D_K = \{-K, \dots, K\}$ and left and right segments $D_- = \{-L, \dots, -K-1\}$ and $D_+ = \{K+1, \dots, L\}$. In what follows we assume that $L$ and $K$ are even and put $k = (L-K)/2$. Then we act as follows.

- Using the data $y_\tau$, $|\tau| \le L$ we compute an optimal solution $\hat{\varphi} \in C_{L-K}(\mathbb{Z})$ to the optimization problem (Con) with $m = L-K$, $n = K$, and $\bar{\varrho} = 4s$; for $t \in D_n$ we compute the interpolating (two-sided) estimate $\hat{x}_t = [\hat{\varphi} * y]_t$.

- We set $m = \lfloor(L+n)/2\rfloor$, $n = k$, $\bar{\varrho} = \bar{\varrho}^+ := 2C^2s^2 \log L$ where $C$ is as in the bound (20) of Proposition 6 and compute an optimal solution $\hat{\varphi}^+ \in C_m(\mathbb{Z})$ to the optimization problem (Con$^+$); for $t \in D_+$ we compute the left (one-sided) prediction $\hat{x}_t = [\hat{\varphi}^+ * \Delta^m y]_t$.

- We set $m = \lfloor(L+n)/n\rfloor$, $n = k$, $\bar{\varrho} = \bar{\varrho}^+$ and compute an optimal solution $\hat{\varphi}^- \in C_m(\mathbb{Z})$ to the “right” analog of (Con$^+$);<fnref n="10" /> for $t \in D_-$ we compute the right (one-sided) prediction $\hat{x}_t = [\hat{\varphi}^- * \Delta^{-m} y]_t$.

We select $K$ to minimize the “total” risk bound of the adaptive recovery over $D_L$.

We have the following corollary of the Propositions 3 and 7 in the present setting.

**Proposition 9** Suppose that $L \ge cs^2 \log s$ with large enough $c > 0$. Then, in the situation of this section, for any $\alpha \in ]0, 1/2]$

$$ \text{Risk}_{D_L, 2, \alpha}(\hat{x}|\mathcal{H}_s) \le C\sigma s^{3/2} \log[L/\alpha]. \quad (23) $$

*Remarks.* The risk bound (23), while significantly improved in terms of dependence on $s$ over the corresponding bound of [15], contains an extra factor $O(s\sqrt{\log L})$ when compared to the lower bound (21). It is unclear to us whether this factor can be reduced for an efficiently computable estimate.

<footnote n="9">⁹ It is worth mentioning that the AST estimate does not require the a priori knowledge of $s$; we can also get rid of this hypothesis when using the procedure which is adaptive to the unknown value of $s$, at the expense of an additional logarithmic factor.</footnote>

<footnote n="10">¹⁰ In the corresponding “right” optimization problem the “left prediction” $\varphi * \Delta^m y$ is replaced with the “right prediction” $\varphi * \Delta^{-m} y$. Therefore, the objective to be minimized in this case is $\|\Delta^m(y - \varphi * \Delta^{-m} y)\|_{n,2}$.</footnote>
It may be worth mentioning that when the frequency separation assumption holds, i.e., when $\delta_{\min} > \frac{2\pi}{2L+1}$ where the separation $\delta_{\min}$ is defined in (22), the above estimation procedure can be simplified: one can “remove” the central segment in the above construction only using left and right adaptive predictive estimates on two half-domains. The “total” $(1 - \alpha)$-reliable $l_2$-loss of the “simplified” adaptive recovery is then

$$O\left(\sigma\sqrt{s^2\log[1/\alpha] + s\log[L/\alpha]}\right).$$

The latter bound is a simple corollary of the oracle inequalities of Proposition 1 and the following statement.

**Lemma 1.** Let $m \in \mathbb{Z}_+$, $\nu > 1$, and let $\mathcal{H}_s[\omega]$ be the set of harmonic oscillations $x$ with the minimal frequency separation satisfying

$$\delta_{\min} \ge \frac{2\pi\nu}{2m+1}. \qquad (24)$$

Then there exists a filter $\phi^o \in \mathbb{C}_m(\mathbb{Z})$ satisfying $x = \phi^o * \Delta^m x$ for all $x \in \mathcal{H}_s[\omega]$ and such that

$$\|\phi^o\|_2 \le \sqrt{\frac{Qs}{2m+1}}, \quad \text{where} \quad Q = \frac{\nu+1}{\nu-1}.$$

In particular, whenever $\delta_{\min} \ge \frac{4\pi}{2m+1}$, one has

$$\|\phi^o\|_2 \le \sqrt{\frac{3s}{2m+1}}.$$

## Acknowledgements

Dmitrii Ostrovskii was supported by ERCIM Alain Bensoussan Scholarship while finalizing this project. Zaid Harchaoui received support from NSF CCF 1740551. Research of Anatoli Juditsky and Arkadi Nemirovski was supported by MIAI Grenoble Alpes (ANR-19-P3IA-0003).

## A Preliminaries

First, let us present some additional notation and technical tools to be used in the proofs.

### A.1 Additional notation

In what follows, $\mathrm{Re}(z)$ and $\mathrm{Im}(z)$ denote, correspondingly, the real and imaginary parts of $z \in \mathbb{C}$, and $\bar{z}$ denotes the complex conjugate of $z$. For a matrix $A$ with complex entries, $\bar{A}$ stands for the conjugation of $A$ (without transposition), $A^T$ for the transpose of $A$, and $A^H$ for its Hermitian conjugate. We denote $A^{-1}$ the
inverse of A when it exists. Tr(A) denotes the trace of a matrix A and det A its determinant; ||A||_F is the Frobenius norm of A, ||A||_* is the operator norm, and ||A|| is the nuclear norm. We also denote λ_max(A) and λ_min(A) the maximal and minimal eigenvalues of a Hermitian matrix A. For a ∈ C^n we denote Diag(a) the n × n diagonal matrix with diagonal entries a_i. We use notation ||x||^*_{n,p} for the ℓ_p-norm of the DFT of x so that

$$ ||x||^*_{n,p} = ||F_n[x]||_p = \left( \sum_{k=1}^{2n+1} |(F_n[x])_k|^p \right)^{1/p} $$

with the standard interpretation of ||·||^*_{n,∞}.

In what follows, we associate linear maps C_n(Z) → C_{n'}(Z) with matrices in C^{(2n+1)×(2n'+1)}.

**Convolution matrices.** We use the following matrix-vector representations of discrete convolution.

- Given y ∈ C(Z), we associate with it an (2n + 1) × (2m + 1) matrix

$$ T(y) = \begin{bmatrix} y_{-n+m} & \cdots & y_{-n} & \cdots & y_{-n-m} \\ \vdots & \ddots & \vdots & \ddots & \vdots \\ y_m & \cdots & y_0 & \cdots & y_{-m} \\ \vdots & \ddots & \vdots & \ddots & \vdots \\ y_{n+m} & \cdots & y_n & \cdots & y_{n-m} \end{bmatrix}, \qquad (25) $$

such that [φ*y]_{-n}^n = T(y)[φ]_{-m}^m for φ ∈ C_m(Z). Its squared Frobenius norm satisfies

$$ ||T(y)||_F^2 = \sum_{|\tau| \le m} ||\Delta^\tau y||_{n,2}^2. \qquad (26) $$

- Given φ ∈ C_m(Z), consider a (2n + 1) × (2m + 2n + 1) matrix

$$ M(\varphi) = \begin{bmatrix} \varphi_m \cdots \varphi_{-m} & 0 & \cdots & 0 \\ 0 & \varphi_m \cdots \varphi_{-m} & 0 & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & \cdots & 0 & \cdots & \varphi_{-m} \end{bmatrix}, \qquad (27) $$

such that for y ∈ C(Z) one has [φ*y]_{-n}^n = M(φ)[y]_{-m-n}^{m+n}, and

$$ ||M(\varphi)||_F^2 = (2n + 1) ||\varphi||_{m,2}^2. \qquad (28) $$
– Given $\varphi \in C_m(\mathbb{Z})$, consider the following circulant matrix of size $2m+2n+1$:

$$ C(\varphi) = \begin{bmatrix} \varphi_0 & \cdots & \varphi_{-m} & 0 & \cdots & 0 & \varphi_m & \cdots & \varphi_1 \\ \varphi_1 & \varphi_0 & \cdots & \varphi_{-m} & 0 & \cdots & 0 & \varphi_m & \cdots & \varphi_2 \\ \cdots & \ddots & \cdots & \cdots & \ddots & \cdots & \cdots & \ddots & \cdots & \cdots \\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\ 0 & \cdots & 0 & \varphi_m & \cdots & \varphi_0 & \cdots & \varphi_{-m} & 0 & 0 \\ \cdots & \ddots & \cdots & \cdots & \ddots & \cdots & \cdots & \ddots & \cdots & \cdots \\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\ \varphi_{-1} & \cdots & \varphi_{-m} & 0 & \cdots & 0 & \varphi_m & \cdots & \varphi_0 \end{bmatrix} . \quad (29) $$

Note that $C(\varphi)[y]_{-m-n}^{m+n}$ is the circular convolution of $[y]_{-m-n}^{m+n}$ and the zero-padded filter

$$ \tilde{\varphi} := [\varphi]_{-m-n}^{m+n} = [0; \dots; \varphi_{-m}; \dots; \varphi_m; 0; \dots; 0], $$

that is, convolution of the periodic extensions of $[y]_{-m-n}^{m+n}$ and $\tilde{\varphi}$ evaluated on $\{-m-n, \dots, m+n\}$. Hence, by the diagonalization property of the DFT operator one has

$$ C(\varphi) = \sqrt{2m+2n+1} F_{m+n}^{\mathrm{H}} \mathrm{diag}(F_{m+n}\tilde{\varphi}) F_{m+n} \quad (30) $$

where with some notational abuse we denote $F_n$ the matrix of DFT with the entries

$$ [F_n]_{kj} = \frac{1}{\sqrt{2n+1}} \exp \left( \frac{2\pi i(k-n)j}{2n+1} \right), \quad 1 \le k, j \le 2n+1. $$

Besides this, note that

$$ \|C(\varphi)\|_{\mathrm{F}}^{2} = (2m + 2n + 1)\|\varphi\|_{m,2}^{2}. $$

*Reformulation of approximate shift-invariance* The following reformulation of Assumption 31 will be convenient for our purposes.

There exists an s-dimensional vector subspace $S_n$ of $\mathbb{C}^{2n+1}$ and an idempotent Hermitian $(2n+1) \times (2n+1)$ matrix $\Pi_{S_n}$ of rank s—projector on $S_n$—such that

$$ \| (I_{2n+1} - \Pi_{S_n}) [\Delta^\tau x]_{-n}^n \|_2 = \| \Delta^\tau \varepsilon \|_{n,2} \le \sigma \varkappa, \quad |\tau| \le m \quad (31) $$

where $I_{2n+1}$ is the $(2n+1) \times (2n+1)$ identity matrix.
## A.2 Technical tools

Deviation bounds for quadratic forms. Let $\zeta \sim CN(0, I_n)$ be a standard complex Gaussian vector, meaning that $\zeta = \xi_1 + i\xi_2$ where $\xi_1$ and $\xi_2$ are two independent draws from $N(0, I_n)$. We use simple facts listed below.

- Due to the unitarity of the DFT, if $\zeta_{-n}^n \sim CN(0, I_{2n+1})$ we also have $F_n[\zeta] \sim CN(0, I_{2n+1})$.

- We use a simple bound

$$ \mathrm{Prob} \left\{ \|\zeta\|_{n,\infty} \le \sqrt{2 \log n + 2u} \right\} \ge 1 - e^{-u} \quad (32) $$

which can be verified directly using that $|\zeta_1|^2 \sim \chi_2^2$.

- The following deviation bounds for $\|\zeta\|_2^2 \sim \chi_{2n}^2$ are due to [26, Lemma 1]:

$$ \begin{aligned} \mathrm{Prob} \left\{ \frac{\|\zeta\|_2^2}{2} \le n + \sqrt{2nu} + u \right\} &\ge 1 - e^{-u}, \\ \mathrm{Prob} \left\{ \frac{\|\zeta\|_2^2}{2} \ge n - \sqrt{2nu} \right\} &\ge 1 - e^{-u}. \end{aligned} \quad (33) $$

By simple algebra we obtain an upper bound for the norm:

$$ \mathrm{Prob} \left\{ \|\zeta\|_2 \le \sqrt{2n} + \sqrt{2u} \right\} \ge 1 - e^{-u}. \quad (34) $$

- Further, let $K$ be an $n \times n$ Hermitian matrix with the vector of eigenvalues $\lambda = [\lambda_1; \dots; \lambda_n]$. Then the real-valued quadratic form $\zeta^H K \zeta$ has the same distribution as $\xi^T B \xi$, where $\xi = [\xi_1; \xi_2] \sim N(0, I_{2n})$, and $B$ is a real $2n \times 2n$ symmetric matrix with the vector of eigenvalues $[\lambda; \lambda]$. We have $\mathrm{Tr}(B) = 2\mathrm{Tr}(K)$, $\|B\|_F^2 = 2\|K\|_F^2$ and $\|B\| = \|K\| \le \|K\|_F$. Invoking again [26, Lemma 1] (a close inspection of the proof shows that the assumption of positive semidefiniteness can be relaxed), we have

$$ \mathrm{Prob} \left\{ \frac{\zeta^H K \zeta}{2} \le \mathrm{Tr}(K) + (u + \sqrt{2u}) \|K\|_F \right\} \ge 1 - e^{-u}. \quad (35) $$

Further, when $K$ is positive semidefinite, we have $\|K\|_F \le \mathrm{Tr}(K)$, whence

$$ \mathrm{Prob} \left\{ \frac{\zeta^H K \zeta}{2} \le \mathrm{Tr}(K)(1 + \sqrt{u})^2 \right\} \ge 1 - e^{-u}. \quad (36) $$

The following lemma, interesting in its own right, controls the inflation of the $l_1$-norm of the DFT of a zero-padded signal.

**Lemma 2.** Let $u \in C_m(\mathbb{Z})$ one has

$$ \|u\|_{m+n,1}^* \le \|u\|_{m,1}^* (1 + \kappa_{m,n}^2)^{1/2} [\log(m+n+1) + 3]. $$
*Proof.* It suffices to show that the bound

$$ \|u\|_{m+n,1}^* \le (1 + \kappa_{m,n}^2)^{1/2}[\log(m+n+1) + 3] $$

holds for all $u \in C_m(Z)$ such that $\|u\|_{m,1}^* \le 1$. We assume that $n \ge 1$, the lemma statement being trivial otherwise.

First of all, function $\|u\|_{m+n,1}^*$ is convex so its maximum over the set $u \in C_m(Z)$, $\|u\|_{m,1}^* \le 1$, is attained at an extreme point $u^j$ of the set given by $F_m[u^j] = e^{i\theta}e^j$ where $e^j$ is the $j$-th canonical basis vector and $\theta \in [0, 2\pi]$. Note that

$$ u_{\tau}^{j} = \frac{1}{\sqrt{2m+1}} \exp \left( i \left[ \theta + \frac{2\pi\tau j}{2m+1} \right] \right), $$

thus, for $\gamma_{m,n} := \sqrt{(2m + 2n + 1)(2m + 1)}$ we obtain

$$ \begin{aligned} \|u^j\|_{m+n,1}^* &= \frac{1}{\gamma_{m,n}} \sum_{k=1}^{2(m+n)+1} \left| \sum_{|\tau| \le m} \exp \left( 2\pi i \tau \left[ \frac{j}{2m+1} - \frac{k}{2m+2n+1} \right] \right) \right| \\ &= \frac{1}{\gamma_{m,n}} \sum_{k=1}^{2(m+n)+1} |\mathcal{D}_m(\omega_{jk})|, \end{aligned} $$

where

$$ \omega_{jk} := 2\pi \left[ \frac{j}{2m+1} - \frac{k}{2m+2n+1} \right] $$

and $\mathcal{D}_m(\cdot)$ is the Dirichlet kernel of order $m$:

$$ \mathcal{D}_m(\omega) := \begin{cases} \frac{\sin((2m+1)\omega/2)}{\sin(\omega/2)}, & \omega \ne 2\pi l, \\ 2m+1, & \omega = 2\pi l. \end{cases} $$

Hence,

$$ \gamma_{m,n} \|u^j\|_{m+n,1}^* \le \max_{\theta \in [0,2\pi]} \left\{ \sum_{k=1}^{2(m+n)+1} \left| \mathcal{D}_m \left( \frac{2\pi k}{2m+2n+1} + \theta \right) \right| \right\}. \quad (37) $$

For any $\theta \in [0, 2\pi]$, the summation in (37) is over the $\theta$-shifted regular $(2m + 2n + 1)$-grid on the unit circle. The contribution to the sum $\sum_{m,n} \Sigma_{m,n}(\theta)$ of the two closest to $x = 1$ points of this grid is at most $2(2m + 1)$. Using the bound

$$ \mathcal{D}_m(\omega) \le |\sin(\omega/2)|^{-1} \le \frac{\pi}{\min(\omega, 2\pi - \omega)}. $$

for the remaining points, and because $f(\omega) = \frac{\pi}{\omega}$ is decreasing on $[\frac{2\pi}{2m+2n+1}, \pi]$ (recall that $n \ge 1$) we arrive at the bound

$$ \Sigma_{m,n}(\theta) \le 2 \left( 2m + 1 + \sum_{k=1}^{m+n+1} \frac{2m + 2n + 1}{2k} \right). $$
Now, using the inequality $H_n \le \log n+1$ for the n-th harmonic number we arrive at the bound

$$ \begin{aligned} \Sigma_{m,n}(\theta) &\le 2(2m+1) + (2m+2n+1)[\log(m+n+1)+1] \\ &\le (2m+2n+1)[\log(m+n+1)+3] \end{aligned} $$

which implies the lemma.

□

## B Proof of Theorems 1 and 2

What is ahead. While it is difficult to describe informally the ideas underlying the proofs of the oracle inequalities, the “mechanics” of the proof of inequality (11), for instance, is fairly simple: for any $\varphi^o$ which is feasible to (Con) one has

$$ \|y - \hat{\varphi} * y\|_{n,2} \le \|y - \varphi^o * y\|_{n,2}, $$

and to prove the inequality (11) all we need to do is to bound tediously all terms of the remainder $\|x - \hat{\varphi} * y\|_{n,2} - \|x - \varphi^o * y\|_{n,2}$. This may be compared to bounding the $l_2$-loss of the Lasso regression estimate. Indeed, let $m = n$ for simplicity, and, given $y \in \mathbb{C}(\mathbb{Z})$, let $T(y)$ be the $(2n+1) \times (2n+1)$ “convolution matrix” as defined by (25) such that for $\varphi \in C_n(\mathbb{Z})$ one has $[\varphi*y]_0^n = T(y)[\varphi]_{-n}^n$. When denoting $f = F_n[\varphi]$, the optimization problem in (Con) can be recast as a “standard” $l_1$-constrained least-squares problem with respect to $f$:

$$ \min_{f \in \mathbb{C}^{2n+1}} \|y - A_n f\|_{n,2}^2 \quad \text{s.t.} \quad \|f\|_1 \le \frac{\bar{\varrho}}{\sqrt{2n+1}} \quad (38) $$

where $A_n = T(y)F_n^H$. Observe that $f^o = F_n[\varphi^o]$ is feasible for (38), so that

$$ \|y - A_n \hat{f}\|_{n,2}^2 \le \|y - A_n f^o\|_{n,2}^2, $$

where $\hat{f} = F_n[\hat{\varphi}]$, and

$$ \begin{aligned} & \|x - A_n \hat{f}\|_{n,2}^2 - \|x - A_n f^o\|_{n,2}^2 \\ &\le 2\sigma(\text{Re}\langle\zeta, x - A_n f^o\rangle_n - \text{Re}\langle\zeta, x - A_n \hat{f}\rangle_n) \\ &\le 2\sigma|\langle\zeta, A_n(f^o - \hat{f})\rangle_n| \le 2\sigma\|A_n^H[\zeta]_{-n}^n\|_{\infty}\|f^o - \hat{f}\|_1 \\ &\le 4\sigma\|A_n^H[\zeta]_{-n}^n\|_{\infty}\frac{\bar{\varrho}}{\sqrt{n+1}}. \end{aligned} $$

In the “classical” situation, where $[\zeta]_{-n}^n$ is independent of $A_n$ (see, e.g., [19]) one would have

$$ \|A_n^H[\zeta]_{-n}^n\|_{\infty} \le c_{\alpha} \sqrt{\log n} \max_j \|[A_n]_j\|_2 \le c_{\alpha} \sqrt{n \log n} \max_{i,j} |A_{ij}| $$

where $c_\alpha$ is a logarithmic in $\alpha^{-1}$ factor. This would rapidly lead to the bound equivalent to (11). The principal difference with the standard setting which is also the source of the main difficulty in the analysis of the properties of adaptive estimates is that the “regression matrix” $A_n$ in the case we are interested in is built of the noisy observations $[y]_{-n}^n$ and thus depends on $[\zeta]_{-n}^n$. In this situation, curbing the cross term is more involved and calls for Assumption 31.
## B.1 Proof of Theorem 1

1. Let $\varphi^o \in C_m(\mathbb{Z})$ be any filter satisfying the constraint in (Con). Then,

$$ \begin{aligned} \|x - \hat{\varphi} * y\|_{n,2}^2 &\le \|(1 - \varphi^o) * y\|_{n,2}^2 - \sigma^2 \|\zeta\|_{n,2}^2 - 2\sigma \operatorname{Re}\langle\zeta, x - \hat{\varphi} * y\rangle_n \\ &= \|x - \varphi^o * y\|_{n,2}^2 - 2 \underbrace{\sigma \operatorname{Re}\langle\zeta, x - \hat{\varphi} * y\rangle_n}_{\delta^{(1)}} \\ &\quad + 2 \underbrace{\sigma \operatorname{Re}\langle\zeta, x - \varphi^o * y\rangle_n}_{\delta^{(2)}}. \end{aligned} \quad (39) $$

Let us bound $\delta^{(1)}$. Denote for brevity $I := I_{2n+1}$, and recall that $\Pi_{S_n}$ is the projector on $S_n$ from (31). We have the following decomposition:

$$ \delta^{(1)} = \underbrace{\sigma \operatorname{Re}\langle[\zeta]_{-n}^n, \Pi_{S_n}[x - \hat{\varphi} * y]_{-n}^n\rangle}_{\delta_1^{(1)}} + \underbrace{\sigma \operatorname{Re}\langle[\zeta]_{-n}^n, (I - \Pi_{S_n})[x - \hat{\varphi} * x]_{-n}^n\rangle}_{\delta_2^{(1)}} \\ - \underbrace{\sigma^2 \operatorname{Re}\langle[\zeta]_{-n}^n, (I - \Pi_{S_n})[\hat{\varphi} * \zeta]_{-n}^n\rangle}_{\delta_3^{(1)}} $$

One can easily bound $\delta_1^{(1)}$ under the premise of the theorem:

$$ \begin{aligned} |\delta_1^{(1)}| &\le \sigma \|\Pi_{S_n}[\zeta]_{-n}^n\|_2 \|\Pi_{S_n}[x - \hat{\varphi} * y]_{-n}^n\|_2 \\ &\le \sigma \|\Pi_{S_n}[\zeta]_{-n}^n\|_2 \|x - \hat{\varphi} * y\|_{n,2}. \end{aligned} $$

Note that $\Pi_{S_n}[\zeta]_{-n}^n \sim \mathcal{CN}(0, I_s)$, and by (34) we have

$$ \operatorname{Prob}\{\|\Pi_{S_n}[\zeta]_{-n}^n\|_2 \ge \sqrt{2s} + \sqrt{2u}\} \le e^{-u}, $$

which gives the bound

$$ \operatorname{Prob}\{|\delta_1^{(1)}| \le \sigma \|x - \hat{\varphi} * y\|_{n,2} (\sqrt{2s} + \sqrt{2\log[1/\alpha_1]})\} \ge 1 - \alpha_1. \quad (40) $$

2. We are to bound the second term of (40). To this end, note first that

$$ \delta_2^{(1)} = \sigma \operatorname{Re}\langle[\zeta]_{-n}^n, (I - \Pi_{S_n})[x]_{-n}^n\rangle - \sigma \operatorname{Re}\langle[\zeta]_{-n}^n, (I - \Pi_{S_n})[\hat{\varphi} * x]_{-n}^n\rangle. $$

By (31), $\|(I - \Pi_{S_n})[x]_{-n}^n\|_2 \le \sigma\varkappa$, thus with probability $1 - \alpha$,

$$ |\langle[\zeta]_{-n}^n, (I - \Pi_{S_n})[x]_{-n}^n\rangle| \le \sigma\varkappa\sqrt{2\log[1/\alpha]}. \quad (41) $$

On the other hand, using the notation defined in (25), we have $[\hat{\varphi} * x]_{-n}^n = T(x)[\hat{\varphi}]_{-m}^m$, so that

$$ \langle[\zeta]_{-n}^n, (I - \Pi_{S_n})[\hat{\varphi} * x]_{-n}^n\rangle = \langle[\zeta]_{-n}^n, (I - \Pi_{S_n})T(x)[\hat{\varphi}]_{-m}^m\rangle. $$
Note that $[T(x)]_{\tau} = [\Delta^{\tau}x]_{-n}^{n}$ for the columns of $T(x)$, $|\tau| \le m$. By (31), we have

$$(I - \Pi_{S_n})T(x) = T(\varepsilon),$$

and by (26),

$$\|(I - \Pi_{S_n})T(x)\|_{F}^{2} = \|T(\varepsilon)\|_{F}^{2} = \sum_{|\tau| \le m} \|\Delta^{\tau}\varepsilon\|_{n,2}^{2} \le (2m + 1)\sigma^2 \varkappa^2.$$

Due to (36) we conclude that

$$\|T(x)^{\mathrm{H}}(I - \Pi_{S_n})[\zeta]_{-n}^{n}\|_{2}^{2} \le 2(2m + 1)\sigma^2 \varkappa^2 (1 + \sqrt{\log[1/\alpha]})^{2}$$

with probability at least $1 - \alpha$. Since

$$|\langle[\zeta]_{-n}^{n}, (I - \Pi_{S_n})T(x)[\hat{\varphi}]_{-m}^{m} \rangle| \le \frac{\bar{\varrho}}{\sqrt{2m+1}} \|T(x)^{\mathrm{H}}(I - \Pi_{S_n})[\zeta]_{-n}^{n}\|_{2},$$

we arrive at the bound with probability $1 - \alpha$:

$$|\langle[\zeta]_{-n}^{n}, (I - \Pi_{S_n})T(x)[\hat{\varphi}]_{-m}^{m} \rangle| \le \sqrt{2}\sigma\varkappa\bar{\varrho}(1 + \sqrt{\log[1/\alpha]}).$$

Along with (41) this results in the bound

$$\mathrm{Prob} \left\{ |\delta_2^{(1)}| \le \sqrt{2}\sigma^2\varkappa(\bar{\varrho} + 1)(1 + \sqrt{\log[1/\min(\alpha_2, \alpha_3)]}) \right\} \ge 1 - \alpha_2 - \alpha_3. (42)$$

3°. Let us rewrite $\delta_3^{(1)}$ as follows:

$$\delta_3^{(1)} = \sigma^2 \mathrm{Re} \langle [\zeta]_{-n}^n, (I - \Pi_{S_n}) M(\hat{\varphi}) [\zeta]_{-m-n}^{m+n} \rangle = \sigma^2 \mathrm{Re} \sigma^2 \langle [\zeta]_{-m-n}^{m+n}, Q M(\hat{\varphi}) [\zeta]_{-m-n}^{m+n} \rangle,$$

where $M(\hat{\varphi}) \in \mathbb{C}^{(2n+1) \times (2m+2n+1)}$ is defined by (27), and $Q \in \mathbb{C}^{(2m+2n+1) \times (2n+1)}$ is given by

$$Q = [O_{m,2n+1}; I - \Pi_{S_n}; O_{m,2n+1}]$$

(Hereafter we denote $O_{m,n}$ the $m \times n$ zero matrix.) Now, by the definition of $\hat{\varphi}$ and since the mapping $\varphi \mapsto M(\varphi)$ is linear,

$$\begin{align*}
\delta_3^{(1)} &= \frac{\sigma^2}{2} ([\zeta]_{-m-n}^{m+n})^{\mathrm{H}} \underbrace{(QM(\hat{\varphi}) + M(\hat{\varphi})^{\mathrm{H}}Q^{\mathrm{H}})}_{K_1(\hat{\varphi})} [\zeta]_{-m-n}^{m+n} \\
&\le \frac{\sigma^2 \bar{\varrho}}{2\sqrt{2m+1}} \max_{\substack{u \in \mathbb{C}_m(\mathbb{Z}), \\ \|u\|_{\infty,1} \le 1}} ([\zeta]_{-m}^{n})^{\mathrm{H}} K_1(u) [\zeta]_{-m-n}^{m+n} \\
&= \frac{\sigma^2 \bar{\varrho}}{\sqrt{2m+1}} \max_{|j| \le m} \max_{\theta \in [0, 2\pi]} \frac{1}{2} ([\zeta]_{-m-n}^{m+n})^{\mathrm{H}} K_1(e^{i\theta} u^j) [\zeta]_{-m-n}^{m+n},
\end{align*}$$

where $u^j \in \mathbb{C}_m(\mathbb{Z})$, and $[u^j]_{-m}^m = F_m^H e^j$, $e^j$ being the j-th canonic basis vector. Indeed, $([\zeta]_{-m-n}^{m+n})^{\mathrm{H}} K_1(u) [\zeta]_{-m-n}^{m+n}$ is clearly a convex function of the argument
$u$ as a linear function of $[\mathrm{Re}(u); \mathrm{Im}(u)];$ as such, it attains its maximum over the set

$$ \mathcal{B}_{m,1} = \{u \in \mathbb{C}_m(\mathbb{Z}) : \|u\|_{m,1}^* \le 1\} \quad (43) $$

at one of the extremal points $e^{i\theta}u^j$, $\theta \in [0, 2\pi]$, of this set. It can be directly verified that

$$ K_1(e^{i\theta}u) = K_1(u) \cos\theta + K_2(u) \sin\theta, $$

where the Hermitian matrix $K_2(u)$ is given by

$$ K_2(u) = i(QM(u) - M(u)^H Q^H). $$

Denoting $q_l^j(\zeta) = \frac{1}{2}([\zeta]_{-m-n}^{m+n})^H K_l(u^j) [\zeta]_{-m-n}^{m+n}$ for $l=1,2$, we have

$$ \begin{aligned} & \max_{\theta \in [0, 2\pi]} \frac{1}{2} ([\zeta]_{-m-n}^{m+n})^H K_1(e^{i\theta} u^j) [\zeta]_{-m-n}^{m+n} \\ &= \max_{\theta \in [0, 2\pi]} q_1^j(\zeta) \cos\theta + q_2^j(\zeta) \sin\theta \\ &= \sqrt{|q_1^j(\zeta)|^2 + |q_2^j(\zeta)|^2} \le \sqrt{2} \max(|q_1^j(\zeta)|, |q_2^j(\zeta)|). \end{aligned} \quad (44) $$

Using (28), by simple algebra we get for $l=1,2$:

$$ \mathrm{Tr}[K_l(u^j)^2] \le 4 \mathrm{Tr}[M(u^j)M(u^j)^H] = 4(2n+1)\|u^j\|_{m,2}^2 \le 4(2n+1). $$

Now let us bound $\mathrm{Tr}[K_l(u)]$, $l=1,2$, on the set, $\mathcal{B}_{m,1}$ cf. (43). One can verify that for the circulant matrix $C(u)$, cf. (29), it holds:

$$ QM(u) = RC(u), $$

where $R = QQ^H$ is an $(2m+2n+1) \times (2m+2n+1)$ projection matrix of rank $s$ defined by

$$ R = \begin{bmatrix} O_{m,m} & O_{m,n+1} & O_{m,m} \\ \hline O_{n+1,m} & I - \Pi_{S_n} & O_{n+1,m} \\ \hline O_{m,m} & O_{m,n+1} & O_{m,m} \end{bmatrix} $$

Hence, we can bound $\mathrm{Tr}[K_l(u)]$, $l=1,2$, as follows:

$$ \begin{aligned} |\mathrm{Tr}[K_l(u)]| & \le 2 |\mathrm{Tr}[RC(u)]| \le 2 \|R\|_* \|C(u)\| \\ & \le 2 \|C(u)\| = 2\sqrt{2m+2n+1} \|\tilde{u}\|_{m+n,1}^*, \end{aligned} \quad (45) $$

where in the last transition we used the Fourier diagonalization property (30). Recall that $u \in \mathbb{C}_m(\mathbb{Z})$, hence $F_{m+n}[u]$ is the Discrete Fourier Transform of the zero-padded filter

$$ \tilde{u} = [0; \dots; 0; [u]_{-m}^m; 0; \dots; 0] \in \mathbb{C}^{2m+2n+1}. $$
Now combining Lemma 2 with (45) we arrive at

$$|\mathrm{Tr}[K_l(u^j)]| \le 2\sqrt{2m+1}(\kappa_{m,n}^2+1)(\log[2m+2n+1]+3), \quad l=1,2.$$

By (35) we conclude that for any fixed pair $(l, j) \in \{1, 2\} \times \{-m, \dots, m\}$, with probability $\ge 1 - \alpha$,

$$|q_l^j(\zeta)| \le |\mathrm{Tr}[K_l(u^j)]| + \|K_l(u^j)\|_F (1 + \sqrt{\log[2/\alpha]})^2.$$

With $\alpha_0 = 2(2m+1)\alpha$, by the union bound together with (43) and (44) we get

$$\mathrm{Prob} \left\{ \delta_3^{(1)} \le 2\sqrt{2}\sigma^2 \bar{\varrho} \left[ (\kappa_{m,n}^2 + 1)(\log[2m + 2n + 1] + 3) + \kappa_{m,n} \left(1 + \sqrt{\log[4(2m + 1)/\alpha_0]}\right)^2 \right] \right\} \ge 1 - \alpha_0. \quad (46)$$

$4^o$. Bounding $\delta^{(2)}$ is relatively easy since $\varphi^o$ does not depend on the noise. We decompose

$$\delta^{(2)} = \sigma \mathrm{Re}\langle \zeta, x - \varphi^o * x \rangle_n - \sigma^2 \mathrm{Re}\langle \zeta, \varphi^o * \zeta \rangle_n.$$

Note that $\mathrm{Re}\langle \zeta, x - \varphi^o * x \rangle_n \sim \mathcal{N}(0, \|x - \varphi^o * x\|_{n,2}^2)$, therefore, with probability $\ge 1 - \alpha$,

$$\mathrm{Re}\langle \zeta, x - \varphi^o * x \rangle_n \le \sqrt{2\log[1/\alpha]} \|x - \varphi^o * x\|_{n,2}. \quad (47)$$

On the other hand, defining

$$\varrho = \sqrt{2m+1} \|\varphi^o\|_{m,1}^*,$$

we have

$$\begin{aligned} \|x - \varphi^o * x\|_{n,2} &\le \|x - \varphi^o * y\|_{n,2} + \sigma \|\varphi^o * \zeta\|_{n,2} \\ &\le \|x - \varphi^o * y\|_{n,2} + \sqrt{2\sigma \varrho \kappa_{m,n}} (1 + \sqrt{\log[1/\alpha]}) \end{aligned} \quad (48)$$

with probability $1 - \alpha$. Indeed, one has

$$\|\varphi^o * \zeta\|_{n,2}^2 = \|M(\varphi^o)[\zeta]_{-m-n}^{m+n}\|_2^2,$$

where for $M(\varphi^o)$ by (28) we have

$$\|M(\varphi^o)\|_F^2 = (2n+1)\|\varphi^o\|_{m,2}^2 \le \kappa_{m,n}^2 \varrho^2. \quad (49)$$

Using (36) we conclude that, with probability at least $1 - \alpha$,

$$\|\varphi^o * \zeta\|_{n,2}^2 \le 2\kappa_{m,n}^2 \varrho^2 (1 + \sqrt{\log[1/\alpha]})^2, \quad (50)$$

which implies (48). Using (47) and (48), we get that with probability at least $1 - \alpha_4 - \alpha_5$,

$$\mathrm{Re}\langle \zeta, x - \varphi^o * x \rangle_n \le \sqrt{2\log[1/\min(\alpha_4, \alpha_5)]} \|x - \varphi^o * y\|_{n,2}.$$
$$
\begin{align}
&+\sqrt{2\sigma\varrho\kappa_{m,n}}(1 + \sqrt{\log[1/\min(\alpha_4, \alpha_5)]}) \nonumber \\
&\le \|x - \varphi^o * y\|_{n,2} \sqrt{2\log[1/\min(\alpha_4, \alpha_5)]} \nonumber \\
&\quad + 2\sigma\varrho\kappa_{m,n}(1 + \sqrt{\log[1/\min(\alpha_4, \alpha_5)]})^2. \tag{51}
\end{align}
$$

Now, the (indefinite) quadratic form

$$
\mathrm{Re}\langle\zeta, \varphi^o * \zeta\rangle_n = \frac{1}{2}([\zeta]_{-m-n}^{m+n})^H K_0(\varphi^o)[\zeta]_{-m-n}^{m+n},
$$

where

$$
K_0(\varphi^o) = [O_{m,2m+2n+1}; M(\varphi^o); O_{m,2m+2n+1}] + [O_{m,2m+2n+1}; M(\varphi^o); O_{m,2m+2n+1}]^H,
$$

whence (cf. 3°)

$$
| \mathrm{Tr}[K_0(\varphi^o)] | \le 2(2n+1) |\varphi_0^o|
$$

Let us bound $|\varphi_0^o|$. Let $e^0$ be the discrete centered Dirac vector in $\mathbb{R}^{2m+1}$, and
note that $\|F_m[e^0]\|_{\infty} = 1/\sqrt{2m+1}$. Then,

$$
|\varphi_m^o| = |\langle [\varphi^o]_{-m}^m, e^0 \rangle| \le \|\varphi^o\|_{m,1}^* \|F_m[e^0]\|_{\infty} \le \frac{\varrho}{2m+1},
$$

whence $|\mathrm{Tr}[K_0(\varphi^o)]| \le 2\kappa_{m,n}^2 \varrho$. On the other hand, by (49),

$$
\|K_0(\varphi^o)\|_{\mathrm{F}}^2 \le 4 \|M(\varphi^o)\|_{\mathrm{F}}^2 \le 4\kappa_{m,n}^2 \varrho^2.
$$

Hence by (35),

$$
\text{Prob} \left\{ -\text{Re}\langle \zeta, \varphi^o * \zeta \rangle_n \le 2\kappa_{m,n}^2 \varrho + 2\kappa_{m,n}\varrho \left(1 + \sqrt{2\log[1/\alpha_6]}\right)^2 \right\} \ge 1 - \alpha_6. \tag{52}
$$

$5^o$. Let us combine the bounds obtained in the previous steps with initial
bound (39). For any $\alpha \in (0,1]$, putting $\alpha_i = \alpha/4$ for $i = 0,1,6$, and $\alpha_j = \alpha/16$,
$2 \le j \le 5$, by the union bound we get that with probability $\ge 1 - \alpha$,

$$
\begin{align*}
& \|x - \hat{\varphi} * y\|_{n,2}^2 \le \|x - \varphi^o * y\|_{n,2}^2 + 2\delta^{(2)} - 2\delta^{(1)} \\
& \quad \text{[by (51)]} \le \|x - \varphi^o * y\|_{n,2}^2 + 2\sigma\|x - \varphi^o * y\|_{n,2} \sqrt{2\log[16/\alpha]} \\
& \quad \text{[by (51)-(52)]} \quad + 4\sigma^2 \varrho \left[ \kappa_{m,n}^2 + 2\kappa_{m,n} \left(1 + \sqrt{2\log[16/\alpha]}\right)^2 \right] \\
& \quad \text{[by (40)]} \quad + 2\sigma \|x - \hat{\varphi} * y\|_{n,2} \left(\sqrt{2s} + \sqrt{2\log[16/\alpha]}\right) \\
& \quad \text{[by (42)]} \quad + 2\sqrt{2}\sigma^2 (\bar{\alpha} + 1) \left(1 + \sqrt{\log[16/\alpha]}\right) \varkappa \\
& \quad \text{[by (46)]} \quad + 4\sqrt{2}\sigma^2 \bar{\alpha} \left[ (\kappa_{m,n}^2 + 1)(\log[2m + 2n + 1] + 3) \right. \\
& \qquad \left. \qquad + \kappa_{m,n} \left(1 + \sqrt{\log[16(m+1)/\alpha]}\right)^2 \right] \tag{53}
\end{align*}
$$
Now, denote $c_\alpha := \sqrt{2\log[16/\alpha]}$ and let

$$u(\alpha) = 2(\sqrt{2} + c_{\alpha}), \qquad (54)$$

$$v_1(\alpha) = 4 \left[ \kappa_{m,n}^2 + 2\kappa_{m,n} (1 + c_\alpha)^2 \right], \qquad (55)$$

$$v_2(\alpha) = 4\sqrt{2} \left[ (\kappa_{m,n}^2 + 1)(\log[2m + 2n + 1] + 3) + \kappa_{m,n} \left(1 + \sqrt{\log[16(2m + 1)/\alpha]}\right)^2 \right]. \qquad (56)$$

In this notation, (53) becomes

$$\begin{aligned} \|x - \hat{\varphi} * y\|_{n,2}^2 &\le \|x - \varphi^o * y\|_{n,2}^2 \\ &\quad + 2\sigma(\sqrt{2s} + c_\alpha) (\|x - \hat{\varphi} * y\|_{n,2} + \|x - \varphi^o * y\|_{n,2}) \\ &\quad + u(\alpha)\sigma^2(\bar{\varrho} + 1)\kappa + (v_1(\alpha) + v_2(\alpha))\sigma^2\bar{\varrho}, \end{aligned} \qquad (57)$$

which implies, by completing the squares, that

$$\|x - \hat{\varphi} * y\|_{n,2} \le \|x - \varphi^o * y\|_{n,2} + 2\sigma(\sqrt{2s} + c_\alpha) \\ + \sigma\sqrt{u(\alpha)(\bar{\varrho} + 1)\kappa + (v_1(\alpha) + v_2(\alpha))\bar{\varrho}}.$$

Let us simplify this bound. Note that

$$u(\alpha) \le 4c_{\alpha}, \qquad (58)$$

while on the other hand,

$$\begin{aligned} v_1(\alpha) + v_2(\alpha) &\le 4\sqrt{2}(\kappa_{m,n}^2 + 1)(\log[2m + 2n + 1] + 4) \\ &\quad + 4.5(4\sqrt{2} + 8)\kappa_{m,n}\log[16(2m + 1)/\alpha] \\ &\le 8(1 + 4\kappa_{m,n})^2\log[110(m + n + 1)/\alpha]. \end{aligned} \qquad (59)$$

We finally arrive at

$$\|x - \hat{\varphi} * y\|_{n,2} \le \|x - \varphi^o * y\|_{n,2} + 2\sigma \left( \sqrt{\bar{\varrho}V_\alpha} + \sqrt{(\bar{\varrho} + 1)c_\alpha\kappa} + \sqrt{2s} + c_\alpha \right) \qquad (60)$$

where we put

$$V_\alpha := 2(1 + 4\kappa_{m,n})^2 \log[110(m + n + 1)/\alpha]. \qquad (61)$$

The bound (11) of the theorem follows from (60) after straightforward simplifications. $\square$

## B.2 Proof of Theorem 2

Denote $\hat{\varrho} = \sqrt{2m+1}\|\hat{\varphi}\|_{m,1}^*$, and let $\varrho = \varrho(\varphi^o) = \sqrt{2m+1}\|\varphi^o\|_{m,1}^*$ for some $\varphi^o \in C_m(\mathbb{Z})$. In the sequel, we use the notation defined in the proof of Theorem 1. We have the following counterpart of (39):

$$\|x - \hat{\varphi} * y\|_{n,2}^2 + \lambda^2 \sigma^2 \bar{\varrho}^2 \le \|x - \varphi^o * y\|_{n,2}^2 - 2\delta^{(1)} + 2\delta^{(2)} + \lambda^2 \sigma^2 \bar{\varrho}^2.$$
When repeating steps 1º–4º of the proof of Theorem 1 we obtain a counterpart of (57):

$$
\begin{align}
\|x - \hat{\varphi} * y\|_{n,2}^2 + \lambda^2 \sigma^2 \hat{\varrho}^2 \le \|x - \varphi^o * y\|_{n,2}^2 &+ 2\sigma(\|x - \varphi^o * y\|_{n,2} \nonumber \\
& + \|x - \hat{\varphi} * y\|_{n,2})(\sqrt{2s} + c_\alpha) + u(\alpha)\sigma^2 \varkappa + v_1(\alpha)\sigma^2 \varrho \nonumber \\
& + \lambda^2 \sigma^2 \varrho^2 + [u(\alpha)\varkappa + v_2(\alpha)] \sigma^2 \hat{\varrho} \tag{62}
\end{align}
$$

with $u(\alpha)$, $v_1(\alpha)$, and $v_2(\alpha)$ given by (54)–(56). We now consider two cases as follows.

(a) First, assume that

$$
\begin{equation}
\begin{split}
\|x - \hat{\varphi} * y\|_{n,2}^2 \le \|x - \varphi^o * y\|_{n,2}^2 &+ 2\sigma(\|x - \varphi^o * y\|_{n,2} + \|x - \hat{\varphi} * y\|_{n,2})(\sqrt{2s} + c_\alpha) \\
& + u(\alpha)\sigma^2 \varkappa + v_1(\alpha)\sigma^2 \varrho + \lambda^2 \sigma^2 \varrho^2.
\end{split}
\tag{63}
\end{equation}
$$

In this case, clearly,

$$
\begin{align}
\|x - \hat{\varphi} * y\|_{n,2} &\le \|x - \varphi^o * y\|_{n,2} + 2\sigma(\sqrt{2s} + c_\alpha) \nonumber \\
&\quad + \sqrt{u(\alpha)\sigma^2\varkappa + v_1(\alpha)\sigma^2\varrho + \lambda^2\sigma^2\varrho^2} \nonumber \\
&\le \|x - \varphi^o * y\|_{n,2} + 2\sigma(\sqrt{2s} + c_\alpha) + \sigma(\sqrt{u(\alpha)\varkappa + v_1(\alpha)\varrho} + \lambda\varrho) \tag{64}
\end{align}
$$

(b) Suppose, on the contrary, that (63) does not hold, we then conclude from (62)
that

$$
\hat{\varrho} \le \lambda^{-2}(u(\alpha)\varkappa + v_2(\alpha)),
$$

and

$$
u(\alpha)\hat{\varrho}\varkappa + v_2(\alpha)\hat{\varrho} \le \lambda^{-2}(u(\alpha)\varkappa + v_2(\alpha))^2.
$$

When substituting the latter bound into (62), we obtain the bound

$$
\|x - \hat{\varphi} * y\|_{n,2} \le \|x - \varphi^o * y\|_{n,2} + 2\sigma(\sqrt{2s} + c_\alpha) \\
\qquad + \sigma(\sqrt{u(\alpha)\varkappa + v_1(\alpha)\varrho} + \lambda^{-1}(u(\alpha)\varkappa + v_2(\alpha)) + \lambda\varrho),
$$

which also holds in the case of (a) due to (64).

Finally, using (58), (59), and the bound

$$
v_1(\alpha) \le 4(1 + \kappa_{m,n})^2(1 + c_\alpha)^2
$$

which directly follows from (55), we conclude that

$$
\|x - \hat{\varphi} * y\|_{n,2} \le \|x - \varphi^o * y\|_{n,2} \\
+ \sigma(\lambda\varrho + 4\lambda^{-1}(c_\alpha\varkappa + V_\alpha)) + 2\sigma\left(\sqrt{\varrho W_\alpha} + \sqrt{c_\alpha\varkappa} + \sqrt{2s} + c_\alpha\right)
$$

with $V_\alpha$ given by (61), and $W_\alpha = (1 + \kappa_{m,n})^2(1 + c_\alpha)^2$. The bound (12) of the theorem follows by a straightforward simplification of the above bound. $\square$
# C Proofs for Section 4

## C.1 Proof of Proposition 2

Let $\Pi_{S_m}$ be the $m+1$-dimensional Euclidean projection matrix on the subspace $S_m \subset \mathbb{C}^{m+1}$ of dimension $\le s$ (in fact, this subspace is exactly of dimension $s$) generated by vectors $x_0^m$ for $x \in S$ (one may set, for instance, $\Pi_{S_m} = Z_m(Z_m^H Z_m)^{-1} Z_m^H$, $Z_m = [z_1, ..., z_{\dim(S_m)}]$, where $z_i$ are linearly independent and such that $z_i = [x_i]_0^m$ with $x_i \in S$). Since $\dim(S) \le s$, one has

$$ \|\Pi_{S_m}\|_2^2 = \mathrm{Tr}(\Pi_{S_m}) \le s. $$

Thus, there is a $j \in \{0, ..., m\}$ such that the $j+1$-th column $r = [\Pi_{S_m}]_j$ of $\Pi_{S_m}$ satisfies

$$ \|r\|_2 \le \sqrt{\frac{s}{m+1}} \le \sqrt{\frac{2s}{2m+1}}, $$

and, because $\Pi_{S_m}$ is the projector on $S_m$ one has $x_j - \langle r, x_0^m \rangle = 0$ for all $x \in S$. Hence, using that $\Delta S = S$ we obtain for all $\tau \in \mathbb{Z}$

$$ x_{\tau} - \langle r, x_{\tau-j+m} \rangle = 0, \quad \tau \in \mathbb{Z}. $$

Finally, let $\phi^o \in \mathbb{C}_m(\mathbb{Z}) = \Delta^{-j}\phi(r)$ where $\phi(r)$ is the inverse slicing map of $\tilde{r} \in \mathbb{C}^{m+1}$ such that $\tilde{r}_i = r_{m+1-i}$. Obviously, $\phi^o \in \mathbb{C}_m(\mathbb{Z})$; on the other hand,

$$ \|\phi^o\|_2 \le \sqrt{\frac{2s}{2m+1}} \quad \text{and} \quad x_t - [\phi^o * x]_t = 0, \quad \forall t \in \mathbb{Z}. \quad \square $$

## C.2 Proof of Proposition 3

In the proofs to follow, the following simple statement will be of use.

### Lemma 3.

(i) Suppose that for all $z \in S$ there is a filter $\phi^o \in \mathbb{C}_m(\mathbb{Z})$ such that $z = \phi^o * z$ with $\|\phi^o\|_2 \le \frac{\rho}{\sqrt{2m+1}}$ for some $\rho \ge 1$. Then for all $x \in \mathcal{X}_{m,n}(s, \varkappa)$ one has

$$ \|x - \phi^o * x\|_{n,2} \le \sigma\varkappa(1 + \rho). \qquad (65) $$

Moreover, if $x \in \bar{\mathcal{X}}_{m,n}(s, \varkappa)$ then

$$ \|x - \phi^o * x\|_{n,\infty} \le \frac{\sigma\varkappa}{\sqrt{2m+1}}(1 + \rho\kappa_{n,m}). \qquad (66) $$

(ii) Similarly, assume that for all $z \in S$ there is $\phi^o \in \mathbb{C}_m(\mathbb{Z})$ such that $z = \phi^o * \Delta^m z$ and $\|\phi^o\|_2 \le \frac{\rho}{\sqrt{2m+1}}$ for some $\rho \ge 1$. Then for all $x \in \mathcal{X}_{m,n}(s, \varkappa)$ one has

$$ \|\Delta^{-m}(x - \phi^o * \Delta^m x)\|_{n,2} \le \sigma\varkappa(1 + \rho). $$

Furthermore, if $x \in \bar{\mathcal{X}}_{m,n}(s, \varkappa)$ then

$$ \|\Delta^{-m}(x - \phi^o * \Delta^m x)\|_{n,\infty} \le \frac{\sigma\varkappa}{\sqrt{2m+1}}(1 + \rho\kappa_{n,m}). $$
*Proof of the lemma.* Here we prove the first statement of the lemma, proof of the second one being completely analogous. Recall that any $x \in \mathcal{X}_{m,n}(s, \varkappa)$ can be decomposed as in $x = x^S + \varepsilon$ where $x^S \in \mathcal{S}$ and $\|\Delta^\tau \varepsilon\|_{n,2} \le \varkappa\sigma$ for all $|\tau| \le m$. Thus,

$$ \|x - [\phi^o * x]\|_{n,2} \le \|x^S - \phi^o * x^S\|_{n,2} + \|\varepsilon\|_{n,2} + \|\phi^o * \varepsilon\|_{n,2} = \varkappa\sigma + \|\phi^o * \varepsilon\|_{n,2} \quad (67) $$

On the other hand, by the Cauchy inequality,

$$ \begin{aligned} \|\phi^o * \varepsilon\|_{n,2}^2 &= \sum_{t=-n}^{n} \left| \sum_{\tau=-m}^{m} \phi_{\tau}^o \varepsilon_{t-\tau} \right|^2 \le \|\phi^o\|_2^2 \sum_{t=-n}^{n} \sum_{\tau=-m}^{m} |\varepsilon_{t-\tau}|^2 \\ &= \|\phi^o\|_2^2 \sum_{\tau=-m}^{m} \|\Delta^\tau \varepsilon\|_{n,2}^2 \le \rho^2 \sigma^2 \varkappa^2. \end{aligned} $$

When substituting the latter bound into (67) we obtain (65).

To show (66) recall that in the case of $x \in \bar{\mathcal{X}}_{m,n}(s, \varkappa)$ we have $x = x^S + \varepsilon$ with $|\varepsilon_\tau| \le \frac{\varkappa\sigma}{\sqrt{2n+1}}$ for all $|\tau| \le m+n$. Then for $|t| \le n$ we get

$$ \begin{aligned} |x_t - [\phi^o * x]_t| &\le |x_t^S - [\phi^o * x^S]_t| + |\varepsilon_t| + |[\phi^o * \varepsilon]_t| \\ &\le \frac{\varkappa\sigma}{\sqrt{2n+1}} + \|\phi^o\|_2 \|\Delta^{-t}\varepsilon\|_{m,2} \\ &\le \frac{\varkappa\sigma}{\sqrt{2n+1}} + \frac{\rho}{\sqrt{2m+1}} \frac{\sigma\varkappa\sqrt{2m+1}}{\sqrt{2n+1}} \le \frac{\sigma\varkappa}{\sqrt{2m+1}}(1 + \rho\kappa_{n,m}). \quad \square \end{aligned} $$

*Proof of the proposition.* W.l.o.g. we may assume that $m = 2m_o$. In the premise of the proposition, by Proposition 2, for any $m_o \ge s-1$ there exists a filter $\phi^o \in C_{m_o}(\mathbb{Z})$ such that

$$ \|\phi_o\|_2 \le \sqrt{\frac{2s}{2m_o + 1}}, \quad z = \phi_o * z \quad \forall z \in \mathcal{S}. \quad (68) $$

When setting $\phi^o = \phi^o * \phi^o \in C_m$ we have $z - \phi^o * z = 0 \quad \forall z \in \mathcal{S}$, and$^{11}$

$$ \|\varphi^o\|_{m,2} \le \|\varphi^o\|_{m,1}^* \le \frac{4s}{\sqrt{2m+1}} \quad (69) $$

(cf. [15, Proposition 3] or [20, Lemma 16]). We now apply Lemma 3.i to obtain for all $x \in \mathcal{X}_{m,n}(s, \varkappa)$

$$ \|x - \varphi^o * x\|_{n,2} \le \sigma\varkappa(4s + 1). \quad (70) $$

Moreover, note that

$$ \|\varphi^o * \zeta\|_{n,2}^2 = \langle \zeta, M(\varphi^o)\zeta \rangle_n, $$

<footnote>$^{11}$ In the case of $m = 2m_o + 1$ one may consider two filters $\phi^o$ and $\psi^o$ of widths $m_o$ and $m_o + 1$ respectively, and then build $\varphi_o = \phi^o * \psi^o \in C_m(\mathbb{Z})$. One easily verifies that in this case $\|\varphi_o\|_{m,1}^* \le \sqrt{2m+1}\|\phi^o\|_2\|\psi^o\|_2 \le \frac{4s}{\sqrt{2m+1}}$.</footnote>
where $M(\varphi)$ is defined by (27). When using the bound (69) along with (28) we obtain

$$ \|M(\varphi^o)\|_{\mathrm{F}}^2 = (2n+1)\|\varphi^o\|_{2}^2 \leq 16\kappa_{m,n}^2 s^2; $$

by (36) this implies that for any $\alpha \in (0, 1)$, with probability at least $1 - \alpha$,

$$ \|\varphi^o * \zeta\|_{n,2} \leq 4\sqrt{2}\sigma\kappa_{m,n}s(1 + \sqrt{\log[1/\alpha]}). \quad (71) $$

The latter bound taken together with (70) implies that with probability $\geq 1 - \alpha$

$$ \begin{aligned} \|x - \varphi^o * y\|_{n,2} &\leq 4\sqrt{2}\kappa_{m,n}\sigma s(1 + \sqrt{\log[1/\alpha]}) + \sigma \varkappa(4s + 1) \\ &\leq C\sigma s(\kappa_{m,n}\sqrt{\log[1/\alpha]} + \varkappa) \end{aligned} $$

when $\alpha \leq 1/2$. We conclude the proof by substituting the above bound for the loss of the estimate $\hat{x} = \varphi^o * y$ and the bound $\|\varphi^o\|_{m,1}^* \leq 4s$ into the oracle inequalities of Theorems 1 and 2. $\square$

### C.3 Proof of Proposition 4

We provide the proof for the case of constrained estimator $\hat{x}_{\mathrm{con}}$, the proof of the proposition for penalized estimator $\hat{x}_{\mathrm{pen}}$ follows exactly same lines. Let $\hat{\varphi} = \hat{\varphi}_{\mathrm{con}}$.

1. W.l.o.g. we assume that $m = 2m_o$. By Proposition 2, for such $m_o$ there is a filter $\phi^o \in C_{m_o}(\mathbb{Z})$ satisfying relationships (68). When applying Lemma 3.i we obtain for all $x \in \bar{\chi}_{m,n}(s, \varkappa)$

$$ \|x - \phi^o * x\|_{n,\infty} \leq \frac{\sigma \varkappa}{\sqrt{2m_o + 1}} (1 + \sqrt{2s\kappa_{m,n,m_o}}). \quad (72) $$

Next, replacing $\varphi^o$ with $\phi^o$ and $n$ with $m$ in the derivation which led us to (71) in the proof of Proposition 3 we conclude that

$$ \|\phi^o * \zeta\|_{m,2} \leq 2\sigma\kappa_{m_o,m}\sqrt{s}(1 + \sqrt{\log[1/\alpha]}) \leq 2\sqrt{2s}\sigma(1 + \sqrt{\log[1/\alpha]}). \quad (73) $$

2. Let now $|t| \leq n - m_o$. We decompose

$$ \begin{aligned} |[x - \hat{\varphi} * y]_t| &= |[(\phi^o + (1 - \phi^o)) * (x - \hat{\varphi} * y)]_t| \\ &\leq |[\phi^o * (x - \hat{\varphi} * y)]_t| + |[(1 - \phi^o) * (1 - \hat{\varphi}) * x]_t| \\ &\quad + \sigma|[\hat{\varphi} * \zeta]_t| + \sigma|[\hat{\varphi} * \phi^o * \zeta]_t| \\ &=: \delta^{(1)} + \delta^{(2)} + \delta^{(3)} + \delta^{(4)}. \end{aligned} \quad (74) $$

We have

$$ \delta^{(1)} \leq \|\phi^o\|_2 \|\Delta^{-t}[x - \hat{\varphi} * y]\|_{m_o,2} \leq \frac{2\sqrt{s}}{\sqrt{2m+1}} \|x - \hat{\varphi} * y\|_{n,2}. $$

Using the bound (14) of Proposition 3 we conclude that with probability $\geq 1 - \alpha/3$

$$ \delta^{(1)} \leq C \sqrt{\frac{s}{2m+1}} \bar{\psi}_{m,n}^{\alpha/3}(\sigma, s, \varkappa). $$
Next, using (72) we get

$$
\begin{align*}
\delta^{(2)} &\le (1 + \|\hat{\varphi}\|_1) \|\Delta^{-t}[(1 - \phi^o) * x]\|_{m_o, \infty} \\
&\le C's \frac{\sigma\kappa}{\sqrt{2m+1}} (1 + \sqrt{2s\kappa_{n,m_o}}) \le \frac{Cs^{3/2}\sigma\kappa}{\sqrt{2m+1}}
\end{align*}
$$

(recall that $n \ge m_o$). Further, by the Parseval's identity, with probability $\ge 1 - \alpha/3$,

$$
\begin{align*}
\delta^{(3)} &= \sigma |\langle F_m[\hat{\varphi}], F_m[\Delta^{-t}\zeta] \rangle| \le \sigma \|\hat{\varphi}\|_{m,1}^* \|\Delta^{-t}\zeta\|_{m,\infty}^* \\
&\le \frac{C's\sigma}{\sqrt{2m+1}} \sqrt{2 \log [3(2m+1)/\alpha]}
\end{align*}
$$

due to (32). Finally, using (73) and the fact that the distribution of $\zeta_{t-m-m_o}^{t+m+m_o}$ is the same as that of $\zeta_{-m-m_o}^{m+m_o}$ we conclude that with probability $\ge 1 - \alpha/3$ it
holds

$$
\| \Delta^{-t} [ \phi^o * \zeta ] \|_{m,2} \le 2\sqrt{2s\sigma} (1 + \sqrt{\log[3/\alpha]}).
$$

Therefore, we have for $\delta^{(4)}$:

$$
\begin{align*}
\delta^{(4)} &\le \sigma \|\hat{\varphi}\|_{m,2} \|\Delta^{-t}[\phi^o * \zeta]\|_{m,2} \\
&\le \frac{C's\sigma}{\sqrt{2m+1}} 2\sqrt{2s\sigma} (1 + \sqrt{\log[3/\alpha]}) \\
&= \frac{C''s^{3/2}\sigma}{\sqrt{2m+1}} (1 + \sqrt{\log[3/\alpha]})
\end{align*}
$$

with prob. $\ge 1 - \alpha/3$. Substituting the bounds for $\delta^{(k)}$, $k = 1, \dots, 4$, into (74) we
arrive at (16). $\square$

C.4 Proof of Proposition 5

As a precursory remark, note that if a finite-dimensional subspace $\mathcal{S}$ is shift-
invariant, i.e., $\Delta\mathcal{S} \subseteq \mathcal{S}$, then necessarily $\Delta\mathcal{S} = \mathcal{S}$ (indeed, $\Delta$ obviously is a
linear transformation with a trivial kernel).

$1^o$. To prove the direct statement, note that the solution set of (17) with $\deg(p(\cdot)) = s$ is a shift-invariant subspace of $\mathbb{C}(\mathbb{Z})$ – let us call it $\mathcal{S}'$. Indeed, if $x \in \mathbb{C}(\mathbb{Z})$ satisfies (17), so does $\Delta x$, so $\mathcal{S}'$ is shift-invariant. To see that $\dim(\mathcal{S}') = s$, note that $x \mapsto x_1^s$ is a bijection $\mathcal{S}' \to \mathbb{C}^s$: under this map arbitrary $x_1^s \in \mathbb{C}^s$ has a unique preimage. Indeed, as soon as one fixes $x_1^s$, (17) uniquely defines the next samples $x_{s+1}, x_{s+2}, \dots$ (note that $p(0) \neq 0$); dividing (17) by $\Delta^s$, one can retrieve the remaining samples of $x$ since $\deg(p(\cdot)) = s$ (we used that $\Delta$ is bijective on $\mathcal{S}$).
$\mathcal{S}^\circ$. To prove the converse, first note that any polynomial $p(\cdot)$ with $\deg(p(\cdot)) = s$ and such that $p(0) = 1$ is uniquely expressed via its roots $z_1, ..., z_s$ as

$$p(z) = \prod_{k=1}^{s} (1 - z/z_k).$$

Since $\mathcal{S}$ is shift-invariant, we have $\Delta\mathcal{S} = \mathcal{S}$ as discussed above, i.e., $\Delta$ is a bijective linear operator on $\mathcal{S}$. Let us fix some basis $E = [e^1; ..., e^s]$ of $\mathcal{S}$ and denote $A$ the $s \times s$ representation matrix of $\Delta$ in this basis, that is, $\Delta(e^j) = \sum_{i=1}^{s} a_{ij}e^i$. By the Jordan theorem basis $E$ can be chosen in such a way that $A$ is upper-triangular. Then, any vector $x \in \mathcal{S}$ satisfies $q(\Delta)x \equiv 0$ where

$$q(z) = \prod_{i=1}^{s} (a_{ii} - z) = \det(A - zI)$$

is the characteristic polynomial of $A$. Note that $\det A = \prod_{i=1}^{s} a_{ii} \neq 0$ since $\Delta$ is a bijection. Hence, choosing

$$p(\Delta) = \frac{q(\Delta)}{\det A}$$

we obtain $\prod_{i=1}^{s} (1 - c_i \Delta)x \equiv 0$ for some complex $c_i \neq 0$. This means that $\mathcal{S}$ is contained in the solution set $\mathcal{S}'$ of (17) with $\deg(p(\cdot)) = s$ and such that $p(0) = 1$. Note that by $\mathbf{1}^\circ \mathcal{S}'$ is also a shift-invariant subspace of dimension $s$, thus $\mathcal{S}$ and $\mathcal{S}'$ coincide. Finally, uniqueness of $p(\cdot)$ follows from the fact that $q(\cdot)$ is a characteristic polynomial of $A$. $\square$

### C.5 Proof of Proposition 6

To prove the proposition we need to exhibit a vector $q \in \mathbb{C}^{n+1}$ of small $\ell_2$-norm and such that the polynomial $1 - q(z) = 1 - [\sum_{i=0}^{n} q_i z^i]$ is divisible by $p(z)$, i.e., that there is a polynomial $r(z)$ of degree $n-s$ such that

$$1 - q(z) = r(z)p(z).$$

Indeed, this would imply that

$$x_t - [q * x]_t = [1 - q(\Delta)]x_t = r(\Delta)p(\Delta)x_t = 0$$

due to $p(\Delta)x_t = 0$,

Our objective is to prove the inequality $\|q\|_2 \le C's\sqrt{\frac{\log[ns]}{n}}$. So, let $\theta_1, ..., \theta_s$ be complex numbers of modulus 1 – the roots of the polynomial $p(z)$. Given $\delta = 1 - \epsilon \in (0, 1)$, let us set $\bar{\delta} = 2\delta/(1 + \delta)$, so that

$$\frac{\bar{\delta}}{\delta} - 1 = 1 - \bar{\delta} > 0. \qquad (75)$$

Consider the function

$$\bar{q}(z) = \prod_{i=1}^{s} \frac{z - \theta_i}{\delta z - \theta_i}.$$
Note that $\bar{q}(\cdot)$ has no singularities in the circle

$$ \mathcal{B} = \{z : |z| \le 1/\bar{\delta}\}; $$

besides this, we have $\bar{q}(0) = 1$. Let $|z| = 1/\bar{\delta}$, so that $z = \bar{\delta}^{-1}w$ with $|w| = 1$. We have

$$ \frac{|z - \theta_i|}{|\delta z - \theta_i|} = \frac{1}{\bar{\delta}} \frac{|w - \bar{\delta}\theta_i|}{|w - \frac{\bar{\delta}}{\delta}\theta_i|}. $$

We claim that when $|w| = 1$, $|w - \bar{\delta}\theta_i| \le |w - \frac{\bar{\delta}}{\delta}\theta_i|$.

Indeed, assuming w.l.o.g. that $w$ is not proportional to $\theta_i$, consider triangle $\Delta$ with the vertices $A = w$, $B = \bar{\delta}\theta_i$ and $C = \frac{\bar{\delta}}{\delta}\theta_i$. Let also $D = \theta_i$. By (75), the segment $AD$ is a median in $\Delta$, and $\angle CDA$ is $\ge \frac{\pi}{2}$ (since $D$ is the closest to $C$ point in the unit circle, and the latter contains $A$), so that $|w - \bar{\delta}\theta_i| \le |w - \frac{\bar{\delta}}{\delta}\theta_i|$.

As a consequence, we get

$$ z \in \mathcal{B} \Rightarrow |\bar{q}(z)| \le \delta^{-s}, \qquad (76) $$

whence also

$$ |z| = 1 \Rightarrow |\bar{q}(z)| \le \delta^{-s}. \qquad (77) $$

Now, the polynomial $p(z) = \prod_{i=1}^{s}(z - \theta_i)$ on the boundary of $\mathcal{B}$ clearly satisfies

$$ |p(z)| \ge \left[ \frac{1}{\bar{\delta}} - 1 \right]^s = \left[ \frac{1 - \delta}{2\bar{\delta}} \right]^s, $$

which combines with (76) to imply that the modulus of the holomorphic in $\mathcal{B}$ function

$$ \bar{r}(z) = \left[ \prod_{i=1}^{s} (\delta z - \theta_i) \right]^{-1} $$

is bounded with $\delta^{-s} \left[ \frac{1-\delta}{2\bar{\delta}} \right]^{-s} = \left[ \frac{2}{1-\bar{\delta}} \right]^s$ on the boundary of $\mathcal{B}$. It follows that the coefficients $r_j$ of the Taylor series of $\bar{r}$ satisfy

$$ |r_j| \le \left[ \frac{2}{1 - \bar{\delta}} \right]^s \bar{\delta}^j, \quad j = 0, 1, 2, \dots $$

When setting

$$ q^{\ell}(z) = p(z)r^{\ell}(z), \quad r^{\ell}(z) = \sum_{j=1}^{\ell} r_j z^j, \qquad (78) $$

for $|z| \le 1$, utilizing the trivial upper bound $|p(z)| \le 2^s$, we get

$$ |q^{\ell}(z) - \bar{q}(z)| \le |p(z)||r^{\ell}(z) - \bar{r}(z)| \le 2^s \left[ \frac{2}{1 - \bar{\delta}} \right]^s \sum_{j=\ell+1}^{\infty} |r_j| $$
$$ \leq \left[ \frac{4}{1 - \delta} \right]^s \frac{\bar{\delta}^{\ell+1}}{1 - \bar{\delta}}. \qquad (79) $$

Note that $q^\ell(0) = p(0)r^\ell(0) = p(0)\bar{r}(0) = 1$, that $q^\ell$ is a polynomial of degree $\ell+s$, and that $q^\ell$ is divisible by $p(z)$. Besides this, on the unit circumference we have, by (79),

$$ |q^\ell(z)| \leq |\bar{q}(z)| + \left[ \frac{4}{1-\bar{\delta}} \right]^s \frac{\bar{\delta}^{\ell+1}}{1-\bar{\delta}} \leq \delta^{-s} + \underbrace{\left[ \frac{4}{1-\bar{\delta}} \right]^d \frac{\bar{\delta}^{\ell+1}}{1-\bar{\delta}}}_{R}, \qquad (80) $$

where we used (77). Now,

$$ \bar{\delta} = \frac{2\delta}{1 + \bar{\delta}} = \frac{2 - 2\epsilon}{2 - \epsilon} = \frac{1 - \epsilon}{1 - \epsilon/2} \leq 1 - \epsilon/2 \leq e^{-\epsilon/2}, $$

and

$$ \frac{1}{1 - \bar{\delta}} = \frac{1 + \bar{\delta}}{1 - \bar{\delta}} = \frac{2 - \epsilon}{\epsilon} \leq \frac{2}{\epsilon}. $$

We can upper-bound $R$:

$$ R = \left[ \frac{4}{1 - \bar{\delta}} \right]^s \frac{\bar{\delta}^{\ell+1}}{1 - \bar{\delta}} \leq \frac{2^{2s+1}}{\epsilon^{s+1}} e^{-\epsilon\ell/2} $$

Now, given positive integer $\ell$ and positive $\alpha$ such that

$$ \frac{\alpha}{\ell} \leq \frac{1}{4}, \qquad (81) $$

let $\epsilon = \frac{\alpha}{2\ell s}$. Since $0 < \epsilon \leq \frac{1}{8}$, we have $-\log(\delta) = -\log(1-\epsilon) \leq 2\epsilon = \frac{\alpha}{\ell s}$, implying that $\bar{\delta} \leq e^{-\epsilon/2} = e^{-\frac{\alpha}{4\ell s}}$, and

$$ R \leq \left[ \frac{8\ell s}{\alpha} \right]^{s+1} \exp\left\{-\frac{\alpha}{4s}\right\}. $$

Now let us put

$$ \alpha = \alpha(\ell, s) = 4s(s + 2)\log(8\ell s); $$

observe that this choice of $\alpha$ satisfies (81), provided that

$$ \ell \geq O(1)s^2 \log(s + 1) $$

with properly selected absolute constant $O(1)$. With this selection of $\alpha$, we have $\alpha \geq 1$, whence

$$ \begin{aligned} R \left[ \frac{\alpha}{\ell} \right]^{-1} & \leq \exp \left\{ -\frac{\alpha}{4s} \right\} \left[ \frac{8\ell s}{\alpha} \right]^{s+1} \frac{\ell}{\alpha} \leq \exp \left\{ -\frac{\alpha}{4s} \right\} [8\ell s]^{s+2} \\ & \leq \exp \left\{ -(s+2) \log(8\ell s) \right\} \exp \left\{ (s+2) \log(8\ell s) \right\} = 1, \end{aligned} $$
that is,

$$R \leq \frac{\alpha}{\ell} \leq \frac{1}{4}. \qquad (82)$$

Furthermore,

$$\begin{aligned} \delta^{-s} &= \exp\{-s \log(1-\epsilon)\} \leq \exp\{2\epsilon s\} = \exp\{\frac{\alpha}{\ell}\} \leq 2, \\ \delta^{-2s} &= \exp\{-2s \log(1-\epsilon)\} \leq \exp\{4\epsilon s\} = \exp\{\frac{2\alpha}{\ell}\} \qquad (83) \\ &\leq 1 + \exp\{\frac{1}{2}\} \frac{2\alpha}{\ell} \leq 1 + \frac{4\alpha}{\ell}. \end{aligned}$$

When invoking (80) and utilizing (83) and (82) we get

$$\frac{1}{2\pi} \oint_{|z|=1} |q^{\ell}(z)|^2 dz \leq \delta^{-2s} + 2\delta^{-s}R + R^2 \leq 1 + 4\frac{\alpha}{\ell} + 4R + \frac{1}{4}R \leq 1 + 10\frac{\alpha}{\ell}.$$

On the other hand, denoting by $q_0, q_1, \dots, q_{\ell+s}$ the coefficients of the polynomial $q^\ell$ and taking into account that $\bar{q}_0 = q^\ell(0) = 1$, we have

$$1 + \sum_{i=1}^{\ell+s} |q_i|^2 = |q_0|^2 + \dots + |q_{\ell+s}|^2 = \frac{1}{2\pi} \oint_{|z|=1} |q^\ell(z)|^2 dz \leq 1 + 10 \frac{\alpha}{\ell}. \qquad (84)$$

We are done: when denoting $n = \ell + s$, and $q(z) = \sum_{i=1}^n q_j z^j$, we have the vector of coefficients $q = [0; q_1; \dots; q_n] \in \mathbb{C}^{n+1}$ of $q(z)$ such that, by (84),

$$\|q\|_2^2 \leq \frac{40s(s+2)\log[8s(n-s)]}{n-s},$$

and such that the polynomial $q^\ell(z) = 1 + q(z)$ is divisible by $p(z)$ due to (78). □

### C.6 Proof of Lemma 1

Let $\Pi_{S_{2m}}$ be the $(2m+1) \times (2m+1)$ projector matrix built in the proof of Proposition 2, but now let $\phi^o \in \mathbb{C}_m(\mathbb{Z})$ be obtained from the last column of $\Pi_{S_{2m}}$. As in that proof, due to the shift-invariance of $\mathcal{H}_s[\omega]$ we have $x = \phi^o * \Delta^m x$ $\forall x \in \mathcal{H}_s[\omega]$. To prove the proposition it remains to bound $\|\phi^o\|_2$.

Note that in the premise of the proposition $S_m$ is spanned by vectors

$$\left\{ v(\omega) : [v(\omega)]_t = \frac{e^{i\omega_k t}}{\sqrt{m+1}}, \quad 0 \le t \le 2m \right\}, \quad \omega \in \{\omega_1, \dots, \omega_s\}.$$

Hence, the projector $\Pi_{S_{2m}}$ can be written as

$$\Pi_{S_m} = V (V^H V)^{-1} V^H,$$

where $V$ is an $(2m+1) \times s$ Vandermonde matrix with columns $v(\omega_k)$, $k = 1, \dots, s$. Note that since $s \leq 2m+1$, and $\omega_k$, $k = 1, \dots, s$ are distinct, matrix $V$ has full column rank. Now, in order to bound $\|\phi^o\|_2$ from above it suffices to separate
the minimal eigenvalue $\lambda_{\min}(V^HV)$ of $V^HV$ from zero. Indeed, assuming that $\lambda_{\min}(V^HV) > 0$ we may write

$$ \Pi_{S_m} = UU^H, $$

where $U = [U_1, ..., U_s]$ is the unitary normalization of $V$:

$$ U = [U_1 \cdots U_s] = V(V^H V)^{-1/2}, \quad U^H U = I_s. $$

Let $u = [u_1, ..., u_s]$ be the last row of $U$, and $v$ that of $V$. Note that the vector $\psi = uU^H = \sum_{k=1}^s u_k [U_k]^H$ has the same $\ell_2$-norm as $\phi^o$, and so $\|\phi^o\|_2^2 = \|u\|_2^2$. On the other hand, because $u = v(V^H V)^{-1/2}$, we arrive at

$$ \|u\|_2^2 \le \|v\|_2^2 \lambda_{\min}^{-1}(V^H V) \le \frac{s}{2m+1} \lambda_{\min}^{-1}(V^H V) $$

where the last inequality is due to the bound $(2m+1)^{-1/2}$ on the moduli of elements of $v$. Finally, we utilize the bound on the condition number of a Vandermonde matrix:

**Lemma 4 ([31, Theorem 2.3]).** Let $\delta_{\min}$ be given by (22); one has

$$ \frac{\lambda_{\max}(V^H V)}{\lambda_{\min}(V^H V)} \le \left(m - \frac{2\pi}{\delta_{\min}}\right)^{-1} \left(m + \frac{2\pi}{\delta_{\min}}\right). $$

We clearly have $\|V\|_* \ge 1$, whence $\lambda_{\max}(V^HV) \ge 1$. Together with (24) this results in

$$ \lambda_{\min}^{-1}(V^H V) \le \frac{\nu + 1}{\nu - 1}, $$

whence the required bound on $\|\phi^o\|_2$. $\square$

### C.7 Proof of Proposition 9

Note that in the premise of the proposition $k = \lfloor L/(s \log[L]) \rfloor$ is correctly defined and $K = L - 2k \ge L/2$ so that

$$ \kappa_{K,k} \le C(s \log L)^{-1/2} \quad \text{and} \quad \kappa_{k,K} \le C' \sqrt{s \log L}. \qquad (85) $$

When applying Proposition 3 (recall that $\varkappa = 0$ in our setting), we conclude that the error of the estimate $\hat{\varphi}^* y$ satisfies, with probability at least $1 - \alpha/3$,

$$ \|x - \hat{x}\|_{K,2} \le C\sigma \left( \kappa_{k,K} s \sqrt{\log[1/\alpha]} + \sqrt{s \log[L/\alpha]} \right). \qquad (86) $$

On the other hand, due to $\kappa_{K,k} \le 1$, applying Proposition 7 we conclude that with probability $1 - \alpha/3$ the error of the left estimate $\hat{\varphi}^* \Delta^m y$ satisfies:

$$ \|\Delta^{-m}(x - \hat{\varphi}^* \Delta^m y)\|_{k,2} \le C' \sigma \left( \kappa_{K,k} s^2 \log[L] \sqrt{\log[1/\alpha]} + s \sqrt{\log[L]} \log[L/\alpha] \right), $$
and the same estimation holds true for the right estimate $\hat{\varphi}^{-} * \Delta^{-m}y$:

$$ \|\Delta^m(x - \hat{\varphi}^{-} * \Delta^{-m}y)\|_{k,2} \le C'\sigma \left( \kappa_{K,k}s^2 \log[L] \sqrt{\log[1/\alpha]} + s\sqrt{\log[L]}\log[L/\alpha] \right). $$

When combining the latter bounds with (86) we arrive at the bound with probability $\ge 1 - \alpha$:

$$ \begin{aligned} \|x - \hat{x}\|_{L,2} &\le \|\Delta^m(x - \hat{\varphi}^{-} * \Delta^{-m}y)\|_{k,2} + \|x - \hat{x}\|_{K,2} + \|\Delta^{-m}(x - \hat{\varphi}^{+} * \Delta^{m}y)\|_{k,2} \\ &\le C\sigma s \sqrt{\log[L]} \log[L/\alpha] + C'\sigma s \sqrt{\log[1/\alpha]} (\kappa_{k,K} + \kappa_{K,k} s \log[L]) \\ &\text{(by (85))} \le C\sigma s \log[L/\alpha] + C''\sigma s \sqrt{s \log[L]} \log[1/\alpha] \le C\sigma s^{3/2} \log[L/\alpha]. \quad \square \end{aligned} $$

## D Naive adaptive estimate

In this section,<fnref n="12" /> we consider the “naive” adaptive estimate $\hat{x} = \hat{\phi} * y$ where $\hat{\phi} \in C_m(\mathbb{Z})$ solves the optimization problem

$$ \min_{\phi \in C_m(\mathbb{Z})} \|y - \phi * y\|_{n,2} \text{ subject to } \|\phi\|_2 \le \frac{\rho}{\sqrt{2m+1}}. \quad (87) $$

Recall that our goal is to show that using estimate $\hat{x}$ is really not a good idea. To make the long story short, from now on, we consider the simplified version of the estimation problem in which $m = n$, signals are $2m + 1$-periodic, and linear estimates are in the form of circular (periodic) convolution

$$ [\phi * y]_t = \sum_{\tau=-m}^{m} \phi_{\tau} y_{s(t,\tau)}, \quad |t| \le m, $$

where $s(t, \tau) = [t + m - \tau \mod 2m + 1] - m$. Because the Discrete Fourier Transform diagonalizes the periodic convolution, problem (87) may be equivalently reformulated in the space of Fourier coefficients

$$ \min_{w \in \mathbb{C}^{2m+1}} \|z - Zw\|_{n,2} \text{ subject to } \|w\|_2 \le \rho \quad (88) $$

where $z = F_m[y]$, $Z = \text{diag}(z)$ (with $A = \text{diag}(a)$ being the diagonal matrix with entries $A_{ii} = a_i$), and $w$ is a properly “rephased” DFT of $\phi$ with $|w_k| = \sqrt{2m+1}|(F_m[\phi])_k|$, $1 \le k \le 2m+1$.

Consider the situation in which the signal to recover is just one “complex sinusoid,” e.g., $x_{\tau} = ae^{\frac{2\pi i\tau}{2m+1}}$, $\tau \in \mathbb{Z}$, $a \in \mathbb{C}$, and let us show that the error of the naive estimate may be much larger than the “oracle” error. We have $F_m[x] = fe_1$ where $e_1$ is the first basis orth, $f = a\sqrt{2m+1}$ with $|f| = \|x\|_{m,2} = |a|\sqrt{2m+1}$, and the “sequence-space” observation $z$ satisfies

$$ z = fe_1 + \sigma\zeta, \quad \zeta \sim \mathbb{CN}(0, I_n). $$

<footnote n="12">¹² We use notation defined in Sections 2.1 and A.1.</footnote>
Obviously, in this case there exist a filter $\phi^o$ with $\|\phi^o\|_2 = (2m + 1)^{-1/2}$ such that $x = \phi^o * x$, so that the integral $\alpha$-risk of the “oracle estimate” $\phi^o * y$ is $O(\sigma)$ up to logarithmic in $\alpha$ factor. Let us show that in this simple situation the risk of the naive estimate may be significantly higher.

First of all, note that the optimal solution $\hat{w}$ to the problem (88) with $\rho = 1$ is of the form

$$ \hat{w}_k = \frac{|z_k|^2}{|z_k|^2 + \lambda}, \quad 1 \le k \le 2m + 1 $$

where $\lambda$ is chosen to ensure $\|\hat{w}\|_2 = 1$. Let us bound $\lambda$ from below. We have

$$ \begin{aligned} 1 = \|\hat{w}\|_2^2 &= \frac{|z_1|^4}{(|z_1|^2 + \lambda)^2} + \sum_{k=2}^{2m+1} \frac{\sigma^4 |\zeta_k|^4}{(\sigma^2 |\zeta_k|^2 + \lambda)^2} \\ &\geq \sum_{k=2}^{2m+1} \frac{\sigma^4 |\zeta_k|^4}{(\sigma^2 M_m^2 + \lambda)^2} \geq \frac{\sigma^4 S_m^2}{2m(\lambda + \sigma^2 M_m)^2} \end{aligned} $$

where $M_m = \max_{1 \le k \le 2m+1} |\zeta_k|^2$ and $S_m = \sum_{k=2}^{2m+1} |\zeta_k|^2$. Since with high probability (say, $1 - O(1/m)$) $M_m = O(\log m)$ and $S_m = O(m)$ (cf. (32) and (33)), for $m$ large enough one has

$$ \lambda \geq \sigma^2 \left( \frac{S_m}{\sqrt{2m}} - M_m \right) \geq c \sigma^2 \sqrt{m} $$

with probability at least $1 - O(1/m)$. As a result,

$$ 1 - \hat{w}_1 = 1 - \frac{|z_1|^2}{|z_1|^2 + \lambda} = \frac{\lambda}{|z_1|^2 + \lambda} \geq \frac{\lambda}{(|f| + \sigma |M_n|)^2 + \lambda} \geq c' $$

whenever $f$ satisfies $|f|^2 \leq C\sigma^2\sqrt{m}$. Next, observe that

$$ \begin{aligned} \|x - \hat{x}\|_{m,2}^2 &= \|F_m[x] - Z\hat{w}\|_2^2 = \|fe_1 - Z\hat{w}\|_2^2 \geq |f - z_1\hat{w}_1|^2 \\ &\geq \frac{1}{2}|f(1 - \hat{w}_1)|^2 - \sigma^2|\zeta_1|^2\hat{w}_1^2 \geq c|f|^2 - \sigma^2 M_m \geq c'|f|^2 \end{aligned} $$

for $|f| \geq c''\sigma\sqrt{\log m}$. In other words, when the signal amplitude satisfies

$$ \frac{c\sigma^2 \log m}{m} \leq |a|^2 \leq \frac{C\sigma^2}{\sqrt{m}}, $$

the loss $\|\hat{x} - x\|_{m,2}$ of the naive estimate is lower bounded, with probability at least $1 - O(1/m)$, with $c'\|x\|_{m,2}$. In particular, when $a \asymp \sigma m^{-1/4}$ this error is at least order of $\sigma m^{1/4}$, which is incomparably worse than the error $O(\sigma)$ of the oracle estimate.

## References

1. B. Bhaskar, G. Tang, and B. Recht. Atomic norm denoising with applications to line spectral estimation. *IEEE Trans. Signal Processing*, 61(23):5987–5999, 2013.
2. P. Bickel, Y. Ritov, and A. Tsybakov. Simultaneous analysis of Lasso and Dantzig selector. *The Annals of Statistics*, 37(4):1705–1732, 2009.

3. L. Birgé and P. Massart. From model selection to adaptive estimation. In *Festschrift for Lucien le Cam*, pages 55–87. Springer, 1997.

4. P. Bühlmann and S. Van De Geer. *Statistics for high-dimensional data: methods, theory and applications*. Springer Science & Business Media, 2011.

5. E. Candes and T. Tao. The Dantzig selector: Statistical estimation when p is much larger than n. *Ann. Statist.*, 35(6):2313–2351, 12 2007.

6. D. Donoho. Statistical estimation and optimal recovery. *Ann. Statist.*, 22(1):238–270, 1994.

7. D. Donoho and I. Johnstone. Ideal spatial adaptation by wavelet shrinkage. *Biometrika*, 81(3):425–455, 1994.

8. D. Donoho, R. Liu, and B. MacGibbon. Minimax risk over hyperrectangles, and implications. *The Annals of Statistics*, 18(3):1416–1437, 1990.

9. D. Donoho and M. Low. Renormalization exponents and optimal pointwise rates of convergence. *The Annals of Statistics*, 20(2):944–970, 1992.

10. M. F. Duarte and R. G. Baraniuk. Spectral compressive sensing. *Appl. & Comput. Harmon. Anal.*, 35(1):111–129, 2013.

11. S. Efromovich and M. Pinsker. Sharp-optimal and adaptive estimation for heteroscedastic nonparametric regression. *Statistica Sinica*, 6:925–942, 1996.

12. A. Goldenshluger and O. Lepski. Bandwidth selection in kernel density estimation: oracle inequalities and adaptive minimax optimality. *The Annals of Statistics*, 39(3):1608–1632, 2011.

13. A. Goldenshluger and O. Lepski. General selection rule from a family of linear estimators. *Theory of Probability & Its Applications*, 57(2):209–226, 2013.

14. A. Goldenshluger and A. Nemirovski. Adaptive de-noising of signals satisfying differential inequalities. *IEEE Transactions on Information Theory*, 43(3):872–889, 1997.

15. Z. Harchaoui, A. Juditsky, A. Nemirovski, and D. Ostrovsky. Adaptive recovery of signals by convex optimization. In *Proceedings of The 28th Conference on Learning Theory (COLT) 2015*, Paris, France, July 3-6, 2015, pages 929–955, 2015.

16. I. Ibragimov and R. Khasminskii. Nonparametric estimation of the value of a linear functional in Gaussian white noise. *Theor. Probab. & Appl.*, 29(1):1–32, 1984.

17. I. Ibragimov and R. Khasminskii. Estimation of linear functionals in Gaussian noise. *Theor. Probab. & Appl.*, 32(1):30–39, 1988.

18. I. Johnstone. Gaussian estimation: sequence and multiresolution models. 2011.

19. A. Juditsky and A. Nemirovski. Functional aggregation for nonparametric regression. *Ann. Statist.*, 28:681–712, 2000.

20. A. Juditsky and A. Nemirovski. Nonparametric denoising of signals with unknown local structure, I: Oracle inequalities. *Appl. & Comput. Harmon. Anal.*, 27(2):157–179, 2009.

21. A. Juditsky and A. Nemirovski. Nonparametric denoising signals of unknown local structure, II: Nonparametric function recovery. *Appl. & Comput. Harmon. Anal.*, 29(3):354–367, 2010.

22. A. Juditsky and A. Nemirovski. On detecting harmonic oscillations. *Bernoulli*, 23(2):1134–1165, 2013.

23. A. Juditsky and A. Nemirovski. Near-optimality of linear recovery from indirect observations. *Mathematical Statistics and Learning*, 1(2):171–225, 2018.

24. A. Juditsky and A. Nemirovski. Near-optimality of linear recovery in gaussian observation scheme under $\|\cdot\|_2$-loss. *Annals of Statistics*, 46(4):1603–1629, 2018.
25. T. Kailath, A. Sayed, and B. Hassibi. *Linear Estimation*. Prentice Hall, 2000.

26. B. Laurent and P. Massart. Adaptive estimation of a quadratic functional by model selection. *Ann. Statist.*, 28(5):1302-1338, 2000.

27. O. Lepski. On a problem of adaptive estimation in Gaussian white noise. *Theory of Probability & Its Applications*, 35(3):454-466, 1991.

28. O. Lepski. Adaptive estimation over anisotropic functional classes via oracle approach. *The Annals of Statistics*, 43(3):1178-1242, 2015.

29. O Lepski, E Mammen, and V Spokoiny. Optimal spatial adaptation to inhomogeneous smoothness: an approach based on kernel estimates with variable bandwidth selectors. *The Annals of Statistics*, 25(3):929-947, 1997.

30. P. Massart. *Concentration inequalities and model selection*, volume 6. Springer, 2007.

31. A. Moitra. Super-resolution, extremal functions and the condition number of Vandermonde matrices. In *Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing*, pages 821–830. ACM, 2015.

32. A. Nemirovski. On non-parametric estimation of functions satisfying differential inequalities. 1991.

33. D. Ostrovsky, Z. Harchaoui, A. Juditsky, and A. Nemirovski. Structure-blind signal recovery. In *Advances in Neural Information Processing Systems*, pages 4817–4825, 2016.

34. M. Pinsker. Optimal filtering of square-integrable signals in gaussian noise. *Probability Peredachi Informatsii*, 16(2):52-68, 1980.

35. A. N. Shiryaev and V. G. Spokoiny. On sequential estimation of an autoregressive parameter. *Stochastics: An International Journal of Probability and Stochastic Processes*, 60(3-4):219-240, 1997.

36. P. Stoica and A. Nehorai. Music, maximum likelihood, and Cramer-Rao bound. *IEEE Transactions on Acoustics, speech, and signal processing*, 37(5):720-741, 1989.

37. G. Tang, B. Bhaskar, and B. Recht. Near minimax line spectral estimation. In *Information Sciences and Systems (CISS), 2013 47th Annual Conference on*, pages 1-6. IEEE, 2013.

38. R. Tibshirani. Regression shrinkage and selection via the Lasso. *J. R. Stat. Soc. Ser. B. Stat. Methodol.*, 58(1):267-288, 1996.

39. A. Tsybakov. *Introduction to Nonparametric Estimation*. Springer, 2008.

40. D. W. Tufts and R. Kumaresan. Estimation of frequencies of multiple sinusoids: Making linear prediction perform like maximum likelihood. *Proceedings of the IEEE*, 70(9):975-989, 1982.

41. L. Wasserman. *All of Nonparametric Statistics*. Springer Texts in Statistics. Springer, 2006.