Solving Minimal Problems Without Matrix Inversion Using FFT-Based Interpolation

Nonlinear inverse problems often trade inexpensive but fragile first-order updates against curvature-aware methods such as Gauss-Newton and Levenberg-Marquardt, which obtain stronger directions by repeatedly solving Jacobian-based linearized systems. We propose a learned alternative: amortize local inverse geometry into a reusable reverse operator. Our framework learns a bidirectional surrogate, Deceptron, and deploys it through D-IPG (Deceptron Inverse-Preconditioned Gradient), an iterative solver that pulls residual-corrected measurement-space proposals back to latent space. The key mechanism is a Jacobian Composition Penalty (JCP), which trains the reverse Jacobian to act as a local left inverse of the forward Jacobian; its runtime counterpart, RJCP, measures the same inverse-consistency error along optimization trajectories. We prove that D-IPG is first-order equivalent to damped Gauss-Newton under local pseudoinverse consistency, with deviation controlled by composition error and conditioning. Across seven PDE inverse-problem benchmarks, D-IPG outperforms standard baselines, achieves 94.8% mean success across the six-problem reliability suite, and reaches comparable or better recovery quality at up to 77x lower inference-time solve cost on the main benchmarks.

The paper introduces an efficient algebraic solver for the 4-sender/6-receiver (4s/6r) Time-of-Arrival (ToA) self-localization problem, which involves determining the relative positions of all receivers and senders given their pairwise distance measurements. The problem is addressed through a new parametrization combining Cayley--Menger determinants with an implicitization technique. The proposed algorithm proceeds in three steps. First, a 148 x 211 Macaulay matrix is constructed from the coefficients of the original polynomial system. Second, PLU decomposition of this matrix yields a 63 x 63 matrix pair. Finally, up to 38 real solutions are obtained via generalized eigendecomposition followed by a validation step. Experiments on synthetic noise-free data demonstrate that the proposed solver outperforms existing methods by approximately three orders of magnitude in numerical accuracy while achieving an average runtime of 1.3x faster than the fastest alternative. Experiments on a real-world acoustic dataset confirm that, when integrated within a RANSAC framework, the solver provides a reliable initial guess for bundle adjustment refinement.

We study nonconvex methods for matrix completion, the problem of recovering a low-rank matrix from a subset of its entries. Convex methods achieve sample complexity linear in the matrix dimension and the rank, up to logarithmic factors, whereas global guarantees for commonly used nonconvex methods require a higher polynomial dependence on the rank. We close this gap by analyzing Riemannian gradient descent (RGD) and Riemannian Gauss--Newton (RGN) methods. For an $n\times n$ matrix of rank $r$ with incoherence parameter $μ$ and condition number $κ$, the two methods achieve exact recovery with high probability from $O(μnr\log n\log(nκ))$ and $O(μnr\log n\log(2μrκ))$ observations, respectively. The methods use a multiscale residual initialization, while the analysis simultaneously controls the spectral error and incoherence. The resulting RGD iterates converge linearly, whereas RGN eventually converges Q-quadratically.