Introduction
Fitting algebraic hypersurfaces—curves or surfaces defined by polynomial equations—to noisy data is a fundamental task in computer vision, robotics, and data analysis. Applications range from identifying circular features in images to modeling complex mechanical parts. While Ordinary Least Squares (OLS) is computationally efficient and easy to implement, it is statistically inconsistent for this task. The nonlinear nature of polynomials introduces a systematic bias that does not vanish even as the number of data points grows toward infinity.
Conversely, Geometric Fit methods, which minimize the orthogonal distance to the surface, are accurate but involve complex, non-linear optimization. These methods are computationally expensive and often converge to local minima rather than the global optimum. This paper presents an Adjusted Least Squares (ALS) approach that bridges this gap, combining the linear-algebraic speed of OLS with the statistical consistency of more complex geometric estimators.
Methodology: Bias Correction and Monomial Sets
The core innovation of the ALS method is bias correction through a process known as deconvolution. In standard OLS, the data matrix is constructed from monomials of the observed noisy coordinates. Because noise is squared or cubed in these monomials, the resulting matrix is biased. The authors address this by replacing standard monomials with homogeneous Hermite polynomials. This transformation ensures that the expected value of the noisy data matrix matches the "true" noiseless matrix, effectively "subtracting" the noise bias from the calculation.
The fitting problem is structured using "quasi-Hankel" matrices, which are built from the moments of the data. By organizing the coefficients this way, the authors can solve for the best-fit parameters using a polynomial eigenvalue problem. This approach is particularly powerful when the noise variance is unknown, as it allows the algorithm to estimate both the surface and the noise level simultaneously.
Geometric Invariance and the Bombieri Norm
A significant contribution of this work is the rigorous treatment of geometric invariance. A robust fitting algorithm should be "objective"—meaning it produces the same geometric result regardless of whether the coordinate system is rotated, translated, or scaled. The authors prove that the choice of norm used to regularize the polynomial coefficients is critical.
Specifically, they demonstrate that using the Bombieri norm (also known as the Kostlan norm) is essential for achieving rotation invariance. Without this specific weighting, which accounts for the combinatorial properties of polynomial coefficients, the "best fit" could change simply because the data was rotated before processing. This ensures that the ALS method is not just a statistical improvement, but a geometrically sound one.
Performance and Consistency
The primary advantage of the ALS estimator is that it is "strongly consistent." In statistical terms, this means that as the number of data points increases, the estimated parameters converge to the true values with probability one. This stands in stark contrast to OLS, where the error typically plateaus at a fixed level determined by the noise variance, regardless of how much data is collected.
Numerical experiments on synthetic and benchmark datasets validate these theoretical claims. In tests using the "Eight Curve" (a quartic Lissajous curve), the ALS error dropped linearly on a log-log scale as more data was added, while OLS failed to improve. Furthermore, in subspace clustering tasks—where data belongs to a union of hyperplanes—ALS significantly outperformed OLS in recovering the underlying linear structures. The method also showed surprising robustness to non-Gaussian noise distributions, such as uniform noise, suggesting its utility extends beyond the strict theoretical assumptions of the Gaussian noise model.
Conclusion
The Adjusted Least Squares method provides a mathematically rigorous and computationally feasible alternative for hypersurface fitting. By addressing the fundamental flaws of OLS through deconvolution and ensuring geometric invariance via the Bombieri norm, the authors offer a tool that is both statistically sound and practically robust. While the method requires some knowledge of the noise structure, its performance gains and consistency make it a superior choice for high-precision applications in computer vision and beyond. Future work may explore more efficient algorithms for the underlying matrix structures and further test robustness against non-stationary noise environments.
Summary updated