Title :
Rank-one matrix completion is solved by the sum-of-squares relaxation of order two
Author :
Augustin Cosse;Laurent Demanet
Author_Institution :
Harvard, IACS and UCL, ICTEAM, School of engineering and applied science, USA
Abstract :
This note studies the problem of nonsymmetric rank-one matrix completion. We show that in every instance where the problem has a unique solution, one can recover the original matrix through the second round of the sum-of-squares/Lasserre hierarchy with minimization of the trace of the moments matrix. Our proof system is based on iteratively building a sum of N - 1 linearly independent squares, where N is the number of monomials of degree at most two, corresponding to the canonical basis (zα - z0α)2. Those squares are constructed from the ideal I generated by the constraints and the monomials provided by the minimization of the trace.
Keywords :
"Convex functions","Minimization","Noise measurement","Conferences","Bipartite graph","Electronic mail","Symmetric matrices"
Conference_Titel :
Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP), 2015 IEEE 6th International Workshop on
DOI :
10.1109/CAMSAP.2015.7383723