The Veronese Parametrisation

model derivation

The single structural fact that makes the algebraic family tractable: the residual is linear in the parameter.

Sources: original to this vault (design and analysis; no single paper).

Theory (CT-ML wiki): Reverse Derivative Category

Setup

Collect all channels of a factor into one vector $x\in {\mathbb{R}}^N$, $N={\sum }_i\dim X_i$. Let $v_d:{\mathbb{R}}^N\to {\mathbb{R}}^m$ be the Veronese embedding of degree $d$ — the vector of all monomials of degree $\le d$:

$$v_d(x)=(1,x_1,\dots ,x_N,x_1^2,x_1{x}_2,\dots ,x_N^d{)}^{\top },m=(\genfrac{}{}{0ex}{}{N+d}{d})$$

A vector of $k$ polynomials of degree $\le d$ is then exactly a matrix $\Theta \in {\mathbb{R}}^{k\times m}$, and the residual of the implicit learner is

$\boxed{r_{\Theta }(x)=\Theta v_d(x)}$

with the relation $R_{\Theta }=V_{\mathbb{R}}(r_{\Theta })=\{x:\Theta v_d(x)=0\}$.

Why this is the right coordinatisation

The model factors as a fixed nonlinear embedding followed by a linear map.

${\mathbb{R}}^N\stackrel{v_d(\text{fixed, exact, sparse})}{\to }{\mathbb{R}}^m\stackrel{\Theta (\text{learned, linear})}{\to }{\mathbb{R}}^k$

Everything learnable is in the linear part. Consequences, each derived in its own note:

consequence	note
fitting is an eigenproblem with a global optimum	Fitting is a Nullspace Problem
the parameter cotangent is rank one per data point	Backpropagation by the Implicit Function Theorem
$\Theta$ is identified only up to $G{L}_k$, so $P=Gr(k,m)$	The Parameter is a Grassmannian
all Jacobians are $\Theta \cdot D{v}_d(x)$ — no autodiff needed	below

This is a genuinely unusual profile. A neural network is nonconvex in its parameters and trivial in its inputs. An algebraic factor is linear in its parameters and hard in its inputs. The difficulty has been moved from learning to inference.

Jacobians, exactly

$D{v}_d(x)\in {\mathbb{R}}^{m\times N}$ has entries $\partial x^{\alpha }/\partial x_j={\alpha }_j{x}^{\alpha -e_j}$ — a sparse matrix of monomials, computable exactly in integer arithmetic on the exponents. So

$J_r(x)=\frac{\partial r_{\Theta }}{\partial x}=\Theta D{v}_d(x)\in {\mathbb{R}}^{k\times N}$

and, splitting $x=(x_{obs},x_{unobs})$ by a polarity,

$$J_o=\Theta D{v}_d(x{)}_{[:,obs]}\in {\mathbb{R}}^{k\times p},J_u=\Theta D{v}_d(x{)}_{[:,unobs]}\in {\mathbb{R}}^{k\times q}$$

There is no automatic differentiation anywhere in this family. Derivatives of every order are exact rational functions of the data, obtained by index arithmetic on exponent vectors. This is worth stating plainly because it is the one place where an algebraic factor is strictly better behaved than any neural alternative: no truncation error, no tape, no checkpointing, and second derivatives are as cheap as first.

The number that kills it

$m=\left(\genfrac{}{}{0ex}{}{N+d}{d}\right)$

$N$	$d$	$m$
10	3	286
20	3	1 771
20	4	10 626
100	3	176 851
100	4	4 598 126
784 (MNIST)	2	308 505
784	3	8.09 × 10⁷

$m$ is simultaneously:

• the parameter count (times $k$);
• the sample complexity — with $M<m$ data points the matrix $V\in {\mathbb{R}}^{M\times m}$ of Fitting is a Nullspace Problem has a nontrivial null space for purely dimensional reasons, so you can fit a variety through the data while learning nothing. You need $M\gg m$;
• the size of the eigenproblem, $O(m^3)$ dense (or $O(m^{2}k)$ iteratively);
• the number of columns Gröbner/border-basis algorithms manipulate.

One number, four exponentials. This is why the family is filed under “low dimensions” and why no amount of implementation cleverness rescues it — see Open Problems in Algebraic Implicit Learning §2 for the escape routes that have been tried (sparse/structured supports, kernelisation, random projection) and why none of them fully works.

Choosing $d$ is not free either

Increasing $d$ does not merely add capacity; it adds spurious vanishing polynomials. If $f$ vanishes on the data and $\mathrm{deg}f\le d-1$, then $x_{j}f$ also vanishes and lies in degree $\le d$. So the null space at degree $d$ automatically contains $N\cdot (\text{null space at }d-1)$ worth of junk carrying no new information.

Any honest fitting procedure must work degree by degree, quotienting out the ideal generated by what was already found. That is exactly what approximate-vanishing-ideal and border-basis algorithms do; see Fitting is a Nullspace Problem §“Doing it properly”.

Related: Fitting is a Nullspace Problem, The Parameter is a Grassmannian, Backpropagation by the Implicit Function Theorem