model derivation

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:

  1. 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_nullspace performs no implicit equilibration or normalisation; users choose the data scale and basis.
  2. 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

stepcost
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