
\section*{Acknowledgment}
This work is supported by the ERC project ``DECODA'' no.320594, in the frame of the European program FP7/2007-2013. We thank L. Dai and K. Pelckmans for motivating discussions.
\subsection{Proofs}\label{proofcomplex-sec}
\begin{proof}[Proof of Proposition~\ref{prop:flat_ext_exp_array}]
\begin{enumerate}
\item By Lemma~\ref{lem:rank_exp_array}, we have that 
\[
\mathop{\text{rank}} \hmatr{\mathcal{B}}{\iarr{h}} = r.
\]
Since $\hmatr{\mathcal{B}}{\iarr{h}}$ is a submatrix of $\hmatr{\mathcal{A}}{\iarr{h}}$ in \eqref{eq:qhankel_rankmin}, the rank of the minimal completion is at least $r$.
Finally, by Lemma~\ref{lem:rank_exp_array}, for the canonical completion \eqref{eq:exp_array}
we have $\mathop{\text{rank}} \hmatr{\mathcal{A}}{\iarr{h}} = r$.

\item[3.] In this case, the conditions of Proposition~\ref{prop:flat_ext} take place.

\item[2.] Consider a matrix of the form
\begin{equation}\label{eq:block_ext}
F = 
\begin{bmatrix}
\hmatr{\mathcal{B}}{\iarr{h}} & \matr{C}\\
\matr{C}^{\T} & \matr{D}
\end{bmatrix},
\end{equation}
where the matrix $\matr{C}$ is known with same image as $\hmatr{\mathcal{B}}{\iarr{h}}$,  and the matrix $\matr{D}$ is unknown.
Since $\mathop{\text{rank}}{\hmatr{\mathcal{B}}{\iarr{h}}} = r$,
for any $B$ we have that there exists unique $\matr{D}$ such that $\mathop{\text{rank}} (F) = r$ (for example, by \cite[Thm. 1.1]{Woerdeman89LAaiA-Minimal}).

Now, observe that for $\iarr{h}$ as in \eqref{eq:qhankel_rankmin}, 
\[
\hmatr{\mathcal{B}^{+}}{\iarr{h}} = 
\begin{bmatrix}
\hmatr{\mathcal{B}}{\iarr{h}} & \matr{C}\\
\matr{C}^{\T} & \hmatr{\delta \mathcal{B}}{\iarr{h}}
\end{bmatrix},
\]
where only $\hmatr{\delta \mathcal{B}}{\iarr{h}}$ is unknown (i.e., it is of the form \eqref{eq:block_ext}). 
The canonical completion  \eqref{eq:exp_array} has rank $r$, and therefore it is the unique completion such that $\mathop{\text{rank}} \hmatr{\mathcal{B}^{+}}{\iarr{h}} = r$.
Finally, since $\mathop{\text{rank}} \hmatr{\mathcal{B}^{+}}{\iarr{h}} = \mathop{\text{rank}} \hmatr{\mathcal{B}}{\iarr{h}}$, by Proposition~\ref{prop:flat_ext}, the overall completion is unique.
\end{enumerate}
\end{proof}



\begin{proof}[Proof of Proposition~\ref{prop:opt_sufficient_complex}]
For $\vect{p}_{\mathbb{C}} \stackrel{\mathrm{def}}{=} \vect{p}_{\mathcal{R}} + i \vect{p}_{\mathcal{I}}$,
consider an SVD of the symmetric matrix ${\struct{\vect{p}_{\mathbb{C}}}}$, 
\begin{equation}\label{eq:S_svd_complex}
\struct{\vect{p}_{\mathbb{C}}} = \matr{U}_{\mathbb{C}} \matr{\Sigma} \matr{V}^{\H}_{\mathbb{C}}, 
\end{equation}
where $\matr{U}^{\H}_{\mathbb{C}} \matr{U}_{\mathbb{C}} = \matr{V}^{\H}_{\mathbb{C}} \matr{V}_{\mathbb{C}} =\matr{I}_r$, and $\matr{\Sigma} \in \mathbb{R}^{n\times n}$ is real diagonal.
Since ${\struct{\vect{p}_{\mathbb{C}}}}$ is symmetric, we have that $\struct{\vect{p}_{\mathbb{C}}} = \overline{\matr{V}}_{\mathbb{C}} \matr{\Sigma} \matr{U}^{\T}_{\mathbb{C}}$ is also an SVD.
 
 Next, we have that the matrices $\matr{B}_{\mathbb{C}} = \matr{B}_{\mathcal{R}}+ i\matr{B}_{\mathcal{I}}$ and $\matr{P}_{\mathbb{C}} = \matr{P}_{\mathcal{R}}+ i\matr{P}_{\mathcal{I}}$ have the form
\[
\begin{split}
 \matr{B}_{\mathcal{R}}& =
\matr{U}_{\mathcal{R}} \matr{V}^{\T}_{\mathcal{R}}  + \matr{U}_{\mathcal{I}} \matr{V}^{\T}_{\mathcal{I}},\quad
\matr{B}_{\mathcal{I}} = \matr{U}_{\mathcal{I}} \matr{V}^{\T}_{\mathcal{R}} - \matr{U}_{\mathcal{R}} \matr{V}^{\T}_{\mathcal{I}}, \\
 \matr{P}_{\mathcal{R}}& =
\matr{U}_{\mathcal{R}} \matr{U}^{\T}_{\mathcal{R}}  + \matr{U}_{\mathcal{I}} \matr{U}^{\T}_{\mathcal{I}} = \matr{V}_{\mathcal{R}} \matr{V}^{\T}_{\mathcal{R}}  + \matr{V}_{\mathcal{I}} \matr{V}^{\T}_{\mathcal{I}} ,\\
\matr{P}_{\mathcal{I}} & =
\matr{U}_{\mathcal{I}} \matr{U}^{\T}_{\mathcal{R}} - \matr{U}_{\mathcal{R}} \matr{U}^{\T}_{\mathcal{I}} = 
\matr{V}_{\mathcal{R}} \matr{V}^{\T}_{\mathcal{I}} -\matr{V}_{\mathcal{I}} \matr{V}^{\T}_{\mathcal{R}}. 
\end{split}
\]
Since the matrix $\matr{P}_{\mathbb{C}}$ is Hermitian and  $\matr{B}_{\mathbb{C}}$ is complex symmetric, we have that  $\matr{P}_{\mathcal{R}}^{\T} =  \matr{P}_{\mathcal{R}}$ and $\matr{P}_{\mathcal{I}}^{\T} =  -\matr{P}_{\mathcal{I}}$, and
$\matr{B}_{\mathcal{R}}^{\T} =  \matr{B}_{\mathcal{R}}$ and $\matr{B}_{\mathcal{I}}^{\T} =  \matr{B}_{\mathcal{I}}$.

Then from \cite{Day.Heroux01SJoSC-Solving}, we have that  the matrix $\mathscr{S}_{ext}(\vect{p}_{ext})$ admits the following SVD:
\begin{equation}\label{eq:Sext_svd}
\mathscr{S}_{ext}(\vect{p}_{ext}) = \matr{U}_{ext} \begin{bmatrix}\matr{\Sigma} & \matr{0} \\ \matr{0} & \matr{\Sigma}\end{bmatrix} \matr{V}_{ext}^{\T},
\end{equation}
where for $\matr{U}_{\mathbb{C}} =  \matr{U}_{\mathcal{R}} +  i\matr{U}_{\mathcal{I}}$ and $\matr{V}_{\mathbb{C}} =  \matr{V}_{\mathcal{R}} +  i\matr{V}_{\mathcal{I}}$
\[
 \matr{U}_{ext} \stackrel{\mathrm{def}}{=} \begin{bmatrix}
 \matr{U}_{\mathcal{R}} & - \matr{U}_{\mathcal{I}} \\
 \matr{U}_{\mathcal{I}} &  \matr{U}_{\mathcal{R}}
\end{bmatrix},  \matr{V}_{ext} \stackrel{\mathrm{def}}{=} \begin{bmatrix}
 \matr{V}_{\mathcal{R}} & - \matr{V}_{\mathcal{I}} \\
 \matr{V}_{\mathcal{I}} &  \matr{V}_{\mathcal{R}}
\end{bmatrix}.
\]
We can express the matrices $\matr{B}_{ext}$ and $\matr{P}_{ext}$ (defined in \eqref{eq:skew_projector} and \eqref{eq:projector}) for the structure $\mathscr{S}_{ext}$.
Straightforward calculations show that
\[
\begin{split}
 \matr{B}_{ext}& \stackrel{\mathrm{def}}{=} \matr{U}_{ext}\matr{V}_{ext}^{\T} = \begin{bmatrix}
\matr{B}_{\mathcal{R}} & -\matr{B}_{\mathcal{I}} \\
\matr{B}_{\mathcal{I}} & \matr{B}_{\mathcal{R}} \\
\end{bmatrix} \\
\matr{P}_{ext} &\stackrel{\mathrm{def}}{=} \matr{U}_{ext}\matr{U}_{ext}^{\T} = \matr{V}_{ext}\matr{V}_{ext}^{\T}  = \begin{bmatrix}
\matr{P}_{\mathcal{R}} & -\matr{P}_{\mathcal{I}} \\
\matr{P}_{\mathcal{I}} & \matr{P}_{\mathcal{R}} \\
\end{bmatrix}.
\end{split}
\]
Next, from \eqref{eq:affine_ext0}, we have that
\begin{equation}\label{eq:affine_ext}
\begin{split}
&\mathscr{S}_{ext}(\vect{p}_{ext}) =
\begin{bmatrix} \matr{S}_{0, \mathcal{R}} & -\matr{S}_{0, \mathcal{I}} \\ \matr{S}_{0, \mathcal{I}} & \matr{S}_{0, \mathcal{R}} \end{bmatrix} + \\
& \sum\limits_{k=1}^{N} p_{k,\mathcal{R}}
\begin{bmatrix} \matr{S}_{k} & 0 \\
0 & \matr{S}_{k}
\end{bmatrix} +
\sum\limits_{k=1}^{N} 
p_{k,\mathcal{I}}
\begin{bmatrix} 0 & -\matr{S}_{k} \\
\matr{S}_{k} & 0
\end{bmatrix},
\end{split}
\end{equation}
where $\matr{S}_0 = \matr{S}_{0, \mathcal{R}} + i\matr{S}_{0, \mathcal{I}}$. 

In what follows, we prove statements of the proposition.

\begin{enumerate}
\item
Analogously to \eqref{eq:subgradient_Sp_matrix} the subgradient of $g(\vect{p}_{ext}) \stackrel{\mathrm{def}}{=} \|\mathscr{S}_{ext}(\vect{p}_{ext}) \|_*$  is equal to 
\[
\left\{ \begin{bmatrix} \vect{a}(\matr{M}_{ext}) \\ \vect{b}(\matr{M}_{ext})\end{bmatrix} : \matr{M}_{ext}\in \mathbb{R}^{2N \times 2N}, \|\matr{M}_{ext}\|_2 \le 1\right\},
\]
where
\[
\begin{split}
a_k(\matr{M}_{ext}) =& \left\langle \begin{bmatrix} \matr{S}_{k} & \matr{0} \\
\matr{0} & \matr{S}_{k}
\end{bmatrix}, \matr{B}_{ext} + \matr{Q}_{ext} \matr{M}_{ext} \matr{Q}_{ext2} \right\rangle_{F}, \\
b_k(\matr{M}_{ext}) =&  \left\langle\begin{bmatrix} \matr{0} & -\matr{S}_{k} \\
\matr{S}_{k} & \matr{0}
\end{bmatrix}, \matr{B}_{ext} + \matr{Q}_{ext} \matr{M}_{ext} \matr{Q}_{ext2} \right\rangle_{F},
\end{split}
\]
and for $\matr{Q}_{\mathbb{C}} =\matr{Q}_{\mathcal{R}} + i\matr{Q}_{\mathcal{I}}  \stackrel{\mathrm{def}}{=} \matr{I}_n - \matr{P}_{\mathbb{C}}$
\[
\matr{Q}_{ext} = \begin{bmatrix}
\matr{Q}_{\mathcal{R}} & -\matr{Q}_{\mathcal{I}} \\
\matr{Q}_{\mathcal{I}} & \matr{Q}_{\mathcal{R}} \\
\end{bmatrix}, \matr{Q}_{ext2} = \begin{bmatrix}
\matr{Q}_{\mathcal{R}} & \matr{Q}_{\mathcal{I}} \\
-\matr{Q}_{\mathcal{I}} & \matr{Q}_{\mathcal{R}} \\
\end{bmatrix}
\]
are the projectors on the left and right nullspace of  $\mathscr{S}_{ext}(\vect{p}_{ext})$.
Immediately, we have that
\[
\begin{split}
2\langle \matr{S}_{k}, \matr{P}_{\mathbb{C}} \rangle_F 
&= 
\left\langle \begin{bmatrix} \matr{S}_{k} & \matr{0} \\
\matr{0} & \matr{S}_{k}
\end{bmatrix}, \matr{B}_{ext} \right\rangle_{F} \\
&+ i
\left\langle
\begin{bmatrix} \matr{0} & -\matr{S}_{k} \\
\matr{S}_{k} & \matr{0}
\end{bmatrix}, \matr{B}_{ext}\right\rangle_F.
\end{split}
\]
Now let us define the matrices 
\begin{equation}\label{eq:M_ext}
\begin{split}
\matr{M}_{ext} &= 
\begin{bmatrix}
\matr{M}_{1} & -\matr{M}_{3} \\
\matr{M}_{2} & \matr{M}_{4}
\end{bmatrix},\;
\matr{M}_{\mathcal{R}} \stackrel{\mathrm{def}}{=} \frac{\matr{M}_1+\matr{M}_4}{2},\\
 \matr{M}_{\mathcal{I}} &\stackrel{\mathrm{def}}{=} \frac{\matr{M}_2+\matr{M}_3}{2},\;
\matr{M}_{\mathbb{C}} \stackrel{\mathrm{def}}{=} \matr{M}_{\mathcal{R}} + i \matr{M}_{\mathcal{I}}. 
\end{split}
\end{equation}
Easy calculations show that the matrix $\matr{Q}_{ext} \matr{M}_{ext} \matr{Q}_{ext2}$ can be expressed as
\begin{equation}\label{eq:M_ext_expr}
\matr{Q}_{ext} \matr{M}_{ext} \matr{Q}_{ext2} = \begin{bmatrix} \matr{C}_1 & -\matr{C}_3\\ \matr{C}_2 & \matr{C}_4\end{bmatrix},
\end{equation}
where 
\[
\begin{smallmatrix}
\matr{C}_1  =  \matr{Q}_{\mathcal{R}}  \matr{M}_{1} \matr{Q}_{\mathcal{R}}   + \matr{Q}_{\mathcal{R}} \matr{M}_{3} \matr{Q}_{\mathcal{I}}- \matr{Q}_{\mathcal{I}} \matr{M}_{2} \matr{Q}_{\mathcal{R}}   + \matr{Q}_{\mathcal{I}} \matr{M}_{4} \matr{Q}_{\mathcal{I}},\\
\matr{C}_2  =  \matr{Q}_{\mathcal{R}} \matr{M}_{2} \matr{Q}_{\mathcal{R}} - \matr{Q}_{\mathcal{R}} \matr{M}_{4} \matr{Q}_{\mathcal{I}}+ \matr{Q}_{\mathcal{I}}  \matr{M}_{1} \matr{Q}_{\mathcal{R}}   + \matr{Q}_{\mathcal{I}} \matr{M}_{3} \matr{Q}_{\mathcal{I}}  ,\\
\matr{C}_3  =  \matr{Q}_{\mathcal{R}} \matr{M}_{3} \matr{Q}_{\mathcal{R}}-\matr{Q}_{\mathcal{R}}  \matr{M}_{1} \matr{Q}_{\mathcal{I}} + \matr{Q}_{\mathcal{I}} \matr{M}_{4} \matr{Q}_{\mathcal{R}} + \matr{Q}_{\mathcal{I}} \matr{M}_{2} \matr{Q}_{\mathcal{I}},\\
\matr{C}_4  =  \matr{Q}_{\mathcal{R}} \matr{M}_{4} \matr{Q}_{\mathcal{R}}+ \matr{Q}_{\mathcal{R}} \matr{M}_{2} \matr{Q}_{\mathcal{I}}  - \matr{Q}_{\mathcal{I}} \matr{M}_{3} \matr{Q}_{\mathcal{R}} +\matr{Q}_{\mathcal{I}}  \matr{M}_{1} \matr{Q}_{\mathcal{I}},\\
\end{smallmatrix}
\]
and 
\[
\matr{Q}_{\mathbb{C}} \matr{M}_{\mathbb{C}} \matr{Q}^{\top}_{\mathbb{C}} = \frac{\matr{C}_1+\matr{C}_4}{2}  +i\frac{\matr{C}_2+\matr{C}_3}{2}.
\]
Then, immediately,
\[
\begin{split}
&2\langle \matr{S}_k, \matr{B}_{\mathbb{C}}+\matr{Q}_{\mathbb{C}} \matr{M}_{\mathbb{C}} \matr{Q}_{\mathbb{C}}\rangle_F\\
= &
\left\langle \begin{bmatrix}\matr{S}_k& \matr{0} \\
\matr{0} & \matr{S}_{k}
\end{bmatrix}, \matr{B}_{ext} - \matr{Q}_{ext} \matr{M}_{ext} \matr{Q}_{ext} \right\rangle_{F} \\
+& i
\left\langle
\begin{bmatrix} \matr{0} & -\matr{S}_{k} \\
\matr{S}_{k} & \matr{0}
\end{bmatrix}, \matr{B}_{ext} - \matr{Q}_{ext} \matr{M}_{ext} \matr{Q}_{ext} \right\rangle_F.
\end{split}
\]
Hence, we obtain that
\[
a_k(\matr{M}_{ext})   + i b_k(\matr{M}_{ext}) =
 \left\langle  \matr{S}_{k} 
, \matr{B}_{\mathbb{C}} + \matr{Q}_{\mathbb{C}} \matr{M}_{\mathbb{C}} \matr{Q}_{\mathbb{C}}^{\top} \right\rangle_{F} 
\]
Finally, it is easy to see that for $\matr{M}_{\mathbb{C}}$ defined as in \eqref{eq:M_ext}
\begin{equation}\label{eq:M_norms}
\begin{split}
&\|\matr{M}_{\mathbb{C}}\|_2 = \left\| \begin{bmatrix} \matr{M}_{\mathcal{R}} & -\matr{M}_{\mathcal{I}} \\ \matr{M}_{\mathcal{I}} & \matr{M}_{\mathcal{R}}  \end{bmatrix} \right\|_2  \\
&= \left\| \frac{\matr{M}_{ext} + \left[\begin{smallmatrix} \matr{0} & -\matr{I} \\ \matr{I} & \matr{0} \end{smallmatrix}\right] \matr{M}_{ext} \left[\begin{smallmatrix} \matr{0} & -\matr{I} \\ \matr{I} & \matr{0} \end{smallmatrix}\right]}{2}  \right\|_2 \\&\le \|\matr{M}_{ext}\|_2,
\end{split}
\end{equation}
where the equality takes place if $\matr{M}_1 = \matr{M}_4$ and $\matr{M}_2 = \matr{M}_3$.
Hence, if  $\|\matr{M}_{ext}\|_2 < 1$ and then  $\|\matr{M}_{\mathbb{C}}\|_2 < 1$, according to \eqref{eq:M_norms}.
Vice versa, if we are given $\matr{M}_{\mathbb{C}} = \matr{M}_{\mathcal{R}} + i \matr{M}_{\mathcal{I}}$ with $\|\matr{M}_{\mathbb{C}}\|_2 < 1$, by taking $\matr{M}_1 = \matr{M}_4 = \matr{M}_{\mathcal{R}}$ and $\matr{M}_2 = \matr{M}_3 = \matr{M}_{\mathcal{I}}$, we obtain $\matr{M}_{ext}$ with $\|\matr{M}_{ext}\|_2  = \|\matr{M}_{\mathbb{C}}\|_2$, which completes the proof.

\item
Let $\matr{M}_{ext}$ be as in \eqref{eq:M_ext},  with $\matr{M}_1 = \matr{M}_4 = \matr{M}_{\mathcal{R}}$, $\matr{M}_2 = \matr{M}_3 = \matr{M}_{\mathcal{I}}$. Then, in view of \eqref{eq:M_ext_expr}, we have that
\[
\matr{Q}_{\mathbb{C}}  \matr{M}_{\mathbb{C}} \matr{Q}^{\T}_{\mathbb{C}} = \matr{0} \iff
\matr{Q}_{ext} \matr{M}_{ext} \matr{Q}_{ext2} = \matr{0},
\]
which completes the proof.
\end{enumerate}
\end{proof}

\begin{proof}[Proof of Lemma~\ref{lem:qhankel_zero_root_projector}]
\begin{enumeratex}
\item
Denote $\set{B} = \trgset{m}{d'}$ (in this case, $s \le \# \set{B}$).
Since $2\set{B} \subseteq \set{A}$, from \eqref{eq:qhankel_Gk}, we have that for any $k \in \{1,\ldots, N\}$
\begin{equation}\label{eq:qhankel_Gk_form}
\matr{S}_k = 
\left[
\begin{array}{c|c}
\matr{0}_{s\times s} & * \\\hline
* & * \\
\end{array}
\right].
\end{equation}
Therefore, $\matr{P}^{\T}_0 \matr{S}_k \matr{P}_0 = \matr{0}$.

\noindent\item
First, denote $\set{C} = \trgset{m}{d''}$ (in this case, $n'' = \# \set{C}$). Then the matrix $\matr{Q}_0$  has the form
\[
\matr{Q}_0 = \begin{bmatrix}  \matr{I}_{s} - \matr{P}'_0 & \matr{0} \\ \matr{0} & \matr{I}_{n-s}\end{bmatrix},
\]
Now, as in Remark~\ref{rem:equivalent_conditions_slrmc_DP15}, we take an arbitrary $\matr{H}= \sum\limits_{k=1}^{N} \Delta p_k \matr{S}_k \neq \matr{0}$. It is sufficient to prove that the following block of the matrix $\matr{Q}_0\matr{H}\matr{Q}^{\T}_0$ is nonzero:
\[
\matr{F}\matr{H}\matr{F}^{\top}\neq \matr{0}, \quad \mbox{where}\quad
\matr{F} \stackrel{\mathrm{def}}{=} \begin{bmatrix}   \matr{0} & \matr{I}_{n-n''}\end{bmatrix}.
\]
It is easy to see that the matrix $\matr{F}\matr{H}\matr{F}^{\top}$ has the form 
\[ 
\matr{F} \matr{H} \matr{F}^{\top} = \hmatr{\set{D}}{\iarr{f}},
\]
where the values of the array $\arr{f} \stackrel{\mathrm{def}}{=} \{f_{\vect{\alpha}}\}_{\alpha \in 2\set{A}}$ are 
\[
{f}_{\vect{\alpha}} \stackrel{\mathrm{def}}{=} 
\begin{cases}
0, & {\vect{\alpha}} \in \set{A},  \\
\Delta p_k, & \vect{\alpha} = \vect{\beta}_{k},
\end{cases}
\]
$\vect{\beta}_{k}$ are defined as in \eqref{eq:ordering_missing_values}, and $\set{D} \stackrel{\mathrm{def}}{=} \set{A} \setminus \set{C}$. Finally, we have that
\[
2\set{D} = \trgset{m}{2d} \setminus \trgset{m}{2d'' + 1} \supseteq2\set{A} \setminus \set{A},
\]
and therefore the matrix $\matr{F} \matr{H} \matr{F}^{\T}$ contains all $\Delta p_k$  and  
 is nonzero for any considered $\matr{H}$.
\end{enumeratex}
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:rank_r}]
By Lemma~\ref{lem:zero_root_perturbation}, we only need to show that for any $\varepsilon > 0$  there exists $\rho$ such that for all $\lambda_k$ satisfying the statements of the theorem it holds that 
\[
\|\matr{P} - \matr{P}_0\|_F <\varepsilon, 
\]
where 
\[
\matr{P}_0 = \begin{bmatrix} \matr{I}_r & \matr{0} \\ \matr{0} & \matr{0}\end{bmatrix} \in \mathbb{R}^{n \times n}.
\]
The distance between projectors can be expressed as
\[
\|\matr{P} - \matr{P}_0\|_F = \|(\matr{I}-\matr{P}) - (\matr{I}-\matr{P}_0)\|_F =
2 \|\matr{P}_0 \matr{U}_{\bot}\|_F,
\]
where  $\matr{U}_{\bot}$ is an orthonormal basis on the nullspace of $\matr{P}$ (the last equality follows from \eqref{eq:norm_diff_proj_int}).

The nullspace of $\matr{P}$ coincides with the image of  the matrix
\[
\matr{K} = 
\begin{bmatrix}
        q_0     & 0      & \ldots &0        \\
        \vdots  & q_0    & \ddots &\vdots   \\
        q_{r}   & \vdots & \ddots &0        \\
        0       & q_{r}  & \ddots &q_0      \\
        \vdots  &\ddots  & \ddots &\vdots   \\
        0       & \ldots & 0      &q_{r}   
\end{bmatrix} \in \mathbb{C}^{n\times (n-r)},
\]
where $q(z)$ is the characteristic polynomial \eqref{eq:char_poly} (with $q_r = 1$).
Then $\matr{U}_{\bot} \in \mathbb{C}^{n\times(n-r)}$ can be found from an SVD $\matr{K} = \matr{U}_{\bot} \matr{\Sigma} \matr{V}^{\H}_{\bot}$, and, by submultiplicativity of matrix norms, we have that 
\[
\frac{\|\matr{P} - \matr{P}_0\|^2_F}{2} \le  \|\matr{P}_0 \matr{K}\|_F^2 \|\matr{\Sigma}^{-1}\|^2_F 
\]
The entries of the matrix $\matr{P}_0 \matr{K}$ are $q_j$, for $j = \{0,\ldots, r-1\}$.
By Vieta's formulae,  these $q_j$ are homogeneous polynomials in the roots $\lambda_k$.
Therefore, there exists a universal constant $C$ such that for all $\lambda_k$, satisfying $|\lambda_{k}| < 1$ it holds that $|q_j| < C \max (|\lambda_{k}|)$.
Hence,
\[
\frac{\|\matr{P} - \matr{P}_0\|^2_F}{2} \le \frac{C(n-r) }{\min{\sigma^2_{min}(\matr{K})}}\max (|\lambda_k|).
\]
From the well-known bounds on eigenvalues of Toeplitz matrices \cite{Grenander.Szego84-Toeplitz}, we know that
\[
\min{\sigma^2_{min}(\matr{K})} \ge \min_{|z| = 1, z \in \mathbb{C}} |q(z)|^2,
\]
which can be bounded from below by a constant if the roots $\lambda_k$  satisfy $|\lambda_k| < \rho_0$
for  $0 < \rho_0 < 1$. Hence, there exists a constant $\widetilde{C}$ such that for all $|\lambda_k| < \rho_0$ the following inequality holds true
\[
{\|\matr{P} - \matr{P}_0\|^2_F} \le \widetilde{C} \max (|\lambda_k|).
\]
\end{proof}

\begin{proof}[Proof of Lemma~\ref{lem:qhankel_limit_projectors}]
Denote $M = \# \set{A}$ and assume that
$\set{D} = \{ \vect{\alpha}_{1}, \ldots, \vect{\alpha}_{r} \}$ and $\delta \set{D} = \{ \vect{\beta}_{1}, \ldots, \vect{\beta}_J \}$.
Since $\vect{y}_1,\ldots, \vect{y}_r$ are $\set{D}$-independent, there exist coefficients $[w_{i,j}]_{i,j=1}^{r,J}$  such that the polynomials
\[
p_j(\vect{y}) \stackrel{\mathrm{def}}{=} \vect{y}^{\vect{\beta}_j} - \sum\limits_{i=1}^{r} w_{i,j} \vect{y}^{\vect{\alpha}_i}
\]
vanish on $\{\vect{y}_1,\ldots, \vect{y}_r\}$. 
The polynomials $p_j(\vect{y})$  constitute a so-called \emph{border basis} \cite[Ch. 2]{Stetter04-Numerical} of the interpolating ideal of $\{\vect{y}_1,\ldots, \vect{y}_r\}$ (the ideal of polynomials vanishing at  $\{\vect{y}_1,\ldots, \vect{y}_r\}$).

Now, define the following polynomials:
\[
p_{j,\rho}(\vect{y}) \stackrel{\mathrm{def}}{=}  \vect{y}^{\vect{\beta}_j} - \sum\limits_{i=1}^{r} w_{i,j} \vect{y}^{\vect{\alpha}_i} \rho^{|\vect{\beta}_j| - |\vect{\alpha}_i|},
\]
which for $\rho >0$ are equal to $\rho^{|\vect{\beta}_j|} p_j(\rho^{-1}\vect{y})$ and therefore vanish  $\{\rho\vect{y}_1,\ldots, \rho\vect{y}_r\}$. Moreover, $p_{j,\rho}(\vect{y}) $ constitute a border basis of the interpolating ideal of $\{\rho\vect{y}_1,\ldots, \rho\vect{y}_r\}$.


Now let us build the left kernel $\mathcal{K}_{\rho} \stackrel{\mathrm{def}}{=} \lker{\mathscr{V}_{\set{A}} (\rho\vect{y}_1, \ldots, \rho \vect{y}_r)}$ of the corresponding Vandermonde matrix.
In what follows, we construct a basis of $\mathcal{K}_{\rho}$.
Consider  sets of multiindices
\[
\begin{split}
\set{E}_1  & =  \{\vect{\epsilon}_{1,1}, \ldots, \vect{\epsilon}_{1,n_1}\}, \cdots
,\set{E}_J   =  \{\vect{\epsilon}_{J,1}, \ldots, \vect{\epsilon}_{J,n_J}\}, \\
\end{split}
\]
such that $n_1 + \ldots + n_J = M-r$ and 
\[
(\set{E}_1 + \{\vect{\beta}_1\}) \cup \cdots \cup (\set{E}_M + \{\vect{\beta}_M\}) = \set{A} \setminus \set{D}.
\]
Then we have that the polynomials $\{q_{j,i,\rho}\}_{j=1,i=1}^{J,n_{j}}$ defined as
\[
q_{j,i,\rho}(\vect{y}) \stackrel{\mathrm{def}}{=} \vect{y}^{\vect{\epsilon}_{j,i}} p_{j, \rho} (\vect{y})
\]
are linearly independent.
Finally, the monomials of each polynomial $q_{j,i,\rho}(\vect{y})$ have degree at most $d$, and therefore,
there exist vectors $\vect{q}_{j,i,\rho} \in \mathbb{C}^{M}$ such that
\[
q_{j,i,\rho}(\vect{y}) = \begin{bmatrix}
\vect{y}^{\vect{\alpha}_1} & \cdots & \vect{y}^{\vect{\alpha}_M} 
\end{bmatrix} \vect{q}_{j,i,\rho}.
\]
Since all $q_{i,j,\rho}(\vect{y})$ vanish on $\vect{y}_1,\ldots, \vect{y}_r$, and $q_{i,j}$ are linearly independent, we have that
\[
\mathcal{K}_{\rho} = \mathop{\text{colspan}} \{\vect{q}_{j,i,\rho}\}_{ j=1, i=1}^{J,n_J}.
\] 
Now we  calculate the limit of $\mathcal{K}_{\rho}$ as $\rho \to 1$.
Consider the cases from the statement of the lemma.

\begin{enumeratex}
\item If $r = \binom{m + d_0}{m}$,  we have that $\set{D} = \trgset{m}{d_0}$, and $\delta \set{D} = \degset{m}{d_0+1}$. Hence, $|\vect{\beta}| > |\vect{\alpha}|$ for all $\vect{\beta} \in \delta\set{D}$, $\vect{\alpha} \in \set{D}$, and we have that 
\[
\lim_{\rho \to 0} q_{j,i,\rho}(\vect{y}) =  q_{j,i,0}(\vect{y}) = \vect{y}^{\varepsilon_{j,i} + \vect{\beta}_j}.
\]
Since all sums $\varepsilon_{j,i} + \beta_j$ are distinct, we have that
\[
\lim_{\rho \to 0} \mathcal{K}_{\rho} = \mathop{\text{colspan}} \begin{bmatrix} 0 \\ I_{N-r}\end{bmatrix},
\]
which implies \eqref{eq:qhankel_proj_lim_trg}.

\item Let $r = \binom{m + d_0}{m}$. Without loss of generality, we assume that elements of $\set{D}$ and $\delta \set{D}$ are ordered such that 
\[
\begin{split}
&\trgset{m}{d_0-1} =  \{ \vect{\alpha}_{1}, \ldots, \vect{\alpha}_{K} \},\quad  
\set{C}_1  =  \{ \vect{\alpha}_{K+1}, \ldots, \vect{\alpha}_{r} \} \subset \degset{m}{d_0},  \\
&\set{C}_2 =  \{ \vect{\beta}_{1}, \ldots, \vect{\beta}_{T} \} \subset \degset{m}{d_0},\quad 
\set{C}_3 =  \{ \vect{\beta}_{T+1}, \ldots, \vect{\beta}_{J} \} \subset \degset{m}{d_0+1}, \\
\end{split}
\]
and $T = L+K-r$, $\set{D} = \trgset{m}{d_0-1} \cup \set{C}_1$, $\delta \set{D} = \set{C}_2\cup \set{C}_3$.
Note that since $\set{C}_3 = \delta \set{D} \setminus \degset{m}{d_0}$, we have that $\set{C}_3 = \delta 
\set{C}_1$. Now we have that
\[
\lim_{\rho \to 0} q_{j,i,\rho}(\vect{y}) = q_{j,i,0}(\vect{y}) =
\begin{cases}
\vect{y}^{\varepsilon_{j,i}} (\vect{y}^{\vect{\beta}_j} - \sum\limits_{l=K+1}^{r} w_{l,j} \vect{y}^{\vect{\alpha}_l}), & j \le T,\\
\vect{y}^{\varepsilon_{j,i} + \vect{\beta}_j}, & j > T.
\end{cases}
\]
Finally, note that we can order $\vect{\epsilon}_{j,i}$ in such a way that $\vect{\epsilon}_{j,1} = \vect{0}$ for all $j$.
Taking into account that $\delta \set{C}_1 = \set{C}_3$, we can cancel lower monomials in $q_{j,i,0}(\vect{y})$, $i > 1$ without changing the linear space spanned by $q_{i,j,0}$.
More precisely, the set of polynomials $\{\widetilde{q}_{i,j}\}^{J,n_J}_{j=1,i=1}$, defined as
\[
\widetilde{q}_{j,i}(\vect{y}) =
\begin{cases}
q_{j,i,0}(\vect{y}), & (i = 1) \mbox{ and } (j \le T),\\
\vect{y}^{\varepsilon_{j,i} + \vect{\beta}_j}, & (i > 1) \mbox{ or } (j > T),\\
\end{cases}
\]
spans the same subspace as $\{\widetilde{q}_{j,i}\}^{J,n_J}_{j=1,i=1}$.
Therefore,  the limit of the kernel has the form
\[
\lim_{\rho \to 0} \mathcal{K}_{\rho} = 
\mathop{\text{colspan}} 
\begin{bmatrix} 
*    & \matr{0} \\ 
\matr{I}_T  & \matr{0} \\  
     & \matr{I}_{N-(K+L)}\end{bmatrix},
\]
where $*$ denotes the elements of $q_{i,j,0}(\vect{y})$ for $j=1$ (\textit{i.e.}, the first $T$ columns correspond to $\widetilde{q}_{j,i}(\vect{y})$ for $i = 1$ and $j \le T$).
Hence, the projector on the orthogonal complement of $\lim_{\rho \to 0} \mathcal{K}_{\rho}$ has the form \eqref{eq:qhankel_proj_lim_general}.
\end{enumeratex}
\end{proof}



\section{Background and main notation}\label{sec:background}
\subsection{Sets of multi-indices}
We denote by $\mathbb{N}$ the set of nonnegative integers.
First, for a multi-index $\vect{\alpha} = ({\alpha_1}, {\alpha_2}, \cdots, {\alpha_m}) \in \mathbb{N}^m$, the monomial  $x_1^{\alpha_1} x_2^{\alpha_2} \cdots x_m^{\alpha_m}$  will be denoted as
$\vect{x}^{\vect{\alpha}}$, 
and its total degree is $|\vect{\alpha}|\stackrel{\mathrm{def}}{=}\sum_\ell \alpha_\ell$.

For ordering the multi-indices, we use in this paper an ordering denoted by $\prec$. It is defined recusively on the size of vectors $\vect\alpha$ and $\vect\beta$ as:
\[
\begin{split}
& \vect\alpha \prec \vect\beta \Leftrightarrow\\
& \Leftrightarrow \left\{\begin{array}{l}
|\vect\alpha| < |\vect\beta| \\
 \mbox{ or } \\
|\vect\alpha| = |\vect\beta| ~ \mbox{and} ~ (\alpha_2, \ldots, \alpha_{m}) 
\prec  (\beta_2, \ldots, \beta_{m})
\end{array}\right.
\end{split}
\]

Next, we shall denote by $\trgset{m}{d}$ the set of multi-indices $\{\vect{\alpha}\in \mathbb{N}^{m}\!:\, |\vect{\alpha}| \le d\}$.
By $\degset{m}{d}$ we denote the set $\{\vect\alpha \in \mathbb{N}^{m}:\, |\vect\alpha| = d\}$. 
It is easy to see that 
\[
\trgset{m}{d} = \degset{m}{0} \cup\degset{m}{1} \cup \cdots \cup \degset{m}{d}.
\]
\begin{example}
Take $m=2$ and $d=3$. Then
\[
\begin{split}
\trgset{2}{3} =& \{{(0,0)}, {(1,0)}, {(0,1)}, {(2,0)}, {(1,1)}, {(0,2)},\\ 
               & \phantom{\{}{(3,0)}, {(2,1)}, {(1,2)}, {(0,3)}\},\\
\degset{2}{0} =& \{ {(0,0)} \}, ~ \degset{2}{1} = \{{(1,0)}, {(0,1)}\},\\
\degset{2}{2} =& \{ {(2,0)}, {(1,1)}, {(0,2)}\}, \\
\degset{2}{3} =& \{ {(3,0)}, {(2,1)}, {(1,2)}, {(0,3)} \}.
\end{split}
\]
The multi-indices  are ordered according to $\prec$ in the sets defined above. In fact, when the total degrees are the same, terms are sorted only by increasing degrees in the second variable.
\end{example}
 
For sets $\set{A}, \set{B} \subset \mathbb{N}^{m}$, we define their Minkowski sum  as
$
\set{A} + \set{B} \stackrel{\mathrm{def}}{=} \{ \vect{\alpha} + \vect{\beta} \,:\, \vect{\alpha}\in\!\set{A}, \vect{\beta}\in\!\set{B} \},
$
with a shorthand notation $2\set{A} \stackrel{\mathrm{def}}{=} \set{A} + \set{A}$.
It is easy to see that $\degset{m}{d_1} + \degset{m}{d_2} = \degset{m}{d_1+d_2}$ and $\trgset{m}{d_1} + \trgset{m}{d_2} = \trgset{m}{d_1+d_2}$.

For $m=1$, we have that $\trgset{1}{d} = \{0,\ldots,d\}$ and 
$\{0,\ldots,d_1\}+ \{0,\ldots,d_2\} = \{0,\ldots,d_1+d_2\}$.
For $m = 2$, an example is shown in Fig.~\ref{fig:msum} (the multi-indices are depicted as black dots).
\begin{figure}[ht!]
\centering
\begin{tikzpicture}[scale=0.6]
\tikzstyle{dot} = [draw,circle,minimum size=1.25mm,fill,inner sep=0mm]
\begin{scope}[xshift = 0cm]
    \draw (0,1.5) node[anchor=east]  {\small$3$};
    \draw (0,2.05) node[anchor=east]  {\small$\alpha_2$};
    \draw (0.5,0) node[anchor=north]  {\small$1$};
    \draw (1,0) node[anchor=north ]  {\small$2$};
    \draw (0,0) node[anchor=north ]    {\small$0$};
    \draw (0,0.5) node[anchor= east]    {\small$1$};
    \draw (0,1) node[anchor= east]    {\small$2$};
    \draw (1.5,0) node[anchor=north ]  {\small$3$};
    \draw (2,0) node[anchor=north ]  {\small$\alpha_1$};
 
    \draw[color=black, help lines, line width=.1pt] (0,0)
      grid[xstep=0.5cm, ystep=0.5cm] (1.25,1.25);
 
    \draw(0,0)      node[dot]   (p00) {};
    \draw(0,0.5)      node[dot]   (p01) {};
    \draw(0,1)      node[dot]   (p01) {};
    \draw(0.5,0)      node[dot]   (p10) {};
    \draw(0.5,0.5)      node[dot]   (p11) {};
    \draw(1,0)      node[dot]   (p20) {};
    \draw(1.5,0)      node[dot]   (p01) {};
    \draw(1,0.5)      node[dot]   (p10) {};
    \draw(0.5,1)      node[dot]   (p11) {};
    \draw(0,1.5)      node[dot]   (p20) {};
 
    \draw [->] (0,0) -- (0,2);
    \draw [->] (0,0) -- (2,0);
    
    \draw(1.85,0.6) node {$+$};
    \draw(4.45,0.6) node {$=$};
\end{scope}   
  
\begin{scope}[xshift = 2.9cm]
    \draw (0,1.5) node[anchor=east]  {\small$3$};
    \draw (0,2.05) node[anchor=east]  {\small$\alpha_2$};
    \draw (0.5,0) node[anchor=north]  {\small$1$};
    \draw (1,0) node[anchor=north ]  {\small$2$};
    \draw (0,0) node[anchor=north ]    {\small$0$};
    \draw (0,0.5) node[anchor= east]    {\small$1$};
    \draw (0,1) node[anchor= east]    {\small$2$};
    \draw (1.5,0) node[anchor=north ]  {\small$3$};
    \draw (2,0) node[anchor=north ]  {\small$\alpha_1$};
 
    \draw[color=black, help lines, line width=.1pt] (0,0)
      grid[xstep=0.5cm, ystep=0.5cm] (1.25,1.25);
 
    \draw(0,0)      node[dot]   (p00) {};
    \draw(0,0.5)      node[dot]   (p01) {};
    \draw(0,1)      node[dot]   (p02) {};
    \draw(0.5,0)      node[dot]   (p10) {};
    \draw(0.5,0.5)      node[dot]   (p11) {};
    \draw(1,0)      node[dot]   (p20) {};
     \draw(1.5,0)      node[dot]   (p01) {};
    \draw(1,0.5)      node[dot]   (p10) {};
    \draw(0.5,1)      node[dot]   (p11) {};
    \draw(0,1.5)      node[dot]   (p20) {};

    \draw [->] (0,0) -- (0,2);
    \draw [->] (0,0) -- (2,0);
\end{scope}    

\begin{scope}[xshift = 5.6cm]
    \draw (0,3.5) node[anchor=east]  {\small$\alpha_2$};
    \draw (0.5,0) node[anchor=north]  {\small$1$};
    \draw (1,0) node[anchor=north ]  {\small$2$};
    \draw (1.5,0) node[anchor=north ]  {\small$3$};
    \draw (2,0) node[anchor=north ]  {\small$4$};
    \draw (2.5,0) node[anchor=north ]  {\small$5$};
    \draw (3,0) node[anchor=north ]  {\small$6$};
    \draw (0,0) node[anchor=north ]    {\small$0$};
    \draw (0,0.5) node[anchor= east]    {\small$1$};
    \draw (0,1) node[anchor= east]    {\small$2$};
    \draw (0,1.5) node[anchor= east]    {\small$3$};
    \draw (0,2) node[anchor= east]    {\small$4$};
    \draw (0,2.5) node[anchor= east]    {\small$5$};
    \draw (0,3) node[anchor= east]    {\small$6$};
    \draw (3.5,0) node[anchor=north ]  {\small$\alpha_1$};
 
    \draw[color=black, help lines, line width=.1pt] (0,0)
      grid[xstep=0.5cm, ystep=0.5cm] (3.25,3.25);
 
    \draw(0,0)      node[dot]   (p00) {};
    \draw(0,0.5)      node[dot]   (p01) {};
    \draw(0,1)      node[dot]   (p02) {};
    \draw(0,1.5)      node[dot]   (p03) {};
    \draw(0,2)      node[dot]   (p04) {};
    \draw(0,2.5)      node[dot]   (p04) {};
    \draw(0,3)      node[dot]   (p04) {};
    \draw(0.5,0)      node[dot]   (p10) {};
    \draw(0.5,0.5)      node[dot]   (p11) {};
    \draw(0.5,1)      node[dot]   (p12) {};
    \draw(0.5,1.5)      node[dot]   (p13) {};
    \draw(0.5,2)      node[dot]   (p13) {};
    \draw(0.5,2.5)      node[dot]   (p13) {};
    \draw(1,0)      node[dot]   (p20) {};
    \draw(1,0.5)      node[dot]   (p21) {};
    \draw(1,1)      node[dot]   (p22) {};
    \draw(1,1.5)      node[dot]   (p22) {};
    \draw(1,2)      node[dot]   (p22) {};
    \draw(1.5,0)      node[dot]   (p30) {};
    \draw(1.5,0.5)      node[dot]   (p31) {};
    \draw(1.5,1)      node[dot]   (p31) {};
    \draw(1.5,1.5)      node[dot]   (p31) {};
    \draw(2,0)      node[dot]   (p40) {};
    \draw(2,0.5)      node[dot]   (p40) {};
    \draw(2,1)      node[dot]   (p40) {};
    \draw(2.5,0)      node[dot]   (p40) {};
    \draw(2.5,0.5)      node[dot]   (p40) {};
 
    \draw(3,0)      node[dot]   (p40) {};
    \draw [->] (0,0) -- (0,3.5);
    \draw [->] (0,0) -- (3.5,0);
\end{scope}  

\end{tikzpicture}%
\caption{Minkowski sum: $\trgset{2}{3}+\trgset{2}{3} = \trgset{2}{6}$.}%
\label{fig:msum}
\end{figure}

Finally, for  $\set{A} \in \mathbb{N}^{m}$, we define its extension\footnote{In the papers \cite{Brachat.etal10LAaiA-Symmetric}, \cite{Laurent.Mourrain09AdM-generalized} and others this notation was used for the set of monomials.} as
\[
\set{A}^{+} \stackrel{\mathrm{def}}{=} \set{A} \cup (\set{A} + \{\vect{e}_1\}) \cup \cdots \cup (\set{A} + \{\vect{e}_{m}\}),
\]
where $\vect{e}_{k}$, $1\le k\lem$,  denotes the vector of $\mathbb{N}^{m}$ having a 1 in the $k$-th entry and zeros elsewhere. The exterior boundary of $\set{A}$ is defined as
\[
\delta\set{A} = \set{A}^{+} \setminus \set{A}.
\]
For example, for $\set{A} = \trgset{m}{d}$ we have that
\[
\set{A}^{+} = \trgset{m}{d+1}, \quad \delta\set{A} = \degset{m}{d+1}.
\]


\subsection{Quasi-Hankel and quasi-Vandermonde matrices}
Let $\set{A}$ be a multi-index set ordered according to $\prec $:
\begin{equation}\label{eq:mind_set}
\set{A} = \{ \vect{\alpha}_1, \ldots, \vect{\alpha}_{M}\},\quad \vect{\alpha}_{k} \in \mathbb{N}^{m}
\end{equation}
 and $\arr{h} = \{h_{\vect{\alpha}}\}_{\alpha \in \set{D}} \subset \mathbb{C}$ be an array of numbers, where $2\set{A}\subset \set{D}\subset \mathbb{N}^{m}$.
Then the symmetric quasi-Hankel  \cite{Mourrain.Pan00Joc-Multivariate} matrix is defined as
\[
\hmatr{\set{A}}{\arr{h}} \stackrel{\mathrm{def}}{=} [ h_{\vect{\alpha}_{i} + \vect{\alpha}_{j}} ]_{i,j=1}^{M,M}
\]

\begin{example}
For $\set{A} = \trgset{1}{d} = \{0, \ldots, d\}$, $M = d+1$, 
the quasi-Hankel matrix is the ordinary Hankel matrix 
\begin{equation}\label{eq:hankel}
\hmatr{\set{A}}{\iarr{h}}  = [ h_{k+l} ]_{k,l=0}^{d,d} = 
\left[
\begin{mediumarray}{cccc}
\cellcolor{lightgray}h_0 & \cellcolor{lightgray}h_1 & \cellcolor{lightgray} \cdots  & \cellcolor{lightgray}h_d \\
\cellcolor{lightgray}h_1 & \cellcolor{lightgray}h_2 &  \cellcolor{lightgray}\iddots & h_{d+1} \\
\cellcolor{lightgray}\vdots &   \cellcolor{lightgray} \iddots &  \iddots & \vdots \\
\cellcolor{lightgray}h_d & h_{d+1}  &  \cdots & h_{2d} 
\end{mediumarray}
\right].
\end{equation}
\end{example}

\begin{example}
In case $m > 1$, for example $\set{A} = \trgset{2}{3}$ 
(as in Fig.~\ref{fig:msum}) the matrix $\hmatr{\set{A}}{\iarr{h}} $ has the form 
\begin{equation}\label{eq:qhankel_trgset}
\left[
\begin{smallarray}{c|cc|ccc|cccc
\cellcolor{lightgray}h_{0,0} &\cellcolor{lightgray} h_{1,0} & \cellcolor{lightgray} h_{0,1} &  \cellcolor{lightgray} h_{2,0} & \cellcolor{lightgray} h_{1,1} & \cellcolor{lightgray} h_{0,2} & \cellcolor{lightgray} h_{3,0} & \cellcolor{lightgray} h_{2,1} & \cellcolor{lightgray} h_{1,2} & \cellcolor{lightgray} h_{0,3} \\
\hline
\cellcolor{lightgray} h_{1,0} & \cellcolor{lightgray} h_{2,0} & \cellcolor{lightgray} h_{1,1} &  \cellcolor{lightgray} h_{3,0} & \cellcolor{lightgray} h_{2,1} & \cellcolor{lightgray} h_{1,2} & h_{4,0} & h_{3,1} & h_{2,2} & h_{1,3} \\
\cellcolor{lightgray} h_{0,1} & \cellcolor{lightgray} h_{1,1} & \cellcolor{lightgray} h_{0,2} &  \cellcolor{lightgray} h_{2,1} & \cellcolor{lightgray} h_{1,2} & \cellcolor{lightgray} h_{0,3} & h_{3,1} & h_{2,2} & h_{1,3} & h_{0,4} \\
\hline
\cellcolor{lightgray} h_{2,0} & \cellcolor{lightgray} h_{3,0} & \cellcolor{lightgray} h_{2,1} &  h_{4,0} & h_{3,1} & h_{2,2} & h_{5,0} & h_{4,1} & h_{3,2} & h_{2,3} \\
\cellcolor{lightgray} h_{1,1} & \cellcolor{lightgray} h_{2,1} & \cellcolor{lightgray} h_{1,2} &  h_{3,1} & h_{2,2} & h_{1,3} & h_{4,0} & h_{3,2} & h_{2,3} & h_{1,4} \\
\cellcolor{lightgray} h_{0,2} & \cellcolor{lightgray} h_{1,2} & \cellcolor{lightgray} h_{0,3} &  h_{2,2} & h_{1,3} & h_{0,4} & h_{3,2} & h_{2,3} & h_{1,4} & h_{0,5} \\
\hline
\cellcolor{lightgray} h_{3,0} & h_{4,0} & h_{3,1} &  h_{5,0} & h_{4,1} & h_{3,2} & h_{6,0} & h_{5,1} & h_{4,2} & h_{3,3} \\
\cellcolor{lightgray} h_{2,1} & h_{3,1} & h_{2,2} &  h_{4,1} & h_{3,2} & h_{2,3} & h_{5,1} & h_{4,2} & h_{3,3} & h_{2,4} \\
\cellcolor{lightgray} h_{1,2} & h_{2,2} & h_{1,3} &  h_{3,2} & h_{2,3} & h_{1,4} & h_{4,2} & h_{3,3} & h_{2,4} & h_{1,5} \\
\cellcolor{lightgray} h_{0,3} & h_{1,3} & h_{0,4} &  h_{2,3} & h_{1,4} & h_{0,5} & h_{3,3} & h_{2,4} & h_{1,5} & h_{0,6} 
\end{smallarray}
\right],
\end{equation}
where we omitted parentheses in subscripts for conciseness. 
Note that in \eqref{eq:qhankel_trgset}, each block corresponds to a subset $\degset{2}{k}$, $0 \le k \le 6$.
\end{example}

Let $\set{A} \subset \mathbb{N}^{m}$ be the ordered multi-index set defined in \eqref{eq:mind_set},
and $\vect{z}_{1}, \ldots, \vect{z}_{r} \in \mathbb{C}^{m}$ be a set of points.
Then the quasi-Vandermonde matrix is defined as
\[
\vmatr{\set{A}}{\vect{z}_{1}, \ldots, \vect{z}_{r}} \stackrel{\mathrm{def}}{=} \begin{bmatrix} (\vect{z}_{j})^{\vect{\alpha}_{i}} \end{bmatrix}_{i,j=1}^{N,r}.
\]
In particular, for $m=1$, $\set{A} = \trgset{1}{d} = \{0,\ldots,d\}$, it is just an ordinary rectangular Vandermonde matrix.

\begin{example}
For $\set{A} = \trgset{2}{3}$, $r=3$ and $\vect{z}_k = \left[\begin{smallmatrix} \lambda_k \\ \mu_k\end{smallmatrix}\right]$, $k\in\{1,2,3\}$,  we have that $\vmatr{\set{A}}{\vect{z}_{1}, \vect{z}_{2}, \vect{z}_{3}} = $
\small\begin{equation}\label{eq:vander_trgset}
\left[\!
\begin{array}{c@{\;}|c@{\;\,}c@{\;\,}|c@{\;\,}c@{\;\,}c@{\;\,}|c@{\;\,}c@{\;\,}c@{\;\,}c@{\;}}
1 & 
\lambda_1 & 
\mu_1 & 
 \lambda_1^2 &
  \lambda_1 \mu_1 &
   \mu_1^2 &
\lambda_1^3 & 
\lambda_1^2 \mu_1 & 
\lambda_1 \mu_1^2  & 
\mu_1^3  \\
1 & 
\lambda_2 & 
\mu_2 & 
 \lambda_2^2 &
  \lambda_2 \mu_2 &
   \mu_2^2 &
\lambda_2^3 & 
\lambda_2^2 \mu_2 & 
\lambda_2 \mu_2^2  & 
\mu_2^3  \\
1 & 
\lambda_3 & 
\mu_3 & 
 \lambda_3^2 &
  \lambda_3 \mu_3 &
   \mu_3^2 &
\lambda_3^3 & 
\lambda_3^2 \mu_3 & 
\lambda_3 \mu_3^2  & 
\mu_3^3  
\end{array}
\right]^{\T}\!\!\!.
\end{equation}\normalsize
\end{example}

Finally, we will use the following definition.
\begin{definition}\label{def:A_independence}
The points $\vect{z}_1, \ldots, \vect{z}_r \in \mathbb{C}^{m}$ are called $\set{A}$-independent if 
\[
\mathop{\text{rank}} \vmatr{\set{A}}{\vect{z}_{1}, \ldots, \vect{z}_{r}} = r.
\]
\end{definition}
The notion of $\set{A}$-independence is equivalent to the fact the monomials $\{\vect{x}^{\vect{\alpha}}\}_{\vect{\alpha}\in \set{A}}$   taken on the grid of points $\{\vect{z}_1, \ldots, \vect{z}_r\}$ form a set of $\#{\set{A}}$ vectors spanning a linear space of dimension $r$. Hence, these monomials can interpolate any function on this grid. 

If $m=1$, the points are always $\set{A}$-independent for any $\set{A}$ with $r \le \#\set{A}$.
Although for $m > 1$ this is no longer the case,  the following remark holds true.

\begin{remark}\label{rem:A_independence_generic}
$\set{A}$-independence is a generic property, 
i.e., points $\{\vect{z}_j\}^r_{j=1}$ randomly drawn according to an absolutely continuous distribution are $\set{A}$-independent if $r \le \#\set{A}$. 
This follows from the fact that the set of $\set{A}$-independent points is open in the Zariski topology.
\end{remark}

\subsection{Complex nuclear norm minimization}
Now let $\struct{\vect{p}}$  be the matrix structure given in \eqref{eq:affine_structure}, but now $\matr{S}_0 \in \mathbb{C}^{n \times n}$, $\matr{S}_k \in \mathbb{R}^{n\times n}$ for  $k \ge 1$, and the parameter is complex $\vect{p}_{\mathbb{C}} \in \mathbb{C}^{N}$, \emph{i.e.},
\eqref{eq:affine_structure} defines a complex-valued map $\mathscr{S}: \mathbb{C}^{N} \to \mathbb{C}^{n \times n}$.

In order to derive the optimality conditions for the complex-valued case, we construct an extended real-valued structure $\mathscr{S}_{ext}: \mathbb{R}^{2N} \to \mathbb{R}^{2n\times 2n}$ as follows.
For $\vect{p}_{ext} = \begin{bmatrix} \vect{p}_{\mathcal{R}} \\ \vect{p}_{\mathcal{I}} \end{bmatrix}$, where $\vect{p}_{\mathcal{R}},\vect{p}_{\mathcal{I}} \in \mathbb{R}^{N}$, we define an equivalent (non-symmetric) matrix structure:
\begin{equation}\label{eq:affine_ext0}
\mathscr{S}_{ext}(\vect{p}_{ext}) \stackrel{\mathrm{def}}{=} 
\begin{bmatrix} \struct{\vect{p}_{\mathcal{R}}} & -\struct{\vect{p}_{\mathcal{I}}} \\ \struct{\vect{p}_{\mathcal{I}}} &  \struct{\vect{p}_{\mathcal{R}}} \end{bmatrix}
\end{equation}
From \cite{Day.Heroux01SJoSC-Solving}, the singular values of $\mathscr{S}_{ext}(\vect{p}_{ext})$ contain two copies of singular values of $\struct{\vect{p}_{\mathbb{C}}}$. Hence,
\[
\rank{\mathscr{S}_{ext}(\vect{p}_{ext})} = 2 \rank{\struct{\vect{p}_{\mathbb{C}}}},
\]
and the complex rank minimization problem \eqref{eq:rankmin}  is equivalent to real rank minimization 
\begin{equation}\label{eq:rankmin_ext}
\widetilde{\vect{p}}_{ext} =  \arg \min_{\vect{p}_{ext} \in \mathbb{R}^{2N}} \mathop{\text{rank}} \mathscr{S}_{ext}(\vect{p}_{ext}).
\end{equation}
Moreover, the problem \eqref{eq:nnmin}, is equivalent to the real nuclear norm minimization problem
\begin{equation}\label{eq:nnmin_ext}
\widehat{\vect{p}}_{ext} =  \arg \min_{\vect{p}_{ext} \in \mathbb{R}^{2N}} \| \mathscr{S}_{ext}(\vect{p}_{ext})\|_*.
\end{equation}
The following proposition shows that we can rewrite the optimality conditions for the problem \eqref{eq:nnmin_ext} in a convenient form, as in  Lemmae~\ref{lem:opt_first_order_nnmin} and \ref{lem:unique_minimizer_nnmin}

\begin{proposition}[Complex optimality conditions]\label{prop:opt_sufficient_complex}
Let $\vect{p}_{\mathbb{C}} = \vect{p}_{\mathcal{R}} + i \vect{p}_{\mathcal{I}} \in \mathbb{C}^N$, $\struct{\vect{p}_{\mathbb{C}}} = \matr{U}_{\mathbb{C}} \Sigma \matr{V}_{\mathbb{C}}^{\H}$ be an SVD of the symmetric matrix $\struct{\vect{p}_{\mathbb{C}}}$, and define $\matr{B}_{\mathbb{C}} := \matr{U}_{\mathbb{C}}^{} \matr{V}_{\mathbb{C}}^{\H}$, $\matr{P}_{\mathbb{C}} = \matr{U}_{\mathbb{C}}^{} \matr{U}_{\mathbb{C}}^{\H}$, and $\matr{Q}_{\mathbb{C}} = \matr{I}_n - \matr{P}_{\mathbb{C}}$.
Then it holds that:

\begin{enumeratex}
\noindent\item The point  $\vect{p}_{\mathbb{C}}$ is a minimizer of \eqref{eq:nnmin_ext} if and only if there exists $\matr{M} \in \mathbb{C}^{n \times n}$ with $\|\matr{M}\|_2 \le 1$ that satisfies \eqref{eq:fo_condition_matrix}.

\noindent\item
The point $\vect{p}_{ext}$ is the unique minimizer of \eqref{eq:nnmin_ext} if there exists $\matr{M} \in \mathbb{C}^{n \times n}$ with $\|\matr{M}\|_2 < 1$ that satisfies \eqref{eq:fo_condition_matrix}, and $\mathscr{A}(\matr{P})$ is full row rank.
\end{enumeratex}
\end{proposition}
\begin{proof}See Appendix \ref{proofcomplex-sec} for a proof.\end{proof}

\begin{remark}\label{rem:equivalent_conditions_slrmc_DP15}
Lemmae~\ref{lem:opt_first_order_nnmin},~\ref{lem:unique_minimizer_nnmin}, and Proposition~\ref{prop:opt_sufficient_complex} are related to  optimality conditions used in \cite{Dai.Pelckmans15A-nuclear}. Indeed, the rank condition on $\rank{\mathscr{A}(\matr{P})} = N$ is equivalent to $\matr{Q}\matr{H}\matr{Q}^{\T} \neq 0$ for all $\matr{H}$ of the form 
\[
\forall \matr{H} =  \sum\limits_{k=1}^{N}\Delta p_k \matr{S}_k , \quad \Delta\vect{p} \in \mathbb{C}^{N} \setminus \{\vect{0}\},
\]
which corresponds to \cite[Proposition 2]{Dai.Pelckmans15A-nuclear}.
Next, the condition \eqref{eq:fo_condition_matrix} can be rewritten as
\[
\langle \matr{S}_k, \matr{B}+\matr{Q}\matr{M}\matr{Q}^{\T}\rangle_F = \matr{0},\quad \forall k\in\{1,\ldots,N\},
\]
which corresponds to the condition in \cite[Lemma 2]{Dai.Pelckmans15A-nuclear}.
The authors of \cite{Dai.Pelckmans15A-nuclear}, however, do not make explicit connection with general optimality conditions for convex optimization problems, presented in Section~\ref{sec:cvx_opt_cond}.
\end{remark}







\section{Introduction}
The problem of completing matrices with missing entries can be traced back to the works of Prony in 1795, and has been addressed since in various fields including: 
compressed sensing \cite{Chen.Chi14IToIT-Robust,CandR09:fcm,Gros11:ieeeit},
system identification and control \cite{DeSc00:jcam,FazePST13:simax,LiuV09:simax}, 
graph theory \cite{Tros00:coa}, 
collaborative filtering \cite{CandP10:pieee}, 
information theory \cite{GrayD05}, 
chemometrics \cite{Bro97:cils}, 
seismics \cite{Hogb03:laa,KreiSS13:geophysics},   
estimation problems and sensor networks \cite{CandP10:pieee}, to cite a few.
It also appears as a subproblem in the computation of symmetric tensor Canonical Polyadic (CP) decompositions \cite{Brachat.etal10LAaiA-Symmetric}.

\subsection{Structured matrix completion}
We are interested in structured matrices of the form
\begin{equation}\label{eq:affine_structure}
\struct{\vect{p}} = \matr{S}_0 + \sum\limits_{k=1}^{N} p_k \matr{S}_k,
\end{equation}
where $\matr{S}_k$, $k \in \{0,\ldots, N\}$ are known linearly independent $n\times n$ matrices, and $\vect{p}=[p_1,\dots, p_N]^{\T}$.
Without loss of  generality, we assume that the matrices $\matr{S}_k \in \mathbb{C}^{n\times n}$ are symmetric (a nonsymmetric matrix completion problem can be always symmetrized).
Thus, $\mathscr{S}$ is an injective map $\mathbb{C}^N \to \mathbb{C}^{n\times n}$, called affine matrix structure.
The Structured Low-Rank Matrix Completion (SLRMC) for complex affine matrix structures is then stated  formally as
\begin{equation}\label{eq:rankmin}
\widetilde{\vect{p}} =  \arg \min_{\vect{p} \in \mathbb{C}^{N}} \rank{\struct{\vect{p}}}.
\end{equation}
In the literature on matrix completion, the problem~\eqref{eq:rankmin} is often formulated in dual form, \textit{i.e.}, as rank minimization subject to linear constraints, and is called affine rank minimization \cite{Recht.etal10SR-Guaranteed}.
In this paper we prefer the formulation \eqref{eq:rankmin}, which seems to be more suitable for completion of structured (\textit{e.g.}, Hankel-like) matrices.

There are special cases when the solution to SLRMC can be found in polynomial time: partially known block-triangular matrices \cite{Woerdeman89LAaiA-Minimal}, Hankel/Toeplitz matrices \cite{Iohvidov82-Toeplitz,Heinig.Rost84-Algebraic}, block-Hankel matrices \cite{Feldmann.Heinig99IEaOT-Parametrization} and some cases of quasi-Hankel matrices \cite{Laurent.Mourrain09AdM-generalized}.
In the general case, the low-rank matrix completion is NP-hard (see, \emph{e.g.}, \cite{Fazel02PhD-Matrix}).

SLRMC can be also considered as an extreme case of Structured Low-rank matrix Approximation (SLRA) problem with missing data \cite{Markovsky.Usevich13SJMAA-Structured}.
The latter problem is more relevant in practice, where we may have noise in addition to missing data.

\subsection{A convex relaxation}
A  popular approach in machine learning \cite{Fazel02PhD-Matrix,Recht.etal10SR-Guaranteed} is to build a  relaxation of LRMC, by replacing the rank with the nuclear norm (\textit{i.e.} the sum of singular values): 
\begin{equation}\label{eq:nnmin}
\widehat{\vect{p}} = \arg \min_{\vect{p} \in \mathbb{C}^{N}} \| \mathscr{S}(\vect{p}) \|_*.
\end{equation}
Now \eqref{eq:nnmin} is a convex optimization problem, and a variety of convex optimization methods can be used to find its global minimum.
A central question  is when do the solutions of \eqref{eq:nnmin} and \eqref{eq:rankmin} coincide (\emph{i.e.}, the conditions on low-rank matrix recovery with the nuclear norm).

A special case of SLRMC is when each matrix $\matr{S}_k$ contains only one nonzero element.
This is the most common unstructured matrix completion: $\matr{S}_0$ is the known part of the matrix and the positions of nonzero elements in $\matr{S}_k$ indicate the values to be completed.
There is a vast literature on the subject on low-rank matrix recovery, where mainly 
the case of unstructured matrix completion is treated.
Most of the results are proved in a random setting  \cite{CandR09:fcm,Recht.etal10SR-Guaranteed,Gros11:ieeeit}: the positions of missing entries (non-zero elements of $\matr{S}_k$, $k \in \{1,\ldots, N\}$) are assumed to be drawn randomly; often the known entries  are also assumed to be random.
There are also results on the general affine rank minimization (which is equivalent to SLRMC), but the linear constraints are also assumed to be drawn randomly according to a certain probability distribution.

Up to the authors' knowledge, there exists only one result \cite{Dai.Pelckmans15A-nuclear}, which 
treats the case of fixed structure, in a very simple case.
\begin{theorem}[{\cite[Thm. 1]{Dai.Pelckmans15A-nuclear} }]\label{thm:rank_one}
Let $\mathscr{S}$ be  a Hankel matrix
\[
\mathscr{S}(\vect{p}) = 
\begin{bmatrix}
1 & \lambda &  \cdots & \lambda^{n} \\
\lambda & \lambda^2 &  \iddots & p_1 \\
\vdots &    \iddots &  \iddots & \vdots \\
\lambda^{n} & p_1 &  \cdots & p_{n-1} \\
\end{bmatrix},
\]
where $\lambda \in (-1;1)$. Then the solution of \eqref{eq:nnmin}, with  $\vect{p} \in \mathbb{R}^{n-1}$, is unique and coincides with the minimal rank (rank-$1$) completion, which is given by
$p_k  = \lambda^{n+k}$.
\end{theorem}
In this paper we extend the results of \cite{Dai.Pelckmans15A-nuclear} in two directions: (i) to  Hankel matrices with arbitrary rank, and (ii) to quasi-Hankel matrices, which are particularly interesting in the context of symmetric tensor CP decomposition \cite{Brachat.etal10LAaiA-Symmetric}.
As in \cite{Dai.Pelckmans15A-nuclear}, we consider cases when the solution to SLRMC is known, and establish conditions on $\mathscr{S}$ when the solution of \eqref{eq:rankmin} and \eqref{eq:nnmin} coincide.

Our results are more general (for example, applicable both in the real and complex cases), and do not depend on the results of \cite{Dai.Pelckmans15A-nuclear}.
However, we believe that our exposition may also help to understand the complicated logic of the proof in \cite{Dai.Pelckmans15A-nuclear}.

In Section~\ref{sec:background} we introduce the main notation, in particular quasi-Hankel matrices, which are generalizations of Hankel matrices.
In Section~\ref{seq:qh_completion} we formally state the considered quasi-Hankel matrix completion problem, and summarize some known results
(this summary is needed for stating the main results of the paper in Section~\ref{sec:results}). 
In Section~\ref{sec:nnmin_genprop} we recall optimality conditions for convex optimization problems, and specialize them to nuclear norm minimization for structured matrices.

Section~\ref{sec:lemmas} contains the main lemmas needed for proofs of the results of the paper. The lemmas imply that the optimality conditions are satisfied if the column space of completed matrices is not too far from a certain simply structured subspace.
Finally, in Section~\ref{sec:results}, we prove the main results of the paper, and illustrate them with numerical experiments in Section~\ref{sec:numerical}.

\section{Hankel and Quasi-Hankel matrix completion}\label{seq:qh_completion}
\input{rankmin-hankel.tex}
\input{rankmin-qhankel.tex}

\input{optimality.tex}
\input{complex.tex}

\input{results-lemmas.tex}
\input{results-hankel.tex}

\subsection{Quasi-Hankel case}\label{sec:qhankel_results}

\input{results-qhankel.tex}

\section{Numerical results}\label{sec:numerical}

\input{numerical.tex}


\section{Appendix}\label{sec:appendix}
\input{appendix.tex}

\input{acknowledgements.tex}

\bibliographystyle{alpha}

\subsection{Hankel case}
In this case we illustrate on the examples Theorem~\ref{thm:rank_r}. Theorem~\ref{thm:rank_r} only states the existence of such radius $\rho$, and a lower bound for $\rho$ may be obtained along the lines of the proof of the theorem. However, this bound may be to small, and in this section we aim at showing on numerical experiments what would be the largest lower bound.

All the numerical experiments are reproducible and available on request.
The MATLAB package CVXOPT \cite{CVX} with default settings is used for nuclear norm minimization.

The setup for the following experiments will be similar. We take a specific $\matr{h}_d$, compute the solution of \eqref{eq:qhankel_rankmin}, and measure the  Frobenius norm between the computed solution and the canonical completion \eqref{eq:canonical_completion}.


\subsubsection{The rank-one case}
First, we consider the rank-one case. We take $n=6$, and a rank-one exponential sequence $\vect{h}_{d}$, i.e. $h_k = \lambda^{k}$, where $\lambda = a + bi$, $a,b \in (-1,1)^2$, and plot the results in Fig.~\ref{fig:cexp}.
\begin{figure}[hbt!]%
\centering
\includegraphics[height=6cm]{code/hankel/hankel_cexp}%
\caption{Nuclear norm reconstruction (Frobenius distance), $h_k = \lambda^{k}$, $\lambda = a + bi$. Black area correspond to the values less than $10^{-6}$.}
\label{fig:cexp}%
\end{figure}

In Fig.~\ref{fig:cexp}, we see that the largest lower bound for $\rho$ is very close to $1$. This coincides with the bound for real $\lambda$ given by Theorem~\ref{thm:rank_one}.

\subsubsection{The  rank-two case}
We consider real sequences $\vect{h}_d$ with $\hrank{\vect{h}_d} = 2$. In this case the following three situations are possible:
\begin{enumerate}
\item $\lambda_1, \lambda_2 \in \mathbb{R}$ (two simple real roots);
\item $\lambda_2 = \overline{\lambda_2} \not\in \mathbb{R}$  (two simple complex conjugate roots);
\item $\lambda_1 \in \mathbb{R}$, $\nu_1 = 2$ (double real root).
\end{enumerate}
The first case is considered in \cite[Fig. 1]{Dai.Pelckmans15A-nuclear}, where it is shown (numerically) that the radius $\rho$ is less than $1$. 
In this section, we examine the second and the third cases.
We generate the corresponding $\vect{h}_d$ and compute the Frobenius distance between the solutions of \eqref{eq:rankmin} and \eqref{eq:nnmin}, i.e., we compute $\|\mathscr{S}(\widetilde{\vect{p}}) - \mathscr{S}(\widehat{\vect{p}})\|_F$.

In Fig.~\ref{fig:sine}, we plot the nuclear norm reconstructions for a $6\times 6$ matrix and the last two cases.
As seen in Fig.~\ref{fig:sine}, the radius is also strictly less than $1$. 
The radius is smaller in the case of a double root and also in the case when two conjugate roots are close to each other. 
\begin{figure}[ht!]%
\centering
\includegraphics[height=6cm]{code/hankel/hankel_sin}\\
\includegraphics[height=6cm]{code/hankel/hankel_lin}%
\caption{Nuclear norm reconstruction (Frobenius distance). Top: for two complex conjugate roots $\lambda_{1,2} = \rho \cdot\exp(\pm i\pi \omega)$ (corresponds to the damped cosine sequence $h_t = \rho^{t} \cdot \cos(\pi (\omega+1)t)$). Bottom: for a double root $\rho$ (corresponds to the damped linear function $h_t = (t \cdot \tan(0.75 \cdot \pi \cdot \varphi) +1) \cdot \rho^t$). Black areas correspond to the values less than $10^{-6}$.}%
\label{fig:sine}%
\end{figure}


\subsection{Multiple exponents}
In this experiment, we aim at estimating the radius $\rho$ based on random realizations of $\lambda_k$.
We fix $n=9$, and for each $r \in \{1,\ldots,4\}$ and for $\rho \in (0,1)$, we generate randomly  the set $\{\lambda_1,\ldots,\lambda_r\}$, such that $|\lambda_1| = \rho$ and $|\lambda_k| \le \rho$.

We consider two situations: 
\begin{itemize}
\item real roots $\lambda_k = \rho_k$ (in this case $\rho_1 = \rho$, and $\rho_k$, $k>1$ are independent and uniformly distributed in $[\rho;-\rho]$)
\item complex roots $\lambda_k = \rho_k e^{i\pi\phi_k}$, where $\rho_k$ are as in the previous example,  $\phi_k$ are independent, uniformly distributed in $[0;1]$, and independent of $\rho_k$.
\end{itemize}

We repeat the experiment $M = 100$ times, and select the maximum Frobenius error across all the realizations. The results are plotted in Fig.~\ref{fig:9roots}.

\begin{figure}[ht!]%
\centering
\includegraphics[height=6cm]{code/hankel/hankel_n9_real}\\
\includegraphics[height=6cm]{code/hankel/hankel_n9_complex}%
\caption{Nuclear norm reconstruction, $n=9$, $M=400$ (Frobenius distance). Top: real roots, bottom: complex roots.
Black area correspond to the values less than $10^{-5}$.}%
\label{fig:9roots}%
\end{figure}

The results in Fig.~\ref{fig:9roots} confirm the conclusions of Theorem~\ref{thm:rank_r}. We see that the nuclear norm heuristic works up to a certain $\rho$.
Note that the bounds are similar for the real and complex cases.

\subsection{Quasi-Hankel case}

\subsubsection{Random exponents}
In this section, we demonstrate Theorem~\ref{thm:qhankel_rank_r}. 
In the experiments, we fix $m=2$, $d=3$ and $r=3$ (thus we are dealing with the completion of the structure \eqref{eq:qhankel_trgset}).
We generate random $\vect{y}_1, \vect{y}_2,\vect{y}_3 \in \mathbb{C}^{m}$, such that 
\[
\vect{y}_k = 
\begin{bmatrix}
a_{k} + i b_{k}\\
e_{k} + i f_{k}\\
\end{bmatrix},
\]
and $a_{k}, b_{k}, e_k, f_k$ are independent identically distributed on $[-0.5;0.5]$.

For  $\rho \in (0;1]$, we define  $\vect{z}_k$ as in Theorem~\ref{thm:qhankel_rank_r}, and consider the matrix completion with nuclear norm for the array \eqref{eq:exp_array}, where $c_k$ are chosen to be $c_1 = c_2 = c_3 = 1$.
We numerically compute the solution $\widehat{\vect{p}}$ of the nuclear norm minimization \eqref{eq:nnmin}, and 
compare it with the solution $\widetilde{\vect{p}}$ of the rank minimization \eqref{eq:rankmin} (which is known from Proposition~\ref{prop:flat_ext_exp_array}).
We repeat the experiment $M = 10$ times, and plot in Fig.~\ref{fig:qhankel_random} the dependence of $\|\widehat{\vect{p}}-\widetilde{\vect{p}}\|_2$.

\begin{figure}[ht!]%
\centering
\includegraphics[height=6cm]{code/qhankel/qhankel_random}%
\caption{Nuclear norm reconstruction for quasi-Hankel matrices (parameter vector distance). Each of the curves represents a realization and shows the dependence of $\|\widehat{\vect{p}}-\widetilde{\vect{p}}\|_2$ on $\rho$.}%
\label{fig:qhankel_random}%
\end{figure}

In Fig.~\ref{fig:qhankel_random}, we see that for each realization of $\vect{y}_k$-s, there exists a radius $\rho_0$  predicted by Theorem~\ref{thm:qhankel_rank_r}.

\subsubsection{Beyond the theoretical results: nonunique decompositions}
As in the previous section, we consider the case $m=2$, $d=3$. But we choose the rank $r=4$, for which the conditions of Theorem~\ref{thm:qhankel_rank_r} no longer hold true.
For $3 \times 3 \times 3$ symmetric tensors, this is exactly the value of generic rank \cite{Iarobbino.Kanev99-Power}.

The construction of the example is based on the correspondence with symmetric tensors.
We take $d$ linearly independent vectors in $\mathbb{R}^{d}$, i.e.,
\[
\vect{v}_1,\ldots, \vect{v}_{d} \in  \mathbb{R}^{d}.
\]
Next, we consider the symmetric tensor obtained by symmetrization of a non-symmetric rank-one tensor:
\[
\mathcal{T} = \mathop{\mathrm{Sym}} (\vect{v}_1 \otimes \cdots \otimes \vect{v}_{d}).
\]
By \cite{Carlini.etal12JoA-solution}, the rank of the tensor $\mathcal{T}$ is equal to $2^{d-1}$, and the tensor admits an infinite family of decompositions, parameterized by
\[
\mathcal{T} = \frac{1}{2^{d-1} d!} \sum_{\varepsilon_2, \ldots, \varepsilon_{d} = 0 }^{1}
(-1)^{\varepsilon_2 + \cdots+ \varepsilon_d}
\otimes^{d} \vect{b}_{\varepsilon_2,\ldots,\varepsilon_d},
\]
where
\[
\vect{b}_{\varepsilon_2,\ldots,\varepsilon_d} \stackrel{\mathrm{def}}{=}
(\gamma_1 \vect{v}_1 + \gamma_2 (-1)^{\varepsilon_2} \vect{v}_2 +  \cdots + (-1)^{\varepsilon_d} \gamma_d\vect{v}_{d} ),
\]
and $\gamma_1,\ldots,\gamma_d \in \mathbb{R}$ satisfy $\gamma_1\cdots\gamma_d = 1$.

In order to set up the matrix completion problem, for given $\gamma_1,\ldots,\gamma_d$, we first construct the  array $\{h_{\vect{\alpha}}\}_{\alpha \in \mathbb{N}^{m}}$ (which is equivalent to the specific tensor decomposition), where $m \stackrel{\mathrm{def}}{=} d-1$, as follows:
\begin{equation}\label{eq:array_nonunique}
h_{\vect{\alpha}} =
 \sum_{\varepsilon_2, \ldots, \varepsilon_{d} = 0 }^{1}
c_{\varepsilon_2, \ldots, \varepsilon_{d}} \vect{\lambda}^{\vect{\alpha}}_{\varepsilon_2, \ldots, \varepsilon_{d}},
\end{equation}
where
\[
\begin{split}
c_{\varepsilon_2, \ldots, \varepsilon_{d}}  & \stackrel{\mathrm{def}}{=} \frac{1}{2^{d-1} d!} (-1)^{\varepsilon_2 + \cdots+ \varepsilon_d} (\vect{b}_{\varepsilon_2,\ldots,\varepsilon_d,1})^d, \\
\vect{\lambda}_{\varepsilon_2,\ldots,\varepsilon_d} & \stackrel{\mathrm{def}}{=}
b_{\varepsilon_2,\ldots,\varepsilon_d,1}^{-1}
\begin{bmatrix}
b_{\varepsilon_2,\ldots,\varepsilon_d,2} \\
\vdots \\
b_{\varepsilon_2,\ldots,\varepsilon_d,d} \\
\end{bmatrix},\\
\vect{b}_{\varepsilon_2,\ldots,\varepsilon_d} &=
\begin{bmatrix}
b_{\varepsilon_2,\ldots,\varepsilon_d,1} \\
\vdots \\
b_{\varepsilon_2,\ldots,\varepsilon_d,d} \\
\end{bmatrix}.
\end{split}
\]
Finally, we solve the nuclear norm minimization problem \eqref{eq:nnmin}, for the structure defined as in \eqref{eq:qhankel_trgset}. 

Assume for instance $(d,m)=(3,2)$ and  consider
\[
\vect{v}_1 = \begin{bmatrix}
4 
\\ 1
\\ 1
\end{bmatrix}, 
\vect{v}_2 = \begin{bmatrix}
1 
\\ 4
\\ 1
\end{bmatrix}, 
\vect{v}_3 = \begin{bmatrix}
1 
\\ 1
\\ 4
\end{bmatrix}.
\]
For this case, the nuclear norm minimization yields a $4$-rank matrix completion, which corresponds to the minimal rank. However, the obtained completion differs from the initial completion \eqref{eq:array_nonunique}, which indicates that the nuclear norm minimization resulted in a different decomposition from the infinite family of decompositions. 

We repeat the experiment for random $\vect{v}_k$, generated as
\[
\begin{bmatrix}
\vect{v}_1 & \vect{v}_2 & \vect{v}_3
\end{bmatrix} = A + E,
\]
where the elements of $E$ are i.i.d. uniform on $[-1;1]$, and $A$ is one of the two matrices:
\[
A = 3\begin{bmatrix} 1& 1 & 1\\1& 1 & 1\\1& 1 & 1\end{bmatrix}, \mbox{ or }
A = 3\begin{bmatrix} 1& 0 & 0\\0& 1 & 0\\0& 0 & 1\end{bmatrix}.
\]
By drawing $M=100$ random realizations, we check when the Euclidean norm of the vector of the last singular values $(\sigma_{5},\ldots,\sigma_{10})$ is less than $10^{-4}$ (we say that the nuclear norm heuristics succeeds in this case). We observed that in the first scenario, the nuclear norm heuristic always failed, but for the second scenario in $77$ cases the nuclear norm heuristic succeeded.













\section{Optimality conditions of nuclear norm minimization}\label{sec:nnmin_genprop}
\subsection{Optimality conditions in convex optimization}\label{sec:cvx_opt_cond}
We recall some definitions from the field of convex optimization \cite[Chapter D]{Hiriart-Urruty.Lemarechal01-Fundamentals}.
For a convex (possibly non-differentiable) function $f: \mathbb{R}^{N} \to \mathbb{R}$, the subdifferential \cite[Def. 1.2.1]{Hiriart-Urruty.Lemarechal01-Fundamentals}  of $f$ is defined as the set $\partial f(\vect{x}) \subset \mathbb{R}^{N}$
\[
\partial f(\vect{x}) \stackrel{\mathrm{def}}{=} \{\vect{d} : f({\vect{y}}) - f(\vect{x}) \ge \langle \vect{d}, \vect{y}-\vect{x}\rangle\quad \forall \vect{y} \in \mathbb{R}^{N} \}.
\]
In particular, if $f$ is differentiable at a point $\vect{x}$, then the subgradient has only one element: the usual gradient, i.e., $\partial f(\vect{x}) = \{ \nabla f(\vect{x})\}$.

For the unconstrained  convex optimization problem
\begin{equation}\label{eq:cvx_opt}
\min_{\vect{x} \in \mathbb{R}^{N}}  f(\vect{x}),
\end{equation}
we recall the first-order optimality condition, which is necessary and sufficient in this case.
\begin{lemma}[First-order optimality, {\cite[Thm. 2.2.1]{Hiriart-Urruty.Lemarechal01-Fundamentals}}]\label{lem:cvx_opt_first_order}
A  point $\vect{x}$ is a minimum point of \eqref{eq:cvx_opt} if and only if 
\begin{equation}\label{eq:first_order_condition}
\vect{0} \in  \partial f(\vect{x}).
\end{equation}
\end{lemma}
In particular, for differentiable functions, the condition of Lemma~\ref{lem:cvx_opt_first_order} reduces to $\nabla f(\vect{x}) = \vect{0}$.
Next, we use a simple uniqueness condition for the minimizer.
\begin{lemma}[Sufficient condition of uniqueness]\label{lem:cvx_opt_uniqueness}
A  point $\vect{x}$ is the unique minimizer of \eqref{eq:cvx_opt} if 
\begin{equation}\label{eq:uniqueness_convex}
\vect{0} \in \inter{\partial f(\vect{x})},
\end{equation}
where $\inter{\cdot}$ denotes the interior of a set.
\end{lemma}
\begin{proof}
In this case for any $\vect{y}\neq \vect{x}$ there exists $\delta > 0$ such that $\delta\cdot(\vect{y}-\vect{x}) \in \partial f(\vect{x})$.
By definition of $\partial f(\vect{x})$, we have that $f(\vect{y}) -f(\vect{x}) \ge \delta \|\vect{y}-\vect{x}\|^2_2 > 0$.
\end{proof}

\subsection{Subdifferential of the nuclear norm}
First, we recall the form of the subdifferential of the nuclear norm of a matrix. 
Let $\matr{X} \in \mathbb{R}^{n_1 \times n_2}$ be a matrix of rank $r$, and let $\matr{X} = \matr{U} \matr{\Sigma} \matr{V}^{\T}$ be an SVD of $\matr{X}$, 
where $\matr{U} \in \mathbb{R}^{n_1 \times r}$, $\matr{V} \in \mathbb{R}^{n_2\times r}$ and $\matr{\Sigma} \in \mathbb{R}^{r\times r}$ is a diagonal matrix of nonzero singular values. 
Next, let $\matr{U}_{\bot} \in \mathbb{R}^{n_1 \times (n_1-r)}$, $\matr{V}_{\bot} \in \mathbb{R}^{n_2\times (n_2-r)}$ be the bases of the left and right nullspaces of $\matr{X}$, respectively.
Then, according to \cite[p. 41]{Watson92LAaiA-Characterization}, the subdifferential of the nuclear norm at $\matr{X}$ is equal to $\partial\|\matr{X}\|_{*} = $
\[
\{\matr{B} + \matr{U}_{\bot} \matr{W} \matr{V}^{\top}_{\bot}: \matr{W} \in \mathbb{R}^{(n_1-r) \times (n_2-r)}\!, \|\matr{W}\|_2 \le 1\},
\]
where $\matr{B}$ is defined as
\begin{equation}\label{eq:skew_projector}
\matr{B} \stackrel{\mathrm{def}}{=} \matr{U} \matr{V}^{\T},
\end{equation}
and $\|\cdot\|_2$ is the spectral norm (largest singular value).

\begin{remark}\label{rem:B_uniqueness}
When the SVD of $\matr{X}$ is not unique, then the matrix $\matr{B}$ from \eqref{eq:skew_projector} is still defined uniquely. In fact, if $\matr{X}$ has multiple singular values, its matrix of left (resp. right) singular vectors is of the form $\matr{U}\matr{\Theta}$ (resp. $\matr{V}\matr{\Theta}$), where $\matr{\Theta}$ is an orthonormal matrix which commutes with $\matr{\Sigma}$. 
\end{remark}
Next we consider a real nuclear norm minimization problem
\begin{equation}\label{eq:nnmin_real}
\widehat{\vect{p}} = \arg \min_{\vect{p} \in \mathbb{R}^{N}} f(\vect{p}), \quad f(\vect{p}) \stackrel{\mathrm{def}}{=} \| \struct{\vect{p}} \|_*,
\end{equation}
where $\mathscr{S}$ is defined in \eqref{eq:affine_structure}. By an analogue of chain rule \cite[Thm. 4.2.1]{Hiriart-Urruty.Lemarechal01-Fundamentals}, we immediately have that
\begin{eqnarray}\label{eq:subgradient_Sp}
\partial f (\vect{p}) &=& 
\Big\{
\begin{bmatrix} \langle \matr{S}_1, \matr{H}\rangle_F & \cdots & \langle \matr{S}_N, \matr{H}\rangle_F \end{bmatrix}^{\T} : \nonumber\\
&& \phantom{\Big\{}\matr{H} \in \partial\|\matr{X}\|_{*}, \matr{X} = \struct{\vect{p}}  \Big\}, 
\end{eqnarray}
where $\langle\cdot,\cdot\rangle_F$ denotes the Frobenius inner product.
In the following section, we will give a more compact form or subdifferentials and optimality conditions.

\subsection{Real nuclear norm minimization}
First, we assume that $\matr{X}$ is symmetric and $n_1 = n_2 = n$, then we have that $\matr{U}_{\bot}\matr{U}_{\bot}^{\top} = \matr{V}_{\bot}\matr{V}_{\bot}^{\top} = \matr{Q}$, where $\matr{Q}$ is the projector on the nullspace of $\matr{X}$. Then the subdifferential can be rewritten as
\begin{equation}\label{eq:subgradient_nnorm}
\partial\|\matr{X}\|_{*} = \{ \matr{B} + \matr{Q}\matr{M}\matr{Q}: \|\matr{M}\|_2 \le 1\},
\end{equation}
where $\matr{B}$ is defined as in \eqref{eq:skew_projector}. We note that $\matr{Q} = \matr{I} -\matr{P}$, where $\matr{P}$ is the orthogonal projector on the column space of $\matr{X}$, which can be obtained as
\begin{equation}\label{eq:projector}
\matr{P} \stackrel{\mathrm{def}}{=} \matr{U}\matr{U}^{\T} =\matr{B} \matr{B}^{\T}.
\end{equation}
Next, we define the matrix 
\begin{equation}\label{eq:bfG}
\mathbf{S} \stackrel{\mathrm{def}}{=} \begin{bmatrix} \mathop{\text{vec}}(\matr{S}_1) & \ldots &  \mathop{\text{vec}}(\matr{S}_{N})\end{bmatrix},
\end{equation}
and for a matrix $\matr{P} \in \mathbb{R}^{n\times n}$ we define
\begin{equation}\label{eq:fo_condition_matrix_left}
\mathscr{A}(\matr{P}) \stackrel{\mathrm{def}}{=} \mathbf{S}^{\T} ((\matr{I} - \matr{P}) \otimes (\matr{I} - \matr{P})) \in \mathbb{R}^{N \times n^2},
\end{equation}
where $\otimes$ denotes the Kronecker product.
Then, by \eqref{eq:subgradient_Sp}, the subgradient of $f$  can be rewritten  as $\partial f (\vect{p})=$
\begin{equation}\label{eq:subgradient_Sp_matrix}
\left\{\mathbf{S}^{\T}\! \mathop{\text{vec}}(\matr{B}) + \mathscr{A}(\matr{P}) \mathop{\text{vec}} (\matr{M})\!:
 \|\matr{M}\|_2 \le 1 \right\}.
\end{equation}
with $\matr{M}\!\in\mathbb{R}^{n\times n}$.
Using \eqref{eq:subgradient_Sp_matrix}, we can rewrite Lemma~\ref{lem:cvx_opt_first_order} and Lemma~\ref{lem:cvx_opt_uniqueness} as follows.
\begin{lemma}[First-order  optimality conditions for real nuclear norm minimization]\label{lem:opt_first_order_nnmin}
A point $\vect{p}^{*}$ is a minimizer of \eqref{eq:nnmin_real} if and only if there exists a matrix $\matr{M} \in \mathbb{R}^{n\times n}$ with $\|\matr{M}\|_2 \le 1$ such that
\begin{equation}\label{eq:fo_condition_matrix}
\mathscr{A}(\matr{P}) \mathop{\text{vec}} (\matr{M}) = -\mathbf{S}^{\T} \mathop{\text{vec}}(\matr{B}).
\end{equation}
where $\matr{B}$ is as in \eqref{eq:skew_projector},
 $\matr{P}$ is as in \eqref{eq:projector}, and $\matr{Q} \stackrel{\mathrm{def}}{=} \matr{I}- \matr{P}$.
\end{lemma}
\begin{proof}
Follows from \eqref{eq:subgradient_Sp_matrix} and Lemma~\ref{lem:cvx_opt_first_order}.
\end{proof}
\begin{lemma}[Sufficient condition of uniqueness]\label{lem:unique_minimizer_nnmin}
A point $\vect{p}$ is the unique minimizer of \eqref{eq:nnmin} if there exists $\matr{M} \in \mathbb{R}^{n\times n}$ with $\|\matr{M}\|_2 < 1$ such that \eqref{eq:fo_condition_matrix} holds and the matrix $\mathscr{A}(\matr{P})$ is full row rank (\emph{i.e.}, is of rank $N$).
\end{lemma}
\begin{proof}
Follows from \eqref{eq:subgradient_Sp_matrix} and Lemma~\ref{lem:cvx_opt_uniqueness}.
\end{proof}

\subsection{Solution of Hankel low-rank completion}\label{sec:lin_rec}
Probably the first complete solution of Problem~\ref{prob:qh_completion} for $m=1$ is  contained in \cite[Ch. II]{Iohvidov82-Toeplitz}, where the problem of matrix completion is called ``singular extension'' of Hankel matrices.
In this section, we will use the theory from \cite{Heinig.Rost84-Algebraic}, and we will provide a summary of results in a simplified form.

For a finite sequence $\vect{h}_d = \begin{bmatrix} h_0 & \ldots& h_{d}\end{bmatrix}^{\T} \in \mathbb{C}^{d+1}$, we denote by $\hrank{\vect{h}_d}$ the smallest number $r$ such that there exists a non-zero vector $\vect{q} = \begin{bmatrix} q_0 & q_1&\ldots &q_r \end{bmatrix}^{\T} \neq 0$ for which
\begin{equation}\label{eq:linrec}
q_0 h_{k}  + \ldots + q_{r} h_{k+r}=0, \quad \forall k\in\{0,\ldots, d-r\}.
\end{equation}
The value $\hrank{\vect{h}_d}$ is equal to the maximal rank of the submatrices of the known triangular part of the Hankel matrix \eqref{eq:hankel} (or, equivalently to the maximal rank of a Hankel matrix that can be constructed only from the elements of the vector $\vect{h}_d$). 
The number $\hrank{\vect{h}_d}$ is called \emph{the first characteristic degree} of $\vect{h}_d$ \cite[Def. 5.3, page 81]{Heinig.Rost84-Algebraic}.
We will also call the vector  $\vect{q}$ as \emph{the characteristic vector}\footnote{In \cite{Heinig.Rost84-Algebraic}, $\vect{q}$ does not have a specific name and is denoted by  $p$.} of $\vect{h}_d$. Next, we recall the following basic properties of ${\vect{h}_d}$ and $\vect{q}$.
\begin{itemize}
\item For any $\vect{h}_d \in \mathbb{C}^{d+1}$, $\hrank{\vect{h}_d} \le \frac{d+2}{2}$ (see \cite[Prop. 5.4]{Heinig.Rost84-Algebraic}).
\item If, in addition, $\hrank{\vect{h}_d} < \frac{d+2}{2}$, then the characteristic vector $\vect{q}$ is unique up to scaling by a constant (see \cite[page 84]{Heinig.Rost84-Algebraic}).
\end{itemize}
In what follows, we assume that $q_r \neq 0$ (this is a generic case). The treatment of the case $q_r = 0$ can be found in \cite[page 84]{Heinig.Rost84-Algebraic}).
Then an explicit representation of ${\vect{h}_d}$ is determined by the \emph{characteristic polynomial} 
\begin{equation}\label{eq:char_poly}
q(z) = \sum\limits_{j=0}^r q_j z^j  = q_r \sum\limits_{k=1}^s (z - \lambda_k)^{\nu_k},
\end{equation}
where  $\lambda_k \in \mathbb{C}$ are distinct,  $\nu_k$ are the multiplicities of the roots, and $r = \nu_1 + \cdots + \nu_s$.
\begin{proposition}[A special case of {\cite[Thm 8.1]{Heinig.Rost84-Algebraic}}]
If $q_r \neq 0$ and all the roots of $q(z)$ are simple ($\nu_k = 1$, $s=r$), then the sequence $\vect{h}_d$ admits a representation
\begin{equation}\label{eq:simple_roots}
h_k = \sum\limits_{j=1}^r c_{j} \lambda_j^k.
\end{equation}
\end{proposition}
\begin{example}
For $\vect{h}_d = \begin{bmatrix} 1 & \lambda & \cdots & \lambda^d \end{bmatrix}^{\T}$ (see Theorem~\ref{thm:rank_one}), we have $\hrank{\vect{h}_d}  = 1$ and the characteristic vector can be chosen as  $\vect{q} = \begin{bmatrix} -\lambda & 1 \end{bmatrix}^{\T}$.
\end{example}
The representation \eqref{eq:simple_roots}  is called a \emph{canonical representation} of $\vect{h}_d$ (or the unique canonical representation in case $\hrank{\vect{h}_d} < \frac{d+2}{2}$).
In the general case \eqref{eq:char_poly}, there are multiple roots and the canonical representation has a more complicated form, as stated by the proposition below.

\begin{proposition}[A special case of {\cite[Thm 8.1]{Heinig.Rost84-Algebraic}}]\label{prop:canonical_hankel_general}
Let  $q_r \neq 0$, $\lambda_1 = 0$ and $\lambda_k \neq 0$, and the multiplicities $\nu_k$ of the roots $\lambda_k$ in \eqref{eq:char_poly} are such that $\nu_1 \ge 0$ and $\nu_k > 1$ for $k \ge 2$. Then the sequence $\vect{h}_d$ has the form
\begin{equation}\label{eq:multiple_roots}
h_k = \sum\limits_{j=2}^s c_j(k) \lambda_j^k + \sum\limits_{l=0}^{\nu_1-1} c_{1,l} \delta(k,l), 
\end{equation}
where $c_j(k)$ are polynomials of degree $(\nu_k-1)$ and $\delta(k,l)$ is the Kronecker symbol.
\end{proposition}
\begin{remark}
In the statement of Proposition~\ref{prop:canonical_hankel_general}, if $\nu_1=0$ then the second term in \eqref{eq:multiple_roots} is absent. 
\end{remark}
\begin{example}
In the extreme case $q(z) = q_r z^r$ (\textit{i.e.}, $r=\nu_1$), the canonical representation \eqref{eq:multiple_roots} becomes
\begin{equation}\label{eq:initial_zero_root}
\vect{h}_d = \begin{bmatrix} c_{1,0} & \cdots & c_{1,r-1} & 0 & \cdots & 0 \end{bmatrix}^{\T},
\end{equation}
\end{example}
Apart from the explicit form of the sequence $\vect{h}_d$, the characteristic polynomial gives a solution to the rank minimization problem \eqref{eq:qhankel_rankmin} (for $m=1$).
\begin{proposition}[{A corollary of \cite[Thm. 5.14]{Heinig.Rost84-Algebraic}}]
Let $\vect{q} \in \mathbb{C}^{r+1}$ be a characteristic vector of $\vect{h}_d$ with  $q_r  \neq 0$, $r = \hrank{\vect{h}_d}$. Then it holds that
\begin{enumeratex} 
\item The rank of the minimal rank completion of $\hmatr{\mathcal{A}}{\iarr{h}}$ in \eqref{eq:hankel} is $r$.
\item A minimum rank completion $h_{d+1}, \ldots, h_{2d}$ is given by
the recursive continuation, for $k > d-r$:
\begin{equation}\label{eq:canonical_completion}
~\hspace{-3em} h_{k+r} = -\frac{1}{q_r} (q_0 h_{k}  + \cdots + q_{r-1} h_{k+r-1}) 
\end{equation}
In addition, the values of $h_{k+r}$ for $k > d-r$ can be obtained by using the corresponding formula of canonical representation, namely \eqref{eq:simple_roots} or \eqref{eq:multiple_roots}.
\item If $r < \frac{d+2}{2}$, then the minimum rank completion is unique.
\end{enumeratex}
\end{proposition}

\subsection{Solution of quasi-Hankel low-rank completion}\label{sec:qh_rank_minim}
Unlike Hankel matrices, for $m > 1$ the quasi-Hankel completion problem does not have a closed form solution.
The simplest case when the solution can be easily found is given by a flat extension theorem {\cite[Thm. 1.4]{Laurent.Mourrain09AdM-generalized}}.
\begin{proposition}[Corollary of {\cite[Thm. 1.4]{Laurent.Mourrain09AdM-generalized}}]\label{prop:flat_ext}
Let $\set{A} = \trgset{m}{d}$, and the values $\{{h}_{\vect{\alpha}}\}_{\vect{\alpha} \in \set{A}}$ be given.
Moreover, let $d' \stackrel{\mathrm{def}}{=} \lfloor \frac{d}{2} \rfloor$, $\set{B} \stackrel{\mathrm{def}}{=} \trgset{m}{d'-1}$, and it holds that 
\[
\rank{\hmatr{\set{B}}{\arr{h}}} = \rank{\hmatr{\set{B}^{+}}{\arr{h}}} = r.
\]
Then the unique solution of Problem~\ref{prob:qh_completion} has rank $r$.
\end{proposition}
Proposition~\ref{prop:flat_ext} induces bounds on rank that are too restrictive. For example, for $\set{A} = \trgset{2}{3}$, $d'=1$ and only rank-one cases can be treated. 
In what follows, we consider arrays of special form, for which Proposition~\ref{prop:flat_ext} can be extended. 

Let $\set{C} \subset \mathbb{N}^{m}$ be arbitrary, $\vect{z}_{1}, \ldots, \vect{z}_{r} \in \mathbb{C}^{m}$,
$c_1, \ldots, c_r \in \mathbb{C}$ be some coefficients, and the array of coefficients $\iarr{h} = \{{h}_{\vect{\alpha}}\}_{\vect{\alpha} \in 2\set{C}}$ be defined as
\begin{equation}\label{eq:exp_array}
h_{\vect{\alpha}} = \sum\limits_{k=1}^r c_k \vect{z}_k^{\vect{\alpha}}.
\end{equation}
It is easy to see that the following lemma holds true

\begin{lemma}\label{lem:rank_exp_array}
For $\arr{h}$ defined as in \eqref{eq:exp_array}, the quasi-Hankel matrix admits the factorization $\hmatr{\set{C}}{\arr{h}} =$
\begin{equation}\label{eq:vandermonde_fac}
 \vmatr{\set{C}}{\vect{z}_{1}, .., \vect{z}_{r}}
\diag{c_1, \ldots, c_r}
(\vmatr{\set{C}}{\vect{z}_{1}, .., \vect{z}_{r}})^{\top}
\end{equation}
and $\rank{\hmatr{\set{C}}{\arr{h}}} \le r$.
If, in addition, $c_k \neq 0$ for all $k$, and  $\vect{z}_1, \ldots, \vect{z}_r$  are $\set{C}$-independent, then 
\[
\rank{\hmatr{\set{C}}{\arr{h}}} = r.
\]
\end{lemma}

Next, we describe an easy improvement of Proposition~\ref{prop:flat_ext} for arrays of form \eqref{eq:exp_array}.

\begin{proposition}\label{prop:flat_ext_exp_array}
Let $\set{A} = \trgset{m}{d}$, $d' \stackrel{\mathrm{def}}{=} \lfloor \frac{d}{2} \rfloor$,~$\set{B} \stackrel{\mathrm{def}}{=} \trgset{m}{d'}$ (it is easy to see that $2\set{B} \subset \set{A}$).
Assume that the coefficients $\{h_{\vect{\alpha}}\}_{\vect{\alpha} \in \set{A}}$ have the form \eqref{eq:exp_array}, where the points $\vect{z}_1,\ldots,\vect{z}_{r}$ are $\set{B}$-independent and
$c_1,\ldots,c_r$ are nonzero.
Then, the following hold true
\begin{enumeratex}
\item The rank of the minimal completion in Problem~\ref{prob:qh_completion} is $r$. A minimal rank completion is  obtained by defining $\{h_{\vect{\alpha}}\}_{\vect{\alpha} \in 2\set{A}}$ using the same formula  \eqref{eq:exp_array} (called canonical completion).
\item If $d$ is odd, the canonical completion  is unique.
\item If $d$ is even, and $\vect{z}_1, \ldots, \vect{z}_r$ are $\trgset{m}{d'-1}$-independent, then the
completion is unique (the canonical completion of Eq. \eqref{eq:exp_array} is the only possible).
\end{enumeratex}
\end{proposition}
\begin{proof}See Appendix \ref{proofcomplex-sec} for a proof.\end{proof}

For example, for the completion of structure shown in \eqref{eq:qhankel_trgset} ($m=2$ and $d=3$), Proposition~\ref{prop:flat_ext_exp_array} covers cases up to rank $3$.
Indeed, let  $\vect{z}_k = \left[\begin{smallmatrix} \lambda_k \\ \mu_k\end{smallmatrix}\right]$, $k\in\{1,2,3\}$,  we have that if the Vandermonde matrix has full rank \eqref{eq:vander_trgset}, then the matrix completion is unique and is given by the canonical completion.

\begin{remark}\label{rem:generic_qhankel_completion}
If the points $\vect{z}_1, \ldots, \vect{z}_r$ are generic, due to Remark~\ref{rem:A_independence_generic}, we can replace the $\set{B}$-independence and $\trgset{m}{d'-1}$-independence by the bounds $r \le \binom{d'+m}{m}$ and $r \le \binom{d'+m-1}{m}$ respectively.
\end{remark}

Finally, we note that for generic cases, the rank bound in Remark~\ref{rem:generic_qhankel_completion} can be further improved by using results of \cite[Theorem~{2.4}]{Oeding.Ottaviani13JoSC-Eigenvectors} (since uniqueness of matrix completion is related to uniqueness of tensor decomposition).
For our purposes, however, Proposition~\ref{prop:flat_ext_exp_array} will be sufficient.


\section{Main results}\label{sec:results}
\subsection{Hankel case}

First, we prove a result that generalizes Theorem~\ref{thm:rank_one}.
\begin{theorem}\label{thm:rank_r}
For any $d$, $n=d+1$, and $r < \frac{d+2}{2}$ there exists  $\rho = \rho(d,r) > 0$ such that
for all $\vect{h}_d$ with $\hrank{\vect{h}_d} = r$ and  $|\lambda_k| < \rho$ in \eqref{eq:char_poly}, the solution of \eqref{eq:nnmin} is unique and coincides with \eqref{eq:canonical_completion}.
\end{theorem}
\begin{proof}See Appendix \ref{proofcomplex-sec} for a proof.\end{proof}

\begin{note}
Theorem~\ref{thm:rank_one} proves a special case of Theorem~\ref{thm:rank_r} and tells  that $\rho(d,1) = 1$ (for $\vect{h}_d \in \mathbb{R}^{d+1}$).
\end{note}


\section{Main lemmas: optimality conditions and simple projectors}\label{sec:lemmas}

\subsection{Quasi-Hankel completion: basis matrices}\label{sec:basis_matrices}
First, we put the rank minimization problem  \eqref{eq:qhankel_rankmin} in the (standard) form \eqref{eq:rankmin}.
In order to do this, we explicitly write down the matrices $\matr{S}_k$ in  \eqref{eq:affine_structure}.
The constant part has the form
\[
\matr{S}_0 \stackrel{\mathrm{def}}{=} \hmatr{\set{A}}{\arr{c}}, 
\]
where $\arr{c} = \{c_{\vect{\alpha}}\}_{\vect{\alpha} \in 2 \set{A}}$ is defined as
\[
{c}_{\vect{\alpha}} \stackrel{\mathrm{def}}{=} 
\begin{cases}
{h}_{\vect{\alpha}}, & {\vect{\alpha}} \in \set{A},  \\
0, & {\vect{\alpha}} \in 2\set{A} \setminus \set{A}.
\end{cases}
\]

\begin{example}
In the case of $\set{A} = \trgset{2}{3}$ (depicted in \eqref{eq:qhankel_trgset}), we have that $\matr{S}_0 = \hmatr{\set{A}}{\arr{c}} = $
\small\[
\left[
\begin{array}{c|c@{\;}c@{\;}|c@{\;}c@{\;}c@{\;}|c@{\;}c@{\;}c@{\;}c}
h_{0,0} & h_{1,0} & h_{0,1} &  h_{2,0} & h_{1,1} & h_{0,2} & h_{3,0} & h_{2,1} & h_{1,2} & h_{0,3} \\
\hline
h_{1,0} & h_{2,0} & h_{1,1} &  h_{3,0} & h_{2,1} & h_{1,2} & 0         & 0         & 0         & 0         \\
h_{0,1} & h_{1,1} & h_{0,2} &  h_{2,1} & h_{1,2} & h_{0,3} & 0         & 0         & 0         & 0 \\
\hline
h_{2,0} & h_{3,0} & h_{2,1} &  0        & 0 & 0 & 0 & 0 & 0 & 0 \\
h_{1,1} & h_{2,1} & h_{1,2} &  0        & 0 & 0 & 0 & 0 & 0 & 0 \\
h_{0,2} & h_{1,2} & h_{0,3} &  0 & 0 & 0 &0 & 0 & 0 &0 \\
\hline
h_{3,0} & 0         & 0         &  0 & 0 & 0 & 0 & 0 & 0 & 0 \\
h_{2,1} & 0         & 0         &  0 & 0 & 0 & 0 & 0 & 0 & 0 \\
h_{1,2} & 0         & 0         &  0 & 0 & 0 & 0 & 0 & 0 & 0 \\
h_{0,3} & 0         & 0         &  0 & 0 & 0 & 0 & 0 & 0 & 0
\end{array}
\right].
\]\normalsize
In the case of Hankel matrices ($\set{A} = \trgset{1}{d}$, see \eqref{eq:hankel}), we have that $n = d+1$, and
$\matr{S}_0$ is given by
\begin{equation}\label{eq:hankel_G0}
\matr{S}_0 = \begin{bmatrix}
h_0     & h_1     & \cdots & h_{d-1} & h_{d} \\
h_1     & h_2     & \iddots & h_{d} & 0     \\
\vdots  & \iddots  & \iddots & \iddots  & \vdots  \\
h_{d-1} & h_{d} & \iddots &  & 0 \\
h_{d} & 0     & \cdots & 0 & 0
\end{bmatrix}
\end{equation}
\end{example}

The number of free parameters in \eqref{eq:affine_structure} is  $N = \#(2\set{A}) - \#(\set{A})$ (\textit{i.e.}, the number of unknowns in \eqref{eq:qhankel_rankmin}).
The corresponding set of multi-indices can be represented as
\begin{equation}\label{eq:ordering_missing_values}
2\set{A} \setminus \set{A}  = \{\bm{\beta}_1,\ldots,\bm{\beta}_{N}\},\quad \bm{\beta}_1 \prec \cdots \prec\bm{\beta}_{N}.
\end{equation}
Next, we define basis arrays $\iarr{e}^{\bm{\beta}} \stackrel{\mathrm{def}}{=} \{e^{\bm{\beta}}\}_{\bm{\alpha} \in \mathbb{N}^{m}}$ as 
\[
e^{\bm{\beta}}_{\bm{\alpha}} \stackrel{\mathrm{def}}{=} 
\begin{cases}
1, & {\bm{\alpha}} = {\bm{\beta}},  \\
0, & {\bm{\alpha}} \neq {\bm{\beta}},
\end{cases}
\]
and $\matr{S}_k$ as
\begin{equation}\label{eq:qhankel_Gk}
\matr{S}_k := \hmatr{\set{A}}{\iarr{e}^{\bm{\beta}_k}}.
\end{equation}
Finally, it is easy to see that
\[
\hmatr{\set{A}}{\iarr{h}} = \mathscr{S}(\vect{p}),
\]
if $\vect{p}$ is defined as  $p_k = \iarr{h}_{\bm{\beta}_k}$.

\begin{example}
For $\set{A} = \trgset{2}{3}$, shown in \eqref{eq:qhankel_trgset}, we have
\[
\begin{split}
\matr{S}_1 &= 
\left[
\begin{smallarray}{c|cc|ccc|cccc}
0  &  0 & 0 &   0 & 0 & 0 &   0 & 0 & 0 & 0 \\
\noalign{\vskip1pt\hrule\vskip1pt}
0  &  0 & 0 &   0 & 0 & 0 &   1 & 0 & 0 & 0 \\
0  &  0 & 0 &   0 & 0 & 0 &   0 & 0 & 0 & 0 \\
\noalign{\vskip1pt\hrule\vskip1pt}
0  &  0 & 0 &   1 & 0 & 0 &   0 & 0 & 0 & 0 \\
0  &  0 & 0 &   0 & 0 & 0 &   0 & 0 & 0 & 0 \\
0  &  0 & 0 &   0 & 0 & 0 &   0 & 0 & 0 & 0 \\
\noalign{\vskip1pt\hrule\vskip1pt}
0  &  1 & 0 &   0 & 0 & 0 &   0 & 0 & 0 & 0 \\
0  &  0 & 0 &   0 & 0 & 0 &   0 & 0 & 0 & 0 \\
0  &  0 & 0 &   0 & 0 & 0 &   0 & 0 & 0 & 0 \\
0  &  0 & 0 &   0 & 0 & 0 &   0 & 0 & 0 & 0 
\end{smallarray}
\right],
\matr{S}_2 = 
\left[
\begin{smallarray}{c|cc|ccc|cccc}
0  &  0 & 0 &   0 & 0 & 0 &   0 & 0 & 0 & 0 \\
\noalign{\vskip1pt\hrule\vskip1pt}
0  &  0 & 0 &   0 & 0 & 0 &   0 & 1 & 0 & 0 \\
0  &  0 & 0 &   0 & 0 & 0 &   1 & 0 & 0 & 0 \\
\noalign{\vskip1pt\hrule\vskip1pt}
0  &  0 & 0 &   0 & 1 & 0 &   0 & 0 & 0 & 0 \\
0  &  0 & 0 &   1 & 0 & 0 &   0 & 0 & 0 & 0 \\
0  &  0 & 0 &   0 & 0 & 0 &   0 & 0 & 0 & 0 \\
\noalign{\vskip1pt\hrule\vskip1pt}
0  &  0 & 1 &   0 & 0 & 0 &   0 & 0 & 0 & 0 \\
0  &  1 & 0 &   0 & 0 & 0 &   0 & 0 & 0 & 0 \\
0  &  0 & 0 &   0 & 0 & 0 &   0 & 0 & 0 & 0 \\
0  &  0 & 0 &   0 & 0 & 0 &   0 & 0 & 0 & 0 
\end{smallarray}
\right],  \\
\matr{S}_3 &= 
\left[
\begin{smallarray}{c|cc|ccc|cccc}
0  &  0 & 0 &   0 & 0 & 0 &   0 & 0 & 0 & 0 \\
\noalign{\vskip1pt\hrule\vskip1pt}
0  &  0 & 0 &   0 & 0 & 0 &   0 & 0 & 1 & 0 \\
0  &  0 & 0 &   0 & 0 & 0 &   0 & 1 & 0 & 0 \\
\noalign{\vskip1pt\hrule\vskip1pt}
0  &  0 & 0 &   0 & 0 & 1 &   0 & 0 & 0 & 0 \\
0  &  0 & 0 &   0 & 1 & 0 &   0 & 0 & 0 & 0 \\
0  &  0 & 0 &   1 & 0 & 0 &   0 & 0 & 0 & 0 \\
\noalign{\vskip1pt\hrule\vskip1pt}
0  &  0 & 0 &   0 & 0 & 0 &   0 & 0 & 0 & 0 \\
0  &  0 & 1 &   0 & 0 & 0 &   0 & 0 & 0 & 0 \\
0  &  1 & 0 &   0 & 0 & 0 &   0 & 0 & 0 & 0 \\
0  &  0 & 0 &   0 & 0 & 0 &   0 & 0 & 0 & 0 
\end{smallarray}
\right], \ldots
\end{split}
\]
For Hankel structure, ($\set{A} = \trgset{1}{d}$, shown in \eqref{eq:hankel}), we have that $N=d$, and the matrices  $\matr{S}_k$, $k \in \{1,\ldots, N\}$ are defined as
\begin{equation}\label{eq:hankel_Gk}
\begin{split}
\matr{S}_1 &=\left[\begin{smallmatrix}
0    & 0     & \cdots & 0 & 0 \\
0     & 0     & \iddots & 0 & 1     \\
\vdots  & \iddots  & \iddots & \iddots  &  0 \\
0 & 0 & \iddots &  & \vdots\\
0 & 1  & 0 & \cdots & 0
\end{smallmatrix}\right],
\;
\cdots,
\;
\matr{S}_{N-1} = \left[\begin{smallmatrix}
0    & 0     & \cdots & 0 & 0 \\
0     & 0     & \iddots & \iddots & \vdots      \\
\vdots  & \iddots  & \iddots & \iddots  & 0 \\
0 & \iddots & \iddots &  & 1 \\
0 & \cdots & 0 & 1 & 0
\end{smallmatrix}\right],\;  \\
\matr{S}_{N} &= \left[\begin{smallmatrix}
0    & 0     & \cdots & 0 & 0 \\
0     & 0     & \iddots & 0 & 0     \\
\vdots  & \iddots  & \iddots & \iddots  & \vdots  \\
0 & 0 & \iddots &  & 0 \\
0 & 0     & \cdots & 0 & 1
\end{smallmatrix}\right]. 
\end{split}
\end{equation}
\end{example}

\subsection{Simple matrices}
Now we show that optimality conditions  hold true for simple matrices.
We take $\set{A} = \trgset{m}{d}$, and consider the matrix completion problem \eqref{eq:qhankel_rankmin}, where $\matr{S}_k$ are defined in Section~\ref{sec:basis_matrices}.
\begin{lemma}\label{lem:qhankel_zero_root_projector}
Let $d' \stackrel{\mathrm{def}}{=} \lfloor\frac{d}{2}\rfloor$, $\matr{P}_0 \in \mathbb{C}^{n\times n}$ be a matrix of the form 
\begin{equation}\label{eq:proj_zero}
\matr{P}_0 \stackrel{\mathrm{def}}{=} \begin{bmatrix}  \matr{P}'_0 & \matr{0} \\ \matr{0} & \matr{0}\end{bmatrix}, \quad \matr{P}'_0 \in \mathbb{C}^{s\times s},
\end{equation}
where $s \le \binom{m+ d'}{m}$.
Then it holds that
\begin{enumeratex}
\item For any $k\in \{1,\ldots,N\}$, 
$\matr{P}^{\T}_0 \matr{S}_k \matr{P}_0  = \matr{0}$.
\item If, in addition, $s \le n'' := \binom{d''+m}{m}$, where $d'' := \lfloor\frac{d-1}{2}\rfloor$, then $\rank{\mathscr{A}(\matr{P}_0)} = N$.
\end{enumeratex}
\end{lemma}
\begin{proof}See Appendix \ref{proofcomplex-sec} for a proof.\end{proof}

\begin{example}
In the case of Hankel matrices ($\set{A} = \trgset{1}{d}$) the first bound is $s \le \lfloor \frac{d+2}{2} \rfloor$, and the first statement of Lemma~\ref{lem:qhankel_zero_root_projector} is evident from \eqref{eq:hankel_Gk}.
The second bound is $s \le \lfloor \frac{d+1}{2} \rfloor$, and a right lower block of the matrix $\matr{Q}_0\matr{H}\matr{Q}^{\top}_0$ (where $\matr{H}$ is defined in Remark~\ref{rem:equivalent_conditions_slrmc_DP15}) has the form
\[
\begin{bmatrix}
0     & \cdots     &0 &\Delta p_1&  \cdots & \Delta p_{r}  \\
\vdots    & \iddots     & \iddots & \iddots& \iddots &  \Delta p_{r+1}    \\
0  & \iddots  & \iddots & \iddots  & \iddots& \vdots   \\
\Delta p_1  & \iddots  & \iddots & \iddots& \iddots  &  \Delta p_{N-2}  \\
\vdots  & \iddots & \iddots & \iddots& \Delta p_{N-2}  & \Delta p_{N-1}  \\
\Delta p_{r} & \Delta p_{r+1}     & \cdots & \Delta p_{N-2} &\Delta  p_{N-1} &\Delta  p_{N}
\end{bmatrix},
\]
and hence all $\Delta p_k$ are present in this block.
\end{example}

Lemma~\ref{lem:qhankel_zero_root_projector} immediately proves that the SLRMC is solved by nuclear norm minimization in very simple cases.

\begin{corollary}\label{cor:zero_root_completion}
In the completion problem~\eqref{eq:qhankel_rankmin} for the structure \eqref{eq:hankel}, let the vector $\vect{h}_d$ be of the form \eqref{eq:initial_zero_root}, with $r \le \frac{d+2}{2}$. Then we have the following.

\begin{enumeratex}
\item A solution of the rank minimization problem is given by $h_k = 0$ for $k > d$, and coincides with the solution of \eqref{eq:nnmin}.
\item If, in addition, $r < \frac{d+2}{2}$, the solution of \eqref{eq:nnmin} is unique.
\end{enumeratex}
\end{corollary}
\begin{proof}
\begin{enumeratex}
\item  Let $\matr{P}_0$ be as in \eqref{eq:proj_zero}, with $s=r$, and $\matr{P}'_0 = \matr{I}_s$. Then,
the matrix $\matr{B}_{\mathbb{C}}$ in \eqref{eq:skew_projector} has the form
$\matr{B}_{\mathbb{C}} = \matr{P}_0 \matr{A} \matr{P}^{\T}_0$.
By Lemma~\ref{lem:qhankel_zero_root_projector}, we have that $\langle \matr{S}_k,\matr{B}_{\mathbb{C}} \rangle_F = \langle \matr{P}^{\T}_0\matr{S}_k\matr{P}_0,\matr{A} \rangle_F = 0$.
The rest follows from Remark~\ref{rem:equivalent_conditions_slrmc_DP15}.
\item  Follows from Remark~\ref{rem:equivalent_conditions_slrmc_DP15}.
\end{enumeratex}
\end{proof}



\subsection{Perturbations of simple projectors}
Now we show that the conditions of Proposition~\ref{prop:opt_sufficient_complex} hold true for perturbations of simple matrices.
First, we need a simple inequality on  distance between projectors.
\begin{lemma}\label{lem:proj_dist}
Let $\matr{B} = \matr{B}^{\T}  = \matr{U}  \matr{V}^{\top}$, where $\matr{U},\matr{V}  \in \mathbb{R}^{n\times r}$ such that $\matr{U}^{\H}\matr{U} = \matr{V}^{\H}\matr{V} = \matr{I}_r$.
Let $\matr{P}_{0}$ be an orthogonal projector on a subspace of $\mathbb{C}^{n}$, such that $\mathop{\text{rank}}(\matr{P}_{0}) = r$. Then we have that 
\[
\|\matr{B} - \matr{P}_0 \matr{B} \matr{P}^{\T}_0\|^2_F \le  2\|(\matr{I}-\matr{P}_0) \matr{U}\|^2_F = \|\matr{P}-\matr{P}_0\|^2_F,
\]
where $\matr{P} = \matr{B}\matr{B}^{\H} = \matr{U}\matr{U}^{\H}$.
\end{lemma}
\begin{proof}
Since $\matr{B}\!-\!\matr{P}_0\matr{B}\matr{P}^{\T}_0 = \matr{B}\!-\!\matr{P}_0\matr{B} \!+\! \matr{P}_0\matr{B} \!-\! \matr{P}_0 \matr{B} \matr{P}_0^{\T}$,
\[
\begin{split}
&\|\matr{B} \!-\! \matr{P}_0 \matr{B} \matr{P}^{\T}_0\|^2_F  \le \|(\matr{I} \!-\! \matr{P}_0) \matr{B}\|^2_F + \|\matr{P}_0 \matr{B} (\matr{I} \!-\! \matr{P}_0^{\T})\|^2_F \\
& \le 2 \|(\matr{I}-\matr{P}_0) \matr{B}\|^2_F = 2 \|(\matr{I}-\matr{P}_0) \matr{U}\|^2_F
\end{split}
\]
Finally, 
\begin{equation}\label{eq:norm_diff_proj_int}
\begin{split}
&\!\!\|\matr{P} - \matr{P}_0\|^2_F  = \trace{\matr{P}^2 + \matr{P}_0^2 - \matr{P}\matr{P}_0 - \matr{P}_0\matr{P}}  \\
&\!\!= 2 \trace{2(\matr{I}-\matr{P}_0)\matr{P}} = 2\|(\matr{I}-\matr{P}_0)\matr{U}\|_F^2,
\end{split}\end{equation}
which completes the proof.
\end{proof}

\begin{remark}
For a symmetric matrix $\struct{\vect{p}}$, the matrix $\matr{B}_{\mathbb{C}}$ defined in Proposition~\ref{prop:opt_sufficient_complex} is also symmetric.
\end{remark}

Next, we prove a perturbation lemma that uses a bound on the distance between projectors. 
\begin{lemma}\label{lem:zero_root_perturbation}
Let  $\mathbf{S}$ and $\mathscr{A}(\matr{P})$ be defined in \eqref{eq:bfG} and \eqref{eq:fo_condition_matrix_left}.
Let $\matr{P}_0 \in \mathbb{C}^{n \times n}$ be a rank-$r$ projector matrix such that 
$\rank{\mathscr{A}(\matr{P}_0)} = N$,  $\matr{P}^{\T}_0 \matr{S}_k \matr{P}_0 = 0$ for all $k \in \{1,\ldots,N\}$, and let $\matr{Q}_0 \stackrel{\mathrm{def}}{=} \matr{I}-\matr{P}_0$.

Then there exists a constant $\varepsilon$ such that for any $\matr{B}$ as in Lemma~\ref{lem:proj_dist} satisfying 
\[
\|\matr{P} - \matr{P}_0\|_F <\varepsilon, 
\]
where $\matr{P} = \matr{B}\matr{B}^{\H}$, it holds that
\begin{enumeratex}
\item The matrix $\mathscr{A}(\matr{P})$ is full row rank.
\item There exists a matrix $\matr{M} \in \mathbb{C}^{n \times n}$, $\|\matr{M}\|_2 < 1$, such that 
\eqref{eq:fo_condition_matrix} is satisfied.
\end{enumeratex}
\end{lemma}
\begin{proof}
\begin{enumeratex}
\item
Since $\mathscr{A}(\matr{P})$ depends polynomially on the entries of $\matr{P}$, and $\mathop{\text{rank}} \mathscr{A}(\matr{P}_0) = N$, the rank is preserved in a neighborhood of $\matr{P}_0$. 
Thus  $\mathop{\text{rank}} \mathscr{A}(\matr{P}) = N$ in a neighbourhood of $\matr{P}_0$.

\noindent\item
Let $\varepsilon_1>0$  be a number such that for any $\matr{P}$,  $\|\matr{P}-\matr{P}_0\|_F \le \varepsilon_1$ we have $\mathscr{A}(\matr{P}) = N$ and $0 < \delta_0 < \sigma_{min}(\mathscr{A}(\matr{P}))$ for some number $\delta_0$. (We can choose such $\varepsilon_1$ by continuity of the smallest singular value.) 
Then, in the $\varepsilon_1$-neighborhood, a solution of \eqref{eq:fo_condition_matrix} always exists.
Next, we consider the  minimum Frobenius norm solution $\matr{M}_* = \matr{M}_*(\matr{P})$ of \eqref{eq:fo_condition_matrix}, which is given by
\[ \begin{split}
&\mathop{\text{vec}} (\matr{M}_*(\matr{P}))) =  -\mathscr{A}(\matr{P})^{\dagger}  \mathbf{S}^{\T} \mathop{\text{vec}} (\matr{B}) \\ &=  -\mathscr{A}(\matr{P})^{\dagger}  \mathbf{S}^{\T} \mathop{\text{vec}} (\matr{B} - \matr{P}_0\matr{B}\matr{P}^{\T}_0), 
\end{split}
\]
where the matrix $\mathscr{A}(\matr{P})^{\dagger}$ is the pseudoinverse of $\mathscr{A}(\matr{P})$, and the last equality holds since $\matr{P}^{\T}_0 \matr{S}_k \matr{P}_0 = 0$ for all $k \in \{1,\ldots,N\}$.
Then, by Lemma~\ref{lem:proj_dist},
\begin{equation}\label{eq:norm_inequality}
\begin{split}
&\|\matr{M}_*\|_2 \le \|\mathop{\text{vec}} (\matr{M}_*(\matr{P})) \|_2 \le \\
&\|\mathscr{A}(\matr{P})^{\dagger}\|_2 \|\mathbf{S}^{\T}\!\|_2  \|\matr{B} \!-\! \matr{P}_0\matr{B}\matr{P}^{\T}_0\|_F <
\frac{\| \mathbf{S}\|_2}{\delta_0} \|\matr{P} \!-\! \matr{P}_0\|_F.
\end{split}
\end{equation}
Finally, define $\varepsilon \stackrel{\mathrm{def}}{=} \min(\varepsilon_1, \frac{\delta_0}{\| \mathbf{S}\|_2})$. 
For such an $\varepsilon$, the right hand side of \eqref{eq:norm_inequality} is  less than or equal to $1$ if $\|\matr{P} - \matr{P}_0\|_F < \varepsilon$, which completes the proof.
\end{enumeratex}
\end{proof}

