Exploring Algorithmic Limits of Matrix Rank Minimization under Affine Constraints

Bo Xin, David Wipf

Many applications require recovering a matrix of minimal rank within an affine constraint set, with matrix completion a notable special case. Because the problem is NP-hard in gene…