Autoencoders & Robust PCA

Chapter 1: The Encoder-Decoder Architecture

An autoencoder has two halves. The encoder maps input x to a low-dimensional latent code z. The decoder maps z back to a reconstruction x̂. The loss is the reconstruction error: how different is x̂ from x?

The encoder compresses. The decoder expands. Training minimizes reconstruction error, which forces the bottleneck z to capture the most important information about x.

The Bottleneck Is the Point

If z has the same dimension as x, the autoencoder can just copy the input (identity function). That teaches nothing. The bottleneck — making dim(z) << dim(x) — forces the network to discover structure. It must decide: what information is essential, and what can be discarded?

python
import torch.nn as nn

class Autoencoder(nn.Module):
    def __init__(self, input_dim=784, z_dim=20):
        super().__init__()
        self.encoder = nn.Sequential(
            nn.Linear(input_dim, 256),
            nn.ReLU(),
            nn.Linear(256, z_dim)
        )
        self.decoder = nn.Sequential(
            nn.Linear(z_dim, 256),
            nn.ReLU(),
            nn.Linear(256, input_dim),
            nn.Sigmoid()  # pixel values in [0,1]
        )

    def forward(self, x):
        z = self.encoder(x)       # [B, 784] -> [B, 20]
        x_hat = self.decoder(z)   # [B, 20] -> [B, 784]
        return x_hat, z

Chapter 2: Linear AE = PCA (The Proof)

Here's a beautiful fact: if the encoder and decoder are both linear (no ReLU, no nonlinearity), the optimal autoencoder recovers PCA exactly. Let's prove it.

Setup

Let the encoder be z = Wx (where W is k×d) and the decoder be x̂ = Dz (where D is d×k). The loss is:

We want to minimize over W and D. Let's write this in matrix form. Stack all data as columns of X (d×n). Then:

The Proof

The product DW is a d×d matrix of rank at most k (since it factors through k dimensions). So we're looking for the best rank-k approximation to the identity (when applied to X). By the Eckart-Young theorem, the best rank-k approximation to X in Frobenius norm is given by the truncated SVD:

The optimal encoder projects onto the top-k singular vectors: W = U_k^T. The optimal decoder reconstructs using those same vectors: D = U_k. This is exactly PCA — projection onto the principal components.

Chapter 3: Variational Autoencoders (VAE)

A regular autoencoder maps each input to a single point in latent space. But what if we want to generate new data? We'd need to sample random points in latent space and decode them. The problem: a regular AE's latent space has "holes" — regions that don't correspond to valid data.

The Variational Autoencoder (VAE) fixes this by making the encoder output a distribution instead of a point. Specifically, it outputs μ and σ for a Gaussian, and we sample z from that Gaussian.

The Reparameterization Trick

We can't backpropagate through a random sample. But we can rewrite sampling as a deterministic function of a separate random variable ε:

Now the gradient flows through μ and σ (deterministic), while ε is just an external random input. This is the reparameterization trick — it makes the sampling step differentiable.

The VAE Loss

Two terms: (1) reconstruction error (make x̂ close to x), and (2) KL divergence that pushes q(z|x) toward the prior p(z) = N(0,I). The KL term ensures the latent space is smooth and complete — no holes.

Chapter 4: Robust PCA — Low-Rank + Sparse

Standard PCA is fragile. A single outlier can rotate the principal components dramatically. What if we knew the corruption was sparse — only affecting some entries, but affecting them badly?

Robust PCA decomposes a matrix X into two components:

where L is low-rank (the clean signal) and S is sparse (the corruption). Think of it as: L is the video background (low-rank because every frame looks similar), S is the foreground (sparse because moving objects occupy few pixels).

Why Not Just Use SVD?

If you SVD the corrupted matrix X, the corruption contaminates every singular vector. SVD finds the best overall low-rank approximation, but it smears the sparse errors across all components. Robust PCA separates them cleanly.

The Convex Relaxation

We want to minimize rank(L) subject to X = L + S with S sparse. But rank minimization is NP-hard. The nuclear norm ||L||_* (sum of singular values) is the tightest convex relaxation of rank. Similarly, ||S||₁ (sum of absolute values) promotes sparsity.

This is Principal Component Pursuit (PCP). Remarkably, under mild conditions (L is not too sparse, S is not too low-rank), this convex program exactly recovers the true L and S.

Chapter 5: Algorithms for Robust PCA

How do we actually solve the PCP convex program? Two main approaches: ADMM (Alternating Direction Method of Multipliers) and iterative thresholding.

ADMM for PCP

ADMM introduces a Lagrange multiplier Y and alternates between updating L, S, and Y:

Singular Value Thresholding (SVT)

The key operation is SVT: take the SVD of a matrix, subtract a threshold τ from each singular value (setting negatives to zero), then reconstruct. This is the proximal operator for the nuclear norm — it shrinks the singular values, effectively reducing rank.

Soft Thresholding (Shrinkage)

For the sparse component, soft thresholding shrinks each element toward zero:

This is the proximal operator for the L1 norm. It zeroes out small entries (they're treated as noise) and shrinks large entries (they're treated as true corruption minus bias).

python
import numpy as np

def robust_pca(X, lam=None, mu=None, tol=1e-6, max_iter=100):
    """Principal Component Pursuit via ADMM."""
    m, n = X.shape
    if lam is None: lam = 1.0 / np.sqrt(max(m, n))
    if mu is None: mu = m * n / (4 * np.abs(X).sum())

    L = np.zeros_like(X)
    S = np.zeros_like(X)
    Y = np.zeros_like(X)

    for _ in range(max_iter):
        # SVT for L
        U, s, Vt = np.linalg.svd(X - S + Y/mu, full_matrices=False)
        s_thresh = np.maximum(s - 1/mu, 0)
        L = U @ np.diag(s_thresh) @ Vt

        # Soft threshold for S
        temp = X - L + Y/mu
        S = np.sign(temp) * np.maximum(np.abs(temp) - lam/mu, 0)

        # Dual update
        residual = X - L - S
        Y = Y + mu * residual

        if np.linalg.norm(residual) / np.linalg.norm(X) < tol:
            break

    return L, S

Chapter 6: Showcase — Matrix Separation

Time to see Robust PCA in action. We'll create a low-rank matrix, corrupt it with sparse errors, and watch the ADMM algorithm cleanly separate the two components.

When Does RPCA Fail?

Try pushing corruption above 40%. The algorithm starts confusing S with L — the sparse component becomes too dense to be distinguishable from low-rank structure. The theoretical guarantee requires:

In plain English: L must be genuinely low-rank, and S must be genuinely sparse. If either condition fails, no algorithm can separate them (information-theoretically impossible).

Chapter 7: Beyond — Connections

Autoencoders and Robust PCA are entry points into a rich landscape of representation learning and matrix decomposition methods.

Related Lessons

Next: NMF & Clustering — what happens when you require non-negativity. Also: Dictionary Learning & Sparse Coding — learning overcomplete dictionaries with sparse codes.