Semidefinite Programming versus Burer-Monteiro Factorization for Matrix Sensing

Abstract

We compare semidefinite programming and Burer–Monteiro factorization for matrix sensing. We identify structured instances where one method succeeds while the other fails, and show that the success of semidefinite programming depends on the rank of the unknown solution whereas Burer–Monteiro performance is rank-independent. The results clarify the distinct strengths of the two approaches.