# A convex relaxation to compute the nearest structured rank deficient matrix

arXiv: https://arxiv.org/abs/1904.09661 · HTML: https://mlsanity.com/paper/1904.09661/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Apr 2019.

## Built on by (most cited first, 7 of 7)

- [Certifiably Optimal Outlier-Robust Geometric Perception: Semidefinite Relaxations and Scalable Global Optimization](https://mlsanity.com/paper/2109.03349/) (2021)
- [Advances in Global Solvers for 3D Vision](https://mlsanity.com/paper/2602.14662/) (2026)
- [An Inexact Projected Gradient Method with Rounding and Lifting by Nonlinear Programming for Solving Rank-One Semidefinite Relaxation of Polynomial Optimization](https://mlsanity.com/paper/2105.14033/) (2021)
- [Semidefinite Relaxations for Robust Multiview Triangulation](https://mlsanity.com/paper/2301.11431/) (2023)
- [Towards Understanding The Semidefinite Relaxations of Truncated Least-Squares in Robust Rotation Search](https://mlsanity.com/paper/2207.08350/) (2022)
- [Algebra and Geometry of Camera Resectioning](https://mlsanity.com/paper/2309.04028/) (2023)
- [Hankel low-rank approximation and completion in time series analysis and forecasting: a brief review](https://mlsanity.com/paper/2206.05103/) (2022)

## Abstract (arXiv)

Given an affine space of matrices L and a matrix Theta∈ L, consider the problem of computing the closest rank deficient matrix to Theta on 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.