Solving Minimal Problems Without Matrix Inversion Using FFT-Based Interpolation

Problem
This paper addresses the computational challenges associated with solving minimal problems in camera geometry, specifically those formulated as systems of multivariate polynomial equations. Traditional methods, such as Gröbner-basis and resultant-based approaches, often require matrix inversion, which can be computationally intensive and numerically unstable. The authors propose a novel, matrix inversion-free method that leverages sparse hidden-variable resultants, filling a gap in the literature regarding efficient and robust solutions for these types of problems. This work is presented as a preprint and has not yet undergone peer review.

Method
The proposed method utilizes a sampling-based approach to construct solvers without the need for matrix inversion. The core technical contribution involves reconstructing the determinant polynomial in the hidden variable using inverse fast Fourier transform (IFFT) interpolation from sampled evaluations. This avoids the need for symbolic expansion, which is a common bottleneck in traditional methods. Once the hidden variable is determined, the remaining unknowns are recovered by identifying rank-1 deficient submatrices and applying Cramer’s rule. To enhance robustness against noise, a greatest common divisor (GCD)-based criterion is employed for submatrix identification. The authors do not disclose specific details regarding the training compute or data used, as the focus is on algorithmic development rather than empirical training.

Results
The experimental results demonstrate that the proposed solver exhibits strong numerical stability and competitive runtime, particularly for small-scale minimal problems. The authors compare their method against traditional Gröbner-basis and resultant-based solvers, although specific baseline methods are not named in the summary. The results indicate that the new approach significantly reduces computational overhead while maintaining accuracy, although exact effect sizes and performance metrics are not provided in the abstract.

Limitations
The authors acknowledge that their method may be less effective for larger-scale problems, where the complexity of polynomial systems increases. Additionally, while the GCD-based criterion improves robustness, it may still be sensitive to noise in certain scenarios. The paper does not address potential limitations related to the scalability of the sampling method or the computational overhead associated with IFFT, which could impact performance in high-dimensional settings.

Why it matters
This work has significant implications for the field of computer vision, particularly in applications requiring robust camera geometry estimation. By providing a matrix inversion-free alternative, the proposed method can enhance the efficiency and stability of solving minimal problems, which are critical in various vision tasks such as 3D reconstruction and motion estimation. The approach may inspire further research into sampling-based techniques and their applications in other areas of computational geometry and optimization.

Authors: Haidong Wu, Snehal Bhayani, Janne Heikkilä
Source: arXiv:2605.06572
URL: https://arxiv.org/abs/2605.06572v1