基于 FFT 插值的免矩阵求逆最小问题求解
Solving Minimal Problems Without Matrix Inversion Using FFT-Based Interpolation
为相机几何中的最小问题求解器提供了一条免矩阵求逆、免符号展开的构造路径：用稀疏隐变量结式加 FFT 插值重建行列式多项式，再用秩亏子矩阵与 Cramer 法则回代未知量，可直接替换 Grobner 基/结式求解器嵌入 RANSAC 等几何估计流程。
原文依据 a sampling-based, matrix inversion-free method that constructs the solvers using sparse hidden-variable resultants
摘要译文
由模型翻译 · 术语统一 · 请对照原文核对关键结论估计相机几何通常涉及求解以多元多项式方程组形式表述的最小问题；由于在线求解器需要进行矩阵求逆，现有基于 Grobner 基或结式的方法在计算上往往面临挑战。本文提出一种基于采样、无需矩阵求逆的方法，利用稀疏隐变量结式构造求解器。隐变量对应的行列式多项式通过逆快速傅里叶变换插值，由采样求值高效重建，从而避免符号展开。求解该多项式可得到隐变量，其余未知量则通过识别秩为 1 的亏子矩阵并应用 Cramer 法则恢复。基于最大公约数的判据保证在噪声下仍能稳健地识别子矩阵。在多种最小问题上的实验表明，所提求解器具有较强数值稳定性和有竞争力的运行时间，尤其在小规模问题上表现突出，为传统 Grobner 基与结式求解器提供了一种实用替代方案。
英文原文摘要 1130 字符
Estimating camera geometry typically involves solving minimal problems formulated as systems of multivariate polynomial equations, which often pose computational challenges when using existing Grobner-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 Grobner-basis and resultant-based solvers.