Derivation and implementation. Complete-data algebraic-distance fitting has a closed-form global optimum: the bottom- eigenspace of the Veronese second-moment matrix. Sampson fitting uses a different, non-convex objective and an iterative solver.
Sources: original analysis; Chojnacki, Brooks, van den Hengel & Gawley (2000), On the fitting of surfaces to data with covariances, §4.1–§4.2, Fig. 1; Absil, Mahony & Sepulchre (2008), Optimization Algorithms on Matrix Manifolds, Chapter 7, Algorithms 10–11; code:
lib/AlgebraicFactors.jl/src/polyfit.jl,veronese.jl,lib/AlgebraicFactors.jl/test/polynomial.jl.Bibliography: Chojnacki et al. 2000 · Absil et al. 2008
Theory (CT-ML wiki): Bayesian Inversion · Cospan
The objective
Given data believed to lie on the relation, and the parametrisation of The Veronese Parametrisation, the algebraic-distance objective is
This is with the vector energy and .
Without a constraint the minimum is , for which and every point lies on the variety. So a normalisation is mandatory. The correct one is (orthonormal rows) — see The Parameter is a Grassmannian for why this is not an arbitrary choice but the coordinatisation of the true parameter space.
The derivation
Write and stack them as rows of . Then
where
is the uncentred second-moment matrix of the Veronese-embedded data: symmetric, positive semidefinite.
The data enters only through . Whatever is, the fitting problem compresses to one PSD matrix — which is also the statement that this is a streaming/one-pass algorithm.
Now minimise over . By the Ky Fan variational principle (equivalently Courant–Fischer applied times), with eigenvalues of :
attained when the rows of span the eigenspace of the smallest eigenvalues of . Equivalently: = the right-singular vectors of with smallest singular values.
A global algebraic-distance optimum, in closed form. This statement applies to this fixed complete-data objective, not all learning in the family. The orthonormal-row constraint is itself non-convex; the spectral solution solves it globally. Sampson fitting and inference remain non-convex.
Choosing is a rank decision
in exact arithmetic. With noise, has no exact null space, and becomes a numerical rank decision from the eigenvalue spectrum — a gap you hope to see, and often do not.
Two things make this harder than a normal PCA rank choice:
- Monomials of different degrees have wildly different scales. and differ by
orders of magnitude on data of magnitude , so the spectrum of is dominated by
scaling artefacts rather than structure. Column-equilibrating , or replacing monomials
by a polynomial basis such as Chebyshev after explicit data scaling, is
often useful, but changes the coefficient metric.
fit_nullspaceperforms no implicit equilibration or normalisation; users choose the data scale and basis. - Higher degrees can obscure the spectral gap, because of redundant polynomials of The Veronese Parametrisation §“Choosing ”: lower-degree relations multiplied by variables produce a whole staircase of near-zero eigenvalues carrying no new information.
Doing it properly: degree by degree
The literature that solved this is the approximate vanishing ideal line — Heldt–Kreuzer–Pokutta–Poulisse’s AVI algorithm, and the closely related Vanishing Component Analysis (Livni et al.) and GPCA (Vidal–Ma–Sastry) for the subspace-arrangement case. The shape of the correct algorithm:
for degree δ = 1, 2, ..., d:
build the candidate set: monomials of degree δ, MINUS the span of
{x_j · f : f already found at degree δ-1} ← quotient out the known ideal
orthogonalise the candidates against the already-found polynomials
evaluate on the data, take the SVD, keep singular vectors below tolerance τ
add the new polynomials to the basis
Two things this buys you:
- the output is a border basis rather than an arbitrary generating set, which is the numerically stable analogue of a Gröbner basis (Kehrein–Kreuzer, Mourrain) — see Composition is Elimination §“Why not Gröbner” for why this distinction is essential;
- the spurious staircase is removed by construction.
The price is a tolerance parameter , and the output is discontinuous in it. There is no principled way to set from data; it is a numerical rank choice; this implementation reports the threshold and spectrum instead of hiding that choice.
What happens with missing channels — and why it is EM
The closed form above assumes every channel is observed for every data point. That is the training-on-complete-data case. If some channels are unobserved (which is the interesting case — that is what makes it a relation and not a dataset), the objective becomes
and the natural algorithm alternates:
- E-step: for fixed , infer by root finding;
- M-step: for fixed , update by the eigenproblem above.
This suggests a hard-completion alternating procedure related to Example 2 of AutoBayes. Minimising missing coordinates is not a posterior expectation and is not generally a closed-form E-step. Only the fixed-completion algebraic M-step has the spectral solution. Neither this alternation nor missing-data inference is implemented here; no convergence claim is made.
Cost
| step | cost |
|---|---|
| build | , one pass, parallel |
| bottom- eigenspace | dense, or per iteration with Lanczos on |
| memory | for |
The table describes the scatter-matrix approach. The implemented direct SVD instead stores V, avoiding squared condition numbers; see polyfit for underdetermined tables and memory use. Earlier unmeasured timing and capacity cutoffs have been removed.
Implemented fits and checks
fit_nullspace returns Θ, all m singular values (including structural zeros),
numerical_rank, nullity and threshold. No column scaling is applied.
fit_sampson uses the full analytic gradient, horizontal projection, QR
retraction and exchangeable solvers: RiemannianGradient() (Armijo),
FNS() for one equation, and the default RiemannianTrustRegion() with analytic
Hessian and truncated CG. Symbols :riemannian, :fns, :trust_region alias defaults;
user subtypes of AbstractSampsonMethod implement sampson_solve using the
public problem/geometry interface. These methods stop on the
Riemannian gradient norm and report convergence separately from iteration count.
See polyfit for the gradient derivation, checked citation, numerical choices
and seeded results: the real 400-point Klein fit in both bases, conic recovery
and noisy cost decrease, retracted-curve gradient differences, finite local
minimum checks, and a two-quadric intersection. The comparison test reaches
1e-7 in four RTR iterations on the ellipse (scaled and unscaled) and the noisy
k=2 curve; see polyfit for costs and limitations. No global Sampson optimum
is claimed.
Related: The Veronese Parametrisation, The Parameter is a Grassmannian, Algebraic versus Geometric Distance, AutoBayes Examples as Factor Graphs