In the state estimation / robotic perception community (e.g., SLAM, 2-view pose estimation, and more) the Burer-Monteiro method has become a really powerful way of solving certain non-convex inverse problems. We recently tried to write a more accessible overview of this approach: https://arxiv.org/abs/2410.00117
The high-level theme behind these approaches has been: (i) model the problem as a QCQP, (ii) form a semidefinite relaxation of the QCQP via Shor's relaxation, (iii) if the semidefinite relaxation is tight and satisfies a specific condition on the constraints (LICQ) then solve with Burer-Monteiro method. This is a nontrivial set of requirements but has allowed for efficient global optimization (often as fast as SOTA local solvers) for a pretty meaningful set of non-convex problems so far.
Favorite kind of problem: Any inverse problem that's convex in terms of some vector solution, but you actually want a low-rank matrix or tensor form of that solution. Bonus points if you want to regularize those factors.
In the state estimation / robotic perception community (e.g., SLAM, 2-view pose estimation, and more) the Burer-Monteiro method has become a really powerful way of solving certain non-convex inverse problems. We recently tried to write a more accessible overview of this approach: https://arxiv.org/abs/2410.00117
The high-level theme behind these approaches has been: (i) model the problem as a QCQP, (ii) form a semidefinite relaxation of the QCQP via Shor's relaxation, (iii) if the semidefinite relaxation is tight and satisfies a specific condition on the constraints (LICQ) then solve with Burer-Monteiro method. This is a nontrivial set of requirements but has allowed for efficient global optimization (often as fast as SOTA local solvers) for a pretty meaningful set of non-convex problems so far.
In this house, we believe the forward model is real.
Favorite kind of problem: Any inverse problem that's convex in terms of some vector solution, but you actually want a low-rank matrix or tensor form of that solution. Bonus points if you want to regularize those factors.