An upper bound on the minimum rank of a symmetric Toeplitz matrix completion problem

We consider a symmetric Toeplitz matrix completion problem, of which the matrix possesses special row and column structures. It has wide applications in diverse areas and is well-known to be computationally NP-hard. This note presents an upper bound on the objective of minimizing the rank of the symmetric Toeplitz matrix in the completion problem based on conclusions from the trigonometric moment problem and the semi-infinite problem. We prove that the upper bound is less than twice the number of the active constraints of the associated semi-infinite problem. Moreover, it is less than twice the number of linear constraints of the problem.

本文研究一类对称托普利茨矩阵（symmetric Toeplitz matrix）补全问题，该类矩阵具有特殊的行与列结构。该问题在多领域具备广泛应用价值，且已被证明属于计算复杂度上的NP难问题。本文基于三角矩问题（trigonometric moment problem）与半无限问题（semi-infinite problem）的相关结论，为该补全问题中最小化对称托普利茨矩阵秩的目标函数推导得到一个上界。我们证明该上界小于对应半无限问题有效约束数的两倍，同时亦小于该问题线性约束的总数的两倍。