Semidefinite Programming versus Burer-Monteiro Factorization for Matrix Sensing
This work clarifies the distinct strengths and weaknesses of two key methods for low-rank optimization problems, aiding practitioners in choosing the right approach for specific matrix sensing tasks.
The paper compares semidefinite programming (SDP) and Burer-Monteiro (B-M) factorization for matrix sensing, showing that B-M fails with high probability on structured matrix completion problems where SDP succeeds, while B-M works on highly sparse problems where SDP fails, and SDP's success improves with higher rank solutions.
Many fundamental low-rank optimization problems, such as matrix completion, phase synchronization/retrieval, power system state estimation, and robust PCA, can be formulated as the matrix sensing problem. Two main approaches for solving matrix sensing are based on semidefinite programming (SDP) and Burer-Monteiro (B-M) factorization. The SDP method suffers from high computational and space complexities, whereas the B-M method may return a spurious solution due to the non-convexity of the problem. The existing theoretical guarantees for the success of these methods have led to similar conservative conditions, which may wrongly imply that these methods have comparable performances. In this paper, we shed light on some major differences between these two methods. First, we present a class of structured matrix completion problems for which the B-M methods fail with an overwhelming probability, while the SDP method works correctly. Second, we identify a class of highly sparse matrix completion problems for which the B-M method works and the SDP method fails. Third, we prove that although the B-M method exhibits the same performance independent of the rank of the unknown solution, the success of the SDP method is correlated to the rank of the solution and improves as the rank increases. Unlike the existing literature that has mainly focused on those instances of matrix sensing for which both SDP and B-M work, this paper offers the first result on the unique merit of each method over the alternative approach.