  Given an affine space of matrices $\mathcal{L}$ and a matrix $\Theta\in
\mathcal{L}$, consider the problem of computing the closest rank deficient
matrix to $\Theta$ on $\mathcal{L}$ with respect to the Frobenius norm. This is
a nonconvex problem with several applications in control theory, computer
algebra, and computer vision. We introduce a novel semidefinite programming
(SDP) relaxation, and prove that it always gives the global minimizer of the
nonconvex problem in the low noise regime, i.e., when $\Theta$ is close to be
rank deficient. Our SDP is the first convex relaxation for this problem with
provable guarantees. We evaluate the performance of our SDP relaxation in
examples from system identification, approximate GCD, triangulation, and camera
resectioning. Our relaxation reliably obtains the global minimizer under
non-adversarial noise, and its noise tolerance is significantly better than
state of the art methods.
