# Solving Minimal Problems Without Matrix Inversion Using FFT-Based Interpolation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 39 references that are in the map.
- First posted on arXiv 7 May 2026.

## Builds on (most cited first, 7 of 7)

- [Beyond Gr"obner Bases: Basis Selection for Minimal Solvers](https://mlsanity.com/paper/1803.04360/) (2018)
- [A sparse resultant based method for efficient minimal solvers](https://mlsanity.com/paper/1912.10268/) (2019)
- [GAPS: Generator for Automatic Polynomial Solvers](https://mlsanity.com/paper/2004.11765/) (2020)
- [Resultant Based Incremental Recovery of Camera Pose from Pairwise Matches](https://mlsanity.com/paper/1901.09364/) (2019)
- [Computing stable resultant-based minimal solvers by hiding a variable](https://mlsanity.com/paper/2007.10100/) (2020)
- [Sparse resultant based minimal solvers in computer vision and their connection with the action matrix](https://mlsanity.com/paper/2301.06443/) (2023)
- [A Conic Transformation Approach for Solving the Perspective-Three-Point Problem](https://mlsanity.com/paper/2504.01620/) (2025)

## Abstract (arXiv)

Estimating camera geometry typically involves solving minimal problems formulated as systems of multivariate polynomial equations, which often pose computational challenges when using existing Gr"obner-basis or resultant-based methods due to matrix inversion needed in the online solver. Here we propose a sampling-based, matrix inversion-free method that constructs the solvers using sparse hidden-variable resultants. The determinant polynomial in the hidden variable is efficiently reconstructed via inverse fast Fourier transform interpolation from sampled evaluations, avoiding symbolic expansion. Solving this polynomial yields the hidden variable, and the remaining unknowns are recovered by identifying rank-1 deficient submatrices and applying Cramer's rule. A greatest common divisor-based criterion ensures robust submatrix identification under noise. Experiments on diverse minimal problems demonstrate that the proposed solver achieves strong numerical stability and competitive runtime, particularly for small-scale problems, providing a practical alternative to traditional Gr"obner-basis and resultant-based solvers.