  The completion of matrices with missing values under the rank constraint is a
non-convex optimization problem. A popular convex relaxation is based on
minimization of the nuclear norm (sum of singular values) of the matrix. For
this relaxation, an important question is whether the two optimization problems
lead to the same solution. This question was addressed in the literature mostly
in the case of random positions of missing elements and random known elements.
In this contribution, we analyze the case of structured matrices with fixed
pattern of missing values, in particular, the case of Hankel and quasi-Hankel
matrix completion, which appears as a subproblem in the computation of
symmetric tensor canonical polyadic decomposition. We extend existing results
on completion of rank-one real Hankel matrices to completion of rank-r complex
Hankel and quasi-Hankel matrices.
