model derivation

The forward pass of an algebraic factor. Given a polarity, inference means solving a polynomial system — and everything interesting follows from counting its solutions.

Sources: original to this vault (design and analysis); code: lib/AlgebraicFactors.jl/src/polynomial.jl, lib/AlgebraicFactors.jl/test/polynomial.jl (single-branch Gaussian sites, rank cases, circle and graph oracles), lib/AlgebraicFactors.jl/ext/AlgebraicFactorsHomotopyContinuationExt.jl, lib/AlgebraicFactors.jl/test/homotopy.jl (isolated square-system roots and branch mixtures); Breiding & Timme, HomotopyContinuation.jl: A Package for Homotopy Continuation in Julia (2018); Breiding, Rose & Timme, Certifying Zeros of Polynomial Systems Using Interval Arithmetic (2023), Theorem 3.6 and Lemma 7.1.

Bibliography: Breiding & Timme 2018 · Breiding et al. 2023

Theory (CT-ML wiki): Compact Closed Category · Statistical Game · Open Model

The problem

Split with observed (clamped) and unobserved (to be inferred), . Inference is

a system of polynomial equations of degree in unknowns, with coefficients depending polynomially on the clamped .

There is no distinguished direction. The same answers any polarity; only the split changes. This is compact closure made completely concrete — the “forward” and “backward” passes of an algebraic factor are the same computation with different variables held fixed.

Well-posedness is a rank condition

squaregenerically finitely many solutions
underdeterminedpositive-dimensional solution set: genuinely multi-valued
overdeterminedgenerically no solution: must minimise instead

More precisely, the polarity is well-posed at a solution iff

which is exactly the hypothesis of the implicit function theorem. So Pointwise well-posedness is computable from Jᵤ, but it is not the interface’s supports_polarity declaration. The latter declares an available algorithm before parameters, beliefs or a point are supplied. PolynomialFactor declares all single-target polarities and computes rank at message time: a deficient Jᵤ returns an improper site, including a flat site at rank zero (polynomial). The square invertible case above is the classical root IFT; k>q can still have an isolated root or a locally unique least-squares minimiser. It is not necessary for all forms of local inference.

The overdetermined case is not a failure mode to be avoided; it is the README’s “output only the closest point to the variety, instead of a point on the variety”. It is handled by replacing root finding with

Nonnegativity gives an infimum, not necessarily an attained minimiser. For example r(x,y)=(xy−1,x) has no zero, yet r(1/n,n)=(0,1/n) tends to zero. The test file checks that sequence; the two equations directly show why no zero exists. Existence or coercivity assumptions are needed before treating minimisation as a total solve. A proper target Gaussian prior makes the fixed-SPD-metric polynomial objective coercive; the implemented finite Gauss–Newton loop still does not certify convergence.

Implemented local approximation

L-SPEC-004 §3(b) implements one branch via the cavity mean (zero without one), exact polynomial Jacobians and Gaussian sites with the Sampson covariance frozen per iteration. iterations relinearises the current posterior with the original prior; likelihood_message returns the extrinsic site and invert pools once. Observed inputs can be Dirac or proper Gaussian. The tests compare all linear polarities with the actual linear constraint, a circle with a separately written fixed-final-metric scalar objective, and ab+c=0 in a Mycelium graph with a joint Laplace calculation. This is Gauss–Newton curvature, not the full Hessian away from zero residual. It neither enumerates roots nor implements the IFT backward pass or game entropy. Optional HomotopyBranches() now enumerates isolated roots of square targets and returns a mixture of regular real branch posteriors (§4, homotopy); no IFT backward pass or game quantities are added.

How many solutions

For a square system of equations of degree in unknowns, over :

and more sharply, by Bernstein–Khovanskii–Kushnirenko (BKK), the number of solutions in the torus is bounded by the mixed volume of the Newton polytopes — much smaller for sparse systems. Since the learned is typically dense in the monomial basis, expect Bézout in practice unless sparsity is imposed.

Bézout bound
2101 024
31059 049
320
330

The exponential is in the number of unobserved channels, not the total dimension. That is a genuinely useful distinction: a factor in variables of which only are ever inferred at once is fine (), even though its parameter count is uncomfortable. Inference cost and learning cost are governed by different exponentials, and a graph can be designed to keep small per message while is large. This is the strongest argument for the factor-graph architecture within this family.

How to actually solve it

Homotopy continuation is the right tool: deform a start system with known solutions into the target and track the paths. Total-degree homotopy tracks paths; polyhedral homotopy tracks only mixed-volume-many. It is:

  • enumerative — tracks paths toward isolated complex roots; numerical failed paths and infinity diagnostics must be inspected before asserting completeness;
  • embarrassingly parallel — one path per core;
  • certifiable — HC’s interval/Krawczyk certification can prove an isolated nonsingular zero near a candidate. This is not α-theory, nor by itself proof that all roots were found.

In Julia this is HomotopyContinuation.jl (Breiding–Timme); the classical alternative is Bertini. For positive-dimensional solution sets, witness sets and numerical irreducible decomposition handle the case.

Cheaper local alternatives, when completeness is not needed: Newton from a warm start (the previous message’s value, or the prior’s mean). This is what a message-passing schedule would actually do in the inner loop, falling back to homotopy only when Newton fails.

Alternatives when the system is not square

  • Gauss–Newton / Levenberg–Marquardt on : uses and needs the vector residual — see Scalar and Multivariate Energy §6. Local, fast, no completeness guarantee.
  • Moment–SOS (Lasserre) relaxation: minimise globally via a hierarchy of SDPs, with a Positivstellensatz certificate of global optimality (Varieties Ideals and Real Nullstellensatz §“Positivstellensatz”). Globally certified, but the order- moment matrix has size and must often exceed 2. Practical for .

Real versus complex

Homotopy continuation finds complex solutions; you want real ones. Three consequences:

  1. You pay for all complex paths and discard most of them. There is no known way to track only the real solutions.
  2. The number of real solutions changes with . Over some regions there are two, over others none. This is the branch structure of Branches and the Discriminant and it makes inference discontinuous in the observed input.
  3. may be empty even when is large (Varieties Ideals and Real Nullstellensatz §“Problem 1”). Inference then has no answer as a hard root problem. A soft model may instead minimise , or report failure: the implemented §4 inference throws and keeps path/root diagnostics available through polynomial_branches.

Where this genuinely works

Not hypothetical — these are the established successes, and they share the profile ” moderate, small, structure known”:

problemsolution count
6R serial manipulator inverse kinematics6exactly 16 (Lee–Liang; Raghavan–Roth; Primrose)
5-point relative pose (essential matrix)5exactly 10 (Demazure; Nistér)
conic through 5 points—1
chemical reaction network steady statessmallvaries; well studied

The inverse-kinematics case is the archetype for the whole family: a relation between joint angles and end-effector pose; inference in one direction is easy (forward kinematics), in the other is a degree-16 root find; the multiple solutions are physically real (elbow up / elbow down), not numerical artefacts; and selecting among them needs a prior.

Related: Branches and the Discriminant, Backpropagation by the Implicit Function Theorem, Channels and Polarity, The Algebraic Factor as a Statistical Game