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

References

• Argyriou A, Evgeniou T, Pontil M. Multi-task feature learning. In: Advances in Neural Information Processing Systems; Vol. 19, 2007. p. 41–48. Vancouver, British Columbia, Canada.
   Google Scholar
• Candes EJ, Recht B. Exact matrix completion via convex optimization. Found Comut Math. 2009;9:717–772.
   Web of Science ®Google Scholar
• Chen Y, Chi Y. Spectral compressed sensing via structured matrix completion. IEEE Trans Inf Theory. 2013;60:6576–6601.
   Web of Science ®Google Scholar
• Fazel M, Pong TK, Sun D, et al. Hankel matrix rank minimization with applications to system identification and realization. SIAM J Matrix Anal Appl. 2013;34:946–977.
   Web of Science ®Google Scholar
• Liu Z, Vandenberghe L. Interior-point method for nuclear norm approximation with application to system identification. SIAM J Matrix Anal Appl. 2010;31:1235–1256.
   Web of Science ®Google Scholar
• Tomasi C, Kanade T. Shape and motion from image streams under orthography: a factorization method. Int J Comput Vis. 1992;9:137–154.
   Web of Science ®Google Scholar
• Cai JF, Candes EJ, Shen Z. A singular value thresholding algorithm for matrix completion. SIAM J Optim. 2010;20:1956–1982.
   Web of Science ®Google Scholar
• Toh KC, Yun S. An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems. Pacific J Optim. 2010;6:615–640.
   Web of Science ®Google Scholar
• Sun R, Luo Z. Guaranteed matrix completion via non-convex factorization. IEEE Trans Inf Theory. 2016;62:6535–6579.
   Web of Science ®Google Scholar
• Drusvyatskiy D, Wolkowicz H. The many faces of degeneracy in conic optimization. Found Trends Syst. 2017;3:77–170.
   Google Scholar
• Huang S, Wolkowicz H. Low-rank matrix completion using nuclear norm with facial reduction. J Glob Optim. 2018;72:5–26.
   Web of Science ®Google Scholar
• Ma S, Wang F, Wei L, et al. Robust principal component analysis using nuclear norm minimization and facial reduction. Technical report. Waterloo (ON): University of Waterloo; 2018. submitted to OPTE.
   Google Scholar
• Fazel M. Matrix rank minimization with applications [Ph.D. thesis]. Stanford University; 2002.
   Google Scholar
• Hu Y, Zhang D, Liu J, et al. Accelerated singular value thresholding for matrix completion. In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Association for Computing Machinery, New York, NY, USA; 2012. p. 298–306.
   Google Scholar
• Ma S, Goldfarb D, Chen L. Fixed point and Bregman iterative methods for matrix rank minimization. Math Program. 2011;128:321–353.
   Web of Science ®Google Scholar
• Shaw AK, Pokala S, Kumaresan R. Toeplitz and Hankel approximation using structured approach. In: IEEE International Conference on Acoustics, Speech and Signal Processing; 1998; 4, p. 2349–2352.
   Google Scholar
• Wang CL, Li C, Wang J. Two modified augmented Lagrange multiplier algorithms for Toeplitz matrix compressive recovery. Comput Math Appl. 2017;74:1915–1921.
   Web of Science ®Google Scholar
• Wang CL, Li C. A mean value algorithm for Toeplitz matrix completion. Appl Math Lett. 2015;41:35–40.
   Web of Science ®Google Scholar
• Wang CL, Li C, Wang J. A modified augmented Lagrange multiplier algorithm for toeplitz matrix completion. Adv Comput Math. 2016;42:1209–1224.
   Web of Science ®Google Scholar
• Barvinok A. A remark on the rank of positive semideffinite matrices subject to affine constraints. Discrete Comput Geom. 2001;25(1):23–31.
   Web of Science ®Google Scholar
• Fawzi H, Gouveia J, Parrilo PA, et al. Positive semidefinite rank. Math Program. 2015;153:133–177.
   Web of Science ®Google Scholar
• Gouveia J, Robinson RZ, Thomas RR. Worst-case results for positive semidefinite rank. Math Program. 2015;153:201–212.
   Web of Science ®Google Scholar
• Pataki G. On the rank of extreme matrices in semideffinite programs and the multiplicity of optimal eigenvalues. Mathematics of Operations Research. 1998;23(2):339–358.
   Web of Science ®Google Scholar
• Cohen N, Dancis J. Inertias of block band matrix completions. SIAM J Matrix Anal Appl. 1998;19:583–612.
   Web of Science ®Google Scholar
• Ellis LR, Lay DC. Rank-preserving extensions of band matrices. Linear Multilinear Algebra. 1990;26:147–179.
   Google Scholar
• Woerdeman HJ. Minimal rank completions of partial banded matrices. Linear Multilinear Algebra. 1993;36:59–68.
   Google Scholar
• Woerdeman HJ. Hermitian and normal completions. Linear Multilinear Algebra. 1997;42:239–280.
   Google Scholar
• Xu Y, Desai J, Yan X. On solving a class of linear semi-infinite programs by the trigonometric moment, arXiv:1909.05712.
   Google Scholar
• Akhiezer NI, Krein MG. Some questions in the theory of moments. Rhode Island: American Mathematical Society Translations; 1962.
   Google Scholar
• Bakonyi M, Lopushanskaya EV. Moment problems for real measures on the unit circle. In: Recent advances in operator theory in Hilbert and Krein spaces, (Operator Theory:Advances and Applications. Vol. 198). Birkhäuser Basel; 2010. p. 49–60.
   Google Scholar
• Ciccariello S, Cervellino A. Generalization of a theorem of Carathéodory. J Phys A. 2006;39:14911–14928.
   Google Scholar
• Cybenko G. Moment problems and low rank Toeplitz approximations, circuits syst. Signal Process. 1982;1:345–366.
   Google Scholar
• Landau HJ. The classical moment problem: hilbertian proofs. J Funct Anal. 1980;38:255–272.
   Web of Science ®Google Scholar
• Helmberg C, Rendl F, Vanderbei RJ, et al. An interior-point method for semidefinite programming. SIAM J Optim. 1996;6:342–361.
   Web of Science ®Google Scholar
• Xu Y, Yan X. On a box-constrained linear symmetric cone optimization problem. J Optim Theory Appl. 2019;181:946–971.
   Web of Science ®Google Scholar
• Bonnans JF, Shapiro A. Perturbation analysis of optimization problems. New York: Springer; 2000.
   Google Scholar
• Grenander U, Szegö G. Toeplitz forms and their applications. Berkeley (CA): University of California Press; 1958.
   Google Scholar