text:
\section{Introduction}
  \input{introduction_WH17.tex}

  \section{Blind Deconvolution from Additional Autocorrelations via SDP}
  \input{blinddeconvolutionsdp.tex}

  \section{Stability Analysis of the SDP}
  \input{stabilitySDP_neu}

  \section{Conclusion}
  \input{conclusion_WH17.tex}

  \section*{References}
  \printbibliography[heading=bibintoc]

  \appendices

  \section{Sylvester Matrix}\label{app:sylvester}%
   \input{sylvesterrank}
   \input{traceinequalities}
\end{document}

\section*{Acknowledgement}

The authors would like to thank Ahmed Douik, Richard Kueng and Peter Jung for many helpful discussions.  The work of
Philipp Walk was supported by the German Research Foundation (DFG) under the grant WA 3390/1 and the one of Babak
Hassibi was supported in part by the National Science Foundation under grants CNS-0932428, CCF-1018927, CCF-1423663 and
CCF-1409204, by a grant from Qualcomm Inc., by NASA's Jet Propulsion Laboratory through the President and Director's
Fund, by King Abdulaziz University, and by King Abdullah University of Science and Technology.

\subsection{Notation}

We will use for $\ensuremath{\mathbb{F}} $ either the real ${\ensuremath{\mathbb R}}$ or complex ${\ensuremath{\mathbb C}}$ field. Although, we will formulate most of the results in the
complex case we derive the stability constant only for the real case due to space of interest and postpone the
complex case to an upcoming  work.  For an integer $N$, we will denote the first $N$ non-negative integers by
$[N]:=\{0,1,\dots,N-1\}$.  Small letters denote scalars in $\K$, bold small letters vectors in $\K^N$  and bold capital
letters denote $N\times M$ matrices in $\K^{N\times M}$. By ${\ensuremath{\mathbf I}}_N$ we denote the $N\times N$ identity matrix and by
${\ensuremath{\mathbb 0}}_N$ the all zero matrix. We denote by $\cc{x}=\Re x -i\Im x$ the complex-conjugate of $x\in{\ensuremath{\mathbb C}}$ and by
$(\cdot)^*=\cc{(\cdot)^T}$ the complex-transpose of a vector or matrix. For a vector ${\ensuremath{\mathbf x}}\in\K^N$ we will denote its
time-reversal (reflection) by ${\ensuremath{\mathbf x}}^-$ given component-wise for $k\in[N]$ by $x_k=x_{N-(k-1)}$.  The linear spaces are
equipped with the scalar product, given by
\begin{align} \begin{split} \skprod{{\ensuremath{\mathbf x}}}{{\ensuremath{\mathbf y}}}&={\ensuremath{\mathbf y}}^*{\ensuremath{\mathbf x}} = \sum_{k} x_k \cc{y_k} \quad\text{for}\quad {\ensuremath{\mathbf x}},{\ensuremath{\mathbf y}}\in\K^N\\
    \skprod{{\ensuremath{\mathbf X}}}{{\ensuremath{\mathbf Y}}}&=\tr({{\ensuremath{\mathbf Y}}}^*{\ensuremath{\mathbf X}})=\sum_{k}({\ensuremath{\mathbf Y}}^*{\ensuremath{\mathbf X}})_{k,k}  \quad\text{for}\quad {\ensuremath{\mathbf x}},{\ensuremath{\mathbf y}}\in\K^N.
  \end{split}
\end{align}
We denote by $\ensuremath{\lambda}_k({\ensuremath{\mathbf A}})$ the $k$th eigenvalue of a Hermitian matrix ${\ensuremath{\mathbf A}}\in\K^{N\times N}$ which we will order by
increasing values, i.e. $\ensuremath{\lambda}_1({\ensuremath{\mathbf A}})\leq \ensuremath{\lambda}_2({\ensuremath{\mathbf A}})\leq\dots\leq \ensuremath{\lambda}_N({\ensuremath{\mathbf A}})$. Moreover, for an arbitrary matrix
${\ensuremath{\mathbf A}}\in \K^{N\times M}$ we will denote the singular values by $\ensuremath{\sigma}_k({\ensuremath{\mathbf A}})=\sqrt{\ensuremath{\lambda}_k({\ensuremath{\mathbf A}}\vA^{*})}\geq 0$ for
$k\in\{1,\dots,\min\{N,M\}\}$, see \cite{HJ90}.  We will use the $\ell^p-$norms for $p\in[1,\infty)$ for ${\ensuremath{\mathbf a}}\in\K^N$
  and ${\ensuremath{\mathbf A}}\in\K^{N\times M}$
\begin{align}
  \Norm{{\ensuremath{\mathbf a}}}_p\!=\!\Big(\sum_k |a_k|^p\Big)^{1/p} \quad\!,\quad \sNorm{{\ensuremath{\mathbf A}}}_p \!=\!\Big(\sum_k
  \ensuremath{\sigma}_k^p({\ensuremath{\mathbf A}})\Big)^{1/p},
\end{align}
We use for the Hilbert norms $\Norm{{\ensuremath{\mathbf a}}}_2\!=\!\Norm{{\ensuremath{\mathbf a}}}$ resp. $\sNorm{{\ensuremath{\mathbf A}}}_2\!=\!\sNorm{{\ensuremath{\mathbf A}}}$ and define for
$p=\infty$
\begin{align}
  \Norm{{\ensuremath{\mathbf a}}}_{\infty}=\max_k |a_k|\ ,\quad \sNorm{{\ensuremath{\mathbf A}}}_{\infty}= \max_k
  \ensuremath{\sigma}_k=\ensuremath{\sigma}_{\max\{N,M\}}\label{eq:inftynorm}.
\end{align}

\subsection{Local Stability on the Tangent Space}

The crucial part for the proof of the injectivity and for the stability is the explicit construction of a \emph{dual
certificate} in \cite{JH16,WJPH17}. The dual certificate is given by a linear combination of the measurement matrices
\eqref{eq:4maskmeasurements}  depending on the observed measurements \eqref{eq:3Nb} usually in a complex algebraic
manner. Fortunately, for the correlation type map ${\ensuremath{\mathcal{A}}}$ the measurements are linked to the measurement matrices by
\emph{banded Toeplitz matrices} generated by unknown vectors ${\ensuremath{\mathbf x}}_1$ and ${\ensuremath{\mathbf x}}_2$. Morepreciselcy, the linear convolution
between ${\ensuremath{\mathbf x}}_i\in{\ensuremath{\mathbb C}}^{\ensuremath{{N_i}}},{\ensuremath{\mathbf x}}_j\in{\ensuremath{\mathbb C}}^{\ensuremath{{N_j}}}$  for any $i,j\in\{1,2\}$ is given by applying the $\ensuremath{{N_{ij}}}\times N_j$ banded
Toeplitz matrix ($\ensuremath{{N_{ij}}}=\ensuremath{{N_i}}+\ensuremath{{N_j}}$), where for the correlation we need also the $\ensuremath{{N_j}}\times\ensuremath{{N_j}}$ time-reversal matrix
\begin{align}
  \ensuremath{\mathbf T}_{j,{\ensuremath{\mathbf x}}_i} \!\!=\!\sum_{k=0}^{\ensuremath{{N_i}}-1} \!\!x_{i,k} \ensuremath{\mathbf T}^k_{\ensuremath{{N_{ij}}}\!-\!1} {\mathbf \Pi}_{\ensuremath{{N_{ij}}}\!-\!1,\ensuremath{{N_j}}},
\quad
\setlength\arraycolsep{2.2pt}
\ensuremath{\mathbf R}_{\ensuremath{{N_j}}}\!=\!\begin{pmatrix}
    0 &\!\!\cdots \!\!  & 1\\[-0.5em]
  \vdots &  \!\diagup\!\!  & \vdots \\
   1 &   \!\!\cdots \! \!&0
  \end{pmatrix}\label{eq:Tform}
\end{align}
where $\ensuremath{\mathbf T}_N$ denotes the elementary Toeplitz matrix \eqref{eq:elementtoeplitz}.
Hence the matrix form of the convolution and correlation is given by
\begin{align}
  {\ensuremath{\mathbf x}}_i*{\ensuremath{\mathbf x}}_j&=\ensuremath{\mathbf T}_{j,{\ensuremath{\mathbf x}}_i}{\ensuremath{\mathbf x}}_j\label{eq:Txij}\\
  {\ensuremath{\mathbf x}}_i*\xbar{{\ensuremath{\mathbf x}}_j \rule{-1.2ex}{1.6ex}^{_{\scriptstyle -}}}&=\ensuremath{\mathbf T}_{j,{\ensuremath{\mathbf x}}_i}\ensuremath{\mathbf R}_{\ensuremath{{N_j}}}\cc{{\ensuremath{\mathbf x}}_j}.\label{eq:Hxij}
\end{align}
Concatenating two such Toeplitz matrices defines the $N\times N$ \emph{Sylvester matrix}
\begin{align}
  \ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf x}}_2^0,-{\ensuremath{\mathbf x}}_1^0}
  \setlength\arraycolsep{2pt}
  \!=\!\begin{pmatrix}\ensuremath{\mathbf T}_{1,{\ensuremath{\mathbf x}}_2^0} & \ensuremath{\mathbf T}_{2,-{\ensuremath{\mathbf x}}_1^0}\end{pmatrix}
  \setlength\arraycolsep{2pt}
  \!=\!\begin{pmatrix}\ensuremath{\mathbf T}_{1,{\ensuremath{\mathbf x}}_2} &
    \ensuremath{\mathbf T}_{2,-{\ensuremath{\mathbf x}}_1}\\ {\ensuremath{\mathbf 0}}^T & {\ensuremath{\mathbf 0}}^T\end{pmatrix}\label{eq:sylvesterx}
\end{align}
where we used the notation
\begin{align}
  {\ensuremath{\mathbf x}}_i^0=\begin{pmatrix}{\ensuremath{\mathbf x}}_i\\ 0\end{pmatrix}\in{\ensuremath{\mathbb C}}^{\ensuremath{{N_i}}+1}\label{eq:xaddzero}.
\end{align}
This allows us to represent any convolution difference
for ${\ensuremath{\mathbf y}}_1\in{\ensuremath{\mathbb C}}^{{{L}_1}}$ and ${\ensuremath{\mathbf y}}_2\in{\ensuremath{\mathbb C}}^{{{L}_2}}$ as a matrix equation
\begin{align}
  \ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf x}}}{\ensuremath{\mathbf y}}=  \ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf x}}_2^0,-{\ensuremath{\mathbf x}}_1^0} \begin{pmatrix}{\ensuremath{\mathbf y}}_1\\ {\ensuremath{\mathbf y}}_2\end{pmatrix}
  &= \begin{pmatrix} {\ensuremath{\mathbf x}}_2*{\ensuremath{\mathbf y}}_1 -{\ensuremath{\mathbf x}}_1*{\ensuremath{\mathbf y}}_2 \\ 0 \end{pmatrix} \label{eq:convdiff}.
\end{align}
We will show in \appref{sec:dualcertificate}, that the dual certificate for each ground truth signals
${\ensuremath{\mathbf x}}_1\in{\ensuremath{\mathbb C}}^{{{L}_1}}$ and ${\ensuremath{\mathbf x}}_2\in{\ensuremath{\mathbb C}}^{{{L}_2}}$ is given by
\begin{align}
  {\ensuremath{\mathbf W}}=\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf x}}_2^0,-{\ensuremath{\mathbf x}}_1^0}^*\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf x}}_2^{0},-{\ensuremath{\mathbf x}}_1^0}\label{eq:dualcertif}.
\end{align}

The injectivity of the convolution-type map ${\ensuremath{\mathcal{A}}}$ and the stability is then fully determined by the singular value
properties of the Sylvester matrix, see \appref{app:sylvester}.  Therefore we have to extend the dual certificate in
\cite[Lem.3]{WJPH17} (injectivity) to a local stability of ${\ensuremath{\mathcal{A}}}$ on the tangent space
$T_{\ensuremath{\mathbf x}}:=\set{{\ensuremath{\mathbf x}}{\ensuremath{\mathbf y}}^*+{\ensuremath{\mathbf y}}{\ensuremath{\mathbf x}}^*}{{\ensuremath{\mathbf y}}\in{\ensuremath{\mathbb C}}^N}$, i.e., for each ground truth signal ${\ensuremath{\mathbf x}}\in{\ensuremath{\mathbb C}}^N$ we have to show that there
exists some $\ensuremath{\gamma}=\ensuremath{\gamma}({\ensuremath{\mathbf x}}_1,{\ensuremath{\mathbf x}}_2)>0$ such that it holds
\begin{align}
  \Norm{{\ensuremath{\mathcal{A}}}({\ensuremath{\mathbf Y}})} \geq \ensuremath{\gamma} \sNorm{{\ensuremath{\mathbf Y}}}\quad,\quad {\ensuremath{\mathbf Y}}\in T_{{\ensuremath{\mathbf x}}}   \label{eq:localRIPAlin},
\end{align}
see also \cite{CSV12,DH12}.

\begin{remark}
  Note, that each ${{L}_1},{{L}_2}$ specify a different linear map ${\ensuremath{\mathcal{A}}}$ even if ${{L}_1}+{{L}_2}=N=\text{const.}$. Therefore,
  $\ensuremath{\gamma}$ depends on ${{L}_1}$ and ${{L}_2}$  and not only on their sum.  Since $T_{{\ensuremath{\mathbf x}}}$ is a linear space it holds
  ${\ensuremath{\mathbf Y}}-\ensuremath{\tilde{\mathbf{Y}}}\in T_{{\ensuremath{\mathbf x}}}$ for all ${\ensuremath{\mathbf Y}},\ensuremath{\tilde{\mathbf{Y}}}\in T_{{\ensuremath{\mathbf x}}}$.
  %
  Moreover, $T_{{\ensuremath{\mathbf x}}}$ does not include all rank$-1$ differences, i.e., not all rank$-2$ matrices and
  \eqref{eq:localRIPAlin} therefore only obeys a \emph{local stability of ${\ensuremath{\mathcal{A}}}$ for rank$-2$ matrices} around the
  ground truth ${\ensuremath{\mathbf x}}\vx^*$ or a \emph{local rank$-2$ RIP}, which is much less strict condition than a rank$-2$ RIP.  In
  fact, a rank$-2$ RIP for convolutions can not hold since the difference of arbitrary convolutions can vanish. Even to
  control the norm of the convolution can be a challenging task for certain signals \cite{WJP15}.
\end{remark}
Since the norms are absolutely homogeneous and  ${\ensuremath{\mathcal{A}}}, T_{{\ensuremath{\mathbf x}}}$ are linear, we need to show \eqref{eq:localRIPAlin}
only for $\ensuremath{\tilde{\mathbf x}}={\ensuremath{\mathbf x}}/\Norm{{\ensuremath{\mathbf x}}}\in\K^N$
\begin{align}
  T_{\ensuremath{\tilde{\mathbf x}}}:=\set{\ensuremath{\tilde{\mathbf x}}{\ensuremath{\mathbf y}}^*+{\ensuremath{\mathbf y}}\ensuremath{\tilde{\mathbf x}}^*}{{\ensuremath{\mathbf y}}\in\K^N}
\end{align}
for $\K\in\{{\ensuremath{\mathbb C}},{\ensuremath{\mathbb R}}\}$.  Let us assume from here that ${\ensuremath{\mathbf x}}=\ensuremath{\tilde{\mathbf x}}$. In fact, the tangent space $\ensuremath{\mathbf T}_{{\ensuremath{\mathbf x}}}$ of rank two
matrices refers to a sum of two convolutions which is parameterized by two unknown as ${\ensuremath{\mathbf y}}=[{\ensuremath{\mathbf y}}_1,{\ensuremath{\mathbf y}}_2]$ with same
dimensions as ${\ensuremath{\mathbf x}}_1$ and ${\ensuremath{\mathbf x}}_2$. The structure of convolution sums is given by Sylvester matrices. Hence, to exploit
their structure  we need to parameterize the matrices in $T_{{\ensuremath{\mathbf x}}}$ by vectors in $\K^N$. Furthermore, we can easily
represent the Schatten $2-$norm of ${\ensuremath{\mathbf Y}}$ in ${\ensuremath{\mathbf y}}$ as
\begin{align}
  \begin{split}
  \sNorm{{\ensuremath{\mathbf Y}}}^2&=\tr(({\ensuremath{\mathbf x}}{\ensuremath{\mathbf y}}^*+ {\ensuremath{\mathbf y}}{\ensuremath{\mathbf x}}^*)^* ({\ensuremath{\mathbf x}}{\ensuremath{\mathbf y}}^*+{\ensuremath{\mathbf y}}{\ensuremath{\mathbf x}}^*))\\
                & =2\tr({\ensuremath{\mathbf x}}{\ensuremath{\mathbf y}}^*{\ensuremath{\mathbf y}}{\ensuremath{\mathbf x}}^*)+ \tr({\ensuremath{\mathbf y}}{\ensuremath{\mathbf x}}^*{\ensuremath{\mathbf y}}{\ensuremath{\mathbf x}}^*)+\tr({\ensuremath{\mathbf x}}{\ensuremath{\mathbf y}}^*{\ensuremath{\mathbf x}}{\ensuremath{\mathbf y}}^*)\\
                &=2 \Norm{{\ensuremath{\mathbf y}}}^2 + 2\Re\{\skprod{{\ensuremath{\mathbf x}}}{{\ensuremath{\mathbf y}}}^2\}.
  \end{split}
  \label{eq:Ynorm}
\end{align}
Then \eqref{eq:localRIPAlin} is equivalent to
\begin{align}
  \Norm{{\ensuremath{\mathcal{A}}}({\ensuremath{\mathbf x}}{\ensuremath{\mathbf y}}^*\!+\!{\ensuremath{\mathbf y}}{\ensuremath{\mathbf x}}^*)}^2\!\geq\! 2\ensuremath{\gamma}^2 (\Norm{{\ensuremath{\mathbf y}}}^2\!+\!\Re\{\skprod{{\ensuremath{\mathbf x}}}{{\ensuremath{\mathbf y}}}^2\})
  \label{eq:localRIPy}
\end{align}
for all ${\ensuremath{\mathbf y}}\in\K^N$. Unfortunately, for $\K={\ensuremath{\mathbb C}}$ we face two problems: First the left hand side of \eqref{eq:localRIPy}
can not be written as a quadratic form in ${\ensuremath{\mathbf y}}$, due to the alternate complex-conjugation,  and second the right hand
side vanishes for some $\rho\geq 0$ if ${\ensuremath{\mathbf y}}=\pm i \rho{\ensuremath{\mathbf x}}$, since $(\skprod{{\ensuremath{\mathbf x}}}{\pm i\rho{\ensuremath{\mathbf x}}})^2=-\rho^2$. In fact,
$\pm i\rho {\ensuremath{\mathbf x}}$ is a one-dimensional real subspace of ${\ensuremath{\mathbb C}}^N$ which parameterize ${\ensuremath{\mathbf Y}}={\ensuremath{\mathbb 0}}$. Hence, these problems
suggest to reformulate the complex case as a real-valued case. In the interest of space,  we will in this work only
consider the stability analysis for the real case and treat the complex case in a follow up paper.

\section{Real Case}
In the real case the scalar product in \eqref{eq:Ynorm} is always real valued and so its product positive. Hence, the
Schatten $2-$norm of ${\ensuremath{\mathbf Y}}$ is for $\Norm{{\ensuremath{\mathbf y}}}=1$ bounded by Cauchy-Schwarz
\begin{align}
  2\leq\sNorm{{\ensuremath{\mathbf Y}}}^2\leq 4.\label{eq:boundY}
\end{align}
Hence we can lower bound the stability constant in \eqref{eq:localRIPAlin} by a smallest singular value problem
\begin{align}
  \ensuremath{\gamma}^2\geq \frac{1}{4}\min_{\Norm{{\ensuremath{\mathbf y}}}=1} \! \Norm{{\ensuremath{\mathcal{A}}}({\ensuremath{\mathbf x}}{\ensuremath{\mathbf y}}^T\!+\!{\ensuremath{\mathbf y}}{\ensuremath{\mathbf x}}^T)}^2
  =\frac{1}{4}\min_{\Norm{{\ensuremath{\mathbf y}}_{\!-}}=1} \Norm{\ensuremath{\mathbf M}{\ensuremath{\mathbf y}}_-}^2
  \label{eq:stabdef}
\end{align}
where we re parameterized ${\ensuremath{\mathbf y}}$ as ${\ensuremath{\mathbf y}}_-=[{\ensuremath{\mathbf y}}_1 , -{\ensuremath{\mathbf y}}_2^-]$.
Then indeed, there exists a linear mixing map $\ensuremath{\mathbf M}$ such that with \eqref{eq:aijk} and \eqref{eq:Aijtrace}  we get
\begin{align}
  {\ensuremath{\mathcal{A}}}({\ensuremath{\mathbf Y}})&={\ensuremath{\mathcal{A}}}({\ensuremath{\mathbf x}}{\ensuremath{\mathbf y}}^T+{\ensuremath{\mathbf y}}{\ensuremath{\mathbf x}}^T)=
   \begin{pmatrix}
       {\ensuremath{\mathbf x}}_1*{\ensuremath{\mathbf y}}_1^- \!+\! {\ensuremath{\mathbf y}}_1*{\ensuremath{\mathbf x}}_1^-\\
       {\ensuremath{\mathbf x}}_1*{\ensuremath{\mathbf y}}_2^- \!+\! {\ensuremath{\mathbf y}}_1*{\ensuremath{\mathbf x}}_2^-\\
       {\ensuremath{\mathbf x}}_2*{\ensuremath{\mathbf y}}_1^- \!+\! {\ensuremath{\mathbf y}}_2*{\ensuremath{\mathbf x}}_1^-\\
       {\ensuremath{\mathbf x}}_2*{\ensuremath{\mathbf y}}_2^- \!+\! {\ensuremath{\mathbf y}}_2*{\ensuremath{\mathbf x}}_2^-
     \end{pmatrix}\label{eq:AY}\\
  \setlength\arraycolsep{3pt}
&  \overset{\eqref{eq:Txij}}{=}
\begin{pmatrix}
  \ensuremath{\mathbf{J}}_1\ensuremath{\mathbf T}_{1,{{\ensuremath{\mathbf x}}_1 \rule{-1.2ex}{1.6ex}^{_{\scriptscriptstyle -}}}} \!\!    & {\ensuremath{\mathbf 0}} \\
  \ensuremath{\mathbf T}_{1,{{\ensuremath{\mathbf x}}_2 \rule{-1.2ex}{1.6ex}^{_{\scriptscriptstyle -}}}}              &   \ensuremath{\mathbf T}_{2,\minus{\ensuremath{\mathbf x}}_1} \\
  \ensuremath{\mathbf R}_{N\!-\!1}\ensuremath{\mathbf T}_{1,{{\ensuremath{\mathbf x}}_2 \rule{-1.2ex}{1.6ex}^{_{\scriptscriptstyle -}}}} &   \ensuremath{\mathbf R}_{N\!-\!1}\ensuremath{\mathbf T}_{2,\minus{\ensuremath{\mathbf x}}_1} \\
  {\ensuremath{\mathbf 0}}                        & \ensuremath{\mathbf{J}}_2\ensuremath{\mathbf T}_{2,\minus{{\ensuremath{\mathbf x}}_2 \rule{-1.2ex}{1.6ex}^{_{\scriptscriptstyle -}}}} \!\!
\end{pmatrix}\!
  \begin{pmatrix} {\ensuremath{\mathbf y}}_1\\ -{\ensuremath{\mathbf y}}_2^-\end{pmatrix}\!= \!\ensuremath{\mathbf M}{\ensuremath{\mathbf y}}_-\notag
\end{align}
where we used the  time reversal matrix \eqref{eq:Hxij} and a  $(2\ensuremath{{N_i}}-1)\times (2\ensuremath{{N_i}}-1)$ intertwining matrix
\begin{align}
  \ensuremath{\mathbf{J}}_i\!=\!{\ensuremath{\mathbf I}}_{\!2\ensuremath{{N_i}}\!-\!1}\! + \!\ensuremath{\mathbf R}_{\!2\ensuremath{{N_i}}\!-\!1}
  \label{eq:intertwining2}
\end{align}
for which holds $\ensuremath{\mathbf{J}}_i=\ensuremath{\mathbf{J}}_i^T$ and $\ensuremath{\mathbf{J}}_i^2=2\ensuremath{\mathbf{J}}$, since $\ensuremath{\mathbf R}_{2\ensuremath{{N_i}}-1}^T=\ensuremath{\mathbf R}_{2\ensuremath{{N_i}}-1}$ and
$\ensuremath{\mathbf R}_{2\ensuremath{{N_i}}-1}^2={\ensuremath{\mathbf I}}_{2\ensuremath{{N_i}}-1}$. Moreover, we can identify a Sylvester matrix without the zero row as
\begin{align}
  \ensuremath{\tilde{\vS}}_-:=\ensuremath{\tilde{\vS}}_{{\ensuremath{\mathbf x}}_2^{-0},-{\ensuremath{\mathbf x}}_1^0}=\begin{pmatrix} \ensuremath{\mathbf T}_{1,{\ensuremath{\mathbf x}}_2^-} & \ensuremath{\mathbf T}_{2,-{\ensuremath{\mathbf x}}_1} \end{pmatrix}\label{eq:Stilde}.
\end{align}
Hence, we can write \eqref{eq:stabdef} as a quadratic form by defining the positive
semi-definite matrix
\begin{align}
  \ensuremath{\mathbf M}^T\!\ensuremath{\mathbf M} &\!=\!
  \setlength\arraycolsep{1.5pt}
  \begin{pmatrix}
    \!\begin{bmatrix}\! \ensuremath{\mathbf T}_{1,{{\ensuremath{\mathbf x}}_1 \rule{-1.2ex}{1.6ex}^{_{\scriptscriptstyle -}}}}^T\!\ensuremath{\mathbf{J}}_{_{\!1}} \\ {\ensuremath{\mathbb 0}}\end{bmatrix} &
    \ensuremath{\tilde{\vS}}^T_{-}& \ensuremath{\tilde{\vS}}^T_{-}\ensuremath{\mathbf R} &
      \begin{bmatrix} {\ensuremath{\mathbb 0}} \\ \ensuremath{\mathbf T}_{2,{{\ensuremath{\mathbf x}}_2 \rule{-1.2ex}{1.6ex}^{_{\scriptscriptstyle -}}}}^T \!\ensuremath{\mathbf{J}}_{_{\!2}} \end{bmatrix} \!
  \end{pmatrix}\!\!
  \begin{pmatrix}
    \begin{bmatrix}\! \ensuremath{\mathbf T}_{1,{{\ensuremath{\mathbf x}}_1 \rule{-1.2ex}{1.6ex}^{_{\scriptscriptstyle -}}}}\ensuremath{\mathbf{J}}_1 & {\ensuremath{\mathbb 0}}\end{bmatrix} \\
    \ensuremath{\tilde{\vS}}_{-}\\
    \ensuremath{\mathbf R}\ensuremath{\tilde{\vS}}_{-}\\
    \begin{bmatrix} {\ensuremath{\mathbb 0}} &\ensuremath{\mathbf{J}}_{_{\!2}}\! \ensuremath{\mathbf T}_{2,\text{-}{{\ensuremath{\mathbf x}}_2 \rule{-1.2ex}{1.6ex}^{_{\scriptscriptstyle -}}}}  \end{bmatrix}
  \end{pmatrix}\notag
  \\
  &=
  \setlength\arraycolsep{2pt}
     \!\begin{bmatrix}\! \ensuremath{\mathbf T}_{1,{{\ensuremath{\mathbf x}}_1 \rule{-1.2ex}{1.6ex}^{_{\scriptscriptstyle -}}}}^T\!\ensuremath{\mathbf{J}}_{_{\!1}}^2 \ensuremath{\mathbf T}_{1,{{\ensuremath{\mathbf x}}_1 \rule{-1.2ex}{1.6ex}^{_{\scriptscriptstyle -}}}} & {\ensuremath{\mathbb 0}} \\
       {\ensuremath{\mathbb 0}} & \ensuremath{\mathbf T}_{2,\text{-}{{\ensuremath{\mathbf x}}_2 \rule{-1.2ex}{1.6ex}^{_{\scriptscriptstyle -}}}}^T \!\ensuremath{\mathbf{J}}_{_{\!2}}^2 \ensuremath{\mathbf T}_{2,\text{-}{{\ensuremath{\mathbf x}}_2 \rule{-1.2ex}{1.6ex}^{_{\scriptscriptstyle -}}}}
    \end{bmatrix}
     +
     2\ensuremath{\tilde{\vS}}_{-}^T\ensuremath{\tilde{\vS}}_{-}
     \label{eq:Bdef}
     \\
  &=
    2
    \begin{pmatrix}{\ensuremath{\mathbf D}}_1 & {\ensuremath{\mathbf 0}} \\ {\ensuremath{\mathbf 0}} & {\ensuremath{\mathbf D}}_2\end{pmatrix}
    + 2\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{-}\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss^T_-
    = 2({\ensuremath{\mathbf D}} + {\ensuremath{\mathbf W}}_{-})
\end{align}
where the block diagonal matrix ${\ensuremath{\mathbf D}}$ and the Sylvester matrix product, given by
\begin{align}
  {\ensuremath{\mathbf W}}_{-}=\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf x}}_2^{-0},-{\ensuremath{\mathbf x}}_1^0}^*\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf x}}_2^{-0},-{\ensuremath{\mathbf x}}_1^{0}},\label{eq:Wminus}
\end{align}
are positive semi-definite by construction.  Note, we can add the zero row to the matrix in \eqref{eq:Stilde} to obtain
the square Sylvester matrix in the product, see also \eqref{eq:sylvesterrangestar}.  However, this Sylvester matrix is
distinct to $\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss$ in \eqref{eq:sylvesterx} by a time-reversal of ${\ensuremath{\mathbf x}}_2$ and therefore denoted by $\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_-$. The
time-reversal is hereby unavoidable, since the cross correlation sum in \eqref{eq:AY} involves all four vectors and
induces a time-reversal either on ${\ensuremath{\mathbf x}}_1$ or ${\ensuremath{\mathbf x}}_2$. This is in contrast to the injectivity result where we do not have
to deal with a sum  and hence not with an extra time-reversal \cite{WJPH17}.  The intertwining matrices generate in the
diagonals
\begin{align}
  \begin{split}
 {\ensuremath{\mathbf D}}_i\!=\! \ensuremath{\mathbf T}_{i,{{\ensuremath{\mathbf x}}_i \rule{-1.2ex}{1.6ex}^{_{\scriptscriptstyle -}}}}^T \!\ensuremath{\mathbf{J}}_{i}\ensuremath{\mathbf T}_{i,{{\ensuremath{\mathbf x}}_i \rule{-1.2ex}{1.6ex}^{_{\scriptscriptstyle -}}}}&=\ensuremath{\mathbf T}_{i,{{\ensuremath{\mathbf x}}_i \rule{-1.2ex}{1.6ex}^{_{\scriptscriptstyle -}}}}^T \!\ensuremath{\mathbf T}_{i,{{\ensuremath{\mathbf x}}_i \rule{-1.2ex}{1.6ex}^{_{\scriptscriptstyle -}}}}\!+\!
  \ensuremath{\mathbf T}_{i,{{\ensuremath{\mathbf x}}_i \rule{-1.2ex}{1.6ex}^{_{\scriptscriptstyle -}}}}^T\!\ensuremath{\mathbf R}_{2N_i-1}\ensuremath{\mathbf T}_{i,{{\ensuremath{\mathbf x}}_i \rule{-1.2ex}{1.6ex}^{_{\scriptscriptstyle -}}}}\\
  &\overset{\eqref{eq:convTopelitzproduct}}{=}\ensuremath{\mathbf T}_{i,i,{\ensuremath{\mathbf a}}_i} + \vH_{i,i,{\ensuremath{\mathbf c}}_{i}}
\end{split}
\end{align}
a sum of the autocorrelation Toeplitz matrix and the autoconvolution Hankel matrix. Here, the elementary Hankel matrix
is given by $\vH_N=\ensuremath{\mathbf T}_N\ensuremath{\mathbf R}_N$.  The stability constant is then given, up to a constant scaling between
\eqref{eq:boundY} as the smallest eigenvalue problem
\begin{align}
  \ensuremath{\gamma}^2 \geq \frac{1}{2} \min_{\Norm{{\ensuremath{\mathbf y}}}=1}
  \skprod{({\ensuremath{\mathbf D}}+{\ensuremath{\mathbf W}}_-){\ensuremath{\mathbf y}}}{{\ensuremath{\mathbf y}}}=\frac{1}{2}\ensuremath{\lambda}_1({\ensuremath{\mathbf D}}+{\ensuremath{\mathbf W}}_-)\label{eq:gamDWoptimization}.
\end{align}

\subsection{Local $2-$RIP}

We are now ready to proof the local restricted isometry property  for rank$-2$ matrices in the tangent space.
\begin{lemi}[Local $2-$RIP]\label{lem:localstab}
  Let ${\ensuremath{\mathbf x}}_1\in{\ensuremath{\mathbb R}}^{{{L}_1}}_{0},{\ensuremath{\mathbf x}}_2\in{\ensuremath{\mathbb R}}^{{{L}_2}}_{0,0}$ such that ${\ensuremath{\mathrm x}}_1\nmid {\ensuremath{\mathrm x}}_2^-$ and set ${\ensuremath{\mathbf x}}=[{\ensuremath{\mathbf x}}_1,{\ensuremath{\mathbf x}}_2]$ with
  $N:={{L}_1}+{{L}_2}$. Then  the linear map ${\ensuremath{\mathcal{A}}}$ in \eqref{eq:4maskmeasurements}   fulfills
  %
  \begin{align}
    \Norm{{\ensuremath{\mathcal{A}}}({\ensuremath{\mathbf Y}})} \geq \ensuremath{\gamma} \sNorm{{\ensuremath{\mathbf Y}}} \quad,\quad {\ensuremath{\mathbf Y}}\in T_{\ensuremath{\mathbf x}}\label{eq:localrank1RIP}
  \end{align}
  %
  where the lower bound satisfy
  %
  \begin{align}
    \ensuremath{\gamma}=\ensuremath{\gamma}(\ensuremath{\tilde{\mathbf x}}_1,\ensuremath{\tilde{\mathbf x}}_2) &\geq \frac{1}{4N\sqrt{2}} \sqrt{\ensuremath{\lambda}_2({\ensuremath{\mathbf W}}_{-})}
     \label{eq:gammalowerbound}
  \end{align}
  %
  with $\ensuremath{\tilde{\mathbf x}}_i={\ensuremath{\mathbf x}}_i/\Norm{{\ensuremath{\mathbf x}}}$ for $i\in\{1,2\}$.
\end{lemi}
\begin{proof}
Since the optimization problem \eqref{eq:gamDWoptimization} for $\ensuremath{\gamma}$ is only dependent on the normalized vectors $\ensuremath{\tilde{\mathbf x}}$ we will
omit the tilde notation over  ${\ensuremath{\mathbf x}},{\ensuremath{\mathbf x}}_1$ and ${\ensuremath{\mathbf x}}_2$.

The eigenvalue problem is a simultaneous eigenvalue problem and bounds like the \emph{dual Weyl inequality}
\cite[Thm.4.3.1]{HJ13}
\begin{align}
  \ensuremath{\lambda}_1({\ensuremath{\mathbf D}}+\ensuremath{{\ensuremath{\mathbf W}}_{\!-}})\geq  \ensuremath{\lambda}_1({\ensuremath{\mathbf D}})+\ensuremath{\lambda}_1(\ensuremath{{\ensuremath{\mathbf W}}_{\!-}})\label{eq:dualweyl}
\end{align}
are not sufficient, since they separate the autocorrelation and crosscorrelation measurements, which both can vanish
separately but not simultaneously. However, we know much more about $\ensuremath{{\ensuremath{\mathbf W}}_{\!-}}$, in fact $\ensuremath{{\ensuremath{\mathbf W}}_{\!-}}$ has rank $N-1$ if the
polynomials ${\ensuremath{\mathrm x}}_2^- (z)$ and ${\ensuremath{\mathrm x}}_1(z)$ are co-prime, see also \eqref{eq:sylvesterrank}, and its one-dimensional
nullspace is spanned by
\begin{align}
  {\ensuremath{\mathbf x}}_-=\begin{pmatrix}{\ensuremath{\mathbf x}}_1 \\ {\ensuremath{\mathbf x}}_2^-\end{pmatrix}.\label{eq:wnull}
\end{align}
Hence, we can project each normalized ${\ensuremath{\mathbf y}}\in{\ensuremath{\mathbb R}}^N$ to  ${\ensuremath{\mathbf x}}_-$ and its orthogonal normalized complement space
$\ensuremath{W_{\!\perp}}:=\set{{\ensuremath{\mathbf w}}\in{\ensuremath{\mathbb R}}^N}{{\ensuremath{\mathbf w}}\bot{\ensuremath{\mathbf x}}_-,\Norm{{\ensuremath{\mathbf w}}}_2=1}$ such that
\begin{align}
  {\ensuremath{\mathbf y}}=\ensuremath{\alpha}{\ensuremath{\mathbf x}}_- + \ensuremath{\beta}\ensuremath{{\ensuremath{\mathbf w}}}\quad,\quad \ensuremath{\alpha},\ensuremath{\beta}\in{\ensuremath{\mathbb R}},\ensuremath{{\ensuremath{\mathbf w}}}\in\ensuremath{W_{\!\perp}}.\label{eq:ranktwoy}
\end{align}
Since $\Norm{{\ensuremath{\mathbf x}}_-}=\Norm{\ensuremath{{\ensuremath{\mathbf w}}}}=1$, it must hold $\Norm{{\ensuremath{\mathbf y}}}_2^2= \ensuremath{\alpha}^2\Norm{{\ensuremath{\mathbf x}}_-}+\ensuremath{\beta}^2\Norm{\ensuremath{{\ensuremath{\mathbf w}}}}=\ensuremath{\alpha}^2+\ensuremath{\beta}^2=1$.
If we want to establish injectivity it would be enough to show that $\skprod{{\ensuremath{\mathbf D}}{\ensuremath{\mathbf x}}_-}{{\ensuremath{\mathbf x}}_-}>0$, but to derive a
stability bound we need to show this  for all ${\ensuremath{\mathbf y}}$ given by \eqref{eq:ranktwoy}, i.e.,
\begin{align}
  \frac{1}{2}\!\Norm{\ensuremath{\mathbf M}{\ensuremath{\mathbf y}}}^2&\!=\!\skprod{({\ensuremath{\mathbf D}}\!+\!\!\ensuremath{{\ensuremath{\mathbf W}}_{\!-}}){\ensuremath{\mathbf y}}}{{\ensuremath{\mathbf y}}} \!=\! \skprod{{\ensuremath{\mathbf D}}{\ensuremath{\mathbf y}}}{{\ensuremath{\mathbf y}}}+\skprod{\ensuremath{{\ensuremath{\mathbf W}}_{\!-}}{\ensuremath{\mathbf y}}}{{\ensuremath{\mathbf y}}}\\
  &\!=\! \skprod{{\ensuremath{\mathbf D}}(\ensuremath{\alpha}{\ensuremath{\mathbf x}}_-\!+\!\ensuremath{\beta} \ensuremath{{\ensuremath{\mathbf w}}})}{\ensuremath{\alpha}{\ensuremath{\mathbf x}}_-\!+\!\ensuremath{\beta}\ensuremath{{\ensuremath{\mathbf w}}}} \!+\! \ensuremath{\beta}^2\!\skprod{\ensuremath{{\ensuremath{\mathbf W}}_{\!-}}\ensuremath{{\ensuremath{\mathbf w}}}}{\ensuremath{{\ensuremath{\mathbf w}}}}\notag.
\end{align}
Therefore we can lower bound the smallest eigenvalue  by a kind of pinching argument to
\begin{align}
  \ensuremath{\lambda}_1&\!=\min_{\Norm{{\ensuremath{\mathbf y}}}=1} \skprod{({\ensuremath{\mathbf D}}+\ensuremath{{\ensuremath{\mathbf W}}_{\!-}}){\ensuremath{\mathbf y}}}{{\ensuremath{\mathbf y}}}\label{eq:Dmin} \\
  &\!=\!\min_{\substack{\ensuremath{\alpha}^2+\ensuremath{\beta}^2=1\\ {\ensuremath{\mathbf w}}\in\ensuremath{W_{\!\perp}}}}
  \!\underbrace{\skprod{{\ensuremath{\mathbf D}}(\ensuremath{\alpha}{\ensuremath{\mathbf x}}_-\!+\!\ensuremath{\beta} \ensuremath{{\ensuremath{\mathbf w}}})}{\ensuremath{\alpha}{\ensuremath{\mathbf x}}_-\!+\!\ensuremath{\beta}\ensuremath{{\ensuremath{\mathbf w}}}}}_{=f_{\ensuremath{\alpha},\ensuremath{\beta}}({\ensuremath{\mathbf w}})\geq 0}
   + \ensuremath{\beta}^2\skprod{\ensuremath{{\ensuremath{\mathbf W}}_{\!-}}\ensuremath{{\ensuremath{\mathbf w}}}}{\ensuremath{{\ensuremath{\mathbf w}}}}\notag\\
  &\geq\min_{\ensuremath{\alpha}^2+\ensuremath{\beta}^2=1}\left( \ensuremath{\beta}^2\ensuremath{\lambda}_2(\ensuremath{{\ensuremath{\mathbf W}}_{\!-}}) +\min_{\ensuremath{{\ensuremath{\mathbf w}}}\in\ensuremath{W_{\!\perp}}}f_{\ensuremath{\alpha},\ensuremath{\beta}}(\ensuremath{{\ensuremath{\mathbf w}}})
  \right)\notag.
\end{align}
Since ${\ensuremath{\mathbf D}}={\ensuremath{\mathbf D}}^T$ and the scalar product is real valued we get
\begin{align}
  f_{\ensuremath{\alpha},\ensuremath{\beta}}(\ensuremath{{\ensuremath{\mathbf w}}}\!)\!=\! \ensuremath{\alpha}^2\!\skprod{{\ensuremath{\mathbf D}}{\ensuremath{\mathbf x}}_-}{\!{\ensuremath{\mathbf x}}_-\!}\!+\!\ensuremath{\beta}^2\!\skprod{{\ensuremath{\mathbf D}}\ensuremath{{\ensuremath{\mathbf w}}}}{\!\ensuremath{{\ensuremath{\mathbf w}}}}
  \!+\!2\ensuremath{\alpha}\ensuremath{\beta}\!\skprod{{\ensuremath{\mathbf D}}{\ensuremath{\mathbf x}}_-}{\!\ensuremath{{\ensuremath{\mathbf w}}}}\label{eq:Dyy}.
\end{align}
The first term can be lower bounded universally for all $\Norm{{\ensuremath{\mathbf x}}}_2^2=1=\Norm{{\ensuremath{\mathbf x}}_1}^2+\Norm{{\ensuremath{\mathbf x}}_2}^2$ by
\begin{align}
    \skprod{{\ensuremath{\mathbf D}}{\ensuremath{\mathbf x}}_-}{{\ensuremath{\mathbf x}}_-}&\overset{\eqref{eq:wnull}}{=}\skprod{{\ensuremath{\mathbf D}}_1{\ensuremath{\mathbf x}}_1}{{\ensuremath{\mathbf x}}_1} +
    \skprod{{\ensuremath{\mathbf D}}_2{\ensuremath{\mathbf x}}_2^-}{{\ensuremath{\mathbf x}}_2^-}\notag\\
    &\overset{\eqref{eq:Bdef}}{=}\frac{1}{2}\Big(\Norm{\ensuremath{\mathbf{J}}_1({\ensuremath{\mathbf x}}_1^-*{\ensuremath{\mathbf x}}_1)}^2_2 +  \Norm{
    \ensuremath{\mathbf{J}}_2({\ensuremath{\mathbf x}}_2*{\ensuremath{\mathbf x}}_2^-)}^2_2\Big) \notag\\
    &= \frac{1}{2}\Big( \Norm{2{\ensuremath{\mathbf a}}_1}_2^2 + \Norm{2{\ensuremath{\mathbf a}}_2}_2^2 \Big)=2(\Norm{{\ensuremath{\mathbf a}}_1}_2^2 + \Norm{{\ensuremath{\mathbf a}}_2}_2^2) \notag\\
   &\geq
   2(\Norm{{\ensuremath{\mathbf x}}_1}_2^4+\Norm{{\ensuremath{\mathbf x}}_2}_2^4) \overset{\eqref{eq:lagrange}}{\geq} 1
 \label{eq:dwowo}
\end{align}
where the first inequality follows from the fact that $\|{{\ensuremath{\mathbf x}}_i*\xbar{{\ensuremath{\mathbf x}}_i \rule{-0.9ex}{1.6ex}^{_{\scriptstyle -}}}\|}^2_2\geq \Norm{{\ensuremath{\mathbf x}}_i}_2^4$. Unfortunately, we
can not derive such a lower estimation for $\skprod{{\ensuremath{\mathbf D}}\ensuremath{{\ensuremath{\mathbf w}}}}{\ensuremath{{\ensuremath{\mathbf w}}}}$ since arbitrary cross correlations are not
invariant to time-reversal. To see this, choose  $\ensuremath{{\ensuremath{\mathbf w}}_{1}}=(1,1)={\ensuremath{\mathbf x}}_2$ and $\ensuremath{{\ensuremath{\mathbf w}}_{2}}=(1,-1)={\ensuremath{\mathbf x}}_1$. Then
${\ensuremath{\mathbf x}}_i\bot\ensuremath{{\ensuremath{\mathbf w}}_i}$ and hence ${\ensuremath{\mathbf x}}_-\perp\ensuremath{{\ensuremath{\mathbf w}}}$ but $\ensuremath{{\ensuremath{\mathbf w}}_i}*{\ensuremath{\mathbf x}}_i^-+ (\ensuremath{{\ensuremath{\mathbf w}}_i}*{\ensuremath{\mathbf x}}_i^-)^-={\ensuremath{\mathbf 0}}$. Also
${\ensuremath{\mathrm x}}_1\nmid{\ensuremath{\mathrm x}}_2$ and ${\ensuremath{\mathrm x}}_2={\ensuremath{\mathrm x}}_2^-$.  If we omit the non-negative part $\ensuremath{\beta}^2\skprod{{\ensuremath{\mathbf D}}\ensuremath{{\ensuremath{\mathbf w}}}}{\ensuremath{{\ensuremath{\mathbf w}}}}\geq 0$ we
only have to lower bound the third term in \eqref{eq:Dyy}. Since $f_{\ensuremath{\alpha},\ensuremath{\beta}}\geq 0$ this gives with \eqref{eq:dwowo}
the non-zero lower bound
\begin{align}
  \min_{\ensuremath{{\ensuremath{\mathbf w}}}\in\ensuremath{W_{\!\perp}}}\!\!f_{\ensuremath{\alpha},\ensuremath{\beta}}(\ensuremath{{\ensuremath{\mathbf w}}}) &\!\geq\! \max\{0,\ensuremath{\alpha}^2 - 2
    |\ensuremath{\alpha}\ensuremath{\beta}|\max_{\ensuremath{{\ensuremath{\mathbf w}}}\in\ensuremath{W_{\!\perp}}}\skprod{{\ensuremath{\mathbf D}}{\ensuremath{\mathbf x}}_-}{\ensuremath{{\ensuremath{\mathbf w}}}}\},\notag
\end{align}
where the scalar product can be split with $\ensuremath{{\ensuremath{\mathbf w}}}\!=[\ensuremath{{\ensuremath{\mathbf w}}_{1}},\ensuremath{{\ensuremath{\mathbf w}}_{2}}]$ in
\begin{align}
  \begin{split}
  |\!\skprod{{\ensuremath{\mathbf D}}{\ensuremath{\mathbf x}}_-}{\!\ensuremath{{\ensuremath{\mathbf w}}}}\!| \!&= |\skprod{{\ensuremath{\mathbf D}}_1{\ensuremath{\mathbf x}}_1}{\ensuremath{{\ensuremath{\mathbf w}}_{1}}} +\skprod{{\ensuremath{\mathbf D}}_2{\ensuremath{\mathbf x}}_2^-}{\ensuremath{{\ensuremath{\mathbf w}}_{2}}}|\\
   &\leq |\skprod{{\ensuremath{\mathbf D}}_1{\ensuremath{\mathbf x}}_1}{\ensuremath{{\ensuremath{\mathbf w}}_{1}}}| +|\skprod{{\ensuremath{\mathbf D}}_2{\ensuremath{\mathbf x}}_2^-}{\ensuremath{{\ensuremath{\mathbf w}}_{2}}}|\\
   &=  |\skprod{\ensuremath{\mathbf{J}}_1\ensuremath{\mathbf T}_{1,{\ensuremath{\mathbf x}}_1^-} {\ensuremath{\mathbf x}}_1}{\ensuremath{\mathbf T}_{1,{\ensuremath{\mathbf x}}_1^-} \ensuremath{{\ensuremath{\mathbf w}}_{1}}}|\\
  &\quad\quad \quad+|\skprod{\ensuremath{\mathbf{J}}_2\ensuremath{\mathbf T}_{2,{\ensuremath{\mathbf x}}_2} {\ensuremath{\mathbf x}}_2^-}{\ensuremath{\mathbf T}_{2,{\ensuremath{\mathbf x}}_2} \ensuremath{{\ensuremath{\mathbf w}}_{2}}}|\\
  &=2 (|\skprod{{\ensuremath{\mathbf a}}_1}{{\ensuremath{\mathbf x}}_1^-*\ensuremath{{\ensuremath{\mathbf w}}_{1}}}| + |\skprod{{\ensuremath{\mathbf a}}_2}{{\ensuremath{\mathbf x}}_2*\ensuremath{{\ensuremath{\mathbf w}}_{2}}}|)
\end{split}
\end{align}
such that by using Cauchy-Schwarz in both terms we get
\begin{align}
  |\!\skprod{{\ensuremath{\mathbf D}}{\ensuremath{\mathbf x}}_-}{\!\ensuremath{{\ensuremath{\mathbf w}}}}\!| \! &\leq \!2 (\Norm{{\ensuremath{\mathbf a}}_1}\Norm{{\ensuremath{\mathbf x}}_1^-\!*\ensuremath{{\ensuremath{\mathbf w}}_{1}}} \!+\!
  \Norm{{\ensuremath{\mathbf a}}_2}\Norm{{\ensuremath{\mathbf x}}_2*\ensuremath{{\ensuremath{\mathbf w}}_{2}}})\\
  \intertext{and by applying the Young inequality}
  \begin{split}
    &\leq\!2\Big( \Norm{{\ensuremath{\mathbf x}}_1}_1^2 \underbrace{\Norm{{\ensuremath{\mathbf x}}_1}}_{\leq 1}\underbrace{\Norm{\ensuremath{{\ensuremath{\mathbf w}}_{1}}}}_{\leq 1} + \Norm{{\ensuremath{\mathbf x}}_2}_1^2
    \underbrace{\Norm{{\ensuremath{\mathbf x}}_2}}_{\leq 1}\underbrace{\Norm{\ensuremath{{\ensuremath{\mathbf w}}_{1}}}}_{\leq 1}\Big)\\
    &\leq\! 2\Big( {{L}_1}\Norm{{\ensuremath{\mathbf x}}_1}^2 + {{L}_2}\Norm{{\ensuremath{\mathbf x}}_2}^2\Big)\leq 2\max\{{{L}_1},{{L}_2}\}\\
    &\leq\! 2(N-1).
  \end{split}\notag
\end{align}
where the last steps follows since $N_1,N_2\geq 1$ and $N=N_1+N_2$.
If $\Norm{{\ensuremath{\mathbf x}}_1}=\Norm{{\ensuremath{\mathbf x}}_2}$ or ${{L}_1}={{L}_2}$ then the bound is $N$.  Hence
\begin{align}
  \min_{\ensuremath{{\ensuremath{\mathbf w}}}} f_{\ensuremath{\alpha},\ensuremath{\beta}}(\ensuremath{{\ensuremath{\mathbf w}}})\geq |\ensuremath{\alpha}|\max\{0,|\ensuremath{\alpha}| -4(N-1)|\ensuremath{\beta}|\}  \label{eq:dzero}
\end{align}
which only gives a strict positive bound if $|\ensuremath{\beta}|\leq \frac{|\ensuremath{\alpha}|}{M}$ with $M=4N-4$. Hence we get
\begin{align}
  \ensuremath{\lambda}_1 \geq  \min_{\substack{|\ensuremath{\alpha}^2|+|\ensuremath{\beta}|^2=1\\ M|\ensuremath{\beta}|\leq |\ensuremath{\alpha}|}}
\Big[|\ensuremath{\beta}|^2 \ensuremath{\lambda}_2(\ensuremath{{\ensuremath{\mathbf W}}_{\!-}})+|\ensuremath{\alpha}|^2 -M|\ensuremath{\beta}||\ensuremath{\alpha}|\}\Big]\notag\label{eq:lagrangeobjective}
\end{align}
Since $0<\ensuremath{\lambda}_2(\ensuremath{{\ensuremath{\mathbf W}}_{\!-}})=\ensuremath{\sigma}_2^2(\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_-)\leq 1$ as shown in \lemref{lem:sigclassic} since $\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_-$ has rank $N-1$, one
can show by using Lagrange multiplier that $M|\ensuremath{\beta}|=|\ensuremath{\alpha}|$ with $|\ensuremath{\beta}|^2=1/(1+M^2)$ yields the minimum in
\eqref{eq:lagrangeobjective} given by
\begin{align}
  \ensuremath{\lambda}_1 \geq \frac{1}{1+M^2} \ensuremath{\lambda}_2({\ensuremath{\mathbf W}}_-).
\end{align}
By using $M^2+1\leq (4N)^2$ this yields to the lower bound
\begin{align}
  \ensuremath{\gamma}({\ensuremath{\mathbf x}}_1,{\ensuremath{\mathbf x}}_2)&\geq\frac{1}{\sqrt{2}} \frac{1}{4N} \sqrt{\ensuremath{\lambda}_2(\ensuremath{{\ensuremath{\mathbf W}}_{\!-}})}
  .\label{eq:gaminlam2}
\end{align}
\end{proof}

\subsection{Stability of the SDP}

Since we have the exact dual certificate, we only have to exploit in the noisy case, that any solution produces a
mean-square error which scales with the noise-power.  We adapt the proof techniques in \cite[Lem.4]{DH12} to derive the
stability result for the denoised SDP.
\renewcommand{\vxgt}{{\ensuremath{\mathbf x}}}
\begin{thm}[Stability of the SDP: Real Case]\label{thm:stability}
  %
  Let ${\ensuremath{\mathcal{A}}}$ be the linear map defined in \eqref{eq:4maskmeasurements}. Let $\vxgt=[{\ensuremath{\mathbf x}}_1,{\ensuremath{\mathbf x}}_2]$ be the ground truth
  signal with  ${\ensuremath{\mathbf x}}_1\in{\ensuremath{\mathbb R}}_{0}^{{{L}_1}}$ and ${\ensuremath{\mathbf x}}_2\in{\ensuremath{\mathbb R}}_{0,0}^{{{L}_2}}$. If $\hat{{\ensuremath{\mathbf X}}}$ is a solution of the noisy SDP
  \eqref{eq:SDPnoisy}, given by the noisy observation ${\ensuremath{\mathbf b}}={\ensuremath{\mathcal{A}}}({\ensuremath{\mathbf x}}\vx^*)+\vn$ for any $\vn\in{\ensuremath{\mathbb C}}^{4N-4}$, then it holds
  %
  \begin{align}
    \sNorm{\hat{{\ensuremath{\mathbf X}}}-{\ensuremath{\mathbf x}}\vx^*} \leq C\Norm{\vn}
  \end{align}
  %
  with $N={{L}_1}+{{L}_2}$ and the stability constant
  %
  \begin{align}
    C\!\leq\! 2N\!\left( \frac{23N^2}{\ensuremath{\lambda}_2({\ensuremath{\mathbf W}})\sqrt{\ensuremath{\lambda}_2(\ensuremath{{\ensuremath{\mathbf W}}_{\!-}})}}\!+\!\frac{1}{\ensuremath{\lambda}_2({\ensuremath{\mathbf W}})}\!
    +\! \frac{4\sqrt{2}}{\sqrt{\ensuremath{\lambda}_2(\ensuremath{{\ensuremath{\mathbf W}}_{\!-}})}}\right)\label{eq:CinW}
  \end{align}
  %
  where ${\ensuremath{\mathbf W}}$ and $\ensuremath{{\ensuremath{\mathbf W}}_{\!-}}$ are given in \eqref{eq:dualcertif} and \eqref{eq:Wminus} for $\ensuremath{\tilde{\mathbf x}}_i\!=\!{\ensuremath{\mathbf x}}_i/\Norm{{\ensuremath{\mathbf x}}}$.
\end{thm}
\begin{proof}
  Let $\hat{{\ensuremath{\mathbf X}}}\succeq {\ensuremath{\mathbf 0}}$ and $\|{\ensuremath{\mathcal{A}}}(\hat{{\ensuremath{\mathbf X}}})-{\ensuremath{\mathbf b}}\|\leq \Norm{\vn}$, i.e., $\ensuremath{\hat{\vX}}$ is a solution of the noisy SDP
  \eqref{eq:SDPnoisy}. For $\vH:=\ensuremath{\hat{\vX}}-{\ensuremath{\mathbf x}}\vx^*$ we get then for the residual
  %
  \begin{align}
    \begin{split}
    \Norm{{\ensuremath{\mathcal{A}}}(\vH)}&=\|{\ensuremath{\mathcal{A}}}(\ensuremath{\hat{\vX}})-{\ensuremath{\mathcal{A}}}({\ensuremath{\mathbf x}}\vx^*)+{\ensuremath{\mathbf b}}-{\ensuremath{\mathbf b}}\|\\
    &\leq \|{\ensuremath{\mathcal{A}}}(\ensuremath{\hat{\vX}})-{\ensuremath{\mathbf b}}\| +    \|{\ensuremath{\mathcal{A}}}({\ensuremath{\mathbf x}}\vx^*)-{\ensuremath{\mathbf b}}\| \leq 2\Norm{\vn}.
  \end{split}\label{eq:residualH}
  \end{align}
  %
  Similarly we get for the projection onto the exact dual certificate by using Cauchy-Schwarz
  and the fact that ${\ensuremath{\mathbf W}}={\ensuremath{\mathcal{A}}}^*(\ensuremath{\boldsymbol{ \ome}})$, as shown in \eqref{eq:AlamW},
  %
  \begin{align}
    \begin{split}
    |\sprod{\vH}{{\ensuremath{\mathbf W}}}|&=|\sprod{{\ensuremath{\mathcal{A}}}(\vH)}{\ensuremath{\boldsymbol{ \ome}}}|
        \leq \Norm{{\ensuremath{\mathcal{A}}}(\vH)}_2 \Norm{\ensuremath{\boldsymbol{ \ome}}}_2\\
        &\leq 2\Norm{\vn} \norm{\ensuremath{\boldsymbol{ \ome}}}_1.
      \end{split}\label{eq:absHW}
  \end{align}
  %
  Since $\ensuremath{\boldsymbol{ \ome}}=[{\ensuremath{\mathbf a}}_1^{(2)},-{\ensuremath{\mathbf a}}_{1,2},-{\ensuremath{\mathbf a}}_{2,1},{\ensuremath{\mathbf a}}_2^{(1)}]$ in
  \eqref{eq:AlamW}, we  get  with the Young inequality
  %
  \begin{align}
    \begin{split}
      \Norm{\ensuremath{\boldsymbol{ \ome}}}_1&=\Norm{{\ensuremath{\mathbf a}}_1^{(2)}}_1+\Norm{{\ensuremath{\mathbf a}}_{1,2}}_1 +\Norm{{\ensuremath{\mathbf a}}_{2,1}}_1 +\Norm{{\ensuremath{\mathbf a}}_2^{(1)}}_1\\
      &\leq\Norm{{\ensuremath{\mathbf x}}_1*\xbar{{\ensuremath{\mathbf x}}_1 \rule{-1.2ex}{1.6ex}^{_{\scriptstyle -}}}}_1 + 2\Norm{{\ensuremath{\mathbf x}}_1*{\ensuremath{\mathbf x}}_2^-}_1+ \Norm{{\ensuremath{\mathbf x}}_2*\xbar{{\ensuremath{\mathbf x}}_2 \rule{-1.2ex}{1.6ex}^{_{\scriptstyle -}}}}_1\\
                &\leq \Norm{{\ensuremath{\mathbf x}}_1}_1^2+ 2\Norm{{\ensuremath{\mathbf x}}_1}_1\Norm{{\ensuremath{\mathbf x}}_2}_1 + \Norm{{\ensuremath{\mathbf x}}_2}_1^2 \\
    &= (\Norm{{\ensuremath{\mathbf x}}_1}_1 + \Norm{{\ensuremath{\mathbf x}}_2}_1)^2
    = \Norm{{\ensuremath{\mathbf x}}}_1^2
    \leq N\Norm{{\ensuremath{\mathbf x}}}_2^2=N.
  \end{split}
  \end{align}
  %
  This gives for the exact dual certificate projection \eqref{eq:absHW} on  $T=T_{{\ensuremath{\mathbf x}}}$ and $T^{\bot}$
  %
  \begin{align}
    2N\Norm{\vn} &\geq |\skprod{\vH}{{\ensuremath{\mathbf W}}}| =|\skprod{\vH_{T}}{{\ensuremath{\mathbf W}}_{T}} + \skprod{\vH_{T^\bot}}{{\ensuremath{\mathbf W}}_{T^\bot}}|\notag\\
    &=\tr({\ensuremath{\mathbf U}}\vH_{T^\bot}{\ensuremath{\mathbf U}}^T {\ensuremath{\mathbf D}}_{\ensuremath{\boldsymbol{ \lam}}} ) \geq \ensuremath{\lambda}_2({\ensuremath{\mathbf W}}) \sNorm{\vH_{T^\bot}}_1\label{eq:htbotbound}
  \end{align}
  %
  where  ${\ensuremath{\mathbf W}}_T=0$ and ${\ensuremath{\mathbf W}}_{T^\bot}={\ensuremath{\mathbf U}}^T{\ensuremath{\mathbf D}}_{\ensuremath{\boldsymbol{ \lam}}}{\ensuremath{\mathbf U}}\succ 0$ since the diagonal matrix ${\ensuremath{\mathbf D}}_{\ensuremath{\boldsymbol{ \lam}}}$ contains the
  positive eigenvalues $\ensuremath{\lambda}_k$ of ${\ensuremath{\mathbf W}}_{T^\bot}$ which must be all larger than the smallest non-zero eigenvalue of
  ${\ensuremath{\mathbf W}}$, i.e.  $\ensuremath{\lambda}_1({\ensuremath{\mathbf W}}_{T^\bot})=\ensuremath{\lambda}_2({\ensuremath{\mathbf W}})$. Moreover, $\vH_{T^{\bot}}=\ensuremath{\hat{\vX}}_{T^\bot}$ is positive semi-definite
  since $\ensuremath{\hat{\vX}}$ is by definition.  Hence the last inequality follows, see also \lemref{lem:tracelowerbound}.  To upper
  bound the norm of $\vH$ we therefore only need to upper bound the norm of  $\vH_T$, which is given by the local
  stability on $T$ in \lemref{lem:localstab},
  %
  \begin{align}
    \ensuremath{\gamma}\sNorm{\vH_T} &\overset{\eqref{eq:localrank1RIP}}{\leq} \Norm{{\ensuremath{\mathcal{A}}}(\vH_T)}=\Norm{{\ensuremath{\mathcal{A}}}(\vH-\vH_{T^\bot})} \label{eq:boundHT}\\
     &\leq \Norm{{\ensuremath{\mathcal{A}}}(\vH)} + \Norm{{\ensuremath{\mathcal{A}}}(\vH_{T^\bot})}
     \overset{\eqref{eq:residualH}}{\leq} 2\Norm{\vn}  +  \Norm{{\ensuremath{\mathcal{A}}}(\vH_{T^\bot})}_1 \notag
  \end{align}
  %
  Now, we need an upper bound of $\Norm{{\ensuremath{\mathcal{A}}}({\ensuremath{\mathbf X}})}_1$ for any Hermitian ${\ensuremath{\mathbf X}}$, which is given by the \emph{Hölder
  inequality} for the \emph{Schatten norms} with $p=1$ and $q=\infty$, see \cite[Thm.2]{Bau11}, and \eqref{eq:4maskmeasurements} as
  %
  \begin{align}
    \begin{split}
      \Norm{{\ensuremath{\mathcal{A}}}({\ensuremath{\mathbf X}})}_1 &= \sum_{j\geq i=1}^2 \! \!\sum_{k=0}^{\ensuremath{{N_i}}\!+\!\ensuremath{{N_j}}\!-\!2} \!\!| \tr({\ensuremath{\mathbf A}}_{i,j,k} {\ensuremath{\mathbf X}})| \\
      &\leq\sum_{i\leq j,m} \sNorm{{\ensuremath{\mathbf A}}_{i,j,k}}_{\infty} \sNorm{{\ensuremath{\mathbf X}}}_1 = M\sNorm{{\ensuremath{\mathbf X}}}_1
    \end{split}\label{eq:AlinXone}
  \end{align}
  %
  where the last equality follows from the observation
  %
  \begin{align}
    \snorm{{\ensuremath{\mathbf A}}_{i,j,k}}^2_{\infty}\overset{\eqref{eq:inftynorm}}{=}\ensuremath{\lambda}_{N}({\ensuremath{\mathbf A}}_{i,j,k}{\ensuremath{\mathbf A}}_{i,j,k}^*)
    =\ensuremath{\lambda}_{N} (\ensuremath{\mathbf T}_{i,j}^{(k)}(\ensuremath{\mathbf T}_{i,j}^{(k)})^T)=1\notag
  \end{align}
  %
  for all $i,j,k$, since the elementary Toeplitz matrices $\ensuremath{\mathbf T}_{i,j}^{(k)}$ generate diagonal matrices having $k$ ones
  on the diagonal and the rest zero. Using \eqref{eq:boundHT} and \eqref{eq:AlinXone} with ${\ensuremath{\mathbf X}}=\vH_{T^\bot}$
  gives us
  %
  \begin{align}
    \sNorm{\vH_T}& \!\leq\! \frac{2}{\ensuremath{\gamma}}\!\left(\!
    \Norm{\vn} \! +\! \frac{M}{2}\! \sNorm{\vH_{T^{\bot}}\!}_1\!\!\right) \!\!\overset{\eqref{eq:htbotbound}}{\leq}\!
    \frac{2\!\Norm{\vn}}{\ensuremath{\gamma}}\!\left(\!\!1 \!+\! \frac{NM}{\ensuremath{\lambda}_2({\ensuremath{\mathbf W}})} \!\right)\!.\label{eq:HTnorm}
  \end{align}
  %
  Using \eqref{eq:HTnorm} and \eqref{eq:htbotbound} with the triangle inequality yields the error
  %
  \begin{align}
    \sNorm{\vH}&\leq \sNorm{\vH_T}+\sNorm{\vH_{T^\bot}}
    \leq \sNorm{\vH_T}+\sNorm{\vH_{T^\bot}}_1\\
    &\leq \Norm{\vn} \cdot\underbrace{\left( \frac{2}{\ensuremath{\gamma}} + \frac{2NM}{\ensuremath{\gamma}\ensuremath{\lambda}_2({\ensuremath{\mathbf W}})} +
    \frac{2N}{\ensuremath{\lambda}_2({\ensuremath{\mathbf W}})}\right)}_{=C}\notag.
  \end{align}
  %
  By using the bound \eqref{eq:gammalowerbound} of \lemref{lem:localstab} and $4\sqrt{2}NM\leq 16\sqrt{2}N^2\leq
  23 N^2$ we get
  %
  \begin{align}
    C&\leq 2N\!\left( \frac{23N^2}{\ensuremath{\lambda}_2({\ensuremath{\mathbf W}})\sqrt{\ensuremath{\lambda}_2(\ensuremath{{\ensuremath{\mathbf W}}_{\!-}})}}\!+\!\frac{1}{\ensuremath{\lambda}_2({\ensuremath{\mathbf W}})}\! +\!
    \frac{4\sqrt{2}}{\sqrt{\ensuremath{\lambda}_2(\ensuremath{{\ensuremath{\mathbf W}}_{\!-}})}}\right)
    \notag
  \end{align}
  %
\end{proof}

\subsection{Universal Stability Bound via Zero Structure}

To obtain a universal bound for the stability constant we need more constraints on the structure of the zeros of ${\ensuremath{\mathrm x}}_1$
and ${\ensuremath{\mathrm x}}_2$. It follows, that a universal stability can be obtained if the zeros fulfill a minimal separation. Let us
define the \emph{zero separation} of ${\ensuremath{\mathrm x}}_1$ and ${\ensuremath{\mathrm x}}_2$ by
\begin{align}
  \ensuremath{\delta}=\min_{l,k}| \ensuremath{\alpha}_k-\ensuremath{\beta}_l|\label{eq:zeroseparationdel},
\end{align}
and the zeros between ${\ensuremath{\mathrm x}}_1^-$ and ${\ensuremath{\mathrm x}}_2$ by
\begin{align}
  \ensuremath{\delta}_-=\min_{l,k}| \frac{1}{\cc{\ensuremath{\alpha}_k}}-\ensuremath{\beta}_l|\label{eq:zeroseparationdelminus},
\end{align}
see also \cite[p.186]{Zip93}.
Then we can proof the following.
\begin{thm}\label{lem:lam2bound}
  Let ${\ensuremath{\mathbf x}}_1\in{\ensuremath{\mathbb R}}^{{{L}_1}}_{0}$ and ${\ensuremath{\mathbf x}}_2\in{\ensuremath{\mathbb R}}^{{{L}_2}}_{0,0}$ such that $N_1,N_2\geq 2$ and the zeros $\ensuremath{\alpha}_k$ and
  $\ensuremath{\beta}_k$ of their $z-$transforms have a separation $\ensuremath{\delta},\ensuremath{\delta}_->0$. Then the stability constant of the denoised
\eqref{eq:SDPnoisy}
  problem is upper bounded by
  %
  \begin{align}
  C\!\leq\!  48N^3 (\ensuremath{\delta}_-\ensuremath{\delta}^2)^{-N_1 N_2} \!\cdot|\ensuremath{\tilde{x}}_{1,0}^3\ensuremath{\tilde{x}}_{2,N_2\!-\!1}|^{-N_1}\!\cdot
  |\ensuremath{\tilde{x}}_{2,0}|^{-3N_2}.\label{eq:Cupperbound}
  \end{align}
  %
\end{thm}
\begin{figure}[t]
  \centering
  \includegraphics[scale=0.4]{S0_nm}
  \caption{Principal Sylvester submatrix of $\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf a}}^0,{\ensuremath{\mathbf b}}^0}$.}\label{fig:S0}
\end{figure}
\begin{remark}
  For $N_1=1$ or $N_2=1$ the polynomials have no zeros and hence the zero separation \eqref{eq:zeroseparationdel} is not defined.
\end{remark}
\noindent{\it Proof. } Since the dual certificate ${\ensuremath{\mathbf W}}=\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf x}}_2^0,-{\ensuremath{\mathbf x}}_1^0}^*\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf x}}_2^0,-{\ensuremath{\mathbf x}}_1^0}$ for any ${\ensuremath{\mathbf x}}_1$ and
${\ensuremath{\mathbf x}}_2$ is a matrix product of Sylvester matrices \eqref{eq:sylvesterx} for which we can control the smallest singular
value \appref{app:sylvestereigenvalue} we also can control the smallest non-zero eigenvalue, since
\begin{align}
  \ensuremath{\lambda}_k({\ensuremath{\mathbf W}})=\ensuremath{\lambda}_k(\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss^*\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss)=\ensuremath{\lambda}_k(\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss\vS^*)=\ensuremath{\sigma}_k^2(\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss) \label{eq:WSlamsig}
\end{align}
for $k\in\{1,\dots, N\}$.
Lets define $\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_0=\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf x}}_2,-{\ensuremath{\mathbf x}}_1^0}$, the $N-1\times N-1$ principal submatrix of $\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss=\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf x}}_2^0,-{\ensuremath{\mathbf x}}_1^0}$ by
deleting the last column and row (handle)
\begin{align}
  \ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss=
  \left(
  \begin{array}{ccc}
    \multicolumn{2}{c|}{\multirow{2}{*}{\raisebox{-.1\normalbaselineskip}[2pt]{\large$\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_0$}}} & {\ensuremath{\mathbf 0}} \\
    \multicolumn{2}{c|}{} & -{\ensuremath{\mathbf x}}_1\!\!\\
    \cline{1-2}
    \rule{0pt}{2.2ex}
    {\ensuremath{\mathbf 0}}^* & {\ensuremath{\mathbf 0}}^*& 0
  \end{array}
  \right).
\end{align}
see \figref{fig:S0}.
Since the lower part of the handle is zero the multiplication with its adjoint creates a zero matrix and the non-zero
upper part of the handle creates a positive semi-definite rank$-1$ matrix
\begin{align}
\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss\vS^*\!=\!
\left(
\begin{array}{ccc}
  \multicolumn{2}{c|}{\multirow{2}{*}{\raisebox{-.1\normalbaselineskip}[2pt]{\large$\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_0\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_0^*$}}} & {\ensuremath{\mathbf 0}} \\
  \multicolumn{2}{c|}{} & -{\ensuremath{\mathbf x}}_1\!\!\!\!\!\\
  \cline{1-2}
  \rule{0pt}{2.2ex}
  {\ensuremath{\mathbf 0}}^* & \!\!-{\ensuremath{\mathbf x}}_1^*\!& 0
\end{array}
\right)
\!+\!
\left(
    \begin{array}{ccc}
      \multicolumn{2}{c|}{\multirow{2}{*}{\raisebox{-.6\normalbaselineskip}[-2pt]{$\begin{matrix} {\ensuremath{\mathbb 0}} & {\ensuremath{\mathbb 0}}\\
        {\ensuremath{\mathbb 0}} &
        {\ensuremath{\mathbf x}}_1{\ensuremath{\mathbf x}}_1^T\end{matrix}$}}} & {\ensuremath{\mathbf 0}}
        \rule{0pt}{2.2ex}
      \\
      \multicolumn{2}{c|}{} & {\ensuremath{\mathbf 0}}\\
      \cline{1-2}
      \rule{0pt}{2.2ex}
      {\ensuremath{\mathbf 0}}^*& {\ensuremath{\mathbf 0}}^*& 0
    \end{array}
\right).
\end{align}
Obviously we have $\ensuremath{\lambda}_1(\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss\vS^*)=0$ and
\begin{align}
  \ensuremath{\lambda}_2(\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss\vS^*)=\ensuremath{\lambda}_1\Big(\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_0\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_0^* +
  \renewcommand{\arraystretch}{0.8}
  \begin{pmatrix}{\ensuremath{\mathbf 0}} \\ {\ensuremath{\mathbf x}}_2\end{pmatrix}
  \setlength\arraycolsep{0.8pt}
  \begin{pmatrix}{\ensuremath{\mathbf 0}}^* &
    {\ensuremath{\mathbf x}}_2^*\end{pmatrix}
  \Big).
\end{align}
Since both matrices are positive semi-definite we get by the dual Weyl inequality \eqref{eq:dualweyl}
\begin{align}
  \ensuremath{\lambda}_2({\ensuremath{\mathbf W}})&\overset{\eqref{eq:WSlamsig}}{=} \ensuremath{\lambda}_2(\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss\vS^*)\geq \ensuremath{\lambda}_1(\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_0\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_0^*)
  =\ensuremath{\sigma}_1^2(\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{0})=\ensuremath{\sigma}^2.
\end{align}
Similar, we get for $\ensuremath{{\ensuremath{\mathbf W}}_{\!-}}=\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss^*_-\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_-$ with $\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_-=\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf x}}_2^{-0},-{\ensuremath{\mathbf x}}_1^0}$
\begin{align}
  \ensuremath{\lambda}_2(\ensuremath{{\ensuremath{\mathbf W}}_{\!-}})\geq \ensuremath{\sigma}_1^2(\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf x}}_2^-,-{\ensuremath{\mathbf x}}_1^0})=\ensuremath{\sigma}_-^2.
\end{align}
Inserting this in \eqref{eq:CinW} gives
\begin{align}
  C\leq 2N\left(\frac{23N^2}{\ensuremath{\sigma}^2 \ensuremath{\sigma}_-} \!+\! \frac{1}{\ensuremath{\sigma}^2}\! +\!\frac{4\sqrt{2}}{\ensuremath{\sigma}_-}  \right)
  \!=\!2N\frac{23N^2\! +\! \ensuremath{\sigma}_-\! +\! 4\sqrt{2}\ensuremath{\sigma}^2}{\ensuremath{\sigma}^2\ensuremath{\sigma}_-}.\notag
\end{align}
Using the bounds in \lemref{lem:sigclassic} we get
\begin{align}
  1\geq \ensuremath{\sigma} &\geq |\ensuremath{\tilde{x}}_{1,0}|^{{{L}_1}} |\ensuremath{\tilde{x}}_{2,0}|^{{{L}_2}} \ensuremath{\delta}^{{{L}_1}{{L}_2}}\\
   1\geq\ensuremath{\sigma}_-&\geq  |\ensuremath{\tilde{x}}_{1,0}|^{{{L}_1}} |\ensuremath{\tilde{x}}_{2,{{L}_2}-1}|^{{{L}_2}} \ensuremath{\delta}_-^{{{L}_1}{{L}_2}}
\end{align}
and with $\ensuremath{\sigma}_-+4\sqrt{2}\ensuremath{\sigma}^2\leq 7\leq N^2$ for $N\geq 4$, this yields to
\begin{flalign}
&&  C\leq 48N^3\ensuremath{\sigma}^{-2}\ensuremath{\sigma}_-^{-1} && \qed\notag
\end{flalign}

\subsection{Singular Value Estimates of Sylvester Matrices}\label{app:sylvestereigenvalue}

Let us conclude this section with a eigenvalue lower bound. If ${\ensuremath{\mathbf a}}\in{\ensuremath{\mathbb C}}^{n}_{0,0}$ and
${\ensuremath{\mathbf b}}\in{\ensuremath{\mathbb C}}^{m}_{0,0}$ then the first and last coefficient of ${\ensuremath{\mathbf a}}$ and ${\ensuremath{\mathbf b}}$ are non-vanishing. Hence,
${\ensuremath{\mathrm a}},{\ensuremath{\mathrm b}}$ are full degree polynomials with non-vanishing zeros (roots).
If $\ensuremath{{\ensuremath{\mathrm a}}^-}$ and $\ensuremath{{\ensuremath{\mathrm b}}^-}$ are co-prime, i.e., share no common zeros, then their resultant,  given by
\begin{align}
  \det \ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf a}},{\ensuremath{\mathbf b}}}\!=\!  b_0^{n\!-\!1}\prod_{l=1}^{m\!-\!1}\ensuremath{{\ensuremath{\mathrm a}}^-}(\ensuremath{\beta}_l)
  &\!\!\overset{\eqref{eq:uaminusfac}}{=}
  a_{0}^{m\!-\!1} b_{0}^{n\!-\!1}\prod_{l=1}^{m-1} \prod_{k=1}^{n-1} (\ensuremath{\beta}_l\! -\!\ensuremath{\alpha}_k)\label{eq:detsab}
\end{align}
is non-vanishing and the $N\!-\!2\times N\!-\!2$ Sylvester matrix $\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf a}},{\ensuremath{\mathbf b}}}$ has full rank, see for example
\cite[Thm.1]{BL09} and \cite[Sec.9.2]{Zip93}.
If we  append a zero to the vector ${\ensuremath{\mathbf a}}$ denoted by ${\ensuremath{\mathbf a}}^0$, see \eqref{eq:xaddzero}, the corresponding polynomial
${\ensuremath{\mathrm a}}^0(z)$ has order $n$
\begin{align}
  {\ensuremath{\mathrm a}}^0(z)&=\sum_{k=0}^{n} a_{n\!-\!k}^0 z^k = z\sum_{k=0}^{n-1} a_{n\!-\!1\!-\!k} z^k =z \prod_{k=1}^{n} (z-\ensuremath{\alpha}_k)
\end{align}
and the zeros $\ensuremath{\alpha}_k$ of ${\ensuremath{\mathrm a}}$ are the non vanishing zeros of ${\ensuremath{\mathrm a}}^0$. We denote the vanishing zero by $\ensuremath{\alpha}^{0}_{n}=0$.
If we do the same for $\ensuremath{{\ensuremath{\mathrm b}}^-}$ then the only common factor of  ${\ensuremath{\mathrm a}}^0$ and ${\ensuremath{\mathrm b}}^0$ is $z$, and the determinant of the
$N\times N$ matrix $\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf a}}^0,{\ensuremath{\mathbf b}}^0}$ vanishes by \eqref{eq:detsab} since $\ensuremath{\alpha}_n^{0}=\ensuremath{\beta}_m^{0}=0$.  However, if we consider
the principal submatrix $\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf a}}^0,{\ensuremath{\mathbf b}}}$, which is given by erasing the last row and last column in $\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf a}}^0,{\ensuremath{\mathbf b}}^0}$,
then the determinant is non vanishing since ${\ensuremath{\mathrm a}}^0(z)$ and ${\ensuremath{\mathrm b}}(z)$ share no common factor and hence
\begin{align}
  \rank(\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf a}}^0,{\ensuremath{\mathbf b}}^0})=N-1 \ \ensuremath{\Leftrightarrow} \ \forall l,k\colon 0\not=\ensuremath{\alpha}_k\not=\ensuremath{\beta}_l\not=0\label{eq:sylvesterrank}
\end{align}

Let us now use \eqref{eq:detsab} to show a lower bound for the smallest singular value of the Sylvester matrix.
\begin{lemi}\label{lem:sigclassic}
Let ${\ensuremath{\mathbf a}}\in{\ensuremath{\mathbb C}}^{n+1}_{0}$ and ${\ensuremath{\mathbf b}}\in{\ensuremath{\mathbb C}}^{m+1}_{0}$ for $n,m\geq 1$ with $\Norm{{\ensuremath{\mathbf a}}}^2+\Norm{{\ensuremath{\mathbf b}}}^2=1$. If the zeros of ${\ensuremath{\mathrm a}}$ and ${\ensuremath{\mathrm b}}$
have a zero separation $\ensuremath{\delta}>0$ as defined in \eqref{eq:zeroseparationdel}, then it holds
\begin{align}
  1\geq\!\frac{\ensuremath{\sigma}_{n+m}(\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf a}},{\ensuremath{\mathbf b}}})}{\sqrt{n+m-1}}\!\geq\!  \ensuremath{\sigma}_1(\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf a}},{\ensuremath{\mathbf b}}})\geq |a_0|^m |b_0|^n \ensuremath{\delta}^{nm}.
\end{align}
\end{lemi}
\noindent {\it Proof. }
Since $\ensuremath{\delta}>0$ the polynomials ${\ensuremath{\mathrm a}}$ and ${\ensuremath{\mathrm b}}$ are coprime.  Hence the rank of $\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss=\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf a}},{\ensuremath{\mathbf b}}}$ is full and all
singular values $\ensuremath{\sigma}_k>0$. It is known that the absolute value of the determinate $\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss=\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf a}},{\ensuremath{\mathbf b}}}$ is the product of
its singular values
\begin{align}
  |\det\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss|= \prod_{k=1}^{n+m} \ensuremath{\sigma}_k (\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss).
\end{align}
Hence we get for the smallest singular value by \cite[Cor.3]{Gun07}
\begin{align}
  \ensuremath{\sigma}_1(\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss)\geq  \left(\frac{n+m-1}{\sNorm{\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss}^2}\right)^{\frac{n+m-1}{2}}\Betrag{\det(\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss)}.\label{eq:gun}
\end{align}
Since the Sylvester matrix is given by
\begin{align}
  \ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss=\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf a}},{\ensuremath{\mathbf b}}}=\begin{pmatrix} \ensuremath{\mathbf T}_{m,{\ensuremath{\mathbf a}}} & \ensuremath{\mathbf T}_{n,{\ensuremath{\mathbf b}}}\end{pmatrix}
\end{align}
we get for the Frobenius norm
\begin{align}
  \sNorm{\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss}^2&=\tr(\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss^*\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss)=\tr\begin{pmatrix} \ensuremath{\mathbf T}_{m,{\ensuremath{\mathbf a}}}^*\ensuremath{\mathbf T}_{m,{\ensuremath{\mathbf a}}} & \ensuremath{\mathbf T}_{m,{\ensuremath{\mathbf a}}}^*\ensuremath{\mathbf T}_{n,{\ensuremath{\mathbf b}}}\\
    \ensuremath{\mathbf T}_{n,{\ensuremath{\mathbf b}}}^*\ensuremath{\mathbf T}_{m,{\ensuremath{\mathbf a}}} & \ensuremath{\mathbf T}_{m,{\ensuremath{\mathbf a}}}^* \ensuremath{\mathbf T}_{m,{\ensuremath{\mathbf a}}}\end{pmatrix}\notag\\
  &\!\!\overset{\eqref{eq:convTopelitzproduct}}{=}\tr(\ensuremath{\mathbf T}_{m,{\ensuremath{\mathbf a}}*\sxbar{{\ensuremath{\mathbf a}}\rule{-1.2ex}{1.4ex}^{_{\ -}}}})+\tr(\ensuremath{\mathbf T}_{n,{\ensuremath{\mathbf b}}*\sxbar{{\ensuremath{\mathbf b}} \rule{-1.2ex}{1.4ex}^{_{\ -}}}})\notag\\
  &=
  m\Norm{{\ensuremath{\mathbf a}}}_2^2 + n\Norm{{\ensuremath{\mathbf b}}}_2^2 \leq \max\{n,m\}(\Norm{{\ensuremath{\mathbf a}}}^2 + \Norm{{\ensuremath{\mathbf b}}}^2 \notag\\
  &\leq \max\{n,m\}\leq n+m-1.\label{eq:frobeniusnormS}
\end{align}
Since $\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss$ has full rank we get $\sNorm{\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss}^2=\sum_{k=1}^{n+m} \ensuremath{\sigma}_k^2\geq (n+m)\ensuremath{\sigma}_1^2$ and hence with
\eqref{eq:frobeniusnormS} the upper bound for $\ensuremath{\sigma}_1$. Furthermore, $n+m-1$ is also an upper bound for $\ensuremath{\sigma}_{max}^2$.
Moreover, we get with \eqref{eq:gun} the lower bound
\begin{flalign}
  &&\ensuremath{\sigma}_1(\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss)\geq |\det(\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss)| \geq |a_0|^m |b_0|^n \ensuremath{\delta}^{nm}&& \qed\notag
\end{flalign}

\renewcommand{\ensuremath{\alpha}}{\ensuremath{\alpha}}
\renewcommand{\ensuremath{\boldsymbol{ \alp}}}{\ensuremath{\ensuremath{\boldsymbol} \alpha}}
\subsection{Alternative bound for the smallest singular value of the Sylvester Matrix}

If there is separate knowledge of the zero structure of ${\ensuremath{\mathrm x}}_1$ and ${\ensuremath{\mathrm x}}_2$ this can lead to tighter bounds.
\begin{lemi}
  Let ${\ensuremath{\mathbf a}}\in{\ensuremath{\mathbb C}}^{n+1}_0,{\ensuremath{\mathbf b}}\in{\ensuremath{\mathbb C}}^{m+1}_0$ as in \lemref{lem:sigclassic}, then
  %
  \begin{align}
    \ensuremath{\sigma}_1(\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf a}},{\ensuremath{\mathbf b}}})&\geq \frac{\ensuremath{\delta}^{N\!-\!1}|a_0b_0|}{N^2}\cdot \frac{\min\{(a/2)^{n-1},(b/2)^{m-1}\}}{a^{1-N}+b^{1-N}}
  \end{align}
  %
  where $N=n+m$, $\ensuremath{\delta}>0$ and
  %
  \begin{align}
  a&=\frac{|a_0|}{|a_0|+1}\quad,\quad b=\frac{|b_0|}{|b_0|+1}.
\end{align}
\end{lemi}
\noindent{\it Proof. }
Let ${\ensuremath{\mathbf a}}\in{\ensuremath{\mathbb C}}_0^{n+1}$ and ${\ensuremath{\mathbf b}} \in{\ensuremath{\mathbb C}}_0^{m+1}$ for $n,m\in{\ensuremath{\mathbb N}}$. Then it holds for the Sylvester matrix and any
$\ensuremath{\lambda}\in{\ensuremath{\mathbb C}}$
\begin{align}
\setlength\arraycolsep{2pt}
  &\begin{pmatrix}1  & \ensuremath{\lambda} & \dots \ \ensuremath{\lambda}^{N\!-\!1}\end{pmatrix} \ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf a}},{\ensuremath{\mathbf b}}}\label{eq:lamnotation}\\
  & \quad =
  \setlength\arraycolsep{1.5pt}
  \begin{pmatrix}{\ensuremath{\mathrm a}}(\ensuremath{\lambda}) & \ensuremath{\lambda} {\ensuremath{\mathrm a}}(\ensuremath{\lambda}) & \dots \ensuremath{\lambda}^n {\ensuremath{\mathrm a}}(\ensuremath{\lambda}) & \ensuremath{\lambda}^{n\!+\!1} {\ensuremath{\mathrm b}}(\ensuremath{\lambda}) \ \dots \
     \ensuremath{\lambda}^{N\!-\!1} {\ensuremath{\mathrm b}}(\ensuremath{\lambda})\end{pmatrix}\notag
\end{align}
with $N=n+m$.
Let us introduce the zero vector
\begin{align}
  \ensuremath{\boldsymbol{ \zet}} = \begin{pmatrix}\ensuremath{\boldsymbol{ \bet}} \\ \ensuremath{\boldsymbol{ \alp}}\end{pmatrix}\in{\ensuremath{\mathbb C}}^N
\end{align}
where $\ensuremath{\alpha}_k$ and $\ensuremath{\beta}_l$ are the zeros of ${\ensuremath{\mathrm a}}(z)$ respectively ${\ensuremath{\mathrm b}}(z)$ as in \eqref{eq:uaminusfac}.
Let us define the $N\times N$ Vandermonde matrix
\begin{align}
  {\ensuremath{\mathbf V}}_{\ensuremath{\boldsymbol{ \zet}}}  \!= \!
  \setlength\arraycolsep{1.8pt}
  \begin{pmatrix}
    \begin{bmatrix}
    \setlength\arraycolsep{2pt}
    1 & \ensuremath{\beta}_1 &  \dots & \ensuremath{\beta}_1^n\\
    1 & \ensuremath{\beta}_2 &  \dots & \ensuremath{\beta}_2^n\\
    \vdots &  & &  \vdots \\
    1 & \ensuremath{\beta}_m & \dots & \ensuremath{\beta}_m^n\\
  \end{bmatrix}
  & \begin{bmatrix}
  \setlength\arraycolsep{2pt}
    \ensuremath{\beta}_1^{n+1} & \ensuremath{\beta}_1^{n+2}  & \dots & \ensuremath{\beta}_1^{n\!+\!m\!-\!1}\\
    \ensuremath{\beta}_2^{n+1} & \ensuremath{\beta}_2^{n+2}  & \dots & \ensuremath{\beta}_2^{n\!+\!m\!-\!1}\\
     \vdots & \vdots & &   \vdots \\
     \ensuremath{\beta}_m^{n+1} & \ensuremath{\beta}_m^{n+2}  & \dots & \ensuremath{\beta}_m^{n\!+\!m\!-\!1}\\
  \end{bmatrix}\\
  %
  \begin{bmatrix}
  1 & \ensuremath{\alpha}_1 &  \dots & \ensuremath{\alpha}_1^n\\
  1 & \ensuremath{\alpha}_2 &  \dots & \ensuremath{\alpha}_2^n\\
  \vdots &  &   \vdots \\
  1 & \ensuremath{\alpha}_n & \dots & \ensuremath{\alpha}_n^n\\
  \end{bmatrix}
  & \begin{bmatrix}
  \ensuremath{\alpha}_1^{n+1} & \ensuremath{\alpha}_1^{n+2}  & \dots & \ensuremath{\alpha}_1^{n\!+\!m\!-\!1}\\
  \ensuremath{\alpha}_2^{n+1} & \ensuremath{\alpha}_2^{n+2}  & \dots & \ensuremath{\alpha}_2^{n\!+\!m\!-\!1}\\
  \vdots & \vdots & &   \vdots \\
  \ensuremath{\alpha}_n^{n+1} & \ensuremath{\alpha}_n^{n+2}  & \dots & \ensuremath{\alpha}_n^{n\!+\!m\!-\!1}\\
  \end{bmatrix}\\
 \end{pmatrix}
\end{align}
generated by the node vector $\ensuremath{\boldsymbol{ \zet}}$.
Hence, setting $\ensuremath{\boldsymbol{ \lam}}=\ensuremath{\boldsymbol{ \zet}}$ we get from the  observation \eqref{eq:lamnotation}
\begin{align}
  {\ensuremath{\mathbf V}}_{\!\ensuremath{\boldsymbol{ \zet}}}\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf a}}{\ensuremath{\mathbf b}}}\!=\! {\ensuremath{\mathbf D}} {\ensuremath{\mathbf V}}_{\!\ensuremath{\boldsymbol{ \alp}},\ensuremath{\boldsymbol{ \bet}}}
 \! =\!\!
 \setlength\arraycolsep{1pt}
 \begin{pmatrix} {\ensuremath{\mathbf D}}_{{\ensuremath{\mathrm a}}(\ensuremath{\boldsymbol{ \bet}})} & {\ensuremath{\mathbb 0}} \\ {\ensuremath{\mathbb 0}} &\! {\ensuremath{\mathbf D}}_{{\ensuremath{\mathrm b}}(\ensuremath{\boldsymbol{ \alp}})}\end{pmatrix}
  \!\begin{pmatrix}
    {\ensuremath{\mathbf V}}_{\!\ensuremath{\boldsymbol{ \bet}}} & {\ensuremath{\mathbb 0}}\\
    {\ensuremath{\mathbb 0}} &{\ensuremath{\mathbf V}}_{\!\ensuremath{\boldsymbol{ \alp}}}
  \end{pmatrix}\label{eq:sylvestervandermonde}
\end{align}
where ${\ensuremath{\mathbf D}}={\ensuremath{\mathbf D}}_{{\ensuremath{\mathrm a}}(\ensuremath{\boldsymbol{ \bet}}),{\ensuremath{\mathrm b}}(\ensuremath{\boldsymbol{ \alp}})}$ is a diagonal matrix generated by evaluating the polynomials at the other
zeros and ${\ensuremath{\mathbf V}}_{\ensuremath{\boldsymbol{ \alp}}}$ and ${\ensuremath{\mathbf V}}_{\ensuremath{\boldsymbol{ \bet}}}$ are $n\times n$ resp. $m\times m$ Vandermonde matrices
\begin{align}
\setlength\arraycolsep{1pt}
  {\ensuremath{\mathbf D}}_{{\ensuremath{\mathrm b}}(\ensuremath{\boldsymbol{ \alp}})}\!=\!\begin{pmatrix}
    {\ensuremath{\mathrm b}}(\ensuremath{\alpha}_1) & 0 & \dots & 0\\
    0 & {\ensuremath{\mathrm b}}(\ensuremath{\alpha}_2) & \dots & 0\\
    \vdots &  & \ddots & \vdots\\
    0 & 0 & \dots & {\ensuremath{\mathrm b}}(\ensuremath{\alpha}_n)
  \end{pmatrix},\quad
  {\ensuremath{\mathbf V}}_{\ensuremath{\boldsymbol{ \alp}}}\!=\!
  \setlength\arraycolsep{1pt}
  \begin{pmatrix}
    1 & \ensuremath{\alpha}_1 & \dots & \ensuremath{\alpha}_1^n\\
    1 & \ensuremath{\alpha}_2 & \dots & \ensuremath{\alpha}_2^n\\
    \vdots & \vdots &  & \vdots\\
    1 & \ensuremath{\alpha}_n & \dots & \ensuremath{\alpha}_n^n\\
  \end{pmatrix}.\notag
\end{align}
Note, ${\ensuremath{\mathbf D}}{\ensuremath{\mathbf V}}_{\ensuremath{\boldsymbol{ \alp}},\ensuremath{\boldsymbol{ \bet}}}$ is not Hermitian. Taking the determinant of both sides in \eqref{eq:sylvestervandermonde} gives
\begin{align}
  \begin{split}
&\quad\quad\quad  \det({\ensuremath{\mathbf V}}_{\ensuremath{\boldsymbol{ \zet}}}\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf a}},{\ensuremath{\mathbf b}}}) = \det({\ensuremath{\mathbf D}} {\ensuremath{\mathbf V}}_{\ensuremath{\boldsymbol{ \alp}},\ensuremath{\boldsymbol{ \bet}}})\\
&\ensuremath{\Leftrightarrow}  \quad \det({\ensuremath{\mathbf V}}_{\ensuremath{\boldsymbol{ \zet}}}) \det(\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf a}},{\ensuremath{\mathbf b}}})= \det ({\ensuremath{\mathbf D}})\det({\ensuremath{\mathbf V}}_{\ensuremath{\boldsymbol{ \alp}}})\det ({\ensuremath{\mathbf V}}_{\ensuremath{\boldsymbol{ \bet}}})
\end{split}
\end{align}
By using the well-known determinant formula for Vandermonde matrices, see \cite[Ch. IX, Exc.6]{LB99}, we have the
equivalence
\begin{align}
  & \det (\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf a}},{\ensuremath{\mathbf b}}\!})\!\!\!\!\prod_{1\leq l<k}^{n+m}\! \!\!(\ensuremath{\zeta}_k\!-\!\ensuremath{\zeta}_l)
  \!=\!\!\prod_{l,k=1}^{m,n} \!\!\!{\ensuremath{\mathrm a}}(\ensuremath{\beta}_l) {\ensuremath{\mathrm b}}(\ensuremath{\alpha}_k)\! \!\prod_{k<k'}^n\!\! (\ensuremath{\alpha}_k\!-\!\ensuremath{\alpha}_{k'})\!\prod_{l<l'}^m
  \!(\ensuremath{\beta}_{l}\!-\!\ensuremath{\beta}_{l'})\notag\\
  &\ensuremath{\Leftrightarrow}  \quad  \det(\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf a}},{\ensuremath{\mathbf b}}})\prod_{1\leq l<k}^{n+m} (\ensuremath{\zeta}_k-\ensuremath{\zeta}_l)
  =a_{0}^m b_0^n \prod_{k,l=1}^{m,n} (\ensuremath{\beta}_l\!-\!\ensuremath{\alpha}_k) \notag\\
  &\quad\quad\quad\quad\cdot \underbrace{\prod_{l,k=1}^{n,m} (\ensuremath{\alpha}_k-\ensuremath{\beta}_l)
  \prod_{k<k'}^n (\ensuremath{\alpha}_k-\ensuremath{\alpha}_{k'})\prod_{l<l'}^m(\ensuremath{\beta}_{l}\!-\!\ensuremath{\beta}_{l'})}_{=\ensuremath{\Delta}}\notag \\
  &\ensuremath{\Leftrightarrow}  \quad  \det(\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf a}},{\ensuremath{\mathbf b}}}) \cdot \ensuremath{\Delta}
  = a_{0}^m b_0^n\prod_{l,k=1}^{m,n} (\ensuremath{\beta}_l-\ensuremath{\alpha}_k) \cdot \ensuremath{\Delta}
  \end{align}
Where $\ensuremath{\Delta}\not=0$ if and only if all zeros are simple and ${\ensuremath{\mathrm a}}$ and ${\ensuremath{\mathrm b}}$ are coprime. If this holds, we can resolve for
the determinant
\begin{align}
  \det(\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf a}},{\ensuremath{\mathbf b}}})= a_0^m b_0^n \prod_{k,l=1}^{m,n}(\ensuremath{\beta}_k-\ensuremath{\alpha}_l)
\end{align}
which proofs \eqref{eq:detsab} if all zeros are simple.  On the other hand we can compute directly from the relation
\eqref{eq:sylvestervandermonde} for any $N\times N$ matrices
\begin{align}
  \begin{split}
  \sNorm{{\ensuremath{\mathbf V}}_{\ensuremath{\boldsymbol{ \zet}}}}_{\infty} \ensuremath{\sigma}_{1}(\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf a}},{\ensuremath{\mathbf b}}}) &\geq\ensuremath{\sigma}_{1} ({\ensuremath{\mathbf V}}_{\ensuremath{\boldsymbol{ \zet}}}\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf a}},{\ensuremath{\mathbf b}}})
  = \ensuremath{\sigma}_1 ({\ensuremath{\mathbf D}} {\ensuremath{\mathbf V}}_{\ensuremath{\boldsymbol{ \alp}},\ensuremath{\boldsymbol{ \bet}}})\\
  &\geq \ensuremath{\sigma}_1({\ensuremath{\mathbf V}}_{\ensuremath{\boldsymbol{ \alp}},\ensuremath{\boldsymbol{ \bet}}})\ensuremath{\sigma}_{1}({\ensuremath{\mathbf D}})
\end{split}
\end{align}
where the first inequality holds by%
\footnote{Note, in Bahtia, the singular values are in decreasing order, i.e., $\ensuremath{\sigma}_1\geq \ensuremath{\sigma}_2\geq \dots\geq
  \ensuremath{\sigma}_r\geq \ensuremath{\sigma}_{r+1}=0=\dots =\ensuremath{\sigma}_n$.}
  \cite[Probl.III.6.2]{Bha96} and the last  by \cite[Thm.9]{MK04b} if ${\ensuremath{\mathbf D}}$ and ${\ensuremath{\mathbf V}}_{\ensuremath{\boldsymbol{ \alp}},\ensuremath{\boldsymbol{ \bet}}}$ are booth
non-singular.  Since both are block diagonal matrices we get further
\begin{align}
 \ensuremath{\sigma}_1({\ensuremath{\mathbf V}}_{\!\ensuremath{\boldsymbol{ \alp}},\ensuremath{\boldsymbol{ \bet}}})\ensuremath{\sigma}_{1}({\ensuremath{\mathbf D}})
 \!\geq\!\min\{\ensuremath{\sigma}_{1}({\ensuremath{\mathbf V}}_{\!\ensuremath{\boldsymbol{ \alp}}}),\ensuremath{\sigma}_1({\ensuremath{\mathbf V}}_{\!\ensuremath{\boldsymbol{ \bet}}})\}
\cdot \ensuremath{\delta}^{N\!-\!1}|a_0b_0|
\end{align}
where we used $\min\{|a_0|,|b_0|\}\geq |a_0|\cdot|b_0|$
since $|a_0|,|b_0|\leq 1$.
For the lower bound of the smallest and
largest singular values of Vandermonde matrices we can use bounds derived and referenced in \cite{AB17}.
Hence we get
\begin{align}
  \ensuremath{\sigma}_1(\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf a}},{\ensuremath{\mathbf b}}})&\geq \ensuremath{\delta}^{N\!-\!1}|a_0b_0|\cdot \sNorm{{\ensuremath{\mathbf V}}_{\ensuremath{\boldsymbol{ \zet}}}}_{\infty}^{-1}\cdot
  \min\{\ensuremath{\sigma}_{1}({\ensuremath{\mathbf V}}_{\ensuremath{\boldsymbol{ \alp}}}),\ensuremath{\sigma}_1({\ensuremath{\mathbf V}}_{\ensuremath{\boldsymbol{ \bet}}})\}\notag\\
  &\geq \frac{\ensuremath{\delta}^{N\!-\!1}|a_0b_0|}{N}\cdot\ensuremath{\Gamma}_1\cdot\ensuremath{\Gamma}_2
\end{align}
where
\begin{align}
  \ensuremath{\Gamma}_1\!&=\!\Big( \max\{\sum_{k=1}^N |\ensuremath{\zeta}_k|^{N-1}, N\}\Big)^{-1}\\
  \ensuremath{\Gamma}_2\!&=\! \min
  \left\{\max_k \!\!\prod_{k\not=k'=1}^n \!\!\!\frac{\max\{1,|\ensuremath{\alpha}_{k'}|\}}{|\ensuremath{\alpha}_k-\ensuremath{\alpha}_{k'}|}
  ,\max_l\!\!\prod_{l\not=l'=1}^m\!\!\!
  \frac{\max\{1,|\ensuremath{\beta}_{l'}|\}}{|\ensuremath{\beta}_{l'}-\ensuremath{\beta}_l|}\right\}\notag
\end{align}
We need lower and upper bounds for the smallest and largest zero in magnitude. Since the coefficient vectors are
normalized we get
\begin{align}
  \max_{k\not=l} |\ensuremath{\alpha}_k -\ensuremath{\alpha}_l|\leq 2 (1+\frac{\Norm{{\ensuremath{\mathbf a}}}}{|a_0|})\leq 2\Big(\frac{1+|a_0|}{|a_0|}\Big)
\end{align}
see for example \cite[Thm.2]{KS91}, and similar for ${\ensuremath{\mathrm b}}$.
Then we get
\begin{align}
  \ensuremath{\Gamma}_1 &\geq \frac{1}{N-1}\frac{1}{a^{1-N} + b^{1-N}} \\
  \ensuremath{\Gamma}_2 &\geq \min\Big\{ (a/2)^{n-1} ,(b/2)^{m-1}\Big\}
  \intertext{where}
  a&=\frac{|a_0|}{|a_0|+1}\quad,\quad b=\frac{|b_0|}{|b_0|+1}
\end{align}
are less than $1/2$.
Hence we get
\begin{flalign*}
&&  \ensuremath{\sigma}_1(\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf a}},{\ensuremath{\mathbf b}}})&\geq \frac{\ensuremath{\delta}^{N\!-\!1}|a_0b_0|}{N^2}\cdot
  \frac{\min\{(a/2)^{n-1},(b/2)^{m-1}\}}{a^{1-N}+b^{1-N}} && \qed
\end{flalign*}
\begin{remark}
  The singular value bounds of the Vandermonde matrices used in this proof are very weak since they include all worst
  cases. If there is more structure known about the zeros of ${\ensuremath{\mathrm x}}_1$ and ${\ensuremath{\mathrm x}}_2$ much tighter bounds are available, for
  example, if all nodes of $\ensuremath{\boldsymbol{ \alp}}$ are lying uniform on the unit circle. Such insights also may lead to signal designs
  where deconvolution is guaranteed to be stable or unstable.
\end{remark}

\section{Dual Certificate}\label{sec:dualcertificate}
To show that ${\ensuremath{\mathbf W}}=\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf x}}_2^0,-{\ensuremath{\mathbf x}}_1^0}\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf x}}_2^0,-{\ensuremath{\mathbf x}}_1^0}$ defines a dual certificate we need to show the following
three properties
\begin{enumerate}[(i)]
  \item ${\ensuremath{\mathbf W}}\succeq 0$
  \item ${\ensuremath{\mathbf W}}{\ensuremath{\mathbf x}}=0$
  \item $\rank({\ensuremath{\mathbf W}})=N-1$
\end{enumerate}
see also \cite{Jag16,JH16,WJPH17}.  By definition ${\ensuremath{\mathbf W}}$ is already positive semi-definite and ${\ensuremath{\mathbf W}}{\ensuremath{\mathbf x}}=0$ by observing
the commutative property of the convolution ${\ensuremath{\mathbf x}}_2*{\ensuremath{\mathbf x}}_1-{\ensuremath{\mathbf x}}_1*{\ensuremath{\mathbf x}}_2={\ensuremath{\mathbf 0}}$ in \eqref{eq:convdiff}. The last property
follows finally by the Sylvester Theorem due to the co-prime condition of ${\ensuremath{\mathrm x}}_1$ and ${\ensuremath{\mathrm x}}_2$ in
\eqref{eq:sylvesterrank}.  The missing injectivity property for the uniqueness result of \thmref{thm:4correlation}
follows then from the local stability result \lemref{lem:localstab}.

\begin{figure*}[!t]
  \begin{subfigure}[b]{0.99\textwidth}
  \centering
     \includegraphics[width=1\textwidth]{CorrelationMatrix_nm}

     \label{fig:ToeplitzCorrelation}
     \vspace{-1em}
  \end{subfigure}
  \caption{Correlation between the vectors ${\ensuremath{\mathbf a}}\in{\ensuremath{\mathbb C}}^{n}$ and ${\ensuremath{\mathbf b}}\in{\ensuremath{\mathbb C}}^{m}$.}
  \label{fig:Toeplitzoperation}
\end{figure*}
The adjoint operator  of ${\ensuremath{\mathcal{A}}}$ in \eqref{eq:4maskmeasurements} is the linear map
\begin{align}
  {\ensuremath{\mathcal{A}}}^*\colon {\ensuremath{\mathbb C}}^M \to {\ensuremath{\mathbb C}}^{N\times N}
\end{align}
which is defined for every
$\ensuremath{\boldsymbol{ \lam}}\in{\ensuremath{\mathbb C}}^M, {\ensuremath{\mathbf X}}\in{\ensuremath{\mathbb C}}^{N\times N}$ as
\begin{align}
  \skprod{{\ensuremath{\mathcal{A}}}^*(\ensuremath{\boldsymbol{ \lam}})}{{\ensuremath{\mathbf X}}}&=\skprod{\ensuremath{\boldsymbol{ \lam}}}{{\ensuremath{\mathcal{A}}}({\ensuremath{\mathbf X}})}=\skprod{\ensuremath{\boldsymbol{ \lam}}}{\ve_m \tr({\ensuremath{\mathbf A}}_m{\ensuremath{\mathbf X}}^*)}\label{eq:Alinadjoint}\\
  &=\skprod{\ensuremath{\boldsymbol{ \lam}}}{\ve_m\skprod{{\ensuremath{\mathbf X}}}{{\ensuremath{\mathbf A}}_m}}=\skprod{\sum_m \ensuremath{\lambda}_m {\ensuremath{\mathbf A}}_m}{{\ensuremath{\mathbf X}}}\notag
\end{align}
where the matrices ${\ensuremath{\mathbf A}}_m$ are given by ${\ensuremath{\mathbf A}}_{i,j,k}$ in \eqref{eq:3Nb} in lexicographical order.
Since this holds for all ${\ensuremath{\mathbf X}}\in{\ensuremath{\mathbb C}}^{N\times N}$ we get
\begin{align}
  \range({\ensuremath{\mathcal{A}}}^*):=\spann\{{\ensuremath{\mathbf A}}_0,\dots,{\ensuremath{\mathbf A}}_{M-1}\}.
\end{align}
To show that the Sylvester matrix product ${\ensuremath{\mathbf W}}$ in \eqref{eq:dualcertif} corresponds to the dual certificate of our
measurements, we need hence to find the corresponding vector $\ensuremath{\boldsymbol{ \lam}}$. To see this, we have to represent ${\ensuremath{\mathbf W}}$ in
terms of the measurements.

If we consider the product of the adjoint Sylvester matrix with itself we get by \eqref{eq:dualcertif} and
\eqref{eq:sylvesterx}
\begin{align}
\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf x}}_2^0,-{\ensuremath{\mathbf x}}_1^0}^* \ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf x}}_2^0,-{\ensuremath{\mathbf x}}_1^0}
&=
  \setlength\arraycolsep{3pt}
  \begin{pmatrix}   \ensuremath{\mathbf T}_{1,{\ensuremath{\mathbf x}}_2}^* & {\ensuremath{\mathbf 0}} \\ -\ensuremath{\mathbf T}_{2,{\ensuremath{\mathbf x}}_1}^* & {\ensuremath{\mathbf 0}} \end{pmatrix}
  \begin{pmatrix}   \ensuremath{\mathbf T}_{1,{\ensuremath{\mathbf x}}_2} & -\ensuremath{\mathbf T}_{2,{\ensuremath{\mathbf x}}_1} \\ {\ensuremath{\mathbf 0}}^T & {\ensuremath{\mathbf 0}}^T\end{pmatrix} \notag \\
&=
\setlength\arraycolsep{3pt}
\begin{pmatrix}
  \ensuremath{\mathbf T}_{1,{\ensuremath{\mathbf x}}_2}^*\ensuremath{\mathbf T}_{1,{\ensuremath{\mathbf x}}_2}  & -\ensuremath{\mathbf T}_{1,{\ensuremath{\mathbf x}}_2}^*\ensuremath{\mathbf T}_{2,{\ensuremath{\mathbf x}}_1}\\
  -\ensuremath{\mathbf T}_{2,{\ensuremath{\mathbf x}}_1}^*\ensuremath{\mathbf T}_{1,{\ensuremath{\mathbf x}}_2} & \ensuremath{\mathbf T}_{2,{\ensuremath{\mathbf x}}_1}^*\ensuremath{\mathbf T}_{2,{\ensuremath{\mathbf x}}_1}\\
\end{pmatrix}\label{eq:sylvesterrangestar}
\end{align}
see \figref{fig:Toeplitzoperation}. Let $i,j,i',j'\in\{1,2\}$ with $i+j=i'+j'$,
then we set $\ensuremath{{N_{ij}}}=\ensuremath{{N_i}}+\ensuremath{{N_j}}=\ensuremath{N_{i'}}+\ensuremath{N_{j'}}$ (we have $N_{1,2}=N$), we get with \eqref{eq:Tform} for the banded Toeplitz products
and the embedding matrix notation in \eqref{eq:elementtoeplitz}

\begin{align}
  \ensuremath{\mathbf T}_{j,{\ensuremath{\mathbf x}}_i^0}^*\ensuremath{\mathbf T}_{j',{\ensuremath{\mathbf x}}_{i'}^0}\!&=\ensuremath{\mathbf T}_{\ensuremath{{N_j}},{\ensuremath{\mathbf x}}_i^0}^*\ensuremath{\mathbf T}_{\ensuremath{N_{j'}},{\ensuremath{\mathbf x}}_{i'}^0} \\
&= \sum_{m=0}^{\ensuremath{{N_i}}-1} \sum_{l=0}^{\ensuremath{N_{i'}}-1}\cc{x_{i,m}} x_{i',l}{\mathbf \Pi}_{i+j,j}^T \ensuremath{\mathbf T}_{\ensuremath{{N_{ij}}}}^{-m}
\ensuremath{\mathbf T}_{\ensuremath{{N_{ij}}}}^{l}{\mathbf \Pi}_{i+j,j}\notag\\
    &=\! \sum_{m=0}^{\ensuremath{{N_i}}-1} \!\sum_{l=0}^{\ensuremath{N_{i'}}-1}\cc{x_{i,m}} x_{i',l}{\mathbf \Pi}_{i+j,j}^T \ensuremath{\mathbf T}^{l-m}_{\ensuremath{{N_{ij}}}}
    {\mathbf \Pi}_{i+j,j'}.\notag
\end{align}
Let us emphasize that $l,m$ are limited by $\ensuremath{{N_i}}\!-\!1$ resp. $\ensuremath{N_{i'}}\!-\!1$, and since we consider the $\ensuremath{{N_i}}$ resp. $\ensuremath{N_{i'}}$
embeddings the zeros on the $l-m$th diagonal in $\ensuremath{\mathbf T}^{l-m}_{\ensuremath{{N_{ij}}}}$ can be ignored. By substituting with $k=l-m$ we get
\begin{align}
  \!\!\ensuremath{\mathbf T}_{\!j,{\ensuremath{\mathbf x}}_i^0}^*\!\ensuremath{\mathbf T}_{\!j'\!,{\ensuremath{\mathbf x}}_{i'}^0}\!\!  &=\!\!\sum_{k=-\ensuremath{{N_i}}+1}^{\ensuremath{N_{i'}}-1}\!\!\!\Big(\sum_{m=0}^{\ensuremath{{N_i}}-1} \cc{x_{i,m}}
  x_{i',k+m}\!\Big) {\mathbf \Pi}_{i+j,j}^T\ensuremath{\mathbf T}_{\ensuremath{{N_{ij}}}}^{k}{\mathbf \Pi}_{i+j,j'}\notag
\intertext{where we set $x_{i,k}=0$ for $k<0$ or $k\geq N_i$. Bringing $m$ on the other side by substituting $m'=m+k$ gets}
  &=\!\!\sum_{k=1\!-\!\ensuremath{{N_i}}}^{\ensuremath{N_{i'}}-1}\!\!\!\Big(\!\sum_{m'=k}^{\ensuremath{{N_i}}-1+k}\!\! \!\cc{x_{i,m'-k}} x_{i',m'}\!\Big)
  {\mathbf \Pi}_{i+j,j}^T\ensuremath{\mathbf T}^{k}_{\ensuremath{{N_{ij}}}}{\mathbf \Pi}_{i+j,j'}\notag\\
  &=\!\!\sum_{k=-\ensuremath{{N_i}}\!+\!1}^{\ensuremath{N_{i'}}-1}\!\! \!\!({\ensuremath{\mathbf x}}_{i'}\!*\!\xbar{{\ensuremath{\mathbf x}}_i \rule{-0.9ex}{1.6ex}^{_{\scriptstyle -}}})_{\ensuremath{{N_i}}\!-\!1\!+\!k}
  {\mathbf \Pi}_{i\!+\!j,j}^T\ensuremath{\mathbf T}^{k}_{\!\ensuremath{{N_{ij}}}}{\mathbf \Pi}_{i\!+\!j,j'}
\intertext{where the inner  sum is the correlation between ${\ensuremath{\mathbf x}}_{i'}$ and ${\ensuremath{\mathbf x}}_{i}$. Using the matrix notation
$\ensuremath{\mathbf T}_{\ensuremath{{N_j}},\ensuremath{N_{j'}}}^{(k)}$ defined in \eqref{eq:LiLj} we get}
  &=\!\sum_{k=0}^{N_{ii'}-2}\! ({\ensuremath{\mathbf x}}_{i'} * \xbar{{\ensuremath{\mathbf x}}_i \rule{-0.9ex}{1.6ex}^{_{\scriptstyle -}}})_k \ensuremath{\mathbf T}_{\ensuremath{{N_j}},\ensuremath{N_{j'}}}^{(k)}
\end{align}
such that we have
\begin{align}
  \ensuremath{\mathbf T}_{j,{\ensuremath{\mathbf x}}_i^0}^*\!\ensuremath{\mathbf T}_{j',{\ensuremath{\mathbf x}}_{i'}^0}\!=\!
  \ensuremath{\mathbf T}_{j,{\ensuremath{\mathbf x}}_i}^*\!\ensuremath{\mathbf T}_{j',{\ensuremath{\mathbf x}}_{i'}}\!=\!\ensuremath{\mathbf T}_{j,j',{\ensuremath{\mathbf x}}_{i'}*\sxbar{{\ensuremath{\mathbf x}}_i \rule{-0.9ex}{1.3ex}^{_-}}}\label{eq:convTopelitzproduct}.
\end{align}
Hence, the time-reversal and complex conjugation for the correlation is obtained  by the adjoint operation. Hence we get
\begin{align}
 \ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf x}}_2^0,-{\ensuremath{\mathbf x}}_1^0}^* \ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss_{{\ensuremath{\mathbf x}}_2^0,-{\ensuremath{\mathbf x}}_1^0}
 \setlength\arraycolsep{3pt}
 &=\begin{pmatrix}
   \ensuremath{\mathbf T}_{1,1,{\ensuremath{\mathbf a}}_2} & -\ensuremath{\mathbf T}_{1,2,{\ensuremath{\mathbf a}}_{1,2}}\\
  - \ensuremath{\mathbf T}_{2,1,{\ensuremath{\mathbf a}}_{2,1}} & \ensuremath{\mathbf T}_{2,2,{\ensuremath{\mathbf a}}_1}
\end{pmatrix}\label{eq:dualcertificateTblocks}
\end{align}
Note, that $\ensuremath{\mathbf T}_{2,1,{\ensuremath{\mathbf a}}_{2,1}}=\ensuremath{\mathbf T}_{2,1,\sxbar{{\ensuremath{\mathbf a}}_{1,2} \rule{-0.9ex}{1.3ex}^{_-}}}$.  Note, that $\ensuremath{\boldsymbol{ \ome}}\not={\ensuremath{\mathbf a}}$ since we need a minus for the
anti-diagonal and ${\ensuremath{\mathbf a}}_1$ and ${\ensuremath{\mathbf a}}_2$ are interchanged.  More precisely we have
\begin{align}
  \ensuremath{\boldsymbol{ \ome}}:=[{\ensuremath{\mathbf a}}_2^{(1)}, -{\ensuremath{\mathbf a}}_{1,2},-{\ensuremath{\mathbf a}}_{2,1},{\ensuremath{\mathbf a}}_{1}^{(2)}]
\end{align}
where ${\ensuremath{\mathbf a}}_i^{(j)}$ are zero padded if $\ensuremath{{N_j}}>\ensuremath{{N_i}}$ and truncated otherwise, such that the dual certificate is given by
\begin{align}
  {\ensuremath{\mathbf W}}&=\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss^*\ensuremath{\mathbf S }}                         % Vektorwertiges Ma{\ss= {\ensuremath{\mathcal{A}}}^*(\ensuremath{\boldsymbol{ \ome}})\notag\\
  &=\!\!\sum_{k={{L}_2}-N_1}^{2{{L}_1}-2} a_{2,k} {\ensuremath{\mathbf A}}_{1,1,k} + \sum_{k=0}^{2{{L}_2}-2} a_{2,k}{\ensuremath{\mathbf A}}_{2,2,k} \\
 &\quad -\sum_{k=0}^{N-2}\Big( a_{1,2,k}{\ensuremath{\mathbf A}}_{1,2,k} +a_{2,1,k}{\ensuremath{\mathbf A}}_{2,1,k}\Big)\notag
 \label{eq:AlamW}
\end{align}
where $a_{i,k}=0$ for $k<0$ and $k>2\ensuremath{{N_i}}-2$ and the sensing matrices ${\ensuremath{\mathbf A}}_{i,j,k}$ in \eqref{eq:4maskmeasurements}. \\

\section{Trace Norm Inequalities}

\begin{lemi}\label{lem:tracelowerbound}
Let ${\ensuremath{\mathbf X}}\succeq 0$ and ${\ensuremath{\mathbf Y}}\succ 0$. Then it holds
\begin{align}
  \tr({\ensuremath{\mathbf X}}{\ensuremath{\mathbf Y}})\geq \ensuremath{\lambda}_{1}({\ensuremath{\mathbf Y}})\sNorm{{\ensuremath{\mathbf X}}}_1
\end{align}
where $\ensuremath{\lambda}_1({\ensuremath{\mathbf Y}})$ is the smallest eigenvalue of ${\ensuremath{\mathbf Y}}$.
\end{lemi}
\begin{proof}
Observe, that by  definition of a positive semi-definite matrix ${\ensuremath{\mathbf A}}$, i.e.,
\begin{align}
  \skprod{{\ensuremath{\mathbf x}}}{{\ensuremath{\mathbf A}}{\ensuremath{\mathbf x}}}\geq 0 \quad,\quad {\ensuremath{\mathbf x}}\in\K^N
\end{align}
for any field $\K\in\{{\ensuremath{\mathbb C}},{\ensuremath{\mathbb R}}\}$, we get with ${\ensuremath{\mathbf x}}=\ve_k$
\begin{align}
  \skprod{\ve_k}{{\ensuremath{\mathbf A}}\ve_k} = a_{k,k}\geq 0 \quad,\quad k\in[N],
\end{align}
i.e., the entries are non-negative if the matrix is positive semi-definite and positive if the matrix is positive.

Hence, the trace of a positive semi-definite matrix is non-negative, and we can lower bound the trace by a non-negative
constant.  We diagonalize ${\ensuremath{\mathbf Y}}$ by an unitary matrix ${\ensuremath{\mathbf U}}$ such that
\begin{align}
  \tr({\ensuremath{\mathbf X}}{\ensuremath{\mathbf U}}\vU^*{\ensuremath{\mathbf Y}}{\ensuremath{\mathbf U}}\vU^*) = \tr({\ensuremath{\mathbf U}}^*{\ensuremath{\mathbf X}}{\ensuremath{\mathbf U}}{\ensuremath{\mathbf D}}_{\ensuremath{\boldsymbol{ \lam}}})
\end{align}
where $\ensuremath{\boldsymbol{ \lam}}=\ensuremath{\boldsymbol{ \lam}}({\ensuremath{\mathbf Y}})$ are the eigenvalues written as a vector in increasing order and ${\ensuremath{\mathbf D}}_{\ensuremath{\boldsymbol{ \lam}}}$ is a diagonal
matrix generated by the vector $\ensuremath{\boldsymbol{ \lam}}$. We can hence write the trace as
\begin{align}
  \sum_{k=1}^N\ensuremath{\lambda}_k({\ensuremath{\mathbf Y}}) \tr({\ensuremath{\mathbf X}}\ve_k\ve_k^*)
   &=\sum_k \ensuremath{\lambda}_k({\ensuremath{\mathbf Y}})\underbrace{x_{k,k}}_{\geq 0}\\
   &\geq \ensuremath{\lambda}_{1}({\ensuremath{\mathbf Y}}))\tr({\ensuremath{\mathbf X}})= \ensuremath{\lambda}_{1}({\ensuremath{\mathbf Y}})\sNorm{{\ensuremath{\mathbf X}}}_1\notag
\end{align}
\end{proof}

\section{Some Remarks for the Local Stability Proof}
In \eqref{eq:dwowo} we can lower bound
\begin{align}
  \Norm{{\ensuremath{\mathbf x}}_1}_2^4+\Norm{{\ensuremath{\mathbf x}}_2}_2^4
\end{align}
by using $\nu=\Norm{{\ensuremath{\mathbf x}}_1}_2^2$ and
$(1-\nu)=\Norm{{\ensuremath{\mathbf x}}_2}_2^2$ with $\nu\in[0,1)$, since  $\Norm{{\ensuremath{\mathbf x}}_1}_2^2 + \Norm{{\ensuremath{\mathbf x}}_2}_2^2= \Norm{{\ensuremath{\mathbf x}}}_2^2=1$. Hence the function
\begin{align}
  f(\nu)=2\nu^2 -2\nu +1
\end{align}
is minimized for $\nu\in[0,1)$ if the derivative vanishes, i.e.,
\begin{align}
   0=4\nu  -2 \quad \ensuremath{\Rightarrow}  \quad \nu=1/2.
\end{align}
Hence we get for the global minimum
\begin{align}
  \min_{\Norm{{\ensuremath{\mathbf x}}_1}_2^2+\Norm{{\ensuremath{\mathbf x}}_2}_2^2=1}\Norm{{\ensuremath{\mathbf x}}_1}_2^4+\Norm{{\ensuremath{\mathbf x}}_2}_2^4 = \frac{1}{2}\label{eq:lagrange}
\end{align}
which is achieved for $\Norm{{\ensuremath{\mathbf x}}_1}_2=\Norm{{\ensuremath{\mathbf x}}_2}_2$.

redpajama_set_name: RedPajamaArXiv


Whether my work is placed in a public, corporate or private space, it always creates a space of its own. You don't need to have an area mapped out in advance to place a piece. The presence of Sculpture creates the necessary space. My work is very human, in scale, and that adds a new level of interactivity and uniqueness to any environment. It has the power to draw diverse people closer and give them an immediate shared experience. I have come to understand and appreciate that once a piece is placed, its life begins. It activates a place and motivates the people whom it touches in a variety of ways. I'm always surprised by the feedback that I receive. For example, a little over a year ago I was approached by a photographer. He told me that he had been doing a series of photo shoots featuring professional dancers using "Dawn" as a prop. People seem to embrace the work, and each person has their relationship with it.
My fascination with symbolism in art began with medieval paintings and works explicitly from the Dutch Renaissance. In The Garden is a direct example of how this fascination has influenced and inspired my work. The Garden of Earthly Delights, by Heironymous Bosch seemed almost surreal to me when I first saw it. I learned that each of the multitude of objects; creatures, flora, and fauna depicted in the painting were symbolic of a greater idea. Some of the symbolism is lost to us, but there is much discussion about the possible interpretations of each object depicted. In the central panel on the lower left-hand side you will see several disproportionately large birds. Even though the painting was created over 500 years ago, the birds are recognizable. I decided to see if I could identify some of the birds. I found a hoopoe, a kingfisher, and this ridiculously large European goldfinch. I decided that my monumental scale strawberry sculpture, titled The Rogue Berry needed a companion piece, and set out to sculpt the goldfinch. I took the approach of polishing the areas of the bird that would be tan colored naturally. Where the coloring would be white, red, black or yellow, the bird's coloration is created using a combination of traditional and contemporary patination techniques. The bird sits atop a polished bronze egg-shaped platter. Both pieces are cast via the lost wax , and they are hand finished, polished and polychromed. In The Garden is a limited edition of 22.


The post Government falls short of deadline to reunite kids, parents appeared first on The Business Journal.
Is this the best solar eclipse photo bomb?
August 22, 2017 Ara Catchatoorian Comments Off on Is this the best solar eclipse photo bomb?


Is Meat Safe to Eat?
More reasons to lose weight!
don't get upset, don't sweat the small stuff, is it worth it?
drug company scams, the dangers of medicine, does medicine cure?
enjoy your work, what's you passion?
how much do you know?
inflammation, cherries, flax seeds, cherries.
loyalty defined, how loyal are they?
Menander, do I know you?
water, drink your water, why drink water?
Beauty Comes From Within, not the Media!
At this point, you can see that there's more to being physically fit than just working out. Nutrition, age, and rest play a significant part. Knowing yourbody type(ectomorph, endomorph or mesomorph) is an important part of becoming the best you can be physically, as well as helping you keep your goals (and results) realistic.
In addition to the physical aspect of working out, the mental aspect is just as important. It's imperative that people remember that and work on their mental fitness as they work on their physical fitness.


On September 27, 2018, the United States Bankruptcy Court for the District of Delaware and the Supreme Court of Singapore entered into a Memorandum of Understanding aimed at improving the efficiency and effectiveness of trans-national insolvency proceedings by encouraging cooperation between the Courts. The Memorandum of Understanding was executed at the Permanent Mission of the Republic of Singapore in New York City by the Hon. Kevin J. Carey of the Delaware Bankruptcy Court and the Hon. Steven Chong Horng Siong of the Singapore Court of Appeal. The Hon. Christopher S. Sontchi, Chief Judge of the United States Bankruptcy Court for the District of Delaware, and the Hon. Chief Justice Sundaresh Menon, Chief Justice of the Supreme Court of Singapore, were also in attendance.
The Memorandum of Understanding notes that both Courts have adopted cross-border insolvency laws based on the UNCITRAL Model Law on Cross-Border Insolvency adopted by the United Nations Commission on International Trade Law and guidelines for court-to-court communication and cooperation based on the Judicial Insolvency Network Guidelines and that the relationship between the Courts is an important element in enhancing the efficiency and effectiveness of cross-border insolvency procedures. Through the Memorandum of Understanding the Courts have agreed to work together to implement cooperation based upon principles of mutual understanding and respect.


10-2020 tph Cone crushers are suitable for medium and fine crushing with processing many kinds of medium and very hard ores and stones such as granite, limestone, barite, marble, calcite, concrete and so on.
Cone crushers from FTM include five types: cone crusher, compound cone crusher(SYMONS), single- and multi- cylinder hydraulic cone crusher, and hydraulic cone crusher. And the machine sizes can be designed according to customer needs.
Cone crushers from FTM have many advantages: High production capacity and crushing rate, low energy consumption;Simple structure, high quality, easy maintenance, and low operating cost ;Low Factory direct-sale Price, Professional service, advanced design ideas and modern equipment, latest technology.