Quasi-Hankel low-rank matrix completion: a convex relaxation

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.