text:
\begin{document}
\section{Introduction}\label{sec:intro}
In what follows, $C$, $C'$, $C''$ etc, stand for absolute constants.

\section{Problem statement}\label{sec:problem}
\noindent To alleviate notation we concentrate on one-dimensional version of the recovery problem announced in the introduction. Furthermore, to streamline the presentation we only consider ``left'' version of the problem -- the extension to more general filtering and prediction problems are straightforward (cf. Section ????). Therefore, our focus is on the estimation problem as follows. Given noisy observations
\be
y_t = x_t + \sigma \zeta_t,\quad t\leq n,
\ee{prob_model}
we want to estimate the value $x_n$ of the signal at $t=n$.
Here, $\zeta_t \sim \CN(0,1)$ are i.i.d. standard complex-valued Gaussian random variables, meaning that $\zeta_0= \xi_0^1 + \imath \xi_0^2$ with i.i.d. $\xi_0^1, \xi_0^2 \sim \N(0, 1)$.

In order to proceed we need some notation.
\paragraph{Signals and filters.}
Let $\C(\Z)$ be the linear space of all two-sided complex-valued sequences $x = \left\{x_t \in \mathbb{C}\right\}_{t \in \mathbb{Z}}$. For $k$ and $k' \in \Z$ we consider finite-dimensional subspaces $$\C(\Z_{k,k'}) = \left\{x \in \C(\Z): \quad x_t = 0, \quad t \notin [k,k'] \right\}.$$ It is convenient to  identify $m$-dimensional complex vectors, $m=k'-k+1$, with elements of $\C(\Z_{k,k'})$ by means of the notation:\footnote{In what follows we use ``Matlab convention:'' for marices $A$ and $B$ of appropriate dimensions we denote by $[A,B]$ their horizontal, and by $[A;B]$ their vertical concatenation.}
\[ x_{k}^{k'}:=[x_k;\, ...;\, x_{k'}]\in \C^{k'-k+1}.
\]
The \textit{convolution} $u * v$ of two sequences $u,v \in \C(\Z)$ is a sequence with elements
\begin{equation*}
[u*v]_t = \sum_{\tau \in \mathbb{Z}} u_\tau v_{t-\tau}, \quad t \in \Z.
\end{equation*}
Using the right-shift operator on $\C(\Z)$, $[\Delta x ]_t = x_{t-1}$, we can write $[\varphi*y]_t=[\varphi(\Delta)y]_t$.

\paragraph{Discrete Fourier transform.}
We define the unitary \emph{Discrete Fourier transform} (DFT) operator $F_{n}:\, \C^{n+1} \to \C^{n+1}$ by
\[
{z\mapsto F_{n} z},\;\; [F_{n} z]_k =
{(n+1)^{-{1/2}}} \sum\limits_{t = 0}^n z_{t}\, e^{\frac{2\pi\imath k t}{n+1}}, \quad 0 \le k \le n.
\]
We associate finite-dimensional linear mappings with matrices with complex entries. When denoting
$F^H_n$, the Hermitian adjoint of $F_n$, by the Fourier inversion theorem, $F^{H}_{n}(F_{n}\, z) = z$.

We denote $\|\cdot\|_p$ the usual $\ell_p$-norms on $\C(\Z)$:
$\|x\|_{p} = (\sum_{t \in \Z} \left| x_t \right|^p)^{1/p}$, $p \in [1, \infty]$. In most cases the argument will be finite-dimensional -- an element of $\C(\Z_{k,k'})$; we reserve the special notation $$\|x\|^{\vphantom{*}}_{n,p} = \|x_0^n\|_p.$$
Furthermore, DFT allows to equip $\C(\Z_{0,n})$  with the norms associated with $\ell_p$-norms in the spectral domain:
\[
\|x\|^*_{n,p} := \|x_0^n\|^*_{p} :=  \|F_{n}x_0^n\|_p, \quad p \in [1, \infty].
\]

Given observations \eqref{prob_model} and $\varphi\in \mathbb{C}(\Z_{0,m}),\;$ (with some terminology abuse we refer to $m\in \N_*$ as the filter \emph{bandwidth}) consider the {\em (left) linear estimation} of  $x$ associated with {\em filter} $\varphi$ given by
\[
\wh{x}_t = [\varphi*y]_t
\]
(using the standard statistical terminology, $\wh{x} $ is merely a ``left'' kernel estimate of $x_t$ using a kernel $\varphi$ supported on $[0,...,m]$).
Our objective is, using only the data, mimic an ``ideal'' filter $\varphi_*\in \C(\Z_{0,m})$, which recovers $x_n$ with small error. In other words, our objective is to build an adaptive filter $\wh\varphi\in\C(\Z_{0,m})$ which estimates $x_n$ from observations \rf{prob_model} with the error ``close'' to that of the ``ideal'' estimator. Let us consider the following construction.
\paragraph{Estimate construction.} Given $m,n\in \N_*$ and $\overline\varrho>0$, let $\wh \varphi_C$ be an optimal solution to the optimization problem
\[
\widehat\varphi_C \in \Argmin_{\varphi\in \C(\Z_{0,m})}\left\{\|y-\varphi*y\|^2_{n,2}:
\|\varphi\|_{m,1}^*\leq {\overline{\varrho}/\sqrt{m+1}}\right\}. \eqno{\rm (CE)}
\]
We refer to $\wh x_n=[\wh\varphi_C*y]_n$ as {\em constrained estimator} of $x_n$.
We also consider {\em penalized estimator} $\wh x_n=[\wh\varphi_P*y]_n$ where
\[
\widehat\varphi_P \in \Argmin\limits_{\varphi \in \C(\Z_{0,m}) }
{\|y-\varphi*y\|^2_{n,2}} + \lambda \sigma^2\left[\|\varphi\|^*_{m,1}\right]^2. \eqno{\rm (PE)}
\]
{\color{red} Note that both (CE) and (PE) are solvable.
As we see, instead of the knowledge of $\varrho$, the penalized estimator essentially requires some knowledge of the noise variance.
We will show that, as long as the penalization parameter is set $\lambda = \cO(1)$, the $\ell_2$ error of the penalized estimator enjoys essentially the same bound as that for the constrained estimator with the ``optimal'' constraint $\overline{\varrho}$ which balances the error of the oracle and its norm in the best possible way.

Hence, in practice we recommend to choose the penalized formulation whenever possible, i.e. whenever the noise variance is known or can be estimated from data.
}

\section{Main result}\label{sec:oracle}
\subsection{$\ell_2$-oracle inequalities}
To analyse the adaptive recoveries we need the following assumption.
\begin{ass}\label{ass:subspace}
{True signal $x \in \C(\Z)$ admits the decomposition $x=x^{\mathcal{S}}+\varepsilon$ with $ x^{\mathcal{S} }\in \mathcal{S},$
where $\mathcal{S}$ is an unknown shift-invariant complex subspace of $\C(\Z)$ of dimension $s$, $1 \le s\le n+1$, and $\varepsilon$ is bounded in the $\ell_2$-norm as follows: for some $\varkappa \ge 0$ and all $\tau \in [0,m],$
\begin{align}\label{eq:eps-small}
\left\|\Delta^{\tau} \varepsilon\right\|_{n,2} \leq \varkappa \aic{\sigma}{\sqrt{n+1}}.
\end{align}}
\end{ass}
\aic{}{Modify according to new definition of $\varkappa$!}
In other words, we assume that
there exists an (unknown) shift-invariant linear subspace $\S \subset \C(\Z)$, $\Delta \S \subseteq \S$, of (a small) dimension $s$, to which the true signal $x$ is close.

To continuer we need the following {\em oracle inequalities} for the $\ell_2$ loss of adaptive estimators which are also of interest for their own sake.

\begin{theorem}\label{th:l2con}
Let $m,n\in \N_*$, $\overline\varrho\geq 1$, and let $\wh\varphi$ be an optimal solution to  {\em (CE)}.
Suppose that Assumption~\ref{ass:subspace} holds with some $s$ and $\varkappa$, and let $\varphi \in\C(\Z_{0,m})$ be feasible to {\em (CE)}, i.e. $\|\varphi\|^*_{m,1}\leq {\overline{\varrho}/\sqrt{m+1}}$.
\par
Then
for any $\alpha \in (0,1)$, there exists a set $\Xi_\alpha$ of realizations of the noise $\zeta$ such that $\P\{\zeta \in \Xi_\alpha\} \ge 1-\alpha$, and whenever $\zeta \in \Xi_\alpha$,
\begin{equation}\label{eq:th1}

\left\|x -  \widehat\varphi * y \right\|_{n,2} \le \left\|x-\varphi * y\right\|_{n,2} + C\sigma r_0^{1/2} \end{equation}
where $\kappa_{m,n}=\sqrt{n+1\over m+1}$, and
\begin{equation}\label{eq:remainder-con}
r_0=r_0(\overline\varrho, s,\varkappa,\kappa_{m,n},\alpha):= \overline\varrho\kappa^2_{m,n}\ln[(m+n)/{\alpha}] + \overline\varrho\varkappa\sqrt{\ln[1/\alpha]} + s.
\end{equation}
\end{theorem}
Proof of Theorem \ref{th:l2con} is given in Appendix~\ref{sec:proracle}.
The counterpart of Theorem \ref{th:l2con} for the penalized estimator is as follows.

\begin{theorem}\label{th:l23pen}
Let $m,n\in \N_*$, and $\wh\varphi$  be an optimal solution to {\em (PE)} with some $\lambda>0$. Suppose that Assumption~\ref{ass:subspace} holds with some $s$ and $\varkappa$. Further, given any $\varrho\geq 1$, let $\varphi \in\C(\Z_{0,n})$ satisfy $\|\varphi\|^*_{m,1}\leq {\varrho/\sqrt{m+1}}.$
\par
Then for any $\alpha \in (0,1)$, there exists a set $\Xi_\alpha$ of realizations of the noise $\zeta$ such that $\mathbb{P}\{\zeta \in \Xi_\alpha\} \ge 1-\alpha$, and whenever $\zeta \in \Xi_\alpha$,
\begin{equation}\label{eq:l23pen1}
\left\|x - \widehat{\varphi} * y\right\|_{n,2} \le  \|x-\varphi*y\|_{n,2} + \sigma \left[ \lambda \varrho + C \lambda^{-1} r_1(\varkappa) + C'r^{1/2}_2 \right],
\end{equation}
where
\begin{align*}
&r_1=r_1(\varkappa,\kappa_{m,n},\alpha):= \kappa^2_{m,n}\ln[(m+n)/\alpha] + \varkappa\sqrt{\ln[1/\alpha]} + 1, \\
&r_2=r_2(\varrho,s,\varkappa,\alpha):= \varrho\ln[1/{\alpha}] + \varkappa\sqrt{\ln[1/\alpha]} + s.
\end{align*}
In particular, when choosing $\lambda=r_1^{1/2}$,
 we get\footnote{Clearly, the best choice of $\lambda=\sqrt{Cr_1/\varrho}$ cannot be implemented, since the parameter  $\varrho$ of $\varphi$ is unknown.}
\[
\left\|x - \widehat{\varphi} * y\right\|_{n,2} \le  \|x-\varphi*y\|_{n,2} + \sigma \left[ C''\varrho r^{1/2}_1 + C'r^{1/2}_2 \right],
\]
for $\zeta \in \Xi_\alpha$.
\end{theorem}
\dimacorr{}{We see that for the penalized least squares estimator, the additive price of adaptation is of order $\cO(\varrho^2)$ rather than $\cO(\varrho)$ as in the constrained case. }

\subsection{Pointwise results}\label{sec:pointwise}
Under the premise of Corollary \ref{cor:l2con}, i.e. when we have both signal simplicity \eqref{eq:ss1} and Assumption~\ref{ass:subspace}, one can also bound the error of the least squares recoveries. For simplicity, we state the guarantee for the constrained recovery with $\overline{\varrho} = \varrho$.

\begin{prop}\label{th:point}
With the same assumptions as in Corollary~\ref{cor:l2con}, LSC with  $\overline{\varrho} = 2\varrho$ satisfies the following: for any $\alpha \in (0,1)$, there exists a set $\Xi_\alpha$ of realizations of the noise $\zeta$ such that $\mathbb{P}\{\zeta \in \Xi_\alpha\} \ge 1-\alpha$, and whenever $\zeta \in \Xi_\alpha$,
\begin{equation}\label{eq:l2con-point}

\left|x_t - [\widehat\varphi * y]_t\right|^2 \lesssim \frac{\sigma^2\varrho}{n+1} \left[\varrho^2 (1 + \ln[1/\alpha]) + E_0(\varrho,\varkappa)\right],
\end{equation}
where $E_0$ is given by \eqref{eq:remainder-con}, and $t \in [m, n]$ (recall that $n=2m$). Hence, for the same $t$,
\[
\E\left|x_t - [\widehat\varphi * y]_t\right|^2 \lesssim \frac{\sigma^2\varrho}{n+1}\left(\varrho^2 + \varrho \ln n + \varrho\varkappa + s \right).
\]
\end{prop}

\dimacorr{}{Recalling the discussion after Theorem \ref{th:l2con}, we conclude the following. If we are interested with MSE at the last $m$ points, and we are not in the ``pessimistic regime'' of very big $\varkappa$, we have to pay a \textit{multiplicative} overhead of $\cO(\varrho^2 + \varrho \ln n)$ for adaptation to $\varphi^o$.}

\dimacorr{}{\begin{remark}[Extending the pointwise result]\label{rem:pointwise-to-l2}
{\em It is easy to see that the guarantee of Proposition \ref{th:point} can be extended from the interval $m,n$ to intervals $[m, Cn]$, for any $C > 1$, provided that the observations are on $[-n, Cn]$, and the signal is $(m,Cn,\varrho)$-simple. By rescaling $N=Cn$, we see that in the situation of \textit{filtering}, when one is permitted to use only unilateral filters and is given observations on $[-N,N]$, one may obtain a pointwise guarantee on $[cN,N]$ for $c < 1$ but not on the entire half-interval $[0,N]$. As we will see in Sec.~\ref{sec:interp}, in the situation of \textit{interpolation}, where one can use bilateral filters, the situation is different. In that case one can obtain the pointwise guarantees on the whole interval $[-N,N]$.}
\end{remark}}
\paragraph{Uniform fit recoveries.}

Consider another type of estimators, called the \textit{uniform fit} estimators, in which instead of the $\ell_2$-norm of the disrepancy term one minimizes the $\ell_\infty$ norm of its Fourier spectrum \cite{nemirovsky1991nonparametric,harchaoui2015adaptive}.
\textit{Constrained uniform fit} estimator $\widehat x = \widehat\varphi * y$ uses the filter\footnote{In fact, \cite{harchaoui2015adaptive} considered a counterpart of UFC, also constrained, which was made adaptive to the oracle norm via the epigraph trick, with the same bounds as for the constrained uniform fit estimator.}
\begin{equation}
\label{eq:l8-1}
\widehat\varphi \in \Argmin_{\varphi\in \C(\Z_{0,n})}\left\{\|y-\varphi*y\|^F_{n,\infty}:\;
\|\varphi\|_{n,1}^F\leq \overline{\varrho}/\sqrt{n+1}\right\},
\tag{UFC}
\end{equation}
and in this paper we also propose the \textit{penalized uniform fit} estimator
\begin{equation}
\label{eq:l8-2}
\widehat\varphi \in \Argmin_{\varphi\in \C(\Z_{0,n})} \|y-\varphi*y\|^F_{n,\infty}
+ \lambda\sigma\sqrt{n+1}\|\varphi\|_{n,1}^F.
\tag{UFP}
\end{equation}

The following proposition, extracted from \cite{harchaoui2015adaptive}, quantifies the statistical accuracy of the constrained uniform fit estimator. The guarantee holds only at the endpoint $t=n$.
\begin{prop}\label{th:l8con}
Assume that $x$ is $(m,n,\varrho)$-simple, with $\varrho\geq 1$, $m\in \Z_+$, and $n=2m$. Then,
any optimal solution~$\wh\varphi$ of~\eqref{eq:l8-1} with $\overline{\varrho} = 2\varrho$ satisfies the following: for any $\alpha \in (0,1)$, there exists a set $\Xi_\alpha$ of realizations of the noise $\zeta$ such that $\mathbb{P}\{\zeta \in \Xi_\alpha\} \ge 1-\alpha$, and whenever $\zeta \in \Xi_\alpha$,
\begin{equation}\label{th:bound:l8con}

\left|x_n - [\widehat\varphi * y]_n\right|^2 \lesssim \frac{\sigma^2\varrho^4 \ln[(n+1)/\alpha]}{n+1}.
\end{equation}
\end{prop}
Here we prove a similar bound for the penalized uniform fit estimator.
\begin{prop}\label{th:l8pen}
Assume the same as in Proposition~\ref{th:l8con}. If we choose $\lambda \ge 4\ln[(n+1)/\alpha] + 1$, any optimal solution $\wh\varphi$ of~\eqref{eq:l8-2} will satisfy the following: for any $\alpha \in (0,1)$, there exists a set $\Xi_\alpha$ of realizations of the noise $\zeta$ such that $\mathbb{P}\{\zeta \in \Xi_\alpha\} \ge 1-\alpha$, and whenever $\zeta \in \Xi_\alpha$,
\begin{equation}\label{th:bound:l8pen}
\left|x_n - [\widehat\varphi * y]_n\right|^2 \lesssim \frac{\sigma^2\varrho^4 \lambda}{n+1}.
\end{equation}
\end{prop}
Comparing Proposition \ref{th:l8con} with Proposition \ref{th:point}, we see that for simple signals, the uniform fit estimators lose by a factor of $\min(\varrho\ln n, \varrho^2)$ to the least squares estimators. Besides, the bounds for the uniform fit estimators hold only at the endpoint $t = n$ (although, given signal simplicity on a longer interval, they might be extended as in Remark \ref{rem:pointwise-to-l2}). On the other hand, Assumption~\ref{ass:subspace} is not needed for the uniform fit estimators to perform provably well.

\paragraph{Comparison for the quadratic risk.}
Let us now revisit the bounds for the quadratic risk $\E \|x-\widehat\varphi * y\|_{n,2}^2$. Recall that from Corollary \ref{cor:l2con}, for least squares estimators we have an ``ad hoc'' bound on the quadratic risk with a multiplicative price of adaptation $\varrho + \ln n$, much better than a guarantee extracted from the pointwise result of Theorem~\ref{th:point}, cf.~Remark~\ref{rem:pointwise-to-l2}. The situation with the uniform fit estimators is different. In this case, the only bound on the quadratic risk that we know is the one following from Propositions~\ref{th:l8con} and \ref{th:l8pen} combined with Remark~\ref{rem:pointwise-to-l2}. This bound suffers a large multiplicative overhead of $\varrho^3\log n$, and besides, it is only true on a restricted interval (cf. Remark~\ref{rem:pointwise-to-l2}).

\section{Simplicity, shift-invariance and difference equations}\label{sec:discussion}
Conditions of the results of Section \ref{sec:problem} merit some comments. The primary question is how  signal simplicity is related to  Assumption A about signal closeness to a shift-invariant subspace. Below we present results which shed some light on this relationship.

As we will see in an instant, signals which are uniformly close to shift-invariant subspaces are simple to interpolate. We  also show that an important subset of such signals -- those which are close to solutions of homogeneous linear difference equations with roots on the unit circle -- are also easy to filter and predict.

We start with a simple result which allows us to concentrate on time-invariant subspaces of $\C(\Z)$ -- solution sets of systems of homogeneous equations.

\begin{lemma}\label{th:shift-inv-approx-err}
Suppose that $\tilde x$ is $(m,n,\tilde\theta,\varrho)$-simple. Then, ${x} := \tilde x + \varepsilon$, where
\begin{equation}\label{eq:eps-unif}
\left\|\Delta^{\tau} \varepsilon\right\|_{n,\infty} \leq \varkappa, \quad 0 \le \tau \le m,
\end{equation}
is $(m,n,\theta,\varrho)$-simple with $\theta = 3(\tilde\theta^2 + (m+1)\varkappa^2/\varrho + \varkappa^2)$.
\end{lemma}
\paragraph{Proof.} Let $\varphi \in \C(\Z_{0,m})$ and $\tilde x\in \C(\Z)$ satisfy \eqref{eq:ss1}. Then for $0 \le t \le n$ one has
\bse
|x_t - [\varphi * x]_t|^2  &\le& 3|\tilde  x_t - [\varphi * \tilde x]_t|^2 +3|\varepsilon_t|^2 + 3|[\varphi* \varepsilon]_t|^2\\
&\leq& {3\tilde\theta^2\varrho\over m+1}+{3\varkappa^2}+3\|\varphi\|_2^2\|[\varepsilon]_{t-m}^t\|_2^2
\leq {3\varrho(\tilde\theta^2 + (m+1)\varkappa^2/\varrho + \varkappa^2)\over m+1}.\quad\quad\quad\mbox{\qed}
\ese

Observe that, when $\tilde x$ in the premise of Lemma \ref{th:shift-inv-approx-err} is an element of a shift-invariant subspace, Assumption A holds for $x=\tilde x+\varepsilon$. On the other hand, quite naturally, the requirement \rf{eq:eps-unif} of the lemma in this case is stronger than condition \rf{eq:eps-small} in Assumption A --  we need uniform closeness to the subspace to ensure simplicity.

\subsection{Simplicity of general shift-invariant subspaces}
As we have already mentioned in Section \ref{sec:problem}, shift-invariant subspaces of $\C(\Z)$ are closely related to homogeneous linear difference equations with constant coefficients. The following simple lemma states this formally (for completeness, we give a proof in Appendix~\ref{sec:prmisc}).

\begin{lemma}\label{th:shift_invariant}
Solution set of a homogeneous linear difference equation
\begin{equation}\label{eq:diff_eq}
[p(\Delta) x]_t \left[= \sum_{\tau = 0}^s p_\tau x_{t-\tau} \right] \equiv 0, \quad t \in \Z,
\end{equation}
where $p(z) = 1 + p_1 z + ... + p_s z^s$ is a polynomial of degree $s$, is a shift-invariant subspace of $\C(\Z)$ of dimension $s$. Conversely, any finite-dimensional shift-invariant subspace $\S$ of $\C(\Z)$ with $\dim(\S)= s$ is the set of solutions of some homogeneous difference equation \eqref{eq:diff_eq} with $\deg(p)=s$. Moreover, under condition $p(0)=1$ such polynomial is unique.
\end{lemma}
Note that solutions to \eqref{eq:diff_eq} are exponential polynomials
\begin{equation}\label{eq:exp_poly}
x_t = \sum_{k=1}^r \sum_{j = 0}^{m_k-1} C_{jk} \; t^{j} e^{\imath \omega_k t}, \quad \forall C_{jk} \in \C.
\end{equation}
where for  $k=1,\, ...,\, r \le s$, $\omega_k \in \C$,  $z_k = e^{\imath \omega_k}$ are the distinct roots of $p(\Delta)$ and $m_k$ are
the corresponding multiplicities. For instance, discrete-time polynomials $x_t=\sum_{k=0}^{s-1} c_k t^k$, $t\in \Z$, of degree $s-1$ (that is, exponential polynomials with all zero frequencies) form a linear space of dimension $s$ of solutions of the equation \eqref{eq:diff_eq} with $p(\Delta) = (1-\Delta)^s$, having coefficients $p_k=(-1)^k {s \choose k}$. Sum of harmonic oscillations $x_t = \sum_{k=1}^s c_k \e^{\imath \omega_k t}$ with all distinct frequencies $\omega_k \in [0,2\pi)$, is another example; here, $p(\Delta) = \prod_{k=1}^s (1-e^{\imath \omega_k}\Delta)$, and so on.

As the next result shows, elements of low-dimensional shift-invariant subspaces of $\C(\Z)$ (same as solutions of linear homogeneous difference equations with constant coefficients, by the above result) are ``almost'' simple. More precisely, such signals are always ``simple to interpolate'' -- there exists a \textit{bilateral} filter $\phi \in \C(\Z_{-m,m})$ of moderate $\ell_2$-norm which {\em exactly} reproduces the signal.
\begin{prop}\label{th:shift-inv-bilateral}
Suppose that $\S$ is an $s$-dimensional subspace of $\C(\Z)$, $x\in \S$, and $s \le k+1$. Then there exists a filter $\phi \in \C(\Z_{-k,k})$ such that
\begin{equation}\label{eq:interps}
\|\phi\|_2\leq \sqrt{s\over k+1}, \;\;\mbox{and}\;\;
x_t-[\phi * x]_t=0 \;\; \text{for any} \;\; t \in \Z.
\end{equation}
\end{prop}
The proof or the proposition is given in Appendix~\ref{sec:prdisc}.
\par
In other words,
given a $s$-dimensional time-invariant subspace $\S$ of $\C(\Z)$, one can build an {\em  interpolating filter} $\phi\in \C(\Z_{-k,k})$ of $\ell_2$-norm not exceeding $\sqrt{s\over k+1}$ which exactly reproduces all $x\in \S$. When combining the result of the proposition with the reasoning in the proof of Lemma \ref{th:shift-inv-approx-err} in the case of interpolating $\varphi$ with $\tilde \theta=0$  we get the following simple
\begin{corollary}\label{cor:s-interp-simple}
Let $\S$ be an $s$-dimensional time-invariant subspace of $\C(\Z)$, $x^{\S}\in \S$ and $x=x^{\S}+\varepsilon$, such that
\[
\left\|\Delta^{\tau+n} \varepsilon\right\|_{2n,\infty} \leq \varkappa,\quad -k \le \tau \le k, \quad k+1\geq s.
\]
Then there is a filter $\phi\in \C(\Z_{-k,k})$ such that

?????????????

\[
\|\phi\|^2_{2}\leq {s\over k+1}, \;\;\mbox{and}\;\;
|x_\tau-[\phi*x]_{\tau}|^2\leq 2{\varkappa^2+\varkappa^2(2k+1)/2s\over k+1}.
\]
In other words, such $x$ is $(2k,n,\theta,2s)$-simple with
\[
\theta=2\sqrt{\varkappa^2+{\varkappa^2(2k+1)\over 2s}}
\]
\end{corollary}

On the other hand, it is clear that Assumption~\ref{ass:subspace} is not sufficient to imply the simplicity of $x$ according to Definition~\ref{def:simple}, i.e. when one is allowed to use only unilateral filters.

Indeed, one can see, for instance, that already the signals coming from the parametric family $\cX_\alpha=\{x\in \C(\Z):\,x_\tau=c\alpha^\tau, \,c\in \C\}$, with a given $|\alpha|>1$, which form a  one-dimensional space of solutions of the equation $x_\tau=\alpha x_{\tau-1}$, cannot be estimated consistently at $t=0$ using only observations on the left of $t$, and thus are not simple.
Of course, in the above example, the ``difficulty'' of the family $\X_\alpha$  is due to instability of solutions of the difference equation which ``explode'' when $\tau\to +\infty$. Note that signals $x\in \X_\alpha$ with $|\alpha|\leq 1$ (decaying exponents, oscillations, and their products) are simple. More generally, suppose again that $x$ belongs to a shift-invariant subspace, or equivalently (see Lemma~\ref{th:shift_invariant}), satisfies a difference equation \eqref{eq:diff_eq} with $p(z)=\sum_{k=0}^s p_k z^k$, where $p(z)$ is the corresponding characteristic polynomial with $\deg(p) = s$. When $p(z)$ possesses the roots {\em inside} the unit circle, the set of solutions to the equation \eqref{eq:diff_eq} contains ``unstable'' signals, unbounded as $\tau \to \infty$. Note that stability of solutions is related to the direction of the time axis: when the characteristic polynomial $p(z)$ has roots {\em outside} the unit circle, there are solutions which grow exponentially fast in the left direction $\tau \to -\infty$. In this case ``right filtering'' -- estimating $x_\tau$ using observations on the right of $\tau$ -- is impossible.

\subsubsection{Exact shift invariance: special case}\label{sec:harm-osc-simple}
A special situation where the signal is always simple arises when $p(z)$ has all its roots on the unit circle. In this case, solutions to \eqref{eq:diff_eq} are ``generalized harmonic oscillations'' (harmonic oscillations modulated by polynomials).

\begin{theorem}\label{th:sines} Let $s$ be a positive integer, and let $p=[p_0;\, ...;\, p_s]$ be such that
the polynomial $p(z)=\sum_{i=0}^s p_i z^i$ has all its roots on the unit circle. Then, for every integer $m$ satisfying
\[
m\gtrsim m(s):= s^2\ln(s+1),
\]
one can point out $\phi \in \C(\Z_{0,m})$

such that any solution to \eqref{eq:diff_eq} satisfies $x_t=[\phi*x]_t,$ $\forall t\in \Z,$ and
\begin{equation}\label{propofq}
\|\phi\|_2 \lesssim {\sqrt{\varrho(s,m)/m}}, \;\;\mbox{where}\;\;
\varrho(s,m) = \min\left\{s^{3}\ln(s+1),\,s^2\ln(ms+1)\right\}.
\end{equation}

\end{theorem}

This bound on the oracle norm can be improved under the additional assumption of separability. Specifically, write the roots of $p(\cdot)$ in the form $z_k = e^{2\pi\imath f_k}$, where the $f_k$ are real, and consider the minimal frequency separation,
\[
\delta_{\min}  := \min_{1 \le i \ne j \le s} {|f_i - f_j|},
\] where $|x-y|$ is the wrap-around distance on the unit circle. The following theorem, proved in Appendix \ref{sec:prdisc}, shows that if the separation is big enough, one can guarantee that $\varrho = \cO(s)$.
\begin{theorem}\label{th:sepsines}
Take any $u > 1$ and let
\begin{equation}\label{eq:min-sep}
\delta_{\min} \ge u/m.
\end{equation}

Then there exists a filter $\phi \in \C(\Z_{0,m})$ satisfying $x_t-[\phi * x]_t = 0$ for any $x\in \S$ and $t \in \Z$ such that
\be
\|\phi\|_2 \le \sqrt{{u+1\over u-1}{s\over m+1}},\ee{separated}
In particular, $\|\phi\|_2 \le \sqrt{3s/(m+1)}$ if  $\delta_{\min}\geq 2/m$.
\end{theorem}

\section{Extensions}\label{sec:extenstions}
\subsection{Interpolation and prediction}\label{sec:interp}
To keep things simple, so far we have been studying the \textit{filtering} formulation of the adaptive recovery problem. Here,, given observations on the domain $[-n,n],$ one would like to recover the signal on $[0,n]$ with a ``unilateral'' filter $\widehat\varphi \in \C(\Z_{0,n})$, so that the corresponding estimate is
\[\widehat x_t = [\widehat\varphi * y]_t = \sum_{\tau = 0}^n \widehat\varphi_\tau y_{t-\tau}, \quad  0 \le t \le n.\]
Following \cite[Sec.~3.2]{harchaoui2015adaptive}, let us consider a more general \textit{interpolation} setting. We add a parameter, ``stride'' $k$, which satisfies $0 \le k \le n$. Our goal is now to estimate the signal on $[-k,n-k]$, via a filter in $\C(\Z_{-k,n-k})$, i.e.
\[\widehat x_t = [\widehat\varphi * y]_t = \sum_{\tau = -k}^{n-k} \widehat\varphi_\tau y_{t-\tau}, \quad  -k \le t \le n-k.\]
In other words, the filter now uses observations on both sides of a target point, except for two cases: filtering $k = 0$, and ``reverse filtering'' $k = n$. If $n = 2k$, we encompass the case of interpolation by a symmetric bilateral filter $\varphi \in \C(\Z_{-k}^k)$.
\dimacorr{Given some $g \in \R$, one defines the parameter $\gamma = (g-1)/2$ and the ``left margin'' $\ell(n) := \gamma n$, and is given two (possibly overlapping) samples: $[y_{-n},\, ...,\, y_n]$ and $[y_{\ell(n)},\, ...,\, y_{\ell(n) + n}]$; note that for $g$ in $[-1,1]$, the second sample is fully contained in the first one.\footnote{In this section for simplicity we always assume that both $\ell(n)$ and $\ell(m)$ are integers.} Ideally we would like to recover $x_t$ on the domain of the second sample by a filter in $\C(\Z_{\ell,\,\ell + n})$. This breaks down to the following special cases.
\begin{enumerate}
\item
\textit{Interpolation}: $|g| \le 1$; the second sample is contained in the first one so that one observes only $y_{-n}^n$. If $|g| < 1$, $x_t$ is estimated via observations both on the left and on the right of $t$, and if $|g| = 1$, the filter is unilateral (we considered the case $g=1$ before). $g = 0$ corresponds to ``median'' interpolation, in which the filter is in the class $\C(\Z_{-n/2, n/2})$.
\item
\textit{Extrapolation}: $|g| > 1$; two samples partially overlap for $|g| \le 2$ and do not overlap for bigger $|g|$. One estimates $x_{\ell(n)}$ via $y_{-n}^0$, and $x_{\ell(n) + n}$ via $y_{0}^n$.
\end{enumerate}
}{}
Using the lag operator $[\Delta x]_t = x_{t-1}$, we can generalize the adaptive recoveries to the new setting. For example, the \textit{$k$-interpolating} constrained least squares estimator corresponds to
\begin{equation}\label{eq:l2-interp}
\widehat\varphi \in \Argmin_{\varphi\in \C(\Z_{-k, n-k})}\left\{\big\| \Delta^{k} \left[y-\varphi*y\right]\big\|^2_{n,2}: \quad
\big\|\Delta^{k}\varphi \big\|_{n,1}^F \leq \overline{\varrho}/\sqrt{n+1}\right\}.
\end{equation}
Inspection of the proofs of Theorems~\ref{th:l2con}~and~\ref{th:l23pen} shows that with obvious adjustments, these theorems remain true in the interpolation setting (we do not even have to adjust Assumption~\ref{ass:subspace}). However, in order to obtain the analogues of the pointwise results of Sec.~\ref{sec:pointwise}, it is necessary to generalize the notion of simplicity.

\begin{definition}\label{def:simple-interp}
$x \in \C(\Z)$ is {\rm $(m,n,k,\varrho)$-interpolable}, with $m,n,k \in \Z_+$, $\varrho\geq 1$, and $0 \le k \le m$, if there exists a filter $\varphi \in \C(\Z_{-k,m-k})$ such that
\begin{equation*}
\E\left\{|x_t - [\varphi * y]_t|^2\right\} \le \frac{\varrho\sigma^2}{m+1}, \quad -m-k\leq t\leq n - k.
\end{equation*}
\end{definition}
Interpolable signals essentially retain the property \eqref{eq:l1f}--\eqref{eq:var2f}. Indeed, fixing $n=2m$ for simplicity, it is easy to see that the filter $\varphi^o = \varphi * \varphi \in \C(\Z_{-2k,n-2k})$ satisfies $\|\Delta^{2k}\varphi^o\|_{n,1}^F \leq 2\varrho/\sqrt{n+1},$ and
\begin{equation*}
\E\left\{|x_t - [\varphi^o * y]_t|^2\right\} \lesssim {\varrho^2\sigma^2\over {m+1}}, \quad -2k \leq t \leq n-2k.
\end{equation*}
Note that $\varphi^o$ is feasible for the $2k$-interpolating estimator with $\overline\varrho \ge \varrho$. Hence, repeating the arguments of Corollary \ref{cor:l2con} and Proposition \ref{th:point}, we can generalize the results of Section \ref{sec:pointwise}. For example, we have the following statement.

\begin{prop}\label{th:l2con-interp}
Assume that $x\in \C(\Z)$ is $(m,n,k_0,\varrho)$-interpolable with $\varrho\geq 1$ and $n=2m$. Let Assumption~\ref{ass:subspace} hold. Then, the estimator corresponding to~\eqref{eq:l2-interp} with $\overline{\varrho} = 2\varrho$ and $k = 2k_0$ satisfies the following: for any $\alpha \in (0,1)$, there exists a set $\Xi_\alpha$ of realizations of the noise $\zeta$ such that $\mathbb{P}\{\zeta \in \Xi_\alpha\} \ge 1-\alpha$, and whenever $\zeta \in \Xi_\alpha$,
\begin{align}

\big\| \Delta^{2k_0} [x - \widehat \varphi * y] \big\|^2_{n,2} \lesssim \sigma^2
&\left[\varrho^2(1 + \ln[1/\alpha]) + E_0(\varrho,\varkappa)\right],\label{eq:interp-l2-loss}\\

\left|[x - \widehat\varphi * y]_{t}\right|^2 \lesssim \frac{\sigma^2\varrho}{n+1}
&\left[\varrho^2 (1 + \ln[1/\alpha]) + E_0(\varrho,\varkappa)\right], \quad t \in [m-3k_0, n-3k_0],\label{eq:interp-point}
\end{align}
where $E_0$ is given by \eqref{eq:remainder-con}.
\end{prop}

\begin{remark}\label{rem:blocks}
{\rm As a result of \eqref{eq:interp-l2-loss}, if we assume that the signal is interpolable for $k = 0$ and $k = m$, we instantly get a bound on the $\ell_2$-loss on the whole observation domain $[-n,n]$, computing only two different filters, a ``left'' filter in $\C(\Z_{0,n})$, and a ``right'' filter in $\C(\Z_{-n,0})$. Moreover, from \eqref{eq:interp-point} it follows that if $m \ge 2$, and the signal is interpolable for all $k \in [0,m]$, we get a pointwise guarantee on $[-n,n]$, computing no more than $5$ different filters.}
\end{remark}

We can extend of the interpolation setting to the \textit{prediction setting} by formally letting $k$ be negative. Specifically, for some "predicting horizon" $h \in \Z_+$ which may be thought of as $h=-k$, we are given observations on $[-n,0]\cup [h,n+h]$, and are asked to recover the signal on $[h,n+h]$ via some ``predicting'' filter in $\C(\Z_{h,n+h})$,
\[\widehat x_t = [\widehat\varphi * y]_t = \sum_{\tau = h}^{n+h} \widehat\varphi_\tau y_{t-\tau}, \quad  h \le t \le n+h.\]
Completely in the same way as in the case of interpolation, we can define, for example, the~\textit{$h$-predicting} counterpart of~\eqref{eq:l2-1}, where we search for a filter which minimizes the empirical error of reproducing the observations on $[h,n+h]$:
\begin{equation}\label{eq:l2-predict}
\widehat\varphi \in \Argmin_{\varphi\in \C(\Z_{h, n+h})}\left\{\big\| \Delta^{-h} \left[y-\varphi*y\right]\big\|^2_{n,2}: \quad
\big\|\Delta^{-h}\varphi \big\|_{n,1}^F \leq \overline{\varrho}/\sqrt{n+1}\right\}.
\end{equation}
We can also define its penalized counterparts. The oracle inequalities of Section \ref{sec:oracle} remain valid for these estimators provided that Assumption \ref{ass:subspace} holds on $[-n,n+h]$.

Now, consider an analogue of Definition \ref{def:simple-interp}.
\begin{definition}\label{def:simple-predict}
$x \in \C(\Z)$ is {\rm $(m,n,h,\varrho)$-predictable}, with $m,n,h \in \Z_+$, $\varrho\geq 1$, if there exists a filter $\varphi \in \C(\Z_{h,m+h})$ such that
\begin{equation*}
\E\left\{|x_t - [\varphi * y]_t|^2\right\} \le \frac{\varrho\sigma^2}{m+1}, \quad -m+h\leq t\leq n+h.
\end{equation*}
\end{definition}
It is easy to make sure that $(m,n+h,h,\varrho)$-predictability guarantees the existence of a ``good'' oracle for $2h$-predicting least squares estimators, i.e. a  filter in $\C(\Z_{2h,n+2h})$ with a small $\ell_1$ norm of the Fourier transform, which reproduces $x$ on $[2h,n+2h]$ with a small error.

Finally, let us formulate a counterpart of Propostition \ref{th:l2con-interp}.
\begin{prop}\label{th:l2con-predict}
Assume that $x\in \C(\Z)$ is $(m,n+2h_0, h_0 \rceil,\varrho)$-predictable with $\varrho\geq 1$ and $n=2m$. Let Assumption~\ref{ass:subspace} hold on $[-n,n+2h_0]$. Then, given observations on $[-n,n+2h_0]$, the estimator corresponding to~\eqref{eq:l2-predict} with $\overline{\varrho} = 2\varrho$ and $h = 2h_0$ satisfies the following: for any $\alpha \in (0,1)$, there exists a set $\Xi_\alpha$ of realizations of the noise $\zeta$ such that $\mathbb{P}\{\zeta \in \Xi_\alpha\} \ge 1-\alpha$, and whenever $\zeta \in \Xi_\alpha$,
\begin{align}

\big\| \Delta^{-2h_0} [x - \widehat \varphi * y] \big\|^2_{n,2} \lesssim \sigma^2
&\left[\varrho^2(1 + \ln[1/\alpha]) + E_0(\varrho,\varkappa)\right],\label{eq:predict-l2-loss}\\

\left|[x - \widehat\varphi * y]_{t}\right|^2 \lesssim \frac{\sigma^2\varrho}{n+1}
&\left[\varrho^2 (1 + \ln[1/\alpha]) + E_0(\varrho,\varkappa)\right], \quad t \in [m+3h_0, n+3h_0],\label{eq:predict-point}
\end{align}
where $E_0$ is given by \eqref{eq:remainder-con}.
\end{prop}
The message of this result is that, given observations on the domain $[-n,n+2h_0]$, one can in fact \textit{predict} the signal beyond this domain, within the ``prediction horizon'' up to the point $t = n+3h_0$.

\section{Applications}\label{sec:applications}

\subsection{Shift-invariance, recoverability, and generalized harmonic oscillations}
Let us look in more detail at the question of how simplicity and recoverability, see Definitions \ref{def:simple} and \ref{def:simple-interp}, are related to  approximate shift-invariance according to Assumption \ref{ass:subspace}.

\subsubsection{Approximate shift-invariance of simple/recoverable signals}\label{sec:smooth}
We start by noting that \textit{all} known to us examples of simple/recoverable signals,  see e.g. \cite[Sec.~4]{jn2-2010}, actually do satisfy Assumption~\ref{ass:subspace} with $\varkappa$ in either of two regimes introduced in Sec.~\ref{sec:oracle}. Let us illustrate it for both regimes.

\paragraph{Parametric regime: polynomials.} Returning to Sec.~\ref{sec:discussion}, again consider estimation of a discrete polynomial of degree $s \le n+1$ on the regular grid. If infinitely continued into both directions, the signal obviously belongs to a shift-invariant subspace of dimension $s$, and hence satisfies Assumption~\ref{ass:subspace} with $\varkappa = 0$. On the other hand, we will see below that such a signal is $(m, n,\tilde\cO(s^2))$-simple for any $m\ge s$ and $n \in \mathbb{N}$, cf. Theorem~\ref{th:sines}, and $(2k,4k,k,\cO(s))$-interpolable, cf. \eqref{eq:interps} for any $k \in \mathbb{N}$ and $s \le 2k$.

\paragraph{Non-parametric regime: curve estimation.} Let $f(t): [-1,1] \to \R$ be a function from a H\"older ball with some $L > 0$ and $s = k + \alpha > 0$ where $\alpha \in (0,1]$, meaning that $f$ has $k$ absolutely continuous derivatives, and $\forall t_1, t_2 \in [-1,1]$ one has
\[
|f^{(k)}(t_1) - f^{(k)} (t_2)|\le L |t_1-t_2|^{\alpha}.
\]
For some $N \in \mathbb{N}$, let $x_\tau = f\left({\tau/N}\right)$, $|\tau| \le N$. Provided that $N$ is big enough, $x$ is close, in the $\ell_2$-distance, to the shift-invariant subspace of polynomials of degree $k$. Indeed, consider the approximation of $f(t)$ by its $k$-th order Taylor polynomial in the origin $t =0$. For every $h \in (0,1)$, the error of this approximation over $|t| \le h$ is uniformly bounded by $C_s Lh^s$. In other words, for $n = hN$ it holds that the error of approximating $x$ by its projection on some shift-invariant subspace satisfies $\| [\varepsilon]_{-n}^n \|_\infty \le C_s Lh^s$, where $\varepsilon_\tau := f(\tau/N) - p_k(\tau/N)$. Hence, Assumption~\ref{ass:subspace} holds with
\begin{equation}\label{eq:kappa-h}
\sigma \varkappa := C_s Lh^s \sqrt{n+1},
\end{equation}
where $n+1 := h(N+1)$. On the other hand, it can be shown that for any $n \in \mathbb{N}$ there exists a pair of filters $\varphi \in \C(\Z_{0,n/2})$ and $\varphi' \in \C(\Z_{-n/2,0})$ with $\ell_2$-norm at most $\rho / \sqrt{n+1}$ for some $\rho$ depending only on $s$, which exactly reproduce any discrete polynomial of degree $k$ at any point; for example, Theorem~\ref{th:sines} provides a bound $\rho(s) = O(s)$ up to the logarithmic factors. The error of reproducing the entire signal by such filters is controlled by the Cauchy-Schwartz inequality. For example, for each $0 \le \tau \le n$ one has
\[
|x_\tau - [\varphi * x]_\tau | = |\varepsilon_\tau - [\varphi * \varepsilon]_\tau | \le |\varepsilon_\tau| + \|\varphi\|_2 \|[\varepsilon]_{\tau-n}^\tau\|_{n,2} \le C_s Lh^s,
\] where the last inequality follows from the previous bounds on $\varkappa(n)$; a complementary bound holds on $[-n,0]$ for $\varphi'$. As a result,
\[
\E |x_\tau - [\varphi * y]_\tau|^2 \le C_s^2 L^2 h^{2s} + \frac{\sigma^2\rho(s)^2}{n+1},
\]
which prompts the choice of bandwidth $h$ balancing the terms in the right hand side. But with \eqref{eq:kappa-h} that gives $\varkappa = C_s \rho(s)$, depending only on $s$, i.e. we find ourself in the non-parametric regime. On the other hand, for such $n$ there exist an oracle of length $n$ to which we can adapt, within a multiplicative factor depending only on $s$, e.g. by solving~\eqref{eq:l2-2}. Finally, note that this argument can be repeated for any point of the grid (at the points close to the border we have one of two unilateral oracle filters at our disposal). A simple calculation shows that as such one recovers the correct minimax rate $N^{-s/(2s+1)}$ of estimating a function over a H\"older ball for the pointwise loss on the grid \cite{nemirovski2000topics,tsybakov_mono}.

Of course, in the above example, there is nothing to adapt to, since the subspace is known, and the oracle filter can be found explicitly. The situation changes, however, when the signal is modulated by a harmonic oscillation of arbitrary frequency, i.e. one considers $\tilde f(t) = e^{\imath\omega t} f(t)$ with $f(t)$ as above. Then the same reasoning can be repeated almost word-by-word (one approximates $\tilde f(t)$ by the modulated Taylor approximation of $f(t)$, and one recovers the same rate $N^{-s/(2s+1)}$ \textit{without knowledge of the modulation frequency.} This becomes even more surprising if we notice that $\tilde f(t)$ can be made \textit{arbitrarily} non-smooth by choosing a large enough frequency.

\subsection{Harmonic oscillations}
Let us revisit the situation considered in Section \ref{sec:harm-osc-simple}, where the characteristic polynomial $p$ has all its roots on the unit circle, and as such, the ``true'' signal is an exponential polynomial \eqref{eq:exp_poly} with \textit{real} frequencies $\omega_k$; further, we call such signals \textit{generalized} harmonic oscillations. The problem of denoising a generalized harmonic oscillation, given observations \eqref{prob_model}, generalizes the well-known problem of \textit{line spectral estimation}, see \cite{recht1,recht2} and references therein. In line spectral estimation, it is additionally assumed that the roots of $p$ are pairwise distinct (and hence the generalized harmonic oscillation becomes an \textit{ordinary} harmonic oscillation $x_t = \sum_{k=1}^s C_k e^{\imath 2\pi f_k t}$). Let us see how our methods can be applied to line spectral estimation, assuming, in addition, that our goal is to recover the signal \textit{at the whole observation domain}.
If the underlying structure of such a signal, as given by the set of its frequencies, is known, the usual least squares estimator has small risk:
\begin{equation}\label{eq:sines-correct-rate}
\MSE(s) \bigg[:= \E \sum_{|t| \le n} |x_t - \wh x_t|^2 \bigg] \lesssim \sigma^2 s,
\end{equation}
which is known to be optimal. As such, the ultimate goal of adaptive estimators in this problem is to approach this bound not knowing the frequencies.

Until recently,

the only estimator in this problem with known non-asymptotic guarantees for the rate of convergence has been Atomic Soft Thresholding \cite{recht1,recht2}. This estimator indeed achieves the rate $\sigma^2 s \log n$ in the case of \textit{well-separated} frequencies (cf. Proposition~\ref{th:sepsines})\footnote{In \cite{recht2}, the logarithmic factor was shown to be unavoidable in a certain sense.}. In the general case, the convergence rate of Atomic Soft Thresholding was known to be $\cO(\sigma\|x\|^F_1\sqrt{sn}$), where $\|x\|^F_1$ is the limit of the $\ell_1$ norm of the signal Fourier transform as $n$ approaches infinity. It was an open question whether there existing algorithms were suboptimal, or a tight lower bound held.

The first successful attempt to bridge this gap was undertaken by the authors of the present paper in \cite{harchaoui2015adaptive} by means of the uniform fit estimators. A fact essentially equivalent to our Proposition \ref{th:l8con} was applied together with the first bound of \eqref{propofq}, Theorem \ref{th:sines}, which gave the convergence rate
\begin{equation*}
\MSE(s) \lsim \sigma^2 s^{12}
\end{equation*}
up to logarithmic factors. As such, the optimal dependency on $\sigma$ was obtained, and the question boiled down to improving the dependency on $s$ (note that the second bound of \eqref{propofq}, proved in this paper, improves the dependency on $s$ to $s^{8}$). Using the least squares estimators introduced in this paper, we get substantial improvements. Indeed, note that a harmonic oscillation with $s$ frequencies satisfies Assumption \ref{ass:subspace} with $\varkappa = 0$. Hence, using Theorem \ref{th:l2con} and the second bound of \eqref{propofq}, we get that for the estimator corresponding to~\eqref{eq:l2-1}\footnote{More precisely, one first solves~\eqref{eq:l2-1} to recover $x$ on $[0,n]$, and then the ``reflected'' version of~\eqref{eq:l2-1}, see Section~\ref{sec:interp}, for recovery on $[-n,0]$.}, it holds
\[
\MSE(s) \lsim \left\{
\begin{array}{ll}
\sigma^2 s^4, \quad &\textup{in the non-separated case},\\
\sigma^2 s^2, \quad &\textup{in the well-separated case}.
\end{array}\right.
\]
In the well-separated case, we can improve the exponent to $s^2$ by using Theorem \ref{th:sepsines} instead of Theorem \ref{th:sines}.

Moreover, it turns out that combining several least squares estimators, we can improve the exponent to $s^3$ in the general case.
\begin{prop}\label{th:sines-best}
There is an estimator $\widehat x$ satisfying
\[
\MSE(s) \lsim \left\{
\begin{array}{ll}
\sigma^2 s^3, \quad &\textup{in the non-separated case},\\
\sigma^2 s^2, \quad &\textup{in the well-separated case}.
\end{array}\right.
\]

\end{prop}
The proof of this proposition is given in Appendix \ref{sec:prmisc}.

\bibliographystyle{abbrv}
\bibliography{references}

\appendix
\section{Preliminaries}
We start with  introducing several objects heavily used in the proofs. We denote $\langle\cdot,\cdot\rangle$ the Hermitian scalar product: for $a,b\in \C^n$,
$\langle a,b\rangle=a^Hb$. For $a, b\in \C(\Z)$ we reserve the shorthand notation
\[
\langle a,b\rangle_n:=\langle a_0^n,b_0^n\rangle=[a_0^n]^Hb_0^n.
\]
By the Parseval identity
\[
\langle a,b\rangle_n:=\langle F_na,F_nb\rangle;
\]
 in particular, $\|x\|_{n,2} = \|x\|^*_{n,2}$.

\paragraph{Convolution matrices.} We use matrix-vector representations of the discrete convolution.
\begin{itemize}
\item
Given $y \in \C(\Z)$, we associate to it an $(n+1)\times(m+1)$ Toeplitz matrix
\be
T(y)=

\left[\begin{array}{llll}
y_{0}&y_{-1}&...&y_{-m}\\
y_{1}&y_{0}&...&y_{1-m}\\
...&...&...&...\\
y_{n}&y_{n-1}&...&y_{n-m}
\end{array}\right].
\ee{s(psi)}
such that $[\varphi*y]_{0}^n = T(y) \varphi_{0}^m$ for $\varphi \in \C(\Z_0^m)$. Its squared Frobenius norm satisfies
\be
\left\|T(y)\right\|_F^2 = \sum\limits_{\tau=0}^m\|\Delta^\tau y\|^2_{n,2}.
\ee{tr21}
\item
Given $\varphi \in \C(\Z_0^m)$, consider an $(n+1)\times(m+n+1)$ matrix
\be
M(\varphi)=
\left[\begin{array}{llllllll}
\varphi_{m}&\varphi_{m-1}&...&\varphi_{0}&0&0&...&0\\
0&\varphi_{m}&...&...&\varphi_{0}&0&...&0\\
...&...&...&...&...&...&...&...\\
0 &...&...&...&0&\varphi_{m}&...&\varphi_{0}
\end{array}\right].
\ee{M(phi)}
For $y \in \C(\Z)$ we have $[\varphi*y]_{0}^n=M(\varphi) y_{-m}^n$ and
\be
\left\|M(\varphi)\right\|_F^2= (n+1)  \|\varphi\|^2_{m,2}.
\ee{tr22}

\item
We also need circular convolution matrix $C(\varphi)\in \C^{(m+n+1)\times (m+n+1)}$ defined for $\varphi \in \C(\Z_0^m)$ according to

\be
C(\varphi) =
\left[\begin{array}{llllllll}
\varphi_{0} &0&...&0&\varphi_{m}&...&...&\varphi_{1}\\
...&...&...&...&...&...&...&...\\
\varphi_{m-1}&...&\varphi_{0}&0&...&...&0&\varphi_{m}\\
\varphi_{m}&...&...&\varphi_{0}&0&...&...&0\\
0&\varphi_{m}&...&...&\varphi_{0}&0&...&0\\
...&...&...&...&...&...&...&...\\
0 &...&0&\varphi_{m}&...&...&...&\varphi_{0}
\end{array}\right].
\ee{C(phi)}
Clearly,
\[
\left\|C(\varphi)\right\|_F^2 = (m+n+1) \|\varphi\|^2_{m,2}.
\]
Furthermore,

$C(\varphi)$ is diagonalized by the DFT:
\begin{equation}\label{eq:circ_diag}
C(\varphi) = F^H_{m+n} D(\varphi) F_{m+n},
\end{equation}
where $D$ is diagonal matrix satisfying
\[|[D]_{kk}|=\sqrt{m+n+1}|[F_{m+n}\varphi_0^{m+n}]_k|
\] where $\varphi_0^{n+m}\in \C^{n+m+1}$ is the filter obtained by padding $\varphi$ with $n$ leading zeros. Moreover, it holds for the nuclear norm $\|C(\varphi)\|$ of $C(\varphi)$:

\be
\|C(\varphi)\|&=& \|D\|=\sqrt{m+n+1}\|\varphi_0^{n+m}\|^*_{n+m,1}\nn
&\leq& {m+n+1\over \sqrt{m+1}}(\ln[m+n+1]+3) \|\varphi\|^*_{m,1},
\ee{eq:C-ell1}
where the last inequality is due to the following result.
\begin{lemma}\label{lemma:zero_padding}
Let $u\in \C^{m+1}$, and let $u_0=[\underbrace{0;...;0}_{n};u]\in \C^{m+n+1}$, $n \ge 1$. Then

\begin{equation*}
\|u_0\|^*_{m+n,1}\le \sqrt{m+n+1\over m+1}  (\ln[m+n+1]+3)\|u\|^*_{m,1}.
\end{equation*}
\end{lemma}
\paragraph{Proof.} We assume w.l.o.g. that $\|u\|^*_{m,1}=1$. Let $n\geq 1$. Observe that convex function $f(\bar{u})=\|(F^H_m \bar{u})_0\|^*_{m+n,1}$ attains its maximum over the set $\|\bar{u}\|^*_{1}\leq 1$ at a canonical orth ${e}_j$, $1\leq j\leq m+1$, of $\bR^{m+1}$. Let $u^j=F^H_m e_j$, so that
$[u^j]_\tau = \frac{1}{\sqrt{m+1}} \exp\left[-\frac{2\pi\imath \tau j}{m+1}\right]$. Thus, we have
\be
\gamma\big\|u^j_0\big\|^*_{m+n,1}
&=& \sum_{k=0}^{m+n} \Bigg| \sum_{\tau=0}^m \exp\Bigg[\imath2\pi\left(\frac{k}{m+n+1} - \frac{j}{m+1}\right)\tau\Bigg] \Bigg|
\\
&\leq & \max_{\theta \in [0,\pi]}\sum_{k=0}^{m+n} \left| D_m\left(\frac{\pi k}{m+n+1} -\theta\right)\right|,
\ee{eq:dirichlet_sum}
where $\gamma =\sqrt{(m+n+1)(m+1)}$, and
\[
D_m(x) =\sum_{\tau=0}^{m}e^{\imath \tau x} =\left\{
\begin{array}{ll}
\frac{\sin ((m+1)x)}{\sin(x)}, & \quad x \ne \pi l,\\
m+1, & \quad x = \pi l.
\end{array}\right.
\]

Observe that $|D_m(x)|\leq B_m(x)$ on the circle $\R/\pi \Z$, where
\[
B_m(x) = \min\left\{m+1,\,
\frac{\pi}{2 \min (x, \pi-x)}\right\}
\]
Now, let $\theta \in [0,\pi]$,

and let $x'$ and $x''$ be the two closest to zero points of the grid $\Gamma=\big\{-\theta,\ldots,{\pi(m+n)\over m+n+1}-\theta\big\}$. We have $D_m(x)\leq  m+1$ for $x=x',x''$, and $|D_m(x)| \le B_m(x)$ for the remaining points of $\Gamma$.
Because that $B_m(x)$ is nonincreasing over $[\frac{\pi}{m+n+1}, \frac{\pi}{2}]$ we obtain
\bse
\gamma\big\|u^j_0\big\|^*_{m+n,1}&\leq&
2(m+1) + \sum_{k=1}^{\left\lceil \frac{m+n-1}{2}\right\rceil} \frac{m+n+1}{k}
\\&\le& 2(m+1) + (m+n+1) \left(\ln\left[\frac{m+n+1}{2}\right]+1\right).\quad\quad\quad\quad\quad\quad\quad\quad
\mbox{\qed}
\ese
\end{itemize}

\paragraph{Deviation bounds.} We use the following simple facts about Gaussian random vectors.
\begin{itemize}
\item
Let $\zeta \sim \C\N(0,I_n)$ be a standard complex Gaussian vector meaning that $\zeta = \xi_1 + \imath\xi_2$ where $\xi_{1,2}$ are two independent draws from $\N(0,I_n)$. We will use a simple bound
\begin{align}\label{eq:complex_gaussian_max}
\prob\left\{\|\zeta\|_{\infty} \le \sqrt{2\ln n + 2u}\right\} \ge 1-e^{-u}
\end{align}
which may be checked by explicitly evaluating the distribution since $|\zeta_1|^2_2 \sim \text{Exp}(1/2)$.\newline
\item
The following deviation bounds for $\|\zeta\|^2_2 \sim \chi^2_{2n}$ are due to \cite[Lemma 1]{lama2000}:
\begin{align}\label{eq:chi_bound_low}
\prob\left\{\half \|\zeta\|^2_2 \le n + \sqrt{2nu} + u \right\} \ge 1-e^{-u}, \quad
\prob\left\{\half \|\zeta\|^2_2 \ge n - \sqrt{2nu} \right\} \ge 1-e^{-u}.
\end{align}
By simple algebra we obtain an upper bound for the norm:
\begin{align}\label{eq:chi_bound}
&\prob\left\{\|\zeta\|_2 \le \sqrt{2n} + \sqrt{2u} \right\} \ge 1-e^{-u}.
\end{align}
\item
Further, let $K\in \H^n$ (an $n \times n$ Hermitian matrix) with the vector of eigenvalues $\lambda = [\lambda_1;\, ...;\, \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]$. Hence, we have $\text{Tr}(B) = 2\text{Tr}(K)$, $\|B\|^2_F = 2\|K\|_F^2$ and $\|B\| = \|K\| \le \|K\|_F$, where $\|\cdot\|$ and $\|\cdot\|_F$ denote the spectral and the Frobenius norm of a matrix. Invoking \cite[Lemma 1]{lama2000} again (a close inspection of the proof shows that the assumption of positive semidefiniteness can be relaxed), we have
\begin{align}\label{trq2}
\prob\left\{\half \zeta^H K \zeta \leq \Tr(K) + (u + \sqrt{2u})\|K\|_F\right\} \geq 1-e^{-u}.

\end{align}
Further, when $K$ is positive semidefinite, we have $\|K\|_F \le \text{Tr}(K)$, whence
\begin{align}\label{trq1}
\prob\left\{\half\zeta^H K \zeta\leq \Tr(K)(1+\sqrt{u})^2\right\} \geq 1-e^{-u}.
\end{align}
\end{itemize}

\section{Proofs for Section~\ref{sec:oracle}}\label{sec:proracle}

Despite striking similarity with Lasso and Danzig selector \cite{tibshirani,candes2007danzig,bickel2009simultaneous}, the estimators of section \ref{sec:general} are of quite different nature. First of all, the $\ell_1$-minimization in these  procedures is aimed to recover a filter but not the signal itself, and this filter is not sparse.\footnote{Unless we consider recovery of signal composed of harmonic oscillations with frequencies on the Fourier grid.} The equivalent of ``regression matrices'' involved in these procedures cannot be assumed to satisfy {\em Restricted Eigenvalue} or {\em Restricted Isometry} conditions, usually imposed to prove statistical properties of ``classical'' $\ell_1$-recoveries. Moreover, being constructed from the noisy signal itself, these matrices depend on the noise, which poses some extra difficulties in the analysis of the properties of these estimators. Let us briefly illustrate these difficulties.

Given $y\in\C(\Z_{-n}^n)$ let  $T(y)$ be
the $(n+1)\times(n+1)$ ``convolution matrix,'' as defined in \eqref{s(psi)}

such that for $\varphi \in \C(\Z_0^n)$ $[\varphi*y]_{0}^n = T(y) \varphi_{0}^n$. When denoting
$f=F_n\varphi$, the optimization problem in \eqref{eq:l2-1} can be recast as
a ``standard'' $\ell_1$-constrained least-squares problem with respect to $f$:
\be
\min_{f\in \C^{n+1}}\left\{\|y-A_nf\|_2^2:\;\|f\|_1\leq \overline{\varrho}/\sqrt{n+1}\right\}
\ee{eq:f2p1}
where $A_n=T(y)F^{-1}_n$. Observe that $f^o=F_n\varphi^o$ is feasible for \eqref{eq:f2p1}, so that
\[
\|y-A_n\wh{f}\|_{n,2}^2\leq \|y-A_nf^o\|_{n,2}^2,
\]
where $\wh{f}=F_n\wh{\varphi}$, so that
\[\begin{array}{l}
\|x-A_n\wh{f}\|_{n,2}^2-\|x-A_nf^o\|_{n,2}^2\leq 2\sigma \left(
\Re\langle\zeta,x-A_nf^o\rangle_n
-\Re\langle \zeta,x-A_n\wh{f}\rangle_n\right)\\\leq
2\sigma \big|\langle\zeta,A_n(f^o-\wh{f})\rangle_n\big|\leq
2\sigma \|A_n^H\zeta_{0}^n\|_\infty\|f^o-\wh{f}\|_1\leq 4\sigma \|A_n^H\zeta_{0}^n\|_\infty{\overline{\varrho}\over \sqrt{n+1}}
\end{array}\]
In the ``classical'' situation, where $\zeta_{0}^n$ is independent of $A_n$ (see, e.g., \cite{judnem2000}), the norm $\|A_n^H\zeta_{0}^n\|_\infty$ is bounded by $c_\alpha \sqrt{\ln n}\max_{j}\|[A_n]_j\|_2\leq c_\alpha \sqrt{n\ln n}\|A_n\|_\infty$ where $\|A\|_\infty=\max_{i,j}|A_{ij}|$ and $c_\alpha$ is a logarithmic in $\alpha^{-1}$ factor. This would rapidly lead to the bound \eqref{eq:th1} of the theorem.
In the case we are interested in, where $A_n$ incorporates observations $y_{-n}^n$ and thus depends on $\zeta_0^n$, curbing the cross term is more involved and requires extra assumptions, e.g. Assumption~\ref{ass:subspace}.
\subsection{Extended formulation}
We will prove simple generalizations of the theorems of Section \ref{sec:oracle} in the case where the length $n$ of the ``validation sample'' may be different from the length $m$ of the filter. Specifically, we consider the ``skewed'' sample
\begin{align}\label{prob_model_mn}
y_\tau = x_\tau + \sigma \zeta_\tau \quad -m \le \tau \le n,
\end{align}
with
\[
\kappa_{m,n} := \sqrt{\frac{n+1}{m+1}}.
\]
Accordingly, we generalize~\eqref{eq:l2-1}~and~\eqref{eq:l2-2} to
\begin{align}
\label{eq:l2-1-mn}
&\wh\varphi\in \Argmin_{\varphi\in \C(\Z^{m}_0)}\big\{\|y-\varphi*y\|_{n,2}:\;
\|\varphi\|_{m,1}^F\leq \overline{\varrho}/\sqrt{m+1}\big\}\tag{LSC$'$}\\
&\wh\varphi \in \Argmin\limits_{\varphi \in \C(\Z_{0}^{m}) }
{\|y-\varphi*y\|^2_{n,2}} + \lambda \sigma^2\left[\|\varphi\|^F_{m,1}\right]^2. \tag{LSP$'$}
\label{eq:l2-2-mn}
\end{align}
The corresponding modification of Assumption A is as follows:
\paragraph{Assumption A$'$}
{\em Let $\mathcal{S}$ be a (unknown) shift-invariant linear subspace of $\C(\Z)$, $\Delta \mathcal{S} = \mathcal{S}$, of dimension $s$, $1 \le s \le n+1$.
We suppose that $x$ admits the decomposition:
\[
x=x^{\mathcal{S}}+\varepsilon,
\]
where $x^{\mathcal{S} }\in \mathcal{S}$, and $\varepsilon$ is ``small'', namely,
\begin{equation*}
{\left\|\Delta^{\tau} \varepsilon\right\|_{n,2}
}\leq \sigma\varkappa, \quad 0 \le \tau \le m.
\end{equation*}}
In what follows we use the following convenient reformulation of Assumption A$'$ (reformulation of Assumption A when $m=n$):
\begin{quotation}\noindent
{\em There exists an $s$-dimensional (complex) subspace $\mathcal{S}_{n} \subset \C^{n+1}$

and  an idempotent matrix $\Pi_{\mathcal{S}_{n}}\in \H^{n+1}$ of rank $s$ -- the projector on $\S_n$ -- such that
\be
\big\|\left(I_{n+1}-\Pi_{\mathcal{S}_{n}}\right) \left[\Delta^\tau x\right]_0^{n}\big\|_2 \, \Big[={\left\|\Delta^{\tau} \varepsilon\right\|_{n,2}
}\Big] \leq \sigma\varkappa\aic{}{\sqrt{n+1}},\;\tau=0, ...,m
\ee{subspace1}
where $I_{n+1}$ is the $(n+1)\times (n+1)$ identity matrix.
}
\end{quotation}
We now state the extended versions of Theorems~\ref{th:l2con}~and~\ref{th:l23pen}. We denote $c_\alpha := \sqrt{2 \ln [16/\alpha]}$.
\begin{theorem}\label{th:l2conl}
Let $m, n\in \Z_+$, $\overline{\varrho}\geq 1$, and let $\varphi^o\in\C(\Z^{m}_0)$ be such that
$\|\varphi^o\|^F_{1}\leq {\overline{\varrho}/\sqrt{m+1}}.$
Suppose that Assumption A$'$ holds for some $s\in \Z_+$ and $\varkappa<\infty$. Then, the following holds for any optimal solution $\wh\varphi$ of~\eqref{eq:l2-1-mn} with probability at least $1-\alpha$, $0<\alpha\leq 1$:

\begin{equation}\label{eq:l2con-stat}
\|x - \widehat{\varphi}*y \|_{n,2} \le \|x-\varphi^{o}*y\|_{n,2} + 2 \sigma \left[\sqrt{\overline\varrho V_\alpha} + \sqrt{(\overline{\varrho}+1)c_\alpha \varkappa\aic{}{\sqrt{n+1}}} + \sqrt{2s}+ c_\alpha \right],
\end{equation}
where
\begin{equation}
\label{eq:V}
V_\alpha = 2\left(1 + 4\kappa_{m,n}\right)^2\ln\left[{55(m+n+1)}/{\alpha}\right].
\end{equation}
\end{theorem}

\begin{theorem}\label{th:l23penl}
Let $m, n \ge 1$, and let $\varphi^o\in\C(\Z^{m}_0)$ be such that $\|\varphi^o\|^F_{m,1} \le \varrho /\sqrt{m+1}$ for some $\varrho \ge 1$. Suppose that Assumption A$'$ holds for some $s\in \Z_+$ and $\varkappa<\infty$. Then, the following holds for any optimal solution $\wh\varphi$ of~\eqref{eq:l2-2-mn} with probability at least $1-\alpha$, $0<\alpha\leq 1$:
\begin{align}\label{eq:l23pen-stat}
\|x - \widehat{\varphi}*y \|_{n,2}
\le \|x-\varphi^{o}*y\|_{n,2} &+\sigma(\lambda \varrho + 4\lambda^{-1}(c_\alpha \varkappa\aic{}{\sqrt{n+1}} + V_\alpha))\nn
&+ 2 \sigma \left[\sqrt{\varrho W_\alpha} + \sqrt{c_\alpha \varkappa\aic{}{\sqrt{n+1}}} + \sqrt{2s} +  c_\alpha \right],
\end{align}
where $V_\alpha$ is given by~\eqref{eq:V}, and
\[
W_\alpha = (1+\kappa_{m,n})^2 (1+c_\alpha)^2.
\]
\end{theorem}

\subsection{Proof of Theorem \ref{th:l2conl}}
We follow the ``Matlab convention'' for matrices: $[A\, B]$ and $[A; B]$ denote, correspondingly, the horizontal and vertical concatenations of two matrices of compatible dimensions.
\paragraph{1$^o$.} The oracle filter $\varphi^{o}$ is feasible in \eqref{eq:l2-1-mn}, hence,
\be
\|x-\wh\varphi*y\|_{n,2}^2&=& \|(1-\varphi^{o})*y\|_{n,2}^2-{\sigma^2\|\zeta}\|_{n,2}^2-2\,\Re{\sigma\langle \zeta}, x-\wh\varphi*y\rangle_n \nn
&=&\|x-\varphi^{o}*y\|_{n,2}^2  - 2\underbrace{\Re{\sigma\langle \zeta}, x-\wh\varphi*y\rangle_n }_{{\delta^{(1)}}} + 2\underbrace{\Re{\sigma\langle \zeta}, x-\varphi^{o}*y\rangle_n }_{{\delta^{(2)}}}.
\ee{first0}

Let us bound ${\delta^{(1)}}$.
Denote for brevity $I := I_{n+1}$, and recall that $\Pi_{\cS_n}$ is the projector on $\mathcal{S}_n$ from \eqref{subspace1}. We have the following decomposition:
\be
{\delta^{(1)}}
&=&\underbrace{\Re{\sigma\langle \zeta_0^n}, \Pi_{\cS_n}[x-\wh\varphi*y]_0^n\rangle}_{{\delta^{(1)}_1}} +\underbrace{\Re{\sigma\langle \zeta_0^n}, (I-\Pi_{\cS_n})[x-\wh\varphi*x]_{0}^n\rangle}_{{\delta^{(1)}_2}}\nn &&-\underbrace{\Re{\sigma^2\langle \zeta_0^n}, (I-\Pi_{\cS_n})[\wh\varphi * {\zeta}]_{0}^n \rangle}_{{\delta^{(1)}_3}}
\ee{I_pi}
One can easily bound $\delta^{(1)}_1$ under the premise of the theorem:
\[
\left|{\delta^{(1)}_1} \right|
\leq {\sigma}\big\|\Pi_{\cS_n} {\zeta}_0^n\big\|_2  \big\|\Pi_{\cS_n}[x-\wh\varphi*y]_0^n\big\|_{2} \leq {\sigma}\big\|\Pi_{\cS_n} {\zeta}_0^n\big\|_2  \big\|x-\wh\varphi*y\big\|_{n,2}.
\]
Due to $\Tr(\Pi_{\cS_n})=s$, and the singular norm $\|\Pi_{\cS_n}\|_*=1$, we have (cf. \rf{eq:chi_bound})
\[
\prob\left\{\big\|\Pi_{\cS_n}\zeta_0^n\big\|_2 \geq \sqrt{2s}+\sqrt{2u}\right\}\leq e^{-u},
\]
which leads to the bound
\be
\text{Prob}\left\{\big|{\delta^{(1)}_1}\big|
\leq \sigma\big\|x-\wh\varphi*y\big\|_{n,2} \left(\sqrt{2s}+\sqrt{2\ln\left[1/\alpha_1\right]}\right) \right\} \ge 1-\alpha_1.
\ee{i11}
\paragraph{2$^o$.} We are to bound the second term of \eqref{I_pi}. To this end, note first that
\bse
{\delta^{(1)}_2} =\Re {\sigma\langle \zeta_0^n}, (I-\Pi_{\cS_n})x_0^n \rangle - \Re{\sigma\langle \zeta_0^n}, (I-\Pi_{\cS_n})[\wh\varphi*x]_0^n\rangle.
\ese
By \eqref{subspace1}, $\left\|(I-\Pi_{\cS_n})x_0^n\right\|_{2}\leq \sigma \varkappa$, thus with probability $1-\alpha$,
\be
\left|{\langle \zeta_0^n}, (I-\Pi_{\cS_n})x_0^n\rangle \right| \le \sigma\varkappa\sqrt{2\ln[1/\alpha]}.
\ee{i22-1}
On the other hand, using the notation defined in \eqref{s(psi)}, we have
 $[\wh\varphi*x]_0^n=T(x)\wh\varphi_{0}^m$, so that
\[
{\langle \zeta_0^n}, (I-\Pi_{\cS_n})[\wh\varphi*x]_0^n\rangle = {\langle \zeta_0^n}, (I-\Pi_{\cS_n})T(x)\wh\varphi_{0}^m\rangle.
\]

Note that $[T(x)]_{\tau} = x^{-\tau+n}_{-\tau}$ for the columns of $T(x)$, $0\le \tau \le m$. By \eqref{subspace1},
\dimacorr{$$(I-\Pi_{\cS_n}) T(x)[\tau+1] = (I-\Pi_{\cS_n})x^{-\tau+n}_{-\tau}=\varepsilon^{\tau+L}_{\tau}$$, i.e.}{} $(I-\Pi_{\cS_n})T(x)=T(\varepsilon)$, and by \eqref{tr21},
\begin{align*}
\left\|(I-\Pi_{\cS_n})T(x)\right\|_F^2 &= \left\| T(\varepsilon)\right\|_F^2
= \sum_{\tau=0}^{m}\big\|\varepsilon_{-\tau}^{-\tau+n}\big\|^2_2 \leq (m+1)\sigma^2\varkappa^2.
\end{align*}
Due to \eqref{trq1} we conclude that
\[
\left\|T(x)^H(I-\Pi_{\cS_n})\zeta_0^n\right\|_2^2 \le 2(m+1)
\sigma^2\varkappa^2\left(1+\sqrt{\ln[1/\alpha]}\right)^2
\]
with probability at least $1-\alpha$. Since
\[\left|\left\langle\zeta_0^n, (I-\Pi_{\cS_n})T(x)\wh\varphi_{0}^m\right\rangle\right|\leq \frac{\overline\varrho}{\sqrt{m+1}} \left\|T(x)^H(I-\Pi_{\cS_n})\zeta_0^n\right\|_{2},
\]
we arrive at the bound with probability $1-\alpha$:
\[
\left|\left\langle\zeta_0^n, (I-\Pi_{\cS_n})T(x)\wh\varphi_{0}^m\right\rangle\right|\le\sqrt{2}\sigma\varkappa\overline{\varrho} \left(1+\sqrt{\ln[1/\alpha]}\right).
\]
Along with \eqref{i22-1} this results in the following bound:
\be

\text{Prob}\left\{\big|{\delta^{(1)}_2}\big|
\leq \sqrt{2}\sigma^2\varkappa(\overline{\varrho}+1) \left(1+\sqrt{\ln\left[1/\min (\alpha_2,\alpha_3)\right]}\right)\right\} \ge 1-\alpha_2-\alpha_3.

\ee{i22}
\paragraph{3$^o$.} Let us rewrite ${\delta^{(1)}_3}$ as follows:
\bse
{\delta^{(1)}_3} &=&\Re{\sigma^2\langle \zeta_0^n}, (I-\Pi_{\cS_n})M(\wh\varphi){\zeta}_{-m}^{n} \rangle =
\Re {\sigma^2\langle \zeta_{-m}^n}, Q M(\wh\varphi){\zeta}_{-m}^{n}\rangle,
\ese
where $M(\wh\varphi)\in \C^{(n+1)\times (m+n+1)}$ is defined by \eqref{M(phi)}, and $Q\in \C^{(m+n+1)\times (n+1)}$ is given by
\begin{equation*}
Q=\left[
\begin{array}{c c}
0_{m,n+1}; & I - \Pi_{\cS_n}
\end{array}
\right];
\end{equation*}
hereinafter we denote $0_{m,n}$ the $m\times n$ zero matrix.
Now, by the definition of $\widehat\varphi$ and since the mapping $\varphi \mapsto M(\varphi)$ is linear,
\be

{\delta^{(1)}_3}
&=&{\half}({\zeta}_{-m}^{n})^H(\underbrace{Q^{\vphantom{*}}M(\wh\varphi)+M(\wh\varphi)^H Q^H}_{K_{1}(\wh\varphi)}) z_{-m}^{n}
\leq\frac{\sigma^2\overline\varrho}{2\sqrt{m+1}}\max\limits_{\scriptsize\begin{array}{c} u \in \C(\Z_0^m),\nn \|u\|^*_{m,1}\leq 1\end{array}} (\zeta_{-m}^{n})^H K_{1}(u) \zeta_{-m}^{n}\\
&=&\frac{\sigma^2\overline\varrho}{\sqrt{m+1}}\,\,\max\limits_{\tiny{1\le j \le m+1}}\,\,\max\limits_{\theta \in [0,2\pi]} \half (\zeta_{-m}^{n})^H K_{1}(e^{\imath\theta} u^j) \zeta_{-m}^{n},

\ee{maxR}
where $u^j \in \C(\Z_0^m)$, and $[u^j]_0^m = F_m^{-1} \text{e}_j$, $\text{e}_j$ being the $j$-th canonical orth of $\R^{m+1}$. Indeed, a linear in $u$ function $(\zeta_{-m}^{n})^H K_{1}(u) \zeta_{-m}^{n}$ attains its maximum over the convex set
\begin{align}\label{eq:hyperoct}
\mathcal{B}_{m,1}^* = \{u \in \C(\Z_0^m), \quad \|u\|^*_{m,1} \le 1\}.
\end{align}
at an extreme point $e^{\imath\theta} u_j$, $\theta \in [0,2\pi]$.
Note that on has $$K_1(e^{\imath\theta}u) = K_1(u)\cos\theta  + K_2(u)\sin\theta $$ for the Hermitian matrix
\begin{align*}
K_2(u) = \imath\left(Q^{\vphantom{*}}M(u) - M(u)^H Q^H \right).
\end{align*}

Therefore,
\be
\max\limits_{u\in \mathcal{B}_{m,1}^*} (\zeta_{-m}^{n})^H K_{1}(u) \zeta_{-m}^{n} &=&\max\limits_{\theta,j}\left[(\zeta_{-m}^n)^H K_1(u^j) \zeta_{-m}^n\cos\theta   + (\zeta_{-m}^n)^H K_2(u^j) \zeta_{-m}^n(\zeta)\sin\theta\right]\nn
&\leq& \sqrt{2}\max_{i=1,2,\,1\leq j\leq m+1} \left\{\big|(\zeta_{-m}^n)^H K_i(u^j) \zeta_{-m}^n\big|\right\}.
\ee{eq:max_complex_to_real}
On the other hand, by \eqref{tr22} we get
\begin{align*}\label{trA1}
\Tr\left[K_{i}(u^j)^2\right] \leq

4\,\Tr[M(u^j)M(u^j)^H]= 4(n+1)\|u^j\|^2_{m,2}\leq 4(n+1), \quad i=1,2.
\end{align*}
Furthermore,
\be
\max_{j}\Tr[K_{i}(u_j)]\leq 2 \sqrt{m+1}(\kappa_{m,n}^2 + 1)  (\ln[m+n+1]+3),
\quad i=1,2.
\ee{eq:K_itrace}
Indeed, we have
$QM(u) =R C(u)$, where
\begin{align*}
R = QQ^H=\left[
\begin{array}{l|l}
0_{m,m} & 0_{m,n+1}\\
\hline
0_{n+1,m} & I-\Pi_{\mathcal{S}_n}
\end{array}
\right]
\end{align*}
is an $(m+n+1)\times (m+n+1)$ projection matrix of rank $s$, and $C(u)$ is the circulant convolution matrix, as in  \rf{C(phi)}.
Note that the nuclear norm  $\|C(u)\|$ satisfies
\[
\|C(u)\|\leq

{m+n+1\over \sqrt{m+1}}(\ln[m+n+1]+3) \|u\|^*_{m,1},
\] cf. \rf{eq:C-ell1}.
Since the spectral norm $\|R\|_*$ of $R$ is equal to $1$, we get
\bse
\big|\Tr[K_{i}(u^j)]\big| &\le& 2\big|\Tr[R C(u^j)]\big| \le 2\|R\|_*  \left\|C(u^j)\right\|\\
&\leq& {m+n+1\over \sqrt{m+1}}(\ln[m+n+1]+3) \|u^j\|^*_{m,1},
\ese
what is \rf{eq:K_itrace}.

When applying \eqref{trq2} we conclude that for $0<\alpha<1$ and any pair $(i,j) \in \{1,2\} \times \{1,\, ...,\, m+1\}$, with probability $1-\alpha'$,
\[ \half \big|\zeta_{-m}^n)^H K_i(u^j) \zeta_{-m}^n\big| \leq \left|\Tr[K_{i}(u^j)]\right| +\left\|K_{i}(u^j)\right\|_F \left(1 + \sqrt{\ln[2/\alpha]}\right)^2.
\]
Choosing $\alpha={\alpha\over 2(m+1)}$, and using the union bound along with \eqref{maxR} and \eqref{eq:max_complex_to_real} we arrive at
\be\begin{array}{rcl}
\Prob\left\{{\delta^{(1)}_3}\leq
2\sqrt{2}\sigma^2\overline{\varrho}\left[(\kappa_{m,n}^2+1)(\ln[m+n+1]+3)\right.\right.&&\nn
\left.\left.+\kappa_{m,n}
\left(1+\sqrt{\ln\left[{4(m+1)\over \alpha_0}\right]}\right)^2\right]\right\} &\ge& 1-\alpha_0.
\end{array}
\ee{i23-2}
\paragraph{4$^o$.} To bound ${\delta^{(2)}}$ we decompose
\[
{\delta^{(2)}} = \sigma \Re\langle \zeta, x-\varphi^{o}*x\rangle_n - \sigma^2\Re\langle \zeta,\varphi^{o}*\zeta\rangle_n.
\]
Note that $\Re\langle \zeta,x-\varphi^{o}*x\rangle_n \sim \N(0,\|x-\varphi^{o}*x\|_{n,2}^2)$, therefore, with probability $1-\alpha$,
\be
\Re\langle\zeta,x-\varphi^{o}*x\rangle_n\leq\sqrt{2\ln[1/\alpha]}  \|x-\varphi^{o}*x\|_{n,2}.
\ee{simple0}
On the other hand,
\begin{align}\label{simple1}
\|x-\varphi^{o}*x\|_{n,2}
&\leq \|x-\varphi^{o}*y\|_{n,2}+\sigma \|\varphi^{o}*\zeta\|_{n,2}\notag\\
&\leq \|x-\varphi^{o}*y\|_{n,2}+\sqrt{2} \sigma \varrho \kappa_{m,n} \left(1+\sqrt{\ln [1/\alpha]}\right)
\end{align}
with probability $1-\alpha$. Indeed, one has
\[
\|\varphi^{o}*\zeta\|^2_{n,2}=\left\|M(\varphi^{o})\zeta_{-m}^n \right\|_2^2,
\]
where for $M(\varphi^{o})$ by $\eqref{tr22}$ we have
\begin{align}\label{eq:trmm}
\left\|M(\varphi^{o})\right\|_F^2  = (n+1)\|\varphi^{o}\|_{m,2}^2 \leq\kappa_{m,n}^2\varrho^2.
\end{align}
Using \eqref{trq1} we conclude that, with probability at least $1-\alpha$,
\begin{equation}\label{eq:phizeta2}
\|\varphi^{o}*\zeta\|^2_{n,2} \leq 2\kappa_{m,n}^2\varrho^2\left(1+\sqrt{\ln[1/\alpha]}\right)^2,
\end{equation}
which implies \eqref{simple1}. Using \eqref{simple0} and \eqref{simple1}, we get that with probability at least $ 1-\alpha_4-\alpha_5$,
\be
\lefteqn{\Re\langle\zeta,x-\varphi^{o}*x\rangle_n}\nn
&\leq& \sqrt{2\ln \left[1/\min(\alpha_4,\alpha_5)\right]} \left[\|x-\varphi^{o}*y\|_{n,2}+\sqrt{2}\sigma\varrho\kappa_{m,n}
\left(1+\sqrt{\ln\left[1/\min(\alpha_4,\alpha_5)\right]}\right)\right]\nn
&\leq& \|x-\varphi^{o}*y\|_{n,2}\sqrt{2\ln\left[1/\min(\alpha_4,\alpha_5)\right]}+2\sigma\varrho \kappa_{m,n}\left(1+\sqrt{\ln \left[1/\min(\alpha_4,\alpha_5)\right]}\right)^2.
\ee{simple2}
The indefinite quadratic form
\begin{align*}
&\Re\langle\zeta,\varphi^{o}*\zeta\rangle_n=\frac{(\zeta_{-m}^n)^H{K_0(\varphi^{o})}\zeta_{-m}^n}{2}
\end{align*}
where $K_0(\varphi^{o}) =
\left[0_{m,m+n+1};\, M(\varphi^{o})\right]+
\left[0_{m,m+n+1}; \, M(\varphi^{o})\right]^H$
can be bounded similarly to 3$^o$. We get
\[
|\Tr[{K_0(\varphi^{o})}]| \le 2(n+1)\left|\varphi^{o}_m\right|\leq 2\kappa_{m,n}^2\varrho.
\]
Indeed, for $e_{m+1} = [0;\, ...;\,0;\,1] \in \R^{m+1}$ one has
\begin{align*}
\left|\varphi^{o}_m\right| = |\langle [\varphi^{o}]_0^m, {e}_{m+1} \rangle| \le \|\varphi^{o}\|^*_{m,1} \|F_m {e}_{m+1}\|_{\infty} \le \frac{\varrho}{m+1}
\end{align*}
since $\|F_m {e}_{m+1}\|_{\infty} = 1/\sqrt{m+1}$.
Next, by \eqref{eq:trmm}, $\left\|K_0(\varphi^{o})\right\|_F^2\leq 4\left\|M(\varphi^{o})\right\|_F^2 \le 4\kappa_{m,n}^2\varrho^2.$ Hence, using \eqref{trq2}, we conclude that
\be
\text{Prob}\left\{-\Re \langle\zeta,\varphi^{o}*\zeta\rangle_n \leq 2\kappa_{m,n}^2\varrho+2\kappa_{m,n}\varrho \left(1+\sqrt{2\ln\left[1/\alpha_6\right]}\right)^2 \right\} \ge 1-\alpha_6.
\ee{i112}
\paragraph{5$^o$.} Now we combine the bounds obtained in $1^o$-$4^o$. For any $\alpha \in (0,1]$, putting $\alpha_0 = \alpha_1 = \alpha_6 = \alpha/4$ and $\alpha_i = \alpha/16$ for $2 \le i \le 5$, by the union bound we get from \eqref{first0} with probability $\geq 1-\alpha$:
\begin{eqnarray}\label{eq:l2con-long}
\|x-\wh\varphi*y\|_{n,2}^2&\leq& \|x-\varphi^{o}*y\|_{n,2}^2+2{\delta^{(2)}}-2{\delta^{(1)}}\\
\mbox{[by \eqref{simple2}]}&\leq& \|x-\varphi^{o}*y\|_{n,2}^2+2\sigma\|x-\varphi^{o}*y\|_{n,2}\sqrt{2\ln[16/\alpha]}\nn
\mbox{[by \eqref{simple2}, \eqref{i112}]}&&+4\sigma^2\varrho\Big[\kappa_{m,n}^2+2\kappa_{m,n}\big(1+\sqrt{2\ln[16/\alpha]}\big)^2\Big]

\nn
\mbox{[by \eqref{i11}]}&&+2\sigma\|x-\wh\varphi*y\|_{n,2}\big(\sqrt{2s}+\sqrt{2\ln [16/\alpha]}\big)

\nn
\mbox{[by \eqref{i22}]}&&+2\sqrt{2}\sigma^2(\overline{\varrho}+1)\big(1+\sqrt{\ln[16/\alpha]}\big)\varkappa

\nn
\mbox{[by \eqref{i23-2}]}&&+4\sqrt{2}\sigma^2\overline{\varrho}\left[(\kappa_{m,n}^2+1)(\ln[m+n+1]+3)
+\kappa_{m,n}(1+\sqrt{\ln\left[{16(m+1)}/{\alpha}\right]})^2\right]\nonumber
\end{eqnarray}
Hence, recalling the notation $c_\alpha := \sqrt{2\ln[16/\alpha]}$ and denoting
\begin{eqnarray}
u(\alpha) &=& 2\big(\sqrt{2}+c_\alpha\big),\label{eq:part-u}\nn
v_1(\alpha) &=& 4\left[\kappa_{m,n}^2+2\kappa_{m,n}\left(1+c_\alpha\right)^2\right],\label{eq:part-v1}\nn
v_2(\alpha )&=& {4\sqrt{2}\left[(\kappa_{m,n}^2+1)(\ln[m+n+1]+3)
+\kappa_{m,n}(1+\sqrt{\ln\left[{16(m+1)}/{\alpha}\right]})^2\right]},\label{eq:part-v2}
\end{eqnarray} we obtain
\begin{equation}
\begin{aligned}
\|x-\wh\varphi*y\|_{n,2}^2 &\le& \|x-\varphi^{o}*y\|_{n,2}^2
+ 2\sigma (\sqrt{2s}+c_\alpha) \left(\|x-\wh\varphi*y\|_{n,2} + \|x-\varphi^{o}*y\|_{n,2}\right)\\&&+ u(\alpha)\sigma^2(\overline\varrho+1)\varkappa + (v_1(\alpha)+v_2(\alpha)) \sigma^2\overline\varrho.
\end{aligned}
\label{eq:uv-compact}
\end{equation}
The latter implies that
\begin{align*}
\|x-\wh\varphi*y\|_{n,2} \le \|x-\varphi^{o}*y\|_{n,2}
+2\sigma\big(\sqrt{2s}+c_\alpha\big) + \sigma\sqrt{u(\alpha)(\overline\varrho+1)\varkappa + (v_1(\alpha)+v_2(\alpha))\overline\varrho}.
\end{align*}
Finally, using the bound
\begin{equation}\label{eq:part-u-bound}
u(\alpha) \le 4c_\alpha
\end{equation}
and
\begin{align}
\label{eq:final_stoch_term}
v_1(\alpha) + v_2(\alpha)
&\le\left(4\sqrt{2} (\kappa_{m,n}^2+1)(\ln[m+n+1]+4) + 4.5(4\sqrt{2}+8)\kappa_{m,n}\ln\left[16(m+1)/\alpha\right]\right)\nn
&\le 8\left(1 + 4\kappa_{m,n}\right)^2 \ln\left[55(m+n+1)/\alpha\right] = 4V_\alpha,
\end{align}
we arrive at \eqref{eq:l2con-stat}. \qed

{\color{red} Up to here! }
\subsection{Proof of Theorem \ref{th:l23penl}}

Using the notation as in the proof of Theorem~\ref{th:l2conl}, with $\widehat\varrho := \sqrt{m+1}\,\|\widehat\varphi\|^*_{m,1}$, due to feasibility of  $\varphi^{o}$ in~\eqref{eq:l2-2-mn}, we get (cf.~\eqref{first0}):
\begin{equation*}
\|x-\wh\varphi*y\|_{n,2}^2 + \lambda^2\sigma^2\widehat\varrho^2
\leq \|x-\varphi^{o}*y\|_{n,2}^2 - 2\delta^{(1)} + 2\delta^{(2)} + \lambda^2\sigma^2\varrho^2.
\end{equation*}
Thus, repeating steps $1^o-4^o$ of the proof of Theorem~\ref{th:l2conl}, we obtain a counterpart of~\eqref{eq:uv-compact}:
\be\begin{array}{rcl}
\|x-\wh\varphi*y\|_{n,2}^2 + \lambda^2\sigma^2\widehat\varrho^2&\leq &\|x-\varphi^{o}*y\|_{n,2}^2 +u(\alpha)\sigma^2\varkappa+v_1(\alpha)\sigma^2\varrho
 + \lambda^2\sigma^2\varrho^2\\
 &&+2\sigma (\|x-\varphi^{o}*y\|_{n,2} + \|x-\wh\varphi*y\|_{n,2})(\sqrt{2s}+c_\alpha)\\
&&+u(\alpha)\sigma^2\wh\varrho\varkappa+v_2(\alpha)\sigma^2\widehat\varrho,
\end{array}
\ee{eq:l23compete}
where $u(\alpha),\,v_1(\alpha),$ and $v_2(\alpha)$ are given by~\eqref{eq:part-u}--\eqref{eq:part-v2}.

Let us now consider two cases. First, assume that
\be\begin{array}{rcl}
\|x-\wh\varphi*y\|_{n,2}^2 &\leq &\|x-\varphi^{o}*y\|_{n,2}^2 +u(\alpha)\sigma^2\varkappa+v_1(\alpha)\sigma^2\varrho
 + \lambda^2\sigma^2\varrho^2\\&&+2\sigma (\|x-\varphi^{o}*y\|_{n,2} + \|x-\wh\varphi*y\|_{n,2}) (\sqrt{2s}+c_\alpha).
\end{array}
\ee{eq:assume1}
In this case, clearly,
\be
\|x-\wh\varphi*y\|_{n,2} &\leq & \|x-\varphi^{o}*y\|_{n,2}+2\sigma\big(\sqrt{2s}+c_\alpha\big)
+\sqrt{u(\alpha)\sigma^2\varkappa+v_1(\alpha)\sigma^2\varrho
 + \lambda^2\sigma^2\varrho^2}\nn
 &\leq &\|x-\varphi^{o}*y\|_{n,2} + 2\sigma (\sqrt{2s}+c_\alpha)+\sigma(\sqrt{u(\alpha)\varkappa+v_1(\alpha)\varrho}
 + \lambda\varrho)
\ee{eq:1stcase}
Now, suppose that, on the contrary,~\eqref{eq:assume1} does not hold. We conclude from~\eqref{eq:l23compete} that in this case,
\[\lambda^2\wh{\varrho}^2 \leq \wh\varrho(u(\alpha)\varkappa+v_2(\alpha)),
\] same as
\[

\wh\varrho \leq\lambda^{-2}(u(\alpha)\varkappa+v_2(\alpha)),
\]
and
\[
u(\alpha)\wh\varrho\varkappa+v_2(\alpha)\wh\varrho
\leq\lambda^{-2}(u(\alpha)\varkappa+v_2(\alpha))^2.
\]
When substituting the latter bound into~\eqref{eq:l23compete}, we obtain
\bse
{\|x-\wh\varphi*y\|_{n,2}}&\leq& \|x-\varphi^{o}*y\|_{n,2} +2\sigma(\sqrt{2s}+c_\alpha)\\
&& + \sigma(\sqrt{u(\alpha)\varkappa+v_1(\alpha)\varrho} + \lambda^{-1} (u(\alpha)\varkappa+v_2(\alpha))+ \lambda\varrho),
\ese
which holds as well when~\eqref{eq:assume1} is false (cf. the right-hand side of~\eqref{eq:1stcase}). Using~\eqref{eq:part-u-bound},~\eqref{eq:final_stoch_term},~and the bound
\bse
v_1(\alpha) \le 4(1+\kappa_{m,n})^2(1+c_\alpha)^2
\ese
which directly follows from~\eqref{eq:part-v1}, we get~\eqref{eq:l23pen-stat}.
\qed

\section{Proofs for Section \ref{sec:pointwise}}\label{sec:prpointwise}
\subsection{Proof of Proposition \ref{th:point}}
First, we decompose
\be
\lefteqn{|[x - \widehat\varphi * y]_t|=|[(\phi^o+(1-\phi^o))*(x - \widehat\varphi * y)]_t|}\nn&\leq&
|[\phi^o*(x - \widehat\varphi * y)]_t| + |[(1-\widehat \varphi) * (1 - \phi^o) * x]_t|
+ \sigma|[\widehat \varphi * \zeta]_t| + \sigma|[\widehat \varphi * \phi^o * \zeta]_t|\nn
&:=&\delta^{(1)}+\delta^{(2)}+\delta^{(3)}+\delta^{(4)}.
\ee{eq:l2point-long}

We have
\[
\delta^{(1)}\leq \|\phi^o\|_2 \big\|[x - \widehat\varphi * y]^t_{t-m}\big\|_{2}\leq{\rho\over \sqrt{m+1}} \|x - \widehat\varphi * y\|_{n,2},
\]
where we used that $t \in [m, n]$.
When using the bound
of Corollary  \ref{cor:l2con} with $\overline{\varrho}=2\rho^2$, we conclude that, with probability $\ge 1-\alpha/3$,
\[
\delta^{(1)}\leq  c{\sigma\rho\over \sqrt{n}}\left[\rho^2\sqrt{\ln[1/\alpha]}+ \rho\sqrt{ \big(\varkappa\ln\big[{1/ \alpha}\big]+\ln\big[{n/ \alpha}\big]\big)}+
\sqrt{s}\right].
\]

Next we get
\bse
\delta^{(2)}\le \left(1 + \left\|\widehat\varphi\right\|_1\right) \left\|[(1 - \phi^o) * x]_{t-n}^t\right\|_{\infty} \le (1+2\rho^2){\sigma\rho\over \sqrt{m+1}},
\ese
where we again used that $t \in [m, n]$.

By the Parseval's identity,
\begin{align*}
\delta^{(3)} =\sigma|\langle F_n[\widehat\varphi]_{0}^n,F_n[\zeta]_{t-n}^{t}\rangle|\leq \sigma\|\widehat{\varphi}\|^F_{n,1} \|\Delta^{n-t}\zeta\|^F_{n,\infty} \le \frac{2\sigma\rho^2}{\sqrt{m+1}} \sigma\sqrt{2 \ln \left[3(n+1)/\alpha\right]},
\end{align*}
where the last inequality, holding with probability $\ge 1-\alpha/3$, is due to \eqref{eq:complex_gaussian_max}.
\par
Finally, observe that, with probability $\geq 1-\alpha/3$ (cf. \eqref{eq:varphizeta}),
\[
\|\phi^o * \zeta\|_{n,2}\leq \sqrt{2}\rho\left(1+\sqrt{\ln[3/\alpha]}\right),
\]
and that the noise as a stationary distribution. Therefore, we have for $\delta^{(4)}$:
\[
\delta^{(4)} \le \sigma\|\widehat \varphi\|_{n,2}\left\|[\phi^o * \zeta]_{t-n}^t\right\|_{2} \le
\sigma\frac{2\rho^2}{\sqrt{m+1}} \sqrt{2}\rho\left(1+\sqrt{\ln[3/\alpha]}\right)=
\sigma\frac{2\sqrt{2}\rho^3}{\sqrt{m+1}}\left(1+\sqrt{\ln[3/\alpha]}\right)
\]
with probability $1-\alpha/3$. When substituting the bound for $\delta^{(k)},\,k=1,...,4$, into \eqref{eq:l2point-long} we arrive at the claim.\qed
\subsection{Proof of Proposition \ref{th:l8con}}
The argument essentially repeats that in \cite{harchaoui2015adaptive}, pp. 6-7, and is given for self-containedness of the paper.
We use the notation $1 * x\,[= x]$ for the identity filter. Let us begin with the "bias-variance" decomposition
\begin{align*}
|x_n  - \widehat{x}_n| = |[x - \widehat \varphi * y]_n| &\le |[(1- \widehat\varphi) * x]_n| + \sigma |[\widehat \varphi * \zeta]_n| \\
&\le |[(1 - \widehat\varphi) * x]_n| +  \sigma \|\widehat \varphi\|^*_{n,1} \|\zeta\|^*_{n,\infty},
\end{align*}
where in the last line we used that $[\widehat \varphi * \zeta]_n = \langle \overline{\zeta}_0^n, \widehat\varphi_n^0 \rangle$.
In the same manner we get
\begin{align*}
|[(1-\widehat\varphi) * x]_n| &\le |[(1-\widehat\varphi) * (1 - \varphi^{o}) * x]_n| + |[\varphi^{o} * (1-\widehat\varphi) * x]_n| \\
&\le (1 + \|\widehat\varphi\|_{1})\, \|(1 - \varphi^{o}) * x\|_{n,\infty} + \|\varphi^{o}\|^*_{n,1} \| (1 - \widehat \varphi) * x \|^*_{n,\infty}.
\end{align*}
The spectral domain disrepancy term $\| (1 - \widehat \varphi) * x \|^*_{n,\infty}$ can be controlled as follows:
\begin{align*}
\| (1 - \widehat \varphi) * x \|^*_{n,\infty} &\le \left\| (1 - \widehat \varphi) * y \right\|^*_{n,\infty} + \sigma \| (1 - \widehat \varphi) * \zeta\|^*_{n,\infty} \\
&\le  \| (1 - \widehat \varphi) * y \|^*_{n,\infty} + \sigma (1 + \|\widehat \varphi\|_1) \max_{0 \le \tau\le n}\|\Delta^\tau \zeta \|^*_{n,\infty}.
\end{align*}
Since $\varphi^{o}$ is feasible in \eqref{eq:l8-1},
\begin{align}\label{eq:l8con-control1}
\begin{split}
\| (1 - \widehat \varphi) * y \|^*_{n,\infty}
&\le \| (1 - \varphi^{o}) * y \|^*_{n,\infty}\\
&\le \|(1-\varphi^{o}) * x\|^*_{n,\infty} +\sigma \|(1-\varphi^{o}) * \zeta\|^*_{n,\infty}\\
&\le \sqrt{n+1}\, \|(1 - \varphi^{o}) * x\|_{n,\infty} + \sigma (1+\|\varphi^{o}\|_1) \max\limits_{0 \le \tau\le n}\|\Delta^\tau  \zeta \|^*_{n,\infty}.
\end{split}
\end{align}
Now note that $\max_{0 \le \tau\le n}\|\Delta^\tau  \zeta \|^*_{n,\infty}$ is the maximum of $n+1$ random variables, each distributed as $\|\zeta\|_{n,\infty}$ by the invariance of the complex Gaussian distribution with respect to unitary transformations. Applying \eqref{eq:complex_gaussian_max} and the union bound, we get that with probability at least $1-\alpha$,
\begin{equation*}
\max_{0 \le \tau\le n}\|\Delta^\tau  \zeta \|^*_{n,\infty} \le 2\sqrt{\ln\left[({n+1})/{\alpha}\right]}.
\end{equation*}
Note that by Young's inequality, $\max(\|\widehat\varphi\|_1,\|\varphi^o\|_1) \le \sqrt{n+1} \max(\|\widehat\varphi\|^*_{n,1},\|\varphi^o\|^*_{n,1})$. Besides,
\begin{equation}\label{eq:l8con-control2}
\max(\|\widehat\varphi\|^*_{n,1},\|\varphi^o\|^*_{n,1}) \le \frac{\overline{\varrho}}{\sqrt{n+1}}.
\end{equation}
Collecting the above bounds, we arrive at the bound with probability $1-\alpha$:
\begin{equation*}
|\widehat x_n - x_n| \le 2\overline\varrho\, (3 + 2\overline\varrho) \frac{\sigma\sqrt{\ln\left[({n+1})/{\alpha}\right]}}{\sqrt{n+1}} + (1 + 2\overline\varrho)\, \|(1 - \varphi^{o}) * x\|_{n,\infty}.
\end{equation*}
The proof is completed by recalling the first bound of \eqref{eq:var2f}. \qed
\subsection{Proof of Proposition \ref{th:l8pen}}
The argument repeats that of Theorem \ref{th:l8con} with the following modification: instead of \eqref{eq:l8con-control1} and \eqref{eq:l8con-control2} one has, for $\widehat\varrho := \sqrt{n+1}\|\widehat\varphi\|^*_{n,1}$,
\begin{align*}
\| (1 - \widehat \varphi) * y \|^*_{n,\infty} + \lambda \widehat\varrho
&\le\| (1 - \varphi^{o}) * y \|^*_{n,\infty} + \lambda \varrho\nn
&\le\sqrt{n+1}\, \| (1 - \varphi^{o}) * x \|_{n,\infty} + \sigma  (1+\varrho) \max\limits_{0 \le \tau\le n}\|\Delta^\tau  \zeta \|^*_{n,\infty} + \lambda \varrho.
\end{align*}
The left hand side of the above display is lower-bounded by either of its constituents, specifically
\begin{align*}
&\lambda\widehat\varrho \le \lambda\varrho + 2\sigma (1 + \varrho) \sqrt{\ln\left[({n+1})/{\alpha}\right]} + \sqrt{n+1}\, \| (1 - \varphi^{o}) * x \|_{n,\infty},
\end{align*}
and, using the first three bounds of the proof of Theorem \ref{th:l8con}, we arrive at
\begin{equation*}
|\widehat x_n - x_n| \le 2\left(\varrho^2 + 2\varrho +(1+\varrho) \widehat\varrho\right) \frac{\sigma\sqrt{\ln\left[({n+1})/{\alpha}\right]}}{\sqrt{n+1}} + (1 + \varrho + \widehat\varrho) \| (1 - \varphi^{o}) * x \|_{n,\infty} + \frac{\lambda \varrho^2}{\sqrt{n+1}}.
\end{equation*}
Combining the above bounds, and recalling the first bound of \eqref{eq:var2f}, we obtain the claim by simple algebra. \qed

The proof goes along the same lines with that of Proposition~\ref{th:l8con}; however, one needs to account for a slightly different definition of oracle feasibility. The following bound remains unchanged:
\begin{equation}
\begin{aligned}
|[x - \widehat \varphi(\Delta) y]_0|
&\le& \sigma \|\widehat \varphi\|^*_{N,1} \underbrace{\|\xi\|^*_{N,\infty}}_{\le\Theta_N}\\
&& +\; \underbrace{\|\varphi^o\|^*_{N,1}}_{\le  \frac{\varrho}{\lambda(2T+1)^{d/2}}} \, \| a(\Delta) (1 - \widehat \varphi(\Delta)a(\Delta)) x \|^*_{N,\infty}\\
&& +\; (1 + \|a(\Delta)\widehat\varphi\|_{1})\, \underbrace{\|(1 - \varphi^o(\Delta)a(\Delta)) x\|_{N,\infty}}_{\le \frac{\theta\varrho \sigma}{\lambda(2T+1)^{d/2}}}.
\end{aligned}
\label{eq:l8pen-inv-init}
\end{equation}
Conditionally on the event $\Theta_N \le \vartheta^\delta_N$, feasibility of $\wh\varphi$ in~\eqref{opt:l8pen-inv} yields that
\begin{align}
& \left\| (1 - \wh\varphi(\Delta)a(\Delta)) y \right\|^*_{N,\infty}
+  \gamma\sigma(2N+1)^{d/2} \|a(\Delta) \wh\varphi\|_{N,1}^*
+ \gamma \sigma(2N+1)^{d/2} \lambda \|\wh\varphi\|_{N,1}^* \nn
&\le \left\| (1 - \varphi^o(\Delta)a(\Delta)) y \right\|^*_{N,\infty} + \gamma \sigma(2N+1)^{d/2} \underbrace{\left( \|a(\Delta) \varphi^o\|_{N,1}^* + \lambda \|\varphi^o\|_{N,1}^* \right)}_{[ \textup{by (a),(b)}]\; \le \; \frac{2\varrho}{(2T+1)^{d/2}}} \nn
&\le \theta Q_d\varrho \sigma + (1+Q_d\varrho) \sigma\Theta_N + 2\gamma Q_d \varrho \sigma.\tag*{[by~the~last~line~of~\eqref{eq:l8-est-discrep},~\eqref{eq:l8-orc-discrep},~and~\eqref{eq:l8-filt-norm}]}\\
&\le (\theta + 2\Theta_N + 2\gamma) Q_d \varrho \sigma \tag*{[ since~$Q_d\varrho \ge 1$]}\\
&\le 3\gamma Q_d \varrho \sigma.
\label{eq:l8pen-inv-long}
\end{align}
Here in the last line we recalled the choice of $\gamma$ used in the theorem.
All the terms in the left-hand side of~\eqref{eq:l8pen-inv-long} are non-negative, so we obtain
\begin{align}
\label{eq:l8pen-inv-norm-phi}
\|\wh\varphi\|_{N,1}^* \le \frac{3\varrho}{\lambda(2T+1)^{d/2}}
\end{align}
and
\begin{align}
\label{eq:l8pen-inv-norm-aphi}
1+\|a(\Delta)\widehat \varphi\|_1 \le 1+ (2N+1)^{d/2} \|a(\Delta)\widehat \varphi\|_{N,1}^*
&\le 1 + 3Q_d \varrho \le 4 Q_d \varrho.
\end{align}
We further have
\begin{align}
\| a(\Delta) (1 - \widehat \varphi(\Delta)a(\Delta)) x \|^*_{N,\infty}
&\le \left\| (1 - \widehat \varphi(\Delta)a(\Delta)) y \right\|^*_{N,\infty}
+ \sigma (1 + \|a(\Delta)\widehat \varphi\|_1) \Theta_N\nn
&\le(3\gamma + 4\Theta_N) Q_d \varrho \sigma \tag*{[by~\eqref{eq:l8pen-inv-long}~and~\eqref{eq:l8pen-inv-norm-aphi}]} \nn
&\le 5 \gamma Q_d \varrho \sigma.
\label{eq:l8pen-inv-last}
\end{align}
Finally, substituting~\eqref{eq:l8pen-inv-norm-phi},~\eqref{eq:l8pen-inv-norm-aphi},~\eqref{eq:l8pen-inv-last} into~\eqref{eq:l8pen-inv-init}, we conclude the proof. \qed

\section{Proofs for Section \ref{sec:discussion}}
\label{sec:prdisc}

\subsection{Proof of  Proposition \ref{th:shift-inv-bilateral}}
 Let $\Pi_{\S_k}\in \H^{k+1}$ be the Euclidean projector
on the space $\S_k$ of elements of $\mathcal{S}$ restricted on $\C(\Z_0^k)$. Since $\dim(\S_k)\leq s$,
$\|\Pi_{\S_k}\|_2^2=\Tr(\Pi_{\S_k})\leq s$, there is $j\in \{0,...,k\}$ such that the $j$-th column $[\Pi_{\S_k}]_j$ of  $\Pi_{\S_k}$ satisfies $\|[\Pi_{\S_k}]_j\|_2\leq \sqrt{s/(k+1)}$. Note that one has $x_j-\langle [\Pi_{\S_k}]_j, x_0^k\rangle=0$, and $\S_k$ is time-invariant, implying that
\[
x_\tau-\langle [\Pi_{\S_k}]_j, x_{\tau-j}^{\tau-j+k}\rangle=0, \;\;\forall \tau \in\Z.
\]
On the other hand, we can always complete $[\Pi_{\S_k}]_j$ with $k$ zeros to construct $\phi^o\in \C(\Z_{-k}^k)$,
$\phi^o=[0;...;0;[\Pi_{\S_k}]_j; 0;...;0]$, in such a way that the $j$-th element of $[\Pi_{\S_k}]_j$ becomes the $k+1$-th entry $[\phi^o]_0$ of $\phi^o$, and such that
\begin{equation*}
\|\phi^o\|_2\leq \|[\Pi_{\S_k}]_j\|_2\leq \sqrt{s\over k+1},\quad \mbox{and}
\quad x_t-[\phi^o*x]_t=0, \quad \forall t \in\Z.
\end{equation*}

\subsection{Proof of Theorem \ref{th:sines}}
Note that to prove the theorem we have to exhibit a vector $q\in \C^{m+1}$ of small $\ell_2$-norm and such that the polynomial
$1-q(z)=1-\left[\sum_{i=0}^m q_iz^i\right]$ is divisible by $p(z)$, i.e., that there is a polynomial $r(z)$ of degree $m-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$,
\par
The bound
$
\|q\|_2\leq C's^{3/2}\sqrt{\ln s\over m}
$
of \eqref{propofq} is proved in \cite[Lemma 6.1]{jn-2014}. Our objective is to prove the ``remaining'' inequality
\[
\|q\|_2\leq C's\sqrt{\ln[ms]\over m}.
\]
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
\begin{equation}\label{eq1}
{\bar{\delta}\over\delta}-1=1-\bar{\delta}>0.
\end{equation}
Consider the function
\[
\bar{q}(z)=\prod_{i=1}^s{z-\theta_i\over\delta z-\theta_i}.
\]
\def\B{{\cal B}}
Note that $\bar{q}(\cdot)$ has no singularities in the circle
\[
\B=\{z:|z|\leq {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
$$
{|z-\theta_i|\over|\delta z-\theta_i|}={1\over\delta}{|w-\bar{\delta}\theta_i|\over |w-{\bar{\delta}\over \delta}\theta_i|}.
$$
 We claim that when $|w|=1$, $|w-\bar{\delta}\theta_i|\leq |w-{\bar{\delta}\over\delta}\theta_i|$.
\begin{quote}
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={\bar{\delta}\over\delta}\theta_i$. Let also $D=\theta_i$. By (\ref{eq1}), the segment $\overline{AD}$ is a median in $\Delta$, and $\angle CDA $ is $\geq{\pi\over 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|\leq |w-{\bar{\delta}\over\delta}\theta_i|$.
\end{quote}
As a consequence, we get
\begin{equation}\label{eq10}
z\in \B\; \Rightarrow\; |\bar{q}(z)|\leq\delta^{-s},
\end{equation}
whence also
\begin{equation}\label{eq5}
|z|=1\;\Rightarrow\; |\bar{q}(z)|\leq\delta^{-s}.
\end{equation}
Now, the polynomial $p(z)=\prod_{i=1}^s(z-\theta_i)$ on the boundary of $\B$ clearly satisfies
$$
|p(z)|\geq \left[{1\over \bar{\delta}}-1\right]^s=\left[{1-\delta\over 2\delta}\right]^s,
$$
which combines with (\ref{eq10}) to imply that the modulus of the holomorphic in $\B$ function
$$
\bar{r}(z)=\left[\prod_{i=1}^s(\delta z-\theta_i)\right]^{-1}
$$
is bounded with $\delta^{-s}\left[{1-\delta\over 2\delta}\right]^{-s}=\left[{2\over 1-\delta}\right]^s$ on the boundary of $\B$. It follows that the coefficients $r_j$ of the Taylor series of $\bar{r}$ satisfy
$$
|r_j|\leq  \left[{2\over 1-\delta}\right]^s\bar{\delta}^{j},\;\;j=0,1,2,...
$$
When setting
\be
q^\ell(z)=p(z)r^\ell(z),\;\;r^\ell(z)=\sum_{j=1}^\ell r_j z^j,
\ee{eq:qldiv}
for $|z|\leq 1$, utilizing the trivial upper bound $|p(z)|\leq 2^s$, we get
\be
|q^\ell(z)-\bar{q}(z)|&=&|p(z)|[r^\ell(z)-\bar{r}(z)]|\leq |p(z)||r^\ell(z)-\bar{r}(z)|\nn
&\leq&2^s\left[{2\over 1-\delta}\right]^s \sum_{j=\ell+1}^\infty |r_j|\leq \left[{4\over 1-\delta}\right]^s{\bar{\delta}^{\ell+1}\over 1-\bar{\delta}}.
\ee{eq12}
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 (\ref{eq12}),
\begin{equation}\label{eq13}
|q^\ell(z)|\leq |\bar{q}(z)|+\left[{4\over 1-\delta}\right]^s{\bar{\delta}^{\ell+1}\over 1-\bar{\delta}}\leq \delta^{-s}+\underbrace{\left[{4\over 1-\delta}\right]^d{\bar{\delta}^{\ell+1}\over 1-\bar{\delta}}}_{R}
\end{equation}
(we have used (\ref{eq5})).
Now,
$$
\bar{\delta}={2\delta\over1+\delta}={2-2\epsilon\over 2-\epsilon}={1-\epsilon\over 1-\epsilon/2}\leq 1-\epsilon/2\leq \e^{-\epsilon/2},

$$
and
$$
{1\over 1-\bar{\delta}}={1+\delta\over 1-\delta}={2-\epsilon\over \epsilon}\leq {2\over\epsilon}.
$$
We can upper-bound $R$:
\[
R=\left[{4\over 1-\delta}\right]^s{\bar{\delta}^{\ell+1}\over 1-\bar{\delta}}
\leq {2^{2s+1}\over\epsilon^{s+1}}\e^{-\epsilon \ell/2}

\]Now, given positive integer $\ell$ and positive $\alpha$ such that
\begin{equation}\label{alphasmall}
{\alpha\over \ell}\leq\four,
\end{equation}
let $\epsilon={\alpha\over 2\ell s}$.
Since $0<\epsilon\leq {1\over 8}$, we have $-\ln(\delta)=-\ln(1-\epsilon)\leq 2\epsilon={\alpha\over \ell s},$ implying that $\bar{\delta}\leq \e^{-\epsilon/2}=\e^{-{\alpha\over 4\ell s}}$, and
\[
R\leq \left[{8\ell s\over\alpha}\right]^{s+1}\exp\{-{\alpha\over 4s}\}.
\]
Now let us put
\[
\alpha=\alpha(\ell,s)=4s(s+2)\ln(8\ell s);
\]
observe that this choice of $\alpha$ satisfies (\ref{alphasmall}), provided that
\begin{equation}\label{nislarge}
\ell\geq O(1)s^2\ln(s+1)
\end{equation}
with properly selected absolute constant $O(1)$. With this selection of $\alpha$, we have $\alpha\geq1$, whence
\bse
R\left[{\alpha\over \ell}\right]^{-1}&\leq& \exp\left\{-{\alpha\over 4s}\right\}\left[{8\ell s\over\alpha}\right]^{s+1}{\ell\over \alpha}\leq\exp\left\{-{\alpha\over 4s}\right\}[8\ell s]^{s+2}\\
&\leq& \exp\{-(s+2)\ln(8\ell s)\}\exp\{(s+2)\ln(8\ell s)\}=1,
\ese
that is,
\begin{equation}\label{RR}
R\leq {\alpha\over \ell}\leq {\four}.
\end{equation}
Furthermore,
\begin{equation}\label{firstterm}
\begin{array}{rcll}
\delta^{-s}&=&\exp\{-s\ln(1-\epsilon)\}\leq \exp\{2\epsilon s\}=\exp\{{\alpha\over \ell}\}\leq 2,\\
\delta^{-2s}&=&\exp\{-2s\ln(1-\epsilon)\}\leq \exp\{4\epsilon s\}=\exp\{{2\alpha\over \ell }\}\leq 1+\exp\{{1\over 2}\}{2\alpha\over \ell}\leq 1+{4\alpha\over \ell}.
\end{array}
\end{equation}
When invoking (\ref{eq13}) and utilizing (\ref{firstterm}) and (\ref{RR}) we get
$$
{1\over 2\pi}\oint_{|z|=1}|q^\ell(z)|^2|dz|\leq \delta^{-2s}+2\delta^{-s}R+R^2\leq
1+4{\alpha\over \ell}+4R+{1\over 4}R\leq 1+10{\alpha\over \ell}.
$$
On the other hand, denoting by $q_0$, $q_1$,...,$q_{\ell+s}$ the coefficients of the polynomial $q^\ell$ and taking into account that $\bar{q}_0=q^\ell(0)=1$, we have
\be
1+\sum_{i=1}^{\ell+s}|q_i|^2=|q_0|^2+...+|q_{\ell+s}|^2={1\over 2\pi}\oint_{|z|=1}|q^\ell(z)|^2|dz|\leq 1+10{\alpha\over \ell}.

\ee{eq:qnorm}
We are done: when denoting $m=\ell+s$, and $q(z)=\sum_{i=1}^m q_j z^j$, we have the vector of coefficients $q=[0;q_1;...;q_m]\in \C^{m+1}$ of $q(z)$ such that, by \eqref{eq:qnorm},
\[
\|q\|^2_2\leq {40s(s+2)\ln[8s(m-s)]\over m-s},
\]
and such that the polynomial $q^\ell(z)=1+q(z)$ is divisible by $p(z)$ due to \eqref{eq:qldiv}.\qed
\subsection{Proof of Theorem \ref{th:sepsines}}
\subsection{Proof of Theorem \ref{th:sepsines}}
Let $\Pi_{\mathcal{S}_m}$ be the projector onto $\S_m$, that is $\S$ restricted on $\C(\Z_{0,m})$. Let $\phi \in \C^{m+1}$ be its last row. Note that $\phi$ satisfies $x_t = [\phi * x]_t$ for any $x\in \S$ and $t \in \Z$. Indeed, the equality holds for $t=m$ by the definition of $\Pi_{\mathcal{S}_m}$, and it holds for any other $t \in \Z$ due to the shift-invariance of $\S$. Let us bound $\|\phi\|_2$.
Because $\S_m$ is spanned by $\{V_k\}_{k=1}^s$,
\[
[V_k]_t = \frac{e^{\imath \omega_k t}}{\sqrt{m+1}}, \quad 0 \le t \le m,
\]
$\Pi_{\mathcal{S}_m}$ can be written as
$$ \Pi_{\mathcal{S}_m} = V\left(V^HV\right)^{-1}V^H,$$
where $V=[V_1,....,V_s]$ ($V$  has full column rank if all the frequencies are distinct).  To upper-bound $\|\phi\|_2$, it suffices to lower bound the minimal eigenvalue $\lambda_{*}$ of  $V^H V$. Indeed, one has the ``economy eignevalue decomposition'' of
$\Pi_{\mathcal{S}_m} = U U^H$ where $U = V(V^HV)^{-1/2} \in \C^{(m+1)\times s}$ satisfies $U^H U = I_s$. Denoting $u$ the last row of $U$, one has \[
\phi = uU^H = \sum_{k=1}^s u_k [U_k]^H,
\] whence, $\|\phi\|_2 = \|u\|_2$. On the other hand, writing $u =v (V^H V)^{-1/2}$, where $v$ is the last row of $V$, we obtain
\[
\|u\|_{2} \le \frac{\|v\|_2}{\sqrt{\lambda_{*}}} \le \sqrt{\frac{s}{\lambda_{*} (m+1)}}
\]
(recall that $|[V]_{kj}|\leq 1/\sqrt{m+1}$). Finally, to lower bound $\lambda_*$ we use following bound on the condition number $Q$ of
$V^HV$ (cf.  \cite[Theorem~2.3]{moitra2015super}):
\[
Q \le \frac{m + \delta^{-1}_{\rm\min}}{m - \delta^{-1}_{\rm\min}}\leq {u+1\over u-1},
\]
provided that the denominator in the right hand side is strictly positive. Since the singular norm of $V$ is at least $1$,   we conclude that \[
\lambda_{*} \geq Q^{-1}\geq {u-1\over u+1},
\]
what implies \rf{separated}.
\qed
\section{Miscellanious proofs}\label{sec:prmisc}
\subsection{Issue with the $\ell_2$-constrained estimator}
Here our goal is to show the technical challenge of analyzing the $\ell_2$-constrained empirical risk minimization estimator \eqref{eq:l2f}. For brevity we omit the indices $[\cdot]_{-m}^n$ everywhere, so that $\zeta$ must be read as $[\zeta]_{-m}^n$, etc. The oracle $\varphi$, which satisfies \eqref{eq:ss1} and \eqref{eq:l2-oracle-characterization}, is a feasible solution for \eqref{eq:l2f}, hence
\begin{equation*}
\|y- \widehat\varphi * y\|^2_2 \le \|y- \varphi * y\|^2_2.
\end{equation*}
On the other hand, for the squared $\ell_2$ loss of the oracle $\varphi$ one has:
\begin{equation*}
\|x- \varphi * y\|^2_2 = \|y- \varphi * y\|^2_2 - \sigma^2\|\zeta\|_2^2 + 2\sigma\langle \zeta, x - \varphi * y \rangle.
\end{equation*}
Expanding in the same way the squared $\ell_2$ loss of $\widehat\varphi$, one obtains
\begin{equation}\label{eq:cross-terms}
\|x- \widehat\varphi * y\|^2_2 = \|x-\varphi * y\|^2_2 + 2\sigma\langle \zeta, x - \varphi * y\rangle + 2\sigma\langle \zeta, x - \widehat\varphi * y\rangle.
\end{equation}
Let us treat $\rho$ as a constant. By using a decomposition similar to the one in the proof of Theorem \ref{th:point}, it is easy to show that the bound of the order $\cO(\sigma^2)$ on the average squared $\ell_2$-loss of a filter implies that the MSE of the filter is of the order $\sigma^2/m$ as needed; moreover, the inverse statement is trivial. Hence, we must prove show that $\E \|x- \widehat\varphi * y\|^2_2 = \cO(\sigma^2)$, and in order to do that, we have to control both cross-terms in \eqref{eq:cross-terms}. The first of them makes no challenge: since $\varphi$ is non-random, we have
\[
\E \sigma \langle \zeta, x - \varphi * y \rangle = \sigma \underbrace{\E \langle \zeta, x - \varphi * x \rangle}_{0} - \sigma^2 \E \langle \zeta, \varphi * \zeta \rangle = -2(m+n)\sigma^2\varphi_0.
\]
Unfortunately, without additional restrictions on the oracle, such as $\varphi_0 \le 0$, the right hand side can be of order $\sigma^2\sqrt{m+n+1}$.

Moreover, even if such restrictions are imposed, and the first cross-term in \eqref{eq:cross-terms} is controlled, a naive attempt to carry out this analysis for the second cross-term fails. Indeed, since $\widehat\varphi$ is random, the only straightforward way to control the second cross-term is the ``worst-case analysis'':
\begin{equation*}
\langle \zeta, \widehat \varphi * \zeta \rangle  \le \max_{\|\varphi\|_{2}\le \rho/\sqrt{m+1} } \langle \zeta, \varphi * \zeta \rangle.
\end{equation*}
Note that if one replaces the usual convolution with the circular one cf. \eqref{eq:circ_diag}, the right hand side with high probability can be as large as $c\rho\sqrt{m+n+1}$ which can be seen through the Parseval identity. There is no reason to assume that the usual convolution behaves nicer than the circular one, and the ``worst-case analysis'' fails. Perhaps, one might try to exploit that $\widehat\varphi$ is not arbitrary, and control the cross-term more cleverly, but we do not know how to carry out such an argument.

\subsection{Proof of Lemma \ref{th:shift_invariant}}

As a precursory remark, note that if a finite-dimensional subspace $\S$ is shift-invariant, i.e. $\Delta \S \subseteq \S$, then necessary $\Delta$ is a bijection on $\S$, and $\Delta\S = \S$. Indeed, when restricted on $\S$, $\Delta$ obviously is a linear transformation with a trivial kernel, and hence a bijection.

To prove the direct statement, note that the solution set of \eqref{eq:diff_eq} with $\deg(p(\cdot)) = s$ is a shift-invariant subspace of $\C(\Z)$ -- let us call it $\S'$. Indeed, if $x \in \C(\Z)$ satisfies $\eqref{eq:diff_eq}$, so does $\Delta x$, so $\S'$ is shift-invariant. To see that $\dim(\S') = s$, note that $x \mapsto x_1^s$ is a bijection $\S' \to \C^s$: under this map arbitrary $x_1^s \in \C^{s}$ has a unique preimage. Indeed, as soon as one fixes $x_1^s$, \eqref{eq:diff_eq} uniquely defines the next samples $x_{s+1}, x_{s+2}, ...$ (note that $p(0) \ne 0$); dividing \eqref{eq:diff_eq} by $\Delta^s$, one can retrieve the remaining samples of $x$ since $\deg(p(\cdot))=s$ (here we used that $\Delta$ is bijective on $\S$).

For the converse statement, first note that any polynomial $p(\cdot)$ with $\deg(p(\cdot)) = s$, $p(0)=1$ is uniquely expressed as $p(z) = \prod_{k=1}^s (1-z/z_k)$ where $z_1, ..., z_s$ are its roots. Since $\S$ is shift-invariant, we have $\Delta \S = \S$ as discussed above, i.e. $\Delta$ is a bijective linear transformation on $\S$. Let us fix some basis $\boldsymbol{e}^T = \begin{bmatrix} e^1,\, ...,\, e^s\end{bmatrix}$ on $\S$, and denote $A$ the $s \times s$ matrix of $\Delta$ in it, i.e. $\Delta(e^j) = \sum_{i=1}^s a_{ij} e^{i}$. The basis $\boldsymbol{e}$ might be chosen such that $A$ is upper-triangular (say, by passing to its Jordan normal form). Then, any vector $x \in \S$ satisfies
$
q(\Delta) x \equiv 0,$
where $q(\Delta) = \prod_{i=1}^s (\Delta - a_{ii}) = \det(\Delta I - A)$ is the characteristic polynomial of $A$.
Note that $\prod_{i=1}^s a_{ii} = \det A \ne 0$ since $\Delta$ is a bijection on $\S$. Hence, introducing $p(\Delta) = q(\Delta) / \det A$, we obtain
$\prod_{i=1}^s (1-\Delta c_i) x \equiv 0$ for some complex numbers $c_i \ne 0$. This means that $\S$ is contained in the solution set $\S'$ of \eqref{eq:diff_eq} with $\deg(p(\cdot))=s$, $p(0)=1$, which is itself a shift-invariant subspace of dimension $s$ (by the direct statement). Since $\dim(\S) = \dim(\S') = s$, the two subspaces coincide.
Uniqueness of $p(\cdot)$ then follows from the fact that $q(\cdot)$ is a characteristic polynomial of $A$.
\qed
\subsection{Proof of relations \eqref{eq:l1f}, \eqref{eq:var2f}, \eqref{eq:oracle-quad-risk}, and \eqref{eq:oracle-quad-loss}}
Let $n=2m$, $\phi\in \C(\Z_0^m)$, and let $\varphi\in \C(\Z_{0}^n)$ satisfy $\varphi=\phi*\phi$. Then
 \bse
 \|\varphi\|^*_{n,1} &=& (2m+1)^{-1/2}\sum_{k=0}^{2m} |[F_{2m}\varphi_{0}^{2m}]_k| =  \sqrt{2m+1}\sum_{k=0}^{2m}  \left({|[F_{2m}\phi_{0}^{2m}]_k|\over{\sqrt{2m+1}}}\right)^2\nn
&=&  \sqrt{2m+1} \|\phi\|^{*2}_{2m,2} =   \sqrt{2m+1}\|\phi\|^2_{2m,2}=   \sqrt{2m+1} \|\phi\|_{m,2}^2
\leq {\sqrt{2m+1} \, \rho^2\over m+1},
 \ese
implying \eqref{eq:l1f}. Moreover, since $1-\phi*\phi=(1+\phi)*(1-\phi)$, for all $x\in \C(\Z)$ one has for all ${\tau}\in \Z$:
\begin{equation}\label{eq:relations-bias}
\begin{aligned}
|x_{{\tau}} - [\varphi^o* x]_{{\tau}}| &= |[(1 +\phi^o)*(1 - \phi^o)*x]_{\tau}| = \left|\sum_{j=0}^m
 [1 + \phi^o]_{j} \,[x - \phi^o*x]_{\tau - j}\right|\\
&\le \|1 + \phi^o\|_1 \max_{0\leq j\leq m} |[x - \phi^o* x]_{{\tau - j}}|\leq {\sigma(1+\rho)\rho\over \sqrt{m+1}}
\end{aligned}
\end{equation}
(we have used \eqref{eq:ss1} to obtain the last inequality). Now, for each $0 \leq \tau \leq m$, $[\varphi^o * \zeta]_\tau \sim \C\N(0,\|\varphi^o\|_2^2)$, and noting that
\[
\|\varphi^o\|_2\leq \|\varphi\|^*_{n,1}\leq{2\rho^2\sqrt{n+1}\over n+2},
\]

we obtain \eqref{eq:var2f} and then \eqref{eq:oracle-quad-risk}. Further, from \eqref{eq:relations-bias} it follows that
\[\|x - [\varphi^o* x]\|_{n,2}\leq \sigma(1+\rho)\rho,
\]
and
\[
\|\varphi^o*\zeta\|_{n,2}^2=\langle \zeta,M(\varphi^o)\zeta\rangle_n,
\]
where $M(\varphi)$ is defined as in \eqref{M(phi)}. Taking into account the bound on $\|\varphi^o\|_2$ once again, we get (cf. \eqref{tr22})
$\|M(\varphi^o)\|_F^2=(n+1)\|\varphi\|_2^2\leq 4\rho^4$,
so that the concentration inequality \eqref{trq1} now implies that, given $0<\alpha\leq 1$, with probability at least $1-\alpha$,
\be
\|\varphi^o*\zeta\|_{n,2}\leq 2\sqrt{2}\rho^2\left(1+\sqrt{\ln[1/\alpha]}\right),
\ee{eq:varphizeta}
and we arrive at
\eqref{eq:oracle-quad-loss}.
\qed

\subsection{Proof of Proposition \ref{th:sines-best}}
We will carefully apply the extended formulation of the results of Section~\ref{sec:proracle}. Recall that we are given a generalized harmonic oscillation signal $x_t$ with $s$ frequencies on the segment $[-N,N]$. Now, let us divide this segment into a large central region $[-N_0,N_0]$ and the remaining ``edge'' of size $N-N_0 \le N_0$.
Let us apply Theorem~\ref{th:l2conl} to recover $x$ at the edges by a unilateral filter. That is, we have an estimator $\widehat x_1 = \widehat\varphi * y$, for some $\varphi \in \C(\Z_{0}^{N+N_0})$ satisfying (neglecting the log factors)
\[
\|\wh \varphi\|_2^2 \le \varrho_{\text{edge}}^2/(N+N_0+1) \lesssim s^4 / (N+N_0+1),
\] and such that
\begin{equation}
\begin{aligned}
\frac{1}{\sigma^2} \sum_{N_0 \le t \le N} \E (x_t-\wh x_t)^2
&\lesssim  \sum_{n_0 \le t \le n} \E |[\wh \varphi * \zeta]_t|^2 + \varrho_\text{edge} (1+\kappa^2_{N+N_0,N-N_0}) + s \\
&\lesssim \varrho_\text{edge}^2 \kappa^2_{N+N_0,N-N_0}  +  \varrho_\text{edge} (1+\kappa^2_{N+N_0,N-N_0})  + s \\
&\lesssim s^4 \kappa^2_{N+N_0,N-N_0}  + s^2,
\end{aligned}
\label{eq:sines-best-edge}
\end{equation}
where we used the bound on $\|\varphi\|_2^2$ in the second transition, and then Theorem~\ref{th:sines} together with $\kappa^2_{n+n_0,n-n_0} \le 1$ in the last transition. By symmetry, we have the same bound for the left edge. As for the central segment, there we can apply the ``interpolation version'' of Theorem~\ref{th:l2conl} (whose formal statement we omit here), computing a filter in the class $\C(\Z_{-(N-N_0)}^{N-N_0})$ such that
\[
\|\wh \varphi\|_2^2 \le \varrho_{\text{center}}^2/(2(N-N_0)+1) \lesssim s^2 / (2(N-N_0)+1)
\] and
\begin{equation}
\begin{aligned}
\frac{1}{\sigma^2} \sum_{-N_0 \le t \le N_0} \E (x_t-\wh x_t)^2
&\lesssim  \sum_{-N_0 \le t \le N_0} \E |[\wh \varphi * \zeta]_t|^2 + \varrho_\text{center} (1+\kappa^2_{2(N-N_0),2N_0}) + s \\
&\lesssim \varrho_\text{center}^2 \kappa^2_{2(N-N_0),2N_0} + s \\
&\lesssim s^2 \kappa^2_{2(N-N_0),2N_0},
\end{aligned}
\label{eq:sines-best-center}
\end{equation}
where we applied Proposition~\ref{th:shift-inv-bilateral} and used that $\kappa^2_{2(N-N_0),2N_0} \ge 1$. Joining~\eqref{eq:sines-best-edge}~and ~\eqref{eq:sines-best-center} (that is, using in each region the corresponding estimator), we obtain that there exists an estimator $\widehat x$ of $x$ on the whole segment $[-N,N]$, which satisfies
\[
\frac{1}{\sigma^2} \sum_{-N \le t \le N} \E (x_t-\wh x_t)^2 \lesssim s^4 \kappa^2_{N+N_0,N-N_0} + s^2 \kappa^2_{2(N-N_0),2N_0} \lesssim s^4 \frac{N-N_0}{N_0} + s^2 \frac{N_0}{N-N_0}.
\]
Finally, note that the bound in the right-hand side is minimized with $N_0/(N-N_0) \sim s$, whence the first bound in the premise of the Proposition follows. The second bound (for the well-separated case) is straightforward. \qed

\end{document}