A Unified Theorem on SDP Rank Reduction
A Unified Theorem on SDP Rank Reduction
We consider the problem of finding a low-rank approximate solution to a system of linear equations in symmetric, positive semidefinite matrices, where the approximation quality of a solution is measured by its maximum relative deviation, both above and below, from the prescribed quantities. We show that a simple randomized polynomial-time …