Sparse Coding · Manifold Interpretation of PCA

§13.4 Sparse coding

Sparse coding (Olshausen & Field 1996) is the most heavily studied linear factor model for unsupervised feature learning and extraction. (Strictly, “sparse coding” names the inference of $\boldsymbol{h}$ and “sparse modeling” the design and learning of the model, but the first term usually covers both.) Like the rest of the family it generates $\boldsymbol{x}$ with a linear decoder plus noise (eq 13.2) — here Gaussian with isotropic precision $\beta$ :

The sparse coding likelihood (eq 13.12)

p(\boldsymbol{x} \mid \boldsymbol{h}) = \mathcal{N}\Big(\boldsymbol{x};\ \boldsymbol{W}\boldsymbol{h} + \boldsymbol{b},\ \tfrac{1}{\beta}\boldsymbol{I}\Big)

$\boldsymbol{W}\boldsymbol{h} + \boldsymbol{b}$	the linear decoder — the reconstruction the code h proposes for x	n
$\beta$	the noise PRECISION (inverse variance): large β = the reconstruction must be tight; it will reappear as the weight on reconstruction error in the encoding objective	scalar
$\tfrac{1}{\beta}\boldsymbol{I}$	isotropic — the same tolerance in every input dimension (compare factor analysis's per-variable ψ)	n × n

The prior over the code is what earns the name: a distribution with a sharp peak at zero — factorized Laplace, Cauchy, or Student-t:

Sharply-peaked priors (eqs 13.13–13.14)

p(h_i) = \text{Laplace}\Big(h_i;\, 0, \tfrac{2}{\lambda}\Big) = \frac{\lambda}{4}\, e^{-\frac{1}{2}\lambda |h_i|}, \qquad p(h_i) \propto \frac{1}{\big(1 + \frac{h_i^2}{\nu}\big)^{\frac{\nu+1}{2}}}

$\lambda$	the sparsity penalty coefficient — the Laplace prior is parametrized so that λ lands directly in the encoding objective below	scalar
$e^{-\frac{1}{2}\lambda \|h_i\|}$	the \|hᵢ\| in the exponent is the signature: its log-gradient has CONSTANT magnitude λ/2 all the way to zero, unlike a Gaussian whose pull fades near 0 — this is what will zero out weak components	Laplace
$\big(1 + h_i^2/\nu\big)^{-\frac{\nu+1}{2}}$	the Student-t alternative: heavy tails plus a sharp peak; ν controls how heavy	Student-t

Why “peaked at zero” means sparse features

The prior says: most factors are inactive most of the time. Compare the Laplace curve below against the Gaussian you know from §3.9: far more mass hugging $0$ , and heavier tails — a few strong activations, many near-silent ones. Exactly the statistics of natural images described by a dictionary of edges and strokes.

The Laplace prior (interactive) — the sharp peak at 0 that makes codes sparse. Shrink γ (= 2/λ, so large λ = small γ) and watch the mass pile onto zero; contrast the smooth-shouldered Gaussian from §3.9.3.

μ0.00γ0.60

a sharp peak at an ARBITRARY point μ = 0.0 — the movable cousin of the exponential

Training is not maximum likelihood. The likelihood is intractable, so training alternates: encode the data (find the best codes for the current dictionary), then update the decoder $\boldsymbol{W}$ to reconstruct better given those codes — a scheme later justified as a principled approximation to maximum likelihood (§19.3). And here is the structural surprise of this model. For PCA we had a parametric encoder — a matrix multiply. Sparse coding’s encoder is an optimization algorithm:

From MAP inference to the sparse coding objective (eqs 13.15–13.18)

\boldsymbol{h}^* = f(\boldsymbol{x}) = \arg\max_{\boldsymbol{h}}\ p(\boldsymbol{h} \mid \boldsymbol{x})

step 1/4: The encoder seeks the single most likely code for THIS input — MAP inference, run afresh for every example. There is no learned mapping to apply.

The $L^1$ norm on $\boldsymbol{h}$ is doing the sparsifying, by exactly the soft-threshold mechanism of §7.1.2: components whose usefulness falls below the threshold are set to exactly zero. Revisit it with sparse-coding eyes — the “unregularized” axis is now how much a dictionary feature wants to activate, and the dead zone is the prior winning:

L¹ soft-thresholding (reused from §7.1.2) — the mechanism inside the sparse coding encoder. Components below the dead-zone threshold α/H become EXACT zeros: the sparse code. L² shrinkage (green) can only shrink proportionally — never to zero.

L¹ — soft-threshold (sparse) L² — proportional shrink

α = 1.00H = 1.50w*ᵢ = 0.60

threshold α/H = 0.67

L² factor H/(H+α) = 0.60

L¹ → 0.00zeroed

L² → 0.36

Any w*ᵢ inside the shaded band |w*ᵢ| ≤ α/H is driven to exactly zero by L¹ — that is sparsity. L² only scales every weight by the same factor, so nonzero weights stay nonzero.

Three practical notes from the book. β is a hyperparameter, typically fixed to 1 — its role overlaps λ’s, so one knob suffices; learning β instead would require keeping the h-independent terms our derivation dropped (else β collapses to 0). Not every approach is probabilistic: often we just want a dictionary of features whose activations are usually zero under this inference — no $p(\boldsymbol{h})$ , $p(\boldsymbol{x} \mid \boldsymbol{h})$ story needed. And a subtlety: under a Laplace prior, an element of $\boldsymbol{h}$ being exactly zero is a probability-zero event — the generative model is not especially sparse; only the feature extractor is! The spike and slab sparse coding model (Goodfellow et al. 2013) fixes this: its prior mixes a point-mass spike at zero with a broad slab, so prior samples contain true zeros.

Parametric encoder vs. optimization encoder

Two ways to encode — click a cell for the caveat.
	Parametric encoder (PCA, ch14 autoencoders)	Optimization encoder (sparse coding)
How h is computed	a fixed learned map, e.g. h = Wᵀ(x − μ)	solve argmin λ‖h‖₁ + β‖x − Wh‖₂² per example
Encoding speed	one matrix multiply (or a few fixed layers)	slow — an iterative algorithm per input
Encoder generalization error	yes — a learned map can fail on unusual x	none — inference is optimal for ANY x
Back-propagation through the encoder	straightforward — it is a differentiable network	hard — the encoder is an algorithm, not a graph
Few-labels regime	weaker as a feature extractor	often generalizes better (≤ 20 labels/class)

Dotted-underlined cells have explanations — click one.

Why good features still make bad samples

Sparse coding — like the other linear factor models — often produces poor samples (fig 13.2), even when it reconstructs well and feeds a classifier useful features. Each individual feature is learned well; the problem is the factorial prior, which activates a random subset of features in each sample. Random subsets of penstrokes rarely make a digit:

Fig 13.2, schematically — a spike-and-slab sparse coding model trained on MNIST learns penstroke features (left). Sampling draws each code component INDEPENDENTLY, combining a random subset of strokes (middle) — almost never a digit. Real digits need coordinated subsets (right): that coordination is exactly what a factorial prior cannot express, motivating non-factorial priors over deeper code layers.

This failure motivates both deeper models that impose a non-factorial distribution on the deepest code layer, and more sophisticated shallow models — the program of chapters 16–20.

§13.5 Manifold interpretation of PCA

Linear factor models — PCA and factor analysis included — can be read as learning a manifold (Hinton et al. 1997; recall the manifold hypothesis of §5.11.3). Probabilistic PCA defines a thin pancake of high probability: a Gaussian that is very narrow along some axes (flat, like a pancake’s height) and elongated along others (wide, like its face). PCA aligns that pancake with a low-dimensional linear manifold in input space:

Fig 13.3 (recreated) — a flat Gaussian concentrating probability near a low-dimensional manifold; the upper half of the “pancake” is drawn above the manifold plane through its middle. Variance orthogonal to the plane is tiny — that direction is “noise”; the large in-plane variances are “signal”, and their directions form a coordinate system for the reduced-dimension data.

The interpretation covers any linear autoencoder trained to reconstruct its input — the bridge to chapter 14. Define the encoder and decoder:

The linear autoencoder (eqs 13.19–13.20)

\boldsymbol{h} = f(\boldsymbol{x}) = \boldsymbol{W}^{\top}(\boldsymbol{x} - \boldsymbol{\mu}), \qquad \hat{\boldsymbol{x}} = g(\boldsymbol{h}) = \boldsymbol{b} + \boldsymbol{V}\boldsymbol{h}

$\boldsymbol{W}^{\top}(\boldsymbol{x} - \boldsymbol{\mu})$	the encoder: center x, then project to d coordinates — a PARAMETRIC map (contrast sparse coding above)	d
$\boldsymbol{\mu}$	the centering point; at the optimum, μ = b = 𝔼[x]	n
$\boldsymbol{b} + \boldsymbol{V}\boldsymbol{h}$	the decoder: map the low-dimensional code back into input space	n

Minimizing the reconstruction error ties every piece to the covariance’s eigenstructure:

Optimal linear reconstruction (eqs 13.21–13.23)

\min\ \mathbb{E}\big[\lVert \boldsymbol{x} - \hat{\boldsymbol{x}} \rVert^2\big] = \sum_{i=d+1}^{D} \lambda_i, \qquad \boldsymbol{C} = \mathbb{E}\big[(\boldsymbol{x} - \boldsymbol{\mu})(\boldsymbol{x} - \boldsymbol{\mu})^{\top}\big]

$\boldsymbol{V} = \boldsymbol{W},\ \boldsymbol{\mu} = \boldsymbol{b} = \mathbb{E}[\boldsymbol{x}]$	the minimizing choice: decoder = encoder transposed back, centering at the mean	optimum
$\boldsymbol{C}$	the input covariance; W's columns become an orthonormal basis spanning the same subspace as C's top-d eigenvectors (for PCA: exactly those eigenvectors, ordered by eigenvalue)	D × D
$\lambda_i = \text{Var along } \boldsymbol{v}^{(i)}$	each eigenvalue IS the variance of x in its eigenvector's direction — all real and non-negative	spectrum
$\sum_{i=d+1}^{D} \lambda_i$	the optimal reconstruction error is exactly the variance you chose to discard; rank-d covariance ⇒ zero error	the price

Worked example — the price of dropping directions

Say $D = 4$ and the covariance eigenvalues are $\lambda = (3.5,\ 1.2,\ 0.4,\ 0.1)$ — total variance $5.2$ . Keeping $d = 2$ components costs $\lambda_3 + \lambda_4 = 0.4 + 0.1 = 0.5$ : the pancake is $4.7/5.2 \approx 90\%$ of the variance, and the two discarded directions were mostly “noise” thickness. Keep $d = 3$ and the price drops to $0.1$ ; if the covariance had rank $2$ , the price at $d = 2$ would be exactly $0$ .

Same solution, two stories

You can derive this $\boldsymbol{W}$ by minimizing reconstruction error — or, equivalently, by maximizing the variance of the code elements $\boldsymbol{h}$ under orthogonal $\boldsymbol{W}$ . Wide pancake face, thin pancake height: two descriptions of one alignment. Replay it by hand in the PCALab of §2.12 — the “snap to principal component” button is eq 13.23 in action.

The manifold view, hands-on (reused from §2.12) — rotate the projection direction and watch total squared error vs. %variance captured trade off; snapping to the principal component minimizes eq 13.21, leaving exactly the discarded-eigenvalue error of eq 13.23.

direction0°show projections & error segments

total squared error: 37.1

variance captured: 77.1%

Rotate d and watch the arg-min from the derivation: error is minimized exactly when d is the eigenvector of XᵀX with the largest eigenvalue.

Chapter close. Linear factor models are among the simplest generative models and the simplest representation learners. Just as linear classifiers and linear regression grew into deep feedforward networks, these models now grow into autoencoder networks (chapter 14) and deep probabilistic models (chapters 16–20) — same tasks, vastly more powerful families.

Check yourself — sparse coding & the manifold view of PCA

1.What is sparse coding's encoder?

2.Why does the L¹ term in argmin λ‖h‖₁ + β‖x − Wh‖₂² produce a SPARSE code?

3.Sparse coding has "no encoder generalization error." What does that mean?

4.Sparse coding reconstructs well and yields good classifier features — yet its SAMPLES look terrible (fig 13.2). Why?

5.Keep d = 2 of D = 4 principal components when the covariance eigenvalues are λ = (3.5, 1.2, 0.4, 0.1). What is the optimal reconstruction error?

6.Under a Laplace prior, how sparse are samples from the sparse coding GENERATIVE model?

6 questions