A convex relaxation to compute the nearest structured rank deficient matrix
Provides the first convex relaxation with provable guarantees for a nonconvex problem relevant to control theory, computer algebra, and computer vision.
The paper introduces a semidefinite programming relaxation for computing the nearest rank-deficient matrix in an affine space, proving it yields the global minimizer in the low-noise regime. The method outperforms state-of-the-art in noise tolerance across applications like system identification and triangulation.
Given an affine space of matrices $\mathcal{L}$ and a matrix $Θ\in \mathcal{L}$, consider the problem of computing the closest rank deficient matrix to $Θ$ 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 $Θ$ 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.