TITLE: Accurate numerical evaluation of a ratio of Bessel functions
QUESTION [4 upvotes]: For fixed positive $x$, I would like to accurately (close to full precision) evaluate the ratio of Bessel functions of the first kind
$$
R_n(x):= \frac{J_{n+1}(x)}{J_n(x)}
$$
as $n$ becomes extremely large. Evaluating the special functions directly fails because both numerator and denominator become very small. However, it is known that this ratio obeys the large $n$ asymptotics
$$
R_n(x) \sim \sqrt{\frac{n}{n+1}} \frac{x}{2(n+1)}
$$
so in principle it seems possible that there is a stable method for computing this quantity. Does anybody have any suggestions?

REPLY [0 votes]: Boost.math uses Miller's algorithm for this problem; see J.M.'s description here. Code to compute the ratio to 100 digits or so:
#include <iostream>
#include <boost/math/constants/constants.hpp>
#include <boost/math/special_functions/bessel.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>

using std::sqrt;
using boost::math::cyl_bessel_j;
using namespace boost::multiprecision;

int main(int argc, char** argv)
{
    cpp_dec_float_100 x{5.7};
    for (int i = 10000; i < 50000; ++i)
    {
        std::cout << "J_" << i << "/J_" << i+1 << " = " << cyl_bessel_j<cpp_dec_float_100>(i+1, x)/cyl_bessel_j<cpp_dec_float_100>(i, x) << "\n";
        std::cout << "asymptotic form = " << sqrt((cpp_dec_float_100)i /(cpp_dec_float_100) i+1)*x/(2*i+2) << "\n";
    }
}


TITLE: Find the adjoint operator of $T_p$
QUESTION [2 upvotes]: Let $V=\mathscr{M}_n(C)$ with an inner product $\langle A,B\rangle=\mathrm{Tr}\,(AB^{*})$, $P$ be a fixed invertible matrix in $V$, and $T_P$ be the linear operator on $V$ defined by $T_{P}(A)=P^{-1}AP$. Find $T^{*}_{P}$, the adjoint operator of $T_P$.
Can you help me?

REPLY [3 votes]: The transformation $T_{P}^*$ should satisfy
$$
\mathrm{Tr}(P^{-1}APB^*)=\langle T_P(A),B\rangle=\langle A,T_P^*(B)\rangle
=\mathrm{Tr}\big(A(T_P^*(B))^*\big),
$$
for all $A,B \in \mathscr M(\mathbb C)$.
But
$$
\mathrm{Tr}(P^{-1}APB^*)=\mathrm{Tr}(APB^*P^{-1})=\mathrm{Tr}\big(A((P^*)^{-1}BP^*)^*\big)=\langle A,T_{P^{*}}(B)\rangle,
$$
and hence the adjoint of the transformation $T_P$ is the transformation $T_{P^*}$.

REPLY [1 votes]: Hint: $Tr(P^{-1}\cdot (APB^*) )=Tr(A \cdot (PB^*P^{-1}))$. Now consider $\hat{T}: \hat{T}(B)=PB^*P^{-1}$...


TITLE: Expansion velocity and recessional velocity
QUESTION [1 upvotes]: Differentiation of scale factors means the rate of expansion. But at the same time,
recession velocity has the following relationship: $\dot{}=\dot{}$
Do the recessional velocity and expansion velocity mean the same thing? (when co-moving distance is fixed)

REPLY [1 votes]: Yes both mean the same velocity.


TITLE: Connected, locally connected, path-connected but not locally path-connected subspace of the plane
QUESTION [33 upvotes]: I am looking for a set in the plane (with respect to the natural Euclidean topology) that is connected, locally connected, path-connected but not locally path-connected. I did not find one in Steen-Seebach, but maybe I overlooked?

REPLY [13 votes]: I'm posting this answer in order to show that the excellent example given by bof does satisfy the required properties - it is path connected and locally connected, but not locally path connected. See that answer for a construction of the set and for plots of it.
As I am not adding any new examples of my own, I'll make this answer community wiki so others can edit it.
I'll start by constructing the set in slightly different way which should represent the tree-like nature of the set a bit better. First, a bit of notation. Use $\mathbb{N}=\{1,2,\ldots\}$ for the positive integers, and $\mathbb{N}^*=\bigsqcup_{n=0}^\infty\mathbb{N}^n$ for the collection of finite sequences of positive integers. For any $a=(a_1,\ldots,a_m)$, $b=(b_1,\ldots,b_n)$ in $\mathbb{N}^*$ and $k\in\mathbb{N}$ then I will write $a\cdot k=(a_1,\ldots,a_m,k)$ $a\cdot b=(a_1,\ldots,a_m,b_1,\ldots,b_n)$. We can also put the lexicographic order on $\mathbb{N}^*$, so that $a\le b$ iff there is a $j\le\min(m,n)$ with $a_i=b_i$ for all $i < j$ and $a_j < b_j$, or if $m\le n$ and $a_i=b_i$ for all $i\le m$.
Now, let $\{x_a\}_{a\in\mathbb{N}^*}$ be real numbers with the following properties,

For any $a\in\mathbb{N}^*$ then $k\mapsto x_{a\cdot k}$ is a strictly increasing sequence strictly bounded below by $x_a$.
For any $a=(a_1,\ldots,a_n)$ with $n\ge1$, then $x_{a\cdot k}\to x_{a^\prime}$ as $k\to\infty$, where $a^\prime=(a_1,\ldots,a_{n-1},a_n+1)$.

These properties are equivalent to saying that $a\mapsto x_a$ is strictly increasing and order-continuous w.r.t. the lexicographic order.
Letting $S(x,y)$ be the closed semicircle in the upper half-plane with endpoints $(x,0)$ and $(y,0)$, we define the set
$$
X=\bigcup_{a\in\mathbb{N}^*,k\in\mathbb{N}}S(x_a,x_{a\cdot k}).
$$
I will use $P_a$ to denote the point $(x_a,0)$, so that $X$ intersects the x-axis precisely at the points $\{P_a\colon a\in\mathbb{N}^*\}$. We can show that $X$ is path connected and locally connected, but is not locally path connected at the points $(x_a,0)$ whenever $a=(a_1,\ldots,a_n)$ with $n\ge1$ and $a_n\ge2$.
The following example gives the same set $X$ as in bof's answer.

$x_{()}=0$,
$x_{(k)}=k/(k+1)$.
$x_{a\cdot k}=(x_{a}+kx_{a^\prime})/(k+1)$ for all $a=(a_1,\ldots,a_n)$ with $n\ge1$, $k\in\mathbb{N}$ and $a^\prime=(a_1,\ldots,a_{n-1},a_n+1)$.

We can prove the following statements.

$X$ is path connected.

By definition, each point of $X$ is connected via an arc of a semicircle to a point $P_{(a_1,\ldots,a_n)}$. This is in turn connected to $P_{(a_1,\ldots,a_{n-1})}$ by a semicircular arc and, applying this inductively, we see that each point of $X$ is connected to $P_{()}$ by a sequence of arcs of semicircles.

The semicircles $S(x_a,x_{a\cdot k})$ minus their endpoints ($P_a,P_{a\cdot k}$) are open in $X$.

This should be clear from the plot of $X$ in bof's answer. If $k > 1$ then it can be seen that the region bounded above by the semicircular arc $S(x_a,x_{a\cdot (k+1)})$ and below by the semicircle $S(x_a,x_{a\cdot(k-1)})$, $S(x_{a\cdot(k-1)},x_{a\cdot k})$ and $S(x_{a\cdot k},x_{a\cdot(k+1)})$ is an open subset of the plane intersecting $X$ at $S(x_a,x_{a\cdot k})$ minus its endpoints.
In the case where $k=1$, we can bound the region from below by the line segment joining $P_a$ to $P_{a\cdot k}$ and the semicircle $S(x_{a\cdot k},x_{a\cdot(k+1)})$.

Let $D$ be an open disc centered on the x-axis. Then $D\cap X$ is connected.

Let $S$ be a nonempty set which is open and closed on $D\cap X$. We need to show that it is all of $D\cap X$. Note that each of the semicircles defining $X$ intersects $D$ in an arc (i.e., connected) meeting one of the points $P_a$, if it intersects it at all. So, $P_a\in S$ for some $a$. We just need to show that $S$ contains all of the points $P_a$ which are in $D$. I'll show that if $a\le b$, $P_a\in S$ and $P_b\in D$ then $P_b\in S$. Applying the same statement to the complement of $S$ will show that it also holds for $a \ge b$, which gives the result.
If $P_a\in S$ and $P_{a\cdot k}\in D$ then the semicircle joining $P_a$ to $P_{a\cdot k}$ lies in $D\cap X$, so $P_{a\cdot k}\in S$. Next, if $a= (a_1,\ldots,a_n)$ has $n\ge1$ and $a^\prime=(a_1,\ldots,a_n+1)$ satisfies $P_{a^\prime}\in D$ then $P_{a^\prime}=\lim_{k\to\infty}P_{a\cdot k}\in S$. Inductively applying this gives $P_{(a_1,\ldots,a_n+k)}\in S$ whenever it is in $D$.
Now consider $a=(a_1,\ldots,a_m)$ and $b=(b_1,\ldots,b_n)$ with $a\le b$, $P_a\in S$ and $P_b\in D\cap X$. If $m\le n$ and $a_i=b_i$ for $i\le m$ then we have $P_{(b_1,\ldots,b_m)}=P_a\in S$. Using the above, we can inductively apply $P_{(b_1,\ldots,b_{m+1})}=P_{(b_1,\ldots,b_m)\cdot b_{m+1}}\in S$. to see that $P_b\in S$.
Finally, consider the case where for some $j\le\min(m,n)$ we have $a_i=b_i$ for all $i < j$ and $a_j < b_j$. From what we have shown above,
$$
P_{(a_1,\dots,a_{m-1}+1)}=\lim_{k\to\infty}P_{(a_1,\dots,a_{m-1},a_m+k)}\in S.
$$
Inductively applying this gives $P_{(a_1,\ldots,a_{j-1},a_j+1)}\in S$. Then, as $b_j=a_j+1+k$ for some $k\ge0$, applying what we have shown above gives $P_{(b_1,\ldots,b_j)}\in S$. Then, using the first case, we have $P_b\in S$.

$X$ is locally connected

Each point of $X$ not on the x-axis lies on one of the semicircles $S(x_a,x_{a\cdot k})$ minus its endpoints which we have shown to be open in $X$. So, $X$ is locally (path) connected away from the x-axis. Next, any point on the x-axis has a base of connected neighborhoods by taking the open discs centered at the point intersected with $X$.

For any $a=(a_1,\ldots,a_n)$ with $n\ge1$ and $a_n \ge 2$, $X$ is not locally path connected at $P_a$.

This remains to be added...


text:
\section{Proof of oracle inequalities}
\label{sec:orc-proofs}

In this section, we prove our main results -- sharp oracle inequalities for regularized least-squares estimators (Theorems~\ref{th:l2con}--\ref{th:l2pen++}).
First, let us present some additional notation and technical tools to be used in the proofs.

\paragraph{Additional notation.}
$\Re(z)$ and $\Im(z)$ denote, correspondingly, the real and imaginary parts of a complex number $z \in \C$, and $\overline{z} = \Re(z) - i\Im(z)$ denotes the complex conjugate of $z$.
We denote $A^\T$ the transpose of a complex-valued matrix $A$, and $A^\H$ its conjugate transpose.
We denote $\overline{A}$ the conjugation of $A$ without transposition.
We denote $A^{-1}$ the inverse of $A$ whenever it is guaranteed to exist.
We denote $\Tr(A)$ the trace of a matrix $A$, $\det(A)$ its determinant, $\|A\|_\F$ the Frobenius norm, and $\|A\|_{\op}$ the operator norm.

We denote $\lmax(A)$ and $\lmin(A)$ the maximal and minimal eigenvalues of a Hermitian matrix $A$.
We denote $\Diag(a)$ the diagonal matrix formed from a vector $a \in \C^{n}$.
We denote $I$ the identity matrix, sometimes with a subscript indicating its size.
We denote $\langle\cdot,\cdot\rangle$ the Hermitian scalar product: for two complex vectors $a, b$ of the same dimension, $\langle a,b\rangle=a^\H b$.
We denote $\langle x, y \rangle_n := \langle [x]_{-n}^n, [y]_{-n}^n\rangle_n$ for $x, y \in \C(\Z)$.

In what follows, we associate linear maps $\C_{n}(\Z) \to \C_{n'}(\Z)$ with matrices in~$\C^{(2n+1)\times (2n'+1)}$.

\subsection{Technical tools}

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

\left[\begin{array}{clclc}
y_{-n+m}& \cdots & y_{-n}&\cdots &y_{-n-m}\\
\vdots &\cdots & \vdots &\cdots &\vdots \\
y_m &  \cdots & y_{0}& \cdots &y_{-m}\\

\vdots &\cdots & \vdots &\cdots &\vdots \\
y_{n+m}& \cdots & y_{n}&\cdots &y_{n-m}
\end{array}\right],
\ee{s(psi)}
such that $[\varphi*y]_{-n}^n = T(y) [\varphi]_{-m}^m$ for $\varphi \in \C_m(\Z)$. Its squared Frobenius norm satisfies
\be
\left\|T(y)\right\|_\F^2 = \sum\limits_{\tau \in \Dom_m} \|\Delta^\tau y\|^2_{n,2}.
\ee{tr21}
\item
Given $\varphi \in \C_m(\Z)$, consider an $(2n+1)\times(2m+2n+1)$ matrix
\be
M(\varphi)=
\left[\begin{array}{cllllllc}
\varphi_{m}&\cdots &\cdots  &\varphi_{-m}&0&\cdots &\cdots &0\\
0&\varphi_{m}&\cdots  &\cdots &\varphi_{-m}&0&\cdots &0\\
\vdots &\ddots &\ddots &\cdots &\cdots &\ddots &\cdots &\vdots \\
\vdots &\cdots &\ddots &\ddots &\cdots &\cdots &\ddots &\vdots \\
0 &\cdots &\cdots &0&\varphi_{m}&\cdots &\cdots &\varphi_{-m}
\end{array}\right],
\ee{M(phi)}
such that for $y \in \C(\Z)$ one has $[\varphi*y]_{-n}^n=M(\varphi) [y]_{-m-n}^{m+n}$, and
\be
\left\|M(\varphi)\right\|_\F^2= (2n+1)  \|\varphi\|^2_{m,2}.
\ee{tr22}

\item
Given $\varphi \in \C_m(\Z)$, consider the following circulant matrix of size $2m+2n+1$:
\be
C(\varphi) =
\left[\begin{array}{ccccccccccccc}
\varphi_{0} &\cdots & \cdots & \varphi_{-m} & 0 & \cdots & \cdots & \cdots &  0  & \vphi_m & \cdots & \cdots & \vphi_1 \\
\vphi_1 & \varphi_{0} &\cdots & \cdots & \varphi_{-m} & 0 & \cdots & \cdots & \cdots &  0  & \vphi_m & \cdots & \vphi_2 \\
\cdots & \cdots & \ddots & \cdots & \cdots & \ddots & \ddots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\
\cdots & \cdots & \cdots & \ddots & \cdots & \cdots & \ddots & \ddots & \cdots & \cdots & \cdots & \cdots & \cdots \\
\cdots & \cdots & \cdots & \cdots & \ddots & \cdots & \cdots & \ddots & \ddots & \cdots & \cdots & \cdots & \cdots \\
\cdots & \cdots & \cdots & \cdots & \cdots & \ddots & \cdots & \cdots & \ddots & \ddots & \cdots & \cdots & \cdots \\
0 & \cdots  & 0 & \varphi_{m} &\cdots & \cdots & \varphi_{0} & \cdots & \cdots & \vphi_{-m} & 0 & \cdots & 0 \\
\cdots & \cdots & \cdots & \ddots & \ddots & \cdots & \cdots & \ddots & \cdots & \cdots & \cdots & \cdots & \cdots \\
\cdots & \cdots & \cdots & \cdots & \ddots & \ddots & \cdots & \cdots & \ddots & \cdots & \cdots & \cdots & \cdots \\
\cdots & \cdots & \cdots & \cdots & \cdots & \ddots & \ddots & \cdots & \cdots & \ddots & \cdots & \cdots & \cdots \\
\cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \ddots & \ddots & \cdots & \cdots & \ddots & \cdots & \cdots \\
\cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \ddots & \ddots & \cdots & \cdots & \ddots & \cdots \\
\varphi_{-1} &\cdots & \cdots & \varphi_{-m} & 0 & \cdots & \cdots  & \cdots &  0  & \vphi_m & \cdots & \cdots & \vphi_0
\end{array}\right].

\ee{C(phi)}
Note that~$C(\varphi) [y]_{-m-n}^{m+n}$ is the circular convolution of $[y]_{-m-n}^{m+n}$ and the zero-padded filter
\[
\tilde\vphi := [\vphi]_{-m-n}^{m+n} = [0; ...; \vphi_{-m}; ...; \vphi_m; 0; ...; 0],
\]
that is, convolution of the periodic extensions of $[y]_{-m-n}^{m+n}$ and $\tilde \vphi$ evaluated on $\Dom_{m+n}$.
Hence, by the diagonalization property of the DFT operator one has
\begin{equation}\label{eq:circ_diag}
C(\varphi) = \sqrt{2m+2n+1}  F^\H_{m+n} \text{diag}(F_{m+n}[\tilde\vphi]) F_{m+n}.
\end{equation}
Besides, note that
\begin{equation*}
\left\|C(\varphi)\right\|_\F^2 = (2m+2n+1) \|\varphi\|^2_{m,2}.
\end{equation*}

\end{itemize}

\paragraph{Deviation bounds for quadratic forms.}
We use simple probabilistic facts listed below.
\begin{itemize}
\item
Let $\zeta \sim \C\N(0,I_n)$ be a standard complex Gaussian vector, meaning that $\zeta = \xi_1 + i\xi_2$ where $\xi_{1}$  and $\xi_{2}$ are two independent draws from $\N(0,I_n)$. We use a simple bound
\begin{align}\label{eq:complex_gaussian_max}
\prob\left\{\|\zeta\|_{\infty} \le \sqrt{2\log n + 2u}\right\} \ge 1-e^{-u}
\end{align}
which can be verified directly using that~$|\zeta_1|^2_2 \sim \chi_2^2$.
\item
The following deviation bounds for $\|\zeta\|^2_2 \sim \chi^2_{2n}$ are due to \cite[Lemma 1]{lama2000}:
\begin{equation}\label{eq:chi_bound_low}
\begin{aligned}
&\prob\left\{\frac{\|\zeta\|^2_2}{2} \le n + \sqrt{2nu} + u \right\} \ge 1-e^{-u},\\
&\prob\left\{\frac{\|\zeta\|^2_2}{2} \ge n - \sqrt{2nu} \right\} \ge 1-e^{-u}.
\end{aligned}
\end{equation}
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$ be 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]$.
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, correspondingly, the spectral and Frobenius norms of a matrix.
Invoking again~\cite[Lemma 1]{lama2000} (a close inspection of the proof shows that the assumption of positive semidefiniteness can be relaxed), we have
\begin{align}\label{trq2}
\prob\left\{\frac{\zeta^\H K \zeta}{2} \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\{\frac{\zeta^\H K \zeta}{2} \leq \Tr(K)(1+\sqrt{u})^2\right\} \geq 1-e^{-u}.
\end{align}
\end{itemize}

\paragraph{Reformulation of approximate shift-invariance}
The following reformulation of Assumption~\ref{ass:subspace} will be convenient for our purposes.
\begin{quotation}\noindent
{\em There exists an $s$-dimensional vector subspace $\S_{n}$ of $\C^{2n+1}$

and an idempotent Hermitian $(2n+1)\times (2n+1)$ matrix~$\Pi_{\S_{n}}$ of rank $s$ -- projector on $\S_n$ -- such that
\be
\big\|\left(I_{2n+1}-\Pi_{\mathcal{S}_{n}}\right) \left[\Delta^\tau x\right]_{-n}^{n}\big\|_2 \, \Big[={\left\|\Delta^{\tau} \varepsilon\right\|_{n,2}
}\Big] \leq \sigma\varkappa, \quad \tau \in \Dom_m,
\ee{subspace1}
where $I_{2n+1}$ is the identity matrix of size $2n+1$.
}
\end{quotation}

\subsection{Proof of Theorem~\ref{th:l2con}}

\paragraph{\underline{Step 1$^o$.}}
Let~$\vphi^o \in \C_m(\Z)$ be any filter satisfying the constraint in~\eqref{opt:l2con}.
Then,
\be
\|x-\wh\varphi*y\|_{n,2}^2
&\le& \|(1-\varphi^{o})*y\|_{n,2}^2-{\sigma^2\|\zeta}\|_{n,2}^2-2\sigma\Re \langle \zeta, x-\wh\varphi*y\rangle_n \nn
&=&\|x-\varphi^{o}*y\|_{n,2}^2  - 2\underbrace{\sigma\Re\langle \zeta, x-\wh\varphi*y\rangle_n }_{{\delta^{(1)}}} + 2\underbrace{\sigma \Re\langle \zeta, x-\varphi^{o}*y\rangle_n }_{{\delta^{(2)}}}.
\ee{first0}

Let us bound ${\delta^{(1)}}$.
Denote for brevity $I := I_{2n+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{\sigma \Re\langle [\zeta]_{-n}^n, \Pi_{\cS_n}[x-\wh\varphi*y]_{-n}^n\rangle}_{{\delta^{(1)}_1}} +\underbrace{\sigma \Re\langle [\zeta]_{-n}^n, (I-\Pi_{\cS_n})[x-\wh\varphi*x]_{-n}^n\rangle}_{{\delta^{(1)}_2}}\nn &&-\underbrace{\sigma^2 \Re\langle [\zeta]_{-n}^n, (I-\Pi_{\cS_n})[\wh\varphi * {\zeta}]_{-n}^n \rangle}_{{\delta^{(1)}_3}}
\ee{I_pi}
One can easily bound $\delta^{(1)}_1$ under the premise of the theorem:
\[
\begin{aligned}
\left|{\delta^{(1)}_1} \right|
&\leq {\sigma}\big\|\Pi_{\cS_n} {[\zeta]}_{-n}^n\big\|_2  \big\|\Pi_{\cS_n}[x-\wh\varphi*y]_{-n}^n\big\|_{2} \nn
&\leq {\sigma}\big\|\Pi_{\cS_n} {[\zeta]}_{-n}^n\big\|_2  \big\|x-\wh\varphi*y\big\|_{n,2}.
\end{aligned}
\]
Note that $\Pi_{\cS_n} [\zeta]_{-n}^n \sim \C\N(0,I_s)$, and by \eqref{eq:chi_bound} we have
\[
\prob\left\{\big\|\Pi_{\cS_n}[\zeta]_{-n}^n\big\|_2 \geq \sqrt{2s}+\sqrt{2u}\right\}\leq e^{-u},
\]
which gives the bound
\be
\prob\left\{\big|{\delta^{(1)}_1}\big|
\leq \sigma\big\|x-\wh\varphi*y\big\|_{n,2} \left(\sqrt{2s}+\sqrt{2\log\left[1/\alpha_1\right]}\right) \right\} \ge 1-\alpha_1.
\ee{i11}

\paragraph{\underline{Step 2$^o$.}} We are to bound the second term of \eqref{I_pi}. To this end, note first that
\bse
{\delta^{(1)}_2} = \sigma \Re \langle [\zeta]_{-n}^n, (I-\Pi_{\cS_n}) [x]_{-n}^n \rangle - \sigma \Re \langle [\zeta]_{-n}^n, (I-\Pi_{\cS_n})[\wh\varphi*x]_{-n}^n\rangle.
\ese
By \eqref{subspace1}, $\left\|(I-\Pi_{\cS_n})[x]_{-n}^n\right\|_{2}\leq \sigma \varkappa$, thus with probability $1-\alpha$,
\be
\left|{\langle [\zeta]_{-n}^n}, (I-\Pi_{\cS_n})[x]_{-n}^n\rangle \right| \le \sigma\varkappa\sqrt{2\log[1/\alpha]}.
\ee{i22-1}
On the other hand, using the notation defined in \eqref{s(psi)}, we have
 $[\wh\varphi*x]_{-n}^n=T(x)[\wh\varphi]_{-m}^m$, so that
\[
{\langle [\zeta]_{-n}^n}, (I-\Pi_{\cS_n})[\wh\varphi*x]_{-n}^n\rangle = {\langle [\zeta]_{-n}^n}, (I-\Pi_{\cS_n})T(x)[\wh\varphi]_{-m}^m\rangle.
\]

Note that $[T(x)]_{\tau} = [\Delta^{\tau} x]^{n}_{-n}$ for the columns of $T(x)$, $\tau \in \Dom_m$. By \eqref{subspace1}, we have

\[
(I-\Pi_{\cS_n})T(x)=T(\varepsilon),
\]
and by \eqref{tr21},
\begin{equation*}
\begin{aligned}
\left\|(I-\Pi_{\cS_n})T(x)\right\|_\F^2
= \left\| T(\varepsilon)\right\|_\F^2
&= \sum_{\tau \in \Dom_m} \left\|\Delta^{\tau}\varepsilon\right\|_{n,2}^2 \nn
&\leq (2m+1)\sigma^2\varkappa^2.
\end{aligned}
\end{equation*}
Due to \eqref{trq1} we conclude that
\[
\left\|T(x)^\H(I-\Pi_{\cS_n})[\zeta]_{-n}^n\right\|_2^2
\le 2(2m+1)\sigma^2\varkappa^2\big(1+\sqrt{\log[1/\alpha]}\big)^2
\]
with probability at least $1-\alpha$. Since
\[\left|\left\langle[\zeta]_{-n}^n, (I-\Pi_{\cS_n})T(x)[\wh\varphi]_{-m}^m\right\rangle\right|\leq \frac{\bar\vrho}{\sqrt{2m+1}} \left\|T(x)^\H(I-\Pi_{\cS_n})[\zeta]_{-n}^n\right\|_{2},
\]
we arrive at the bound with probability $1-\alpha$:
\[
\left|\left\langle[\zeta]_{-n}^n, (I-\Pi_{\cS_n})T(x)[\wh\varphi]_{-m}^m\right\rangle\right|\le\sqrt{2}\sigma\varkappa\bar{\vrho} \big(1+\sqrt{\log[1/\alpha]}\big).
\]
Along with \eqref{i22-1} this results in the bound
\be

\prob\left\{\big|{\delta^{(1)}_2}\big|
\leq \sqrt{2}\sigma^2\varkappa(\bar{\vrho}+1) \big(1+\sqrt{\log\left[1/\min (\alpha_2,\alpha_3)\right]}\big)\right\} \ge 1-\alpha_2-\alpha_3.

\ee{i22}

\paragraph{\underline{Step 3$^o$.}} Let us rewrite ${\delta^{(1)}_3}$ as follows:
\bse
{\delta^{(1)}_3} &=&\sigma^2\Re\langle [\zeta]_{-n}^n, (I-\Pi_{\cS_n})M(\wh\varphi){[\zeta]}_{-m-n}^{m+n} \rangle =
\sigma^2 \Re \sigma^2\langle [\zeta]_{-m-n}^{m+n}, Q M(\wh\varphi){[\zeta]}_{-m-n}^{m+n}\rangle,
\ese
where $M(\wh\varphi)\in \C^{(2n+1)\times (2m+2n+1)}$ is defined by \eqref{M(phi)}, and $Q\in \C^{(2m+2n+1)\times (2n+1)}$ is given by
\begin{equation*}

Q=
\begin{bmatrix}
O_{m,2n+1} \\
I - \Pi_{\cS_n} \\
O_{m,2n+1}
\end{bmatrix}.

\end{equation*}
(Hereafter we denote $O_{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,
\begin{equation}
\label{maxR}
\begin{aligned}
{\delta^{(1)}_3}
&=\frac{\sigma^2}{2}({[\zeta]}_{-m-n}^{m+n})^\H(\underbrace{Q^{\vphantom{*}}M(\wh\varphi)+M(\wh\varphi)^\H Q^\H}_{K_{1}(\wh\varphi)}) [\zeta]_{-m-n}^{m+n}\\
&\leq\frac{\sigma^2\bar\vrho}{2\sqrt{2m+1}}\max\limits_{\scriptsize\begin{array}{c} u \in \C_m(\Z),\nn \|u\|^\F_{m,1}\leq 1\end{array}} (\zeta_{-m}^{n})^\H K_{1}(u) [\zeta]_{-m-n}^{m+n}\\
&=\frac{\sigma^2\bar\vrho}{\sqrt{2m+1}}\,\,\max\limits_{\tiny{j \in \Dom_m}}\,\,\max\limits_{\theta \in [0,2\pi]} \half ([\zeta]_{-m-n}^{m+n})^\H K_{1}(e^{i\theta} u^j) [\zeta]_{-m-n}^{m+n},

\end{aligned}
\end{equation}
where $u^j \in \C_m(\Z)$, and $[u^j]_{-m}^m = F_m^{\H} \text{e}^j$, $\text{e}^j$ being the discrete Dirac pulse centered at $j \in \Z$.
Indeed, $([\zeta]_{-m-n}^{m+n})^\H K_{1}(u) [\zeta]_{-m-n}^{m+n}$ is clearly a convex function of the argument $u$ as a linear function of $[\Re(u); \Im(u)]$; as such, it attains its maximum over the set
\begin{align}\label{eq:hyperoct}
\mathcal{B}_{m,1} = \{u \in \C_m(\Z): \|u\|^\F_{m,1} \le 1\}
\end{align}
at one of the extremal points~$e^{i\theta} u^j$, $\theta \in [0,2\pi]$, of this set.
It can be directly verified that
\[
K_1(e^{\imath\theta}u) = K_1(u)\cos\theta  + K_2(u)\sin\theta,
\]
where the Hermitian matrix $K_2(u)$ is given by
\begin{align*}
K_2(u) = i \left(Q^{\vphantom{*}}M(u) - M(u)^\H Q^\H \right).
\end{align*}
Denoting $q^j_l(\zeta) = \half([\zeta]_{-m-n}^{m+n})^\H K_l(u^j) [\zeta]_{-m-n}^{m+n}$ for $l=1,2$, we have
\begin{equation}
\label{eq:max_complex_to_real}
\begin{aligned}
\max\limits_{\theta \in [0,2\pi]} \half ([\zeta]_{-m-n}^{m+n})^\H K_{1}(e^{\imath\theta} u^j) [\zeta]_{-m-n}^{m+n}
&= \max\limits_{\theta \in [0,2\pi]} q^j_1(\zeta)\cos\theta   + q^j_2(\zeta)\sin\theta \\
&=\sqrt{|q_1^j(\zeta)|^2 + |q_2^j(\zeta)|^2} \\
&\le \sqrt{2}\max (|q_1^j(\zeta)|, |q_2^j(\zeta)|).
\end{aligned}
\end{equation}
By simple algebra and using \eqref{tr22}, we get for $l=1,2$:
\begin{align*}

\Tr [K_{l}(u^j)^2]
&\leq

4\Tr[M(u^j)M(u^j)^\H] \\
&= 4(2n+1)\|u^j\|^2_{m,2} \\
&\leq 4(2n+1).
\end{align*}
Now let us bound  $\Tr[K_{l}(u)]$, $l=1,2$, on the set , $\mathcal{B}_{m,1}$ cf.~\eqref{eq:hyperoct}.
One can verify that for the circulant matrix $C(u)$, cf. \eqref{C(phi)}, it holds:
\bse
QM(u) = {R} C(u),
\ese
where $R = Q^{\vphantom{H}}Q^\H$ is an $(2m+2n+1)\times (2m+2n+1)$ projection matrix of rank $s$ defined by
\begin{align*}
R = \left[
\begin{array}{lll}
O_{m,m} & O_{m,n+1} & O_{m,m}\\
O_{n+1,m} & I-\Pi_{\mathcal{S}_n} & O_{n+1,m} \\
O_{m,m} & O_{m,n+1} & O_{m,m}.
\end{array}
\right]
\end{align*}
Hence, denoting $\|\cdot\|_\op$ and $\|\cdot\|_\nuc$ the operator and nuclear matrix norms, we can bound $\Tr[K_{l}(u)]$, $l=1,2$, as follows:
\begin{align}
|\Tr[K_{l}(u)]|
&\le 2\big|\Tr[R C(u)]\big| \nn
&\le 2\|R\|_\op  \left\|C(u)\right\|_\nuc \nn
&\le 2\|C(u)\|_\nuc \nn
&= 2\sqrt{2m+2n+1}\|\tilde u\|^\F_{m+n, 1},
\label{eq:for-zero-padding}
\end{align}

where in the last transition we used the Fourier diagonalization property~\eqref{eq:circ_diag}.
Recall that $u \in \C_m(\Z)$, hence $F_{m+n}[u]$ is the Discrete Fourier transform of the \textit{zero-padded filter}
\[
\tilde u = [0; ...; 0; [u]_{-m}^m; 0; ... ; 0] \in \C^{2m+2n+1}.
\]
The following lemma, interesting in its own right, controls the inflation of the $\ell_1$-norm of the DFT of a filter after zero padding.
The proof, presented later on, relies to the fact that the normalized $\ell_1$-norm of the Dirichlet kernel of order $N$ grows not faster than $\log N$.

\vspace{0.4cm}

\fbox{
\begin{minipage}{0.9\textwidth}
\begin{lemma}[{\bf $\ell_1$-norm of the DFT after zero-padding}]
\label{lemma:zero_padding}
For any $u \in \C_m(\Z)$, one has

\begin{equation*}
\|u\|^\F_{m+n,1} \le \|u\|^\F_{m,1} \sqrt{1 + \kappa^2_{m,n}} [\log(m+n+1)+3].
\end{equation*}
\end{lemma}
\end{minipage}
}

\vspace{0.4cm}

Combining this lemma with~\eqref{eq:for-zero-padding} we arrive at
\[
\left|\Tr[K_{l}(u^j)]\right| \le 2 \sqrt{2m+1}(\kappa_{m,n}^2 + 1)  (\log[2m+2n+1]+3), \quad l=1,2.
\]
By \eqref{trq2} we conclude that for any fixed pair $(l,j) \in \{1,2\} \times \Dom_m$, with probability $\ge 1-\alpha$,
\[
\big|q^j_l(\zeta)\big| \leq \left|\Tr[K_{l}(u^j)]\right| +\left\|K_{l}(u^j)\right\|_\F \big(1 + \sqrt{\log[2/\alpha]}\big)^2.
\]
With $\alpha_0 = 2(2m+1)\alpha$,  by the union bound together with~\eqref{maxR}~and~\eqref{eq:max_complex_to_real} we get
\begin{equation}
\label{i23-2}
\begin{aligned}
&\Prob\left\{{\delta^{(1)}_3}
\leq 2\sqrt{2}\sigma^2\bar{\vrho}\left[ (\kappa_{m,n}^2+1)(\log[2m+2n+1]+3)+\kappa_{m,n}\big(1+\sqrt{\log\left[{4(2m+1)}/{\alpha_0}\right]}\big)^2\right]\right\} \\
&\ge 1-\alpha_0.
\end{aligned}
\end{equation}

\paragraph{\underline{Step 4$^o$.}} Bounding ${\delta^{(2)}}$ is relatively easy since $\varphi^{o}$ does not depend on the noise. 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 $\ge 1-\alpha$,
\be
\Re\langle\zeta,x-\varphi^{o}*x\rangle_n\leq\sqrt{2\log[1/\alpha]}  \|x-\varphi^{o}*x\|_{n,2}.
\ee{simple0}
On the other hand, defining
\[
\vrho = \sqrt{2m+1} \|\vphi^o\|_{m,1}^\F,
\]
we have
\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} \big(1+\sqrt{\log [1/\alpha]}\big)
\end{align}
with probability $1-\alpha$. Indeed, one has
\[
\|\varphi^{o}*\zeta\|^2_{n,2}=\left\|M(\varphi^{o})[\zeta]_{-m-n}^{m+n} \right\|_2^2,
\]
where for $M(\varphi^{o})$ by $\eqref{tr22}$ we have
\begin{equation}
\label{eq:trmm}
\begin{aligned}
\left\|M(\varphi^{o})\right\|_\F^2
= (2n+1)\|\varphi^{o}\|_{m,2}^2
\leq\kappa_{m,n}^2\varrho^2.
\end{aligned}
\end{equation}
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\big(1+\sqrt{\log[1/\alpha]}\big)^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$,
\begin{equation}
\begin{aligned}
&\Re\langle\zeta,x-\varphi^{o}*x\rangle_n \\
&\;\leq \sqrt{2\log \left[1/\min(\alpha_4,\alpha_5)\right]}
\left[\|x-\varphi^{o}*y\|_{n,2}+\sqrt{2}\sigma\varrho\kappa_{m,n} \big(1+\sqrt{\log[1/\min(\alpha_4,\alpha_5)]}\big)\right]\\
&\;\leq \|x-\varphi^{o}*y\|_{n,2}\sqrt{2\log\left[1/\min(\alpha_4,\alpha_5)\right]}+2\sigma\varrho \kappa_{m,n}\big(1+\sqrt{\log \left[1/\min(\alpha_4,\alpha_5)\right]}\big)^2.
\end{aligned}
\label{simple2}
\end{equation}
Now, the (indefinite) quadratic form
\begin{align*}
&\Re\langle\zeta,\varphi^{o}*\zeta\rangle_n=\half ([\zeta]_{-m-n}^{m+n})^\H{K_0(\varphi^{o})}[\zeta]_{-m-n}^{m+n},
\end{align*}
where
\[
K_0(\varphi^{o}) =
\begin{bmatrix}
O_{m,2m+2n+1} \\
M(\varphi^{o})\\
O_{m,2m+2n+1}
\end{bmatrix}+
\begin{bmatrix}
O_{m,2m+2n+1} \\
M(\varphi^{o})\\
O_{m,2m+2n+1}
\end{bmatrix}^\H,
\]

whence (cf. {\bf Step 3$^o$})
\begin{align*}
|\Tr [{K_0(\varphi^{o})}]|
&\le 2(2n+1)\left|\varphi^{o}_0\right|

\end{align*}
Let us bound $\left|\varphi^{o}_0\right|$.
Let~$e^{0}$ be the discrete centered Dirac vector in $\R^{2m+1}$, and note that $\|F_m [{e}^0]\|_{\infty} = 1/\sqrt{2m+1}$.
Then,
\begin{align*}
\left|\varphi^{o}_m\right|
= |\langle [\varphi^{o}]_{-m}^m, {e}^0 \rangle|
\le \|\varphi^{o}\|^\F_{m,1} \|F_m [{e}^0]\|_{\infty}
\le \frac{\vrho}{2m+1},
\end{align*}
whence $|\Tr[{K_0(\varphi^{o})}]| \leq 2\kappa_{m,n}^2\vrho$.

On the other hand, 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 by \eqref{trq2},
\begin{equation}
\label{i112}
\Prob\left\{-\Re \langle\zeta,\varphi^{o}*\zeta\rangle_n \leq 2\kappa_{m,n}^2\varrho+2\kappa_{m,n}\varrho \big(1+\sqrt{2\log\left[1/\alpha_6\right]}\big)^2 \right\} \ge 1-\alpha_6.
\end{equation}

\paragraph{\underline{Step 5$^o$.}}
Let us combine the bounds obtained in the previous steps with initial bound~$\eqref{first0}$. For any $\alpha \in (0,1]$, putting $\alpha_i = \alpha/4$ for $i = 0, 1, 6$, and $\alpha_j = \alpha/16$, $2 \le j \le 5$, by the union bound we get that with probability $\ge 1-\alpha$,
\begin{eqnarray}
\|x-\wh\varphi*y\|_{n,2}^2
&\leq& \|x-\varphi^{o}*y\|_{n,2}^2+2{\delta^{(2)}}-2{\delta^{(1)}}\nn
\mbox{[by \eqref{simple2}]}&\leq& \|x-\varphi^{o}*y\|_{n,2}^2+2\sigma\|x-\varphi^{o}*y\|_{n,2}\sqrt{2\log[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\log[16/\alpha]}\big)^2\Big]

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

\nn
\mbox{[by \eqref{i22}]}
&&+ \, 2\sqrt{2}\sigma^2(\bar{\vrho}+1)\big(1+\sqrt{\log[16/\alpha]}\big)\varkappa

\nn
\mbox{[by \eqref{i23-2}]}
&&+ \, 4\sqrt{2}\sigma^2\bar{\vrho} \Big[(\kappa_{m,n}^2+1)(\log[2m+2n+1]+3) +\kappa_{m,n}\left(1+\sqrt{\log\left[{16(m+1)}/{\alpha}\right]}\right)^2\Big] \nn
\label{eq:l2con-long}
\end{eqnarray}
Now, denote $c_\alpha := \sqrt{2\log[16/\alpha]}$ and let
\begin{align}
u(\alpha) &= 2\big( \sqrt{2}+c_\alpha\big),\label{eq:part-u}\\
v_1(\alpha) &= 4\left[ \kappa_{m,n}^2+2\kappa_{m,n}\left(1+c_\alpha\right)^2\right],\label{eq:part-v1}\\
v_2(\alpha )&= 4\sqrt{2} \Big[ (\kappa_{m,n}^2+1)(\log[2m+2n+1]+3) +\kappa_{m,n}\left(1+\sqrt{\log\left[{16(2m+1)}/{\alpha}\right]}\right)^2\Big].
\label{eq:part-v2}
\end{align}
In this notation, \eqref{eq:l2con-long} becomes
\begin{align}
\|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)\nn
&+ u(\alpha)\sigma^2(\bar\varrho+1)\varkappa + (v_1(\alpha)+v_2(\alpha)) \sigma^2\bar\varrho,
\label{eq:uv-compact}
\end{align}
which implies, by completing the squares, that
\begin{align*}
\|x-\wh\varphi*y\|_{n,2} \le \|x-\varphi^{o}*y\|_{n,2}
+2\sigma(\sqrt{2s}+c_\alpha) + \sigma\sqrt{u(\alpha)(\bar\varrho+1)\varkappa + (v_1(\alpha)+v_2(\alpha))\bar\varrho}.
\end{align*}
Finally, let us simplify this bound. Note that
\begin{equation}\label{eq:part-u-bound}
u(\alpha) \le 4c_\alpha,
\end{equation}
while on the other hand,
\begin{align}
\label{eq:final_stoch_term}
v_1(\alpha) + v_2(\alpha)
&\le 4\sqrt{2} (\kappa_{m,n}^2+1)(\log[2m+2n+1]+4) + 4.5(4\sqrt{2}+8)\kappa_{m,n}\log\left[16(2m+1)/\alpha\right]\nn
&\le 8\left(1 + 4\kappa_{m,n}\right)^2 \log\left[110(m+n+1)/\alpha\right].
\end{align}
Hence we arrive at
\begin{equation}\label{eq:l2con-mn-stat}
\|x - \widehat{\varphi}*y \|_{n,2} \le \|x-\varphi^{o}*y\|_{n,2} + 2 \sigma \left( \sqrt{\bar\varrho V_\alpha} + \sqrt{(\bar{\varrho}+1)c_\alpha \varkappa} + \sqrt{2s}+ c_\alpha \right),
\end{equation}
where we introduced
\begin{equation}
\label{eq:V}
V_\alpha := 2\left(1 + 4\kappa_{m,n}\right)^2\log \left[{110(m+n+1)}/{\alpha}\right].
\end{equation}
The bound~\eqref{eq:th1} of the theorem follows from~\eqref{eq:l2con-mn-stat} after some straightforward simplifications.
\qed

\subsection{Proof of Theorem \ref{th:l2pen++}}

Denote~$\wh\vrho = \sqrt{2m+1}\|\wh\vphi\|_{m,1}^\F$, and let~$\vrho = \sqrt{2m+1}\|\vphi^o\|_{m,1}^\F$ for a feasible solution~$\vphi^o$ to~\eqref{opt:l2pen++}.
In the rest, we will use the same notation as in the previous proof.

Due to feasibility of~$\varphi^{o}$, we have the following counterpart of~\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 {\bf Steps~1$^o$--4$^o$} of the previous proof, we obtain a counterpart of~\eqref{eq:uv-compact}:
\begin{equation}
\begin{array}{lll}
\|x-\wh\varphi*y\|_{n,2}^2 + \lambda^2\sigma^2\widehat\varrho^2
\leq
&\|x-\varphi^{o}*y\|_{n,2}^2 + 2\sigma (\|x-\varphi^{o}*y\|_{n,2} + \|x-\wh\varphi*y\|_{n,2})(\sqrt{2s}+c_\alpha)\\
&\; + u(\alpha)\sigma^2\varkappa+v_1(\alpha)\sigma^2\varrho + \lambda^2\sigma^2\varrho^2 + \left[u(\alpha)\varkappa+v_2(\alpha)\right]\sigma^2\wh\varrho, \label{eq:l23compete}
\end{array}
\end{equation}
with~$u(\alpha)$, $v_1(\alpha)$, and~$v_2(\alpha)$ given by~\eqref{eq:part-u}--\eqref{eq:part-v2}.
We now consider two cases as follows.

\paragraph{{\bf \underline{Case (a).}}}
First, assume that
\begin{equation}
\begin{array}{rclcl}
\|x-\wh\varphi*y\|_{n,2}^2 &\leq& \|x-\varphi^{o}*y\|_{n,2}^2 &+& 2\sigma (\|x-\varphi^{o}*y\|_{n,2} + \|x-\wh\varphi*y\|_{n,2}) (\sqrt{2s}+c_\alpha) \\
&&&+& u(\alpha)\sigma^2\varkappa+v_1(\alpha)\sigma^2\varrho + \lambda^2\sigma^2\varrho^2.
\end{array}
\label{eq:assume1}
\end{equation}
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}

\paragraph{{\bf \underline{Case (b).}}}
Suppose, on the contrary, that~\eqref{eq:assume1} does not hold, we then conclude from~\eqref{eq:l23compete} that

\[

\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
\[
{\|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),
\]
which is also satisfied in {\bf {Case (a)}} due to~\eqref{eq:1stcase}.\\

Finally, 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 that
\[

\begin{aligned}
\|x - \widehat{\varphi}*y \|_{n,2}
\le \|x-\varphi^{o}*y\|_{n,2} &+\sigma(\lambda \varrho + 4\lambda^{-1}(c_\alpha \varkappa + V_\alpha)) + 2 \sigma \left(\sqrt{\varrho W_\alpha} + \sqrt{c_\alpha \varkappa} + \sqrt{2s} +  c_\alpha \right),
\end{aligned}
\]
with $V_\alpha$ is given by~\eqref{eq:V}, and
$
W_\alpha = (1+\kappa_{m,n})^2 (1+c_\alpha)^2.
$
The bound~\eqref{eq:l2pen++} of the theorem follows by simplifying the above bound in a straightforward manner.
\qed

\subsection*{Proof of Lemma~\ref{lemma:zero_padding}}
\label{proof:zero_padding}
Let us prove that the bound of the theorem,
\begin{equation*}
\|u\|^\F_{m+n,1} \le \sqrt{1 + \kappa^2_{m,n}}  [\log(m+n+1)+3],
\end{equation*}
holds on the unit ball
\[
\mathcal{B}_{m,1} = \{u \in \C_m(\Z): \|u\|^\F_{m,1} \le 1\};
\]
then, the statement will follow by the homogeneity of the norm $\|\cdot\|^\F_{m+n,1}$. We assume that $n \ge 1$ (otherwise the statement of the lemma is trivial).

First of all, function $\|u\|^\F_{m+n,1}$ is convex on $\cB_{m,1}$, so its maximum over this set is attained at one the extreme points $u^j \in \C_m(\Z)$ which are given by
$F_m [u^j]_{-m}^m = e^{i \theta} {e}^j$ where ${e}^j$ is the discrete Dirac pulse centered at $j \in \Z$, and $\theta \in [0,2\pi]$.
Note that
\[
u^j_\tau = \frac{1}{\sqrt{2m+1}} \exp\left[i\left(\theta+\frac{2\pi \tau j}{2m+1}\right)\right],
\]
hence, for~$\gamma_{m,n} := \sqrt{(2m+2n+1)(2m+1)}$ we obtain
\begin{align*}
\big\|u^j\big\|^\F_{m+n,1}
&= \frac{1}{\gamma_{m,n}} \sum_{k \in \Dom_{m+n}} \left| \sum_{\tau \in \Dom_m} \exp\left[2\pi i \tau\left(\frac{j}{2m+1} - \frac{k}{2m+2n+1} \right)\right] \right| \\

&= \frac{1}{\gamma_{m,n}} \sum_{k \in \Dom_{m+n}} \left| \textup{DirKer}_m\left(\omega_{jk}\right)\right|, \quad \text{where} \quad \omega_{jk} := 2\pi \left(\frac{j}{2m+1} - \frac{k}{2m+2n+1} \right),
\end{align*}
where~$\textup{DirKer}_m(\cdot)$ is the Dirichlet kernel of order $m$:
\begin{equation*}
\textup{DirKer}_m(\omega) := \left\{
\begin{aligned}
&\frac{\sin \left({(2m+1)\omega}/{2}\right)}{\sin\left({\omega}/{2}\right)}, & \quad \omega \ne 2\pi l,\\
&2m+1, & \quad \omega = 2\pi l.
\end{aligned}\right.
\end{equation*}
Hence,
\begin{align}\label{eq:dirichlet_sum}
\gamma_{m,n} \|u^j\|^\F_{m+n,1} \le \max_{\theta \in [0,2\pi]} \left\{  \Sigma_{m,n}(\theta) := \sum_{k \in \Dom_{m+n}} \left| \textup{DirKer}_m\left(\frac{2\pi k}{2m+2n+1}  + \theta \right)\right| \right\}.
\end{align}

For any $\theta \in [0,2\pi]$, the summation in \eqref{eq:dirichlet_sum} is over the $\theta$-shifted regular $(2m+2n+1)$-grid on the unit circle.
The contribution to the sum $\Sigma_{m,n}(\theta)$ of the two closest to $x = 1$ points of this grid is at most $2(2m+1)$.
On the other hand, for the remaining points, we can use the bound
\[
\textup{DirKer}_m(\omega) \le \frac{1}{|\sin(\omega/2)|} \le \frac{\pi}{\min(\omega, 2\pi-\omega)}.
\]
Finally, note that $f(\omega) = \frac{\pi}{\omega}$ decreases on $[\frac{2\pi}{2m+2n+1}, \pi]$ (recall that $n \ge 1$).

These considerations result in the following estimate:
\begin{align*}
\Sigma_{m,n}(\theta)
&\le 2\left(2m+1 + \sum_{k=1}^{m+n+1} \frac{2m+2n+1}{2k}\right).
\end{align*}
Using the bound $H_n \le \log n + 1$ for harmonic numbers, we arrive at
\[
\Sigma_{m,n}(\theta) \le 2(2m+1) + (2m+2n+1) \left[\log(m+n+1)+1\right] \le (2m+2n+1) \left[\log(m+n+1)+3\right],
\]
and the lemma is proved. \qed

config: arxiv


TITLE: Is there a way to visualize, like a picture in mind, the $n$-th derivative?
QUESTION [0 upvotes]: Is there a way to visualize (like a picture in mind) the $n$-th derivative ?
For $n=1$ is the tangent line and we can visualize it quite well.
More abstractly is it possible to see the geometric significance of the $n$-th derivative for all $n$?
For example can the human eye distinguish the graph of a $C^4$ function from a $C^5$ function ?

REPLY [1 votes]: The tangent line is the first order Taylor polynomial. The n:th derivative can be "visualized" in the same sense as the n:th order Taylor polynomial. This will only give a localized significance to the derivative.
There are many other important properties of derivatives. For instance when solving differential equations the exponential functions are very important since they are "their own" derivatives. Then splitting the function into sums of exponentials may help solve the problem.


TITLE: $11$ matches are to be played,Each having $3$ distinct outcome,
QUESTION [0 upvotes]: $11$ matches are to be played,Each having $3$ distinct outcome, in how many ways one can predict the outcomes such that $6$ outcomes turn out to be correct?
My thought
$11C_{6}\times 3^5$
am I right?

REPLY [1 votes]: Hint There are $\binom{11}{6}$ different combinations of the $6$ different outcomes which can be correct.
Now, you only have $1$ for each of the $6$ matches, and you have $2$ different choices for the $5$ matches which need to be wrong (not 3).
Thus, there are exactly $\binom{11}{6}2^5$ different ways of picking exactly 6 outcomes.
If you need at least $6$ outcomes, calculate exactly 6,7,8,9,10 and exactly 11, otherwise you double count some combinations.