The minimum of a linear autoencoder, step by step

STATEMENT

Prove that the smallest loss of a linear autoencoder is the sum of the discarded eigenvalues, find every pair of matrices that attains it, and evaluate the result on four points.

GIVEN

Centred data with covariance $\mat S=\sum_{i=1}^d\lambda_i\vec u_i\vec u_i^{\mathsf T}$, where $\lambda_1\geq\cdots\geq\lambda_d>0$ and the $\vec u_i$ are orthonormal. The loss is the first line of (I.12.2), with $\mat E\in\R^{k\times d}$, $\mat D\in\R^{d\times k}$ and $k<d$. Assume $\lambda_k>\lambda_{k+1}$. For the numbers, use the four points of I.12.B01 with $k=1$.

FIND

(a) The best encoder for a fixed decoder, and the end-to-end map it gives. (b) The loss of that map in terms of an orthonormal basis. (c) The lower bound and the condition for equality. (d) All minimising pairs. (e) The eigenvalues, the optimal map, its loss and two different factorisations for the four points. (f) The other stationary projection and a path that leaves it downhill.

STRATEGY

Reduce pairs of matrices to subspaces by solving for the encoder. Then write the retained variance as a weighted sum of eigenvalues and bound the weights.

SOLUTION

(a) Fix $\mat D$ with independent columns. For one input, the derivative of $\|\vec x-\mat D\vec z\|^2$ with respect to $\vec z$ is $-2\mat D^{\mathsf T}(\vec x-\mat D\vec z)$. It vanishes at

which is the unique minimum because $\mat D^{\mathsf T}\mat D$ is positive definite. The same matrix serves every input, so $\mat E=(\mat D^{\mathsf T}\mat D)^{-1}\mat D^{\mathsf T}$ and

Direct multiplication gives $\mat P^2=\mat P$ and $\mat P^{\mathsf T}=\mat P$: the orthogonal projection onto the columns of $\mat D$. No other encoder gives any input a better code, so no encoder has a smaller loss than $\mat P$. Because $\lambda_d>0$ the data span every direction, and a different encoder gives some of them a strictly worse one.

(b) Choose $\mat Q\in\R^{d\times k}$ with orthonormal columns spanning the same subspace. Then $\mat P=\mat Q\mat Q^{\mathsf T}$, and $\mat I-\mat P$ is symmetric with $(\mat I-\mat P)^2=\mat I-\mat P$. Moving one factor around the trace,

This is (I.12.4).

(c) Substitute the eigendecomposition:

Since $\mat Q\mat Q^{\mathsf T}$ is a projection and $\vec u_i$ a unit vector, $0\leq c_i\leq1$. Since the $\vec u_i$ are an orthonormal basis, $\sum_ic_i=\operatorname{tr}(\mat Q^{\mathsf T}\mat Q)=k$. Therefore $\sum_{i\leq k}(1-c_i)=\sum_{i>k}c_i$, and

So the retained variance is at most $\lambda_1+\cdots+\lambda_k$, and

Because $\lambda_k>\lambda_{k+1}$, equality requires $c_i=0$ for every $i>k$, hence $c_i=1$ for every $i\leq k$. A unit vector whose projection has length one lies in the subspace. The subspace is therefore the span of $\vec u_1,\ldots,\vec u_k$, and $\mat P=\mat U_k\mat U_k^{\mathsf T}$.

(d) A decoder attains the bound exactly when its columns span that subspace, that is, $\mat D=\mat U_k\mat G$ with $\mat G=\mat U_k^{\mathsf T}\mat D$ invertible. By (a) the encoder must then be

Every invertible $\mat G$ gives a minimiser, and these are all of them. This is (I.12.5).

A decoder of rank below $k$ spans fewer than $k$ dimensions. Its retained variance is at most $\lambda_1+\cdots+\lambda_{k-1}$, which is strictly less because $\lambda_k>0$.

(e) For the four points, $\mat S$ has trace $5$ and determinant $2.92\cdot2.08-1.44^2=4$, so its eigenvalues solve $\lambda^2-5\lambda+4=0$: they are $4$ and $1$. Solving $(\mat S-4\mat I)\vec u=\vec 0$ gives $\vec u_1=(0.8,0.6)$, and then $\vec u_2=(-0.6,0.8)$. With $k=1$,

For the point $(1,2)$ the code under $\mat G=1$ is $0.8+1.2=2$, the reconstruction is $(1.6,1.2)$ and the residual is $(-0.6,0.8)$, of squared length $1$. The same holds at every corner.

Two factorisations of the same map: $\mat G=1$ gives $\mat D=(0.8,0.6)^{\mathsf T}$ and $\mat E=(0.8,\,0.6)$. $\mat G=1/5$ gives $\mat D=(0.16,0.12)^{\mathsf T}$ and $\mat E=(4,\,3)$.

(f) Setting $\mat D=\vec u_2$ and $\mat E=\vec u_2^{\mathsf T}$ makes both gradients of (I.12.2) vanish, with loss $\lambda_1=4$. Rotate the direction to $\cos\theta\,\vec u_2+\sin\theta\,\vec u_1$. By (b) the loss is $5-(\cos^2\theta+4\sin^2\theta)=4-3\sin^2\theta$. At $\theta=0.1$ it is $3.970100$. The point is stationary and is not a minimum.

Check — sanity

The optimal map has trace $1$, the dimension of the subspace, and squares to itself: its first entry is $0.64^2+0.48^2=0.64$. The retained variance $4$ and the loss $1$ add to the total $5$.