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

Abstract

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.

Keywords:

• Toeplitz matrix
• rank
• trigonometric moment problem
• semi-infinite problem

Acknowledgments

We would like to express our deepest gratitude to Reviewers since they not only provide an alternative simpler proof of some result, but also lead us to significantly improve the manuscript.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

X. Yan was supported in part by National Natural Science Foundation of China [No. 11901424] and NSF of Shanxi Province [No. 201801D121022]. Y. Xu was supported in part by National Natural Science Foundation of China [No. 11501100, 11571178, 11671082 and 11871149].