The Parameter is a Grassmannian

model derivation

Derivation. The parameter of an algebraic factor is not a matrix; it is a $k$-plane. This is the cleanest concrete instance in the whole vault of Definition 2.5’s insistence that $P^{\prime }\ne P$.

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

Theory (CT-ML wiki): Statistical Game · Parametric Lens · Lens · Gradient Based Learning with Parametric Lenses

The non-identifiability

If $A\in G{L}_k(\mathbb{R})$ then $r_{A\Theta }=A{r}_{\Theta }$, so

$V(r_{A\Theta })=V(r_{\Theta })\text{and}⟨\text{rows of }A\Theta ⟩=⟨\text{rows of }\Theta ⟩$

The variety, the ideal, and the relation all depend on $\Theta$ only through its row space. The parameter is therefore genuinely a point of the Grassmannian

$P=\mathrm{Gr}(k,m),\dim P=k(m-k)$

not of ${\mathbb{R}}^{k\times m}$ (dimension $km$). The $k^2$ missing dimensions are pure gauge.

This is not pedantry. Three things go wrong if you ignore it:

1. Gradient descent on $\Theta \in {\mathbb{R}}^{k\times m}$ drifts along the gauge directions, changing the parameter without changing the model. Step sizes become meaningless; two runs that learned the same relation look maximally different.
2. $\Theta \to 0$ is a global minimiser of any residual objective, and it is reachable by descent. The normalisation $\Theta {\Theta }^{\top }=I_k$ of Fitting is a Nullspace Problem is not a regulariser bolted on to prevent collapse — it is a chart on $\mathrm{Gr}(k,m)$, and collapse is the symptom of using the wrong space.
3. The “spurious polynomial” pathology is the same phenomenon: a polynomial with tiny coefficients that “almost vanishes” everywhere is a point of ${\mathbb{R}}^{k\times m}$ near the origin, which is not a point of the Grassmannian at all.

The Riemannian gradient, derived

Represent a point by $\Theta \in {\mathbb{R}}^{k\times m}$ with $\Theta {\Theta }^{\top }=I_k$ (a Stiefel representative; the Grassmannian is the quotient by the $O(k)$ action). The horizontal (tangent-to-$\mathrm{Gr}$) space at $\Theta$ is

$T_{\Theta }=\{\Delta \in {\mathbb{R}}^{k\times m}:\Delta {\Theta }^{\top }=0\}$

i.e. row-wise orthogonal to the current row space. Given a Euclidean gradient $G={\nabla }_{\Theta }f$, the projection onto $T_{\Theta }$ is

$\boxed{{\Pi }_{\Theta }(G)=G-G{\Theta }^{\top }\Theta }$

Check: ${\Pi }_{\Theta }(G){\Theta }^{\top }=G{\Theta }^{\top }-G{\Theta }^{\top }(\Theta {\Theta }^{\top })=G{\Theta }^{\top }-G{\Theta }^{\top }=0$. ✓

The update is then a retraction, not an addition:

${\Theta }^{+}=\mathrm{qf}(\Theta -\eta {\Pi }_{\Theta }(G))$

where $\mathrm{qf}$ orthonormalises the rows (thin QR of the transpose, or a polar factor). Edelman–Arias–Smith is the standard reference for the geometry; the point here is only that ${\Theta }^{+}\ne \Theta +\Delta$.

This is exactly $(P,P^{\prime })$

Definition 2.5 carries a parameter pair $(P,P^{\prime })$ with $f^{\ast }:P\times A\times B^{\prime }\to P^{\prime }\times A^{\prime }$, and the vault’s note on it says the distinction matters “for a parameter constrained to a manifold, where the update lives in the tangent space, not in the manifold”. Here that is not a hypothetical:

$P=\mathrm{Gr}(k,m),P^{\prime }=T_{\Theta }\mathrm{Gr}(k,m)$

and Definition 3.11’s gradient-update lens $G^{\ast }(p,p^{\prime })=p+p^{\prime }$ is type-incorrect. The correct lens is

$G(\Theta )=\Theta ,G^{\ast }(\Theta ,\Delta )=\mathrm{qf}(\Theta +{\Pi }_{\Theta }(\Delta ))$

which is still a perfectly good lens $(P,P)\to (P,P^{\prime })$ — the framework accommodates it without modification. The categorical setup was right and the naive implementation was wrong, which is a satisfying vindication of taking the $(P,P^{\prime })$ distinction seriously.

And it is the natural gradient Definition 27 asks for

Definition 27 says the default semantics is gradient descent with respect to the Fisher information metric — the Bayesian learning rule. On $\mathrm{Gr}(k,m)$ the canonical (Riemannian) metric is $⟨{\Delta }_1,{\Delta }_2⟩=\mathrm{tr}({\Delta }_1{\Delta }_2^{\top })$ restricted to the horizontal space, and ${\Pi }_{\Theta }$ above is the metric-correct gradient. So in this family the natural gradient is not an expensive approximation of an intractable Fisher matrix — it is a projection costing one $k\times m$ matrix product.

Interaction with the rank-one structure

Backpropagation by the Implicit Function Theorem derives that each data point contributes a rank-one cotangent ${\bar{\Theta }}_i={\lambda }_i{v}_d(x_i{)}^{\top }$. So a minibatch of size $B$ gives $G$ of rank $\le B$, and

${\Pi }_{\Theta }(G)=G-G{\Theta }^{\top }\Theta$

is also rank $\le B$. The Riemannian update is a rank-$B$ perturbation of a $k$-plane. That is a well-studied object (subspace tracking; incremental SVD), and it means the update costs $O(Bkm)$ rather than $O(k{m}^2)$ — which is the difference between feasible and not at $m\sim 10^4$.

Caveat: the Grassmannian is the right space only for a fixed $k$ and $d$

Model selection — choosing how many generators and what degree — moves you between Grassmannians of different dimensions, and there is no smooth path. The numerical rank decision of Fitting is a Nullspace Problem is therefore a discrete jump between manifolds, not a continuous shrinkage. No continuous relaxation of it is known that behaves well; see Open Problems in Algebraic Implicit Learning §4.

Related: Fitting is a Nullspace Problem, Parametric Lens, Factors are Parameterized Statistical Games, Backpropagation by the Implicit Function Theorem