Learning Linear and Independent Structures — A Guided Journey

This post is a record of my learning journey through Chapter 2 of the Berkeley Deep Representation Learning book. Rather than a polished summary, it captures the actual process — the questions, the derivations, the stuck points, and the moments of clarity. Everything under Me: I derived myself on paper. Everything under Claude: is guidance, hints, or consolidation.

We agreed on a format: I attempt everything on paper first, photograph my work, and Claude gives targeted hints only where I’m stuck. No spoon-feeding.

Chapter Map

Here’s the skeleton of what actually matters in Chapter 2, stripped of all book filler:

CENTRAL PROBLEM: Data lives on a low-dimensional manifold
                 in a high-dimensional space. Recover it.

┌─────────────────────────────────────────────────────────┐
│ 2.1  PCA — one linear subspace                          │
│   • Model: x = Uz + ε                                   │
│   • Key insight: denoising = projection onto subspace   │
│   • Solution: top eigenvectors of XX^T/N                │
│   • Algorithm: power iteration                          │
├─────────────────────────────────────────────────────────┤
│ 2.2  Complete Dictionary Learning / ICA                 │
│   — UNION of subspaces, not their span                  │
│   • Why PCA fails: rotation invariance destroys sparsity│
│   • Key insight: sparsity ↔ non-Gaussianity ↔ kurtosis  │
│   • Solution: maximize ℓ⁴ norm (MSP algorithm)          │
└─────────────────────────────────────────────────────────┘

Section 2.1 — Principal Components Analysis

The Setup

We have \(N\) data points \(\{\mathbf{x}_i\}_{i=1}^N \subset \mathbb{R}^D\). We believe they approximately live on a \(d\)-dimensional subspace, where \(d \ll D\). The data-generating model is:

where \(\mathbf{U} \in \mathbb{R}^{D \times d}\) has orthonormal columns (so \(\mathbf{U}^\top \mathbf{U} = \mathbf{I}_d\)), \(\mathbf{z}_i \in \mathbb{R}^d\) is the low-dimensional latent code, and \(\boldsymbol{\varepsilon}_i\) is small noise.

Goal: Recover \(\mathbf{U}\) from data.

Step 1 — Optimal Code for Fixed Subspace

Claude: Given fixed \(\mathbf{U}\) (orthonormal columns), find the \(\mathbf{z}_i\) minimising \(\|\mathbf{x}_i - \mathbf{U}\mathbf{z}_i\|_2^2\). What does it mean geometrically?

Me: I write the squared norm as a transpose product and expand:

Expanding:

The cross terms both equal the same scalar so they combine. Using \(\mathbf{U}^\top\mathbf{U} = \mathbf{I}_d\):

Differentiating with respect to \(\tilde{\mathbf{z}}_i\) and setting to zero:

(Note: I initially wrote \(\mathbf{z}_i = \mathbf{x}_i^\top\mathbf{U}\) — a row vector — then caught the shape error and corrected to the column vector form.)

Claude: Exactly right. Note: the two cross terms collapse because both are scalars, so a scalar equals its own transpose — you’ll use that trick constantly.

Now push further: what is \(\mathbf{U}\mathbf{U}^\top\mathbf{x}_i\) geometrically?

Me: (sketch) Taking \(D=3\), \(d=1\), so \(\mathbf{U} = \mathbf{u}\) is a single unit vector:

The scalar \(\mathbf{u}^\top\mathbf{x}_i\) is the component of \(\mathbf{x}_i\) along \(\mathbf{u}\), and we scale \(\mathbf{u}\) by it. This is the orthogonal projection of \(\mathbf{x}_i\) onto the line spanned by \(\mathbf{u}\).

Claude: Perfect. Generalising: \(\mathbf{U}\mathbf{U}^\top\) is orthogonal projection onto the \(d\)-dimensional subspace spanned by the columns of \(\mathbf{U}\).

Retention anchor: Why is \(\mathbf{U}\mathbf{U}^\top\mathbf{x}_i\) the denoised version of \(\mathbf{x}_i\)?

Answer chain: \(\mathbf{x}_i = \mathbf{U}\mathbf{z}_i + \boldsymbol{\varepsilon}_i\) → the true signal lives on the subspace → projection strips the noise component → \(\hat{\mathbf{x}}_i = \mathbf{U}\mathbf{U}^\top\mathbf{x}_i\).

Step 2 — Minimising Reconstruction Error Equals Maximising Projected Variance

Claude: Show that minimising \(\frac{1}{N}\sum_{i=1}^N \|\mathbf{x}_i - \tilde{\mathbf{U}}\tilde{\mathbf{U}}^\top\mathbf{x}_i\|_2^2\) is equivalent to maximising \(\frac{1}{N}\sum_{i=1}^N \|\tilde{\mathbf{U}}^\top\mathbf{x}_i\|_2^2\).

Me: Expand the reconstruction error:

Using idempotency of the projection: \(\tilde{\mathbf{U}}^\top\tilde{\mathbf{U}} = \mathbf{I}_d\), so \(\tilde{\mathbf{U}}\tilde{\mathbf{U}}^\top\tilde{\mathbf{U}}\tilde{\mathbf{U}}^\top = \tilde{\mathbf{U}}\tilde{\mathbf{U}}^\top\). Therefore the last two terms collapse:

Summing over all \(i\):

Minimising the left side is therefore equivalent to:

Claude: The key step you nailed: idempotency \((\mathbf{U}\mathbf{U}^\top)^2 = \mathbf{U}\mathbf{U}^\top\) collapsed the last two terms. Geometrically this is Pythagoras — total energy of \(\mathbf{x}_i\) minus captured energy equals residual error.

Step 3 — The Objective Becomes a Trace

Claude: Show \(\frac{1}{N}\sum_i \|\tilde{\mathbf{U}}^\top\mathbf{x}_i\|_2^2 = \mathrm{tr}\!\left(\tilde{\mathbf{U}}^\top \frac{\mathbf{X}\mathbf{X}^\top}{N}\tilde{\mathbf{U}}\right)\).

Me: Writing \(\tilde{\mathbf{U}}^\top\mathbf{x}_i\) explicitly — \(\tilde{\mathbf{U}}^\top\) has rows \(\mathbf{u}_1^\top, \dots, \mathbf{u}_d^\top\)

Therefore:

using the identity \(\|\mathbf{v}\|^2 = \mathrm{tr}(\mathbf{v}\mathbf{v}^\top)\). Summing:

using linearity of trace and \(\sum_i \mathbf{x}_i\mathbf{x}_i^\top = \mathbf{X}\mathbf{X}^\top\).

Step 4 — The Solution is the Top Eigenvectors

Claude: For \(d=1\), maximise \(\tilde{\mathbf{u}}^\top\mathbf{M}\tilde{\mathbf{u}}\) subject to \(\|\tilde{\mathbf{u}}\|=1\), where \(\mathbf{M} = \mathbf{X}\mathbf{X}^\top/N\). For general \(d\), show the solution consists of the top \(d\) eigenvectors of \(\mathbf{M}\).

Me: I use the Lagrangian approach. For finding the first principal component \(\mathbf{u}_1\):

Setting derivatives to zero:

So \(\mathbf{u}\) is an eigenvector of \(\mathbf{M}\). Since we want to maximise \(\mathbf{u}^\top\mathbf{M}\mathbf{u} = \lambda\mathbf{u}^\top\mathbf{u} = \lambda\), we choose the eigenvector corresponding to the largest eigenvalue.

For \(\mathbf{u}_2\), we add the orthogonality constraint \(\mathbf{u}_1^\top\mathbf{u}_2 = 0\):

Left-multiplying by \(\mathbf{u}_1^\top\):

So the equation reduces to \(\mathbf{M}\mathbf{u}_2 = \lambda_1\mathbf{u}_2\) — again an eigenvector of \(\mathbf{M}\), and the maximiser is the eigenvector with the second largest eigenvalue.

By induction, the optimal \(\tilde{\mathbf{U}}^\star\) has columns equal to the top \(d\) eigenvectors of \(\mathbf{M} = \mathbf{X}\mathbf{X}^\top/N\).

PCA Summary and Retention Anchors

The full PCA pipeline:

This is a linear autoencoder. The denoised output \(\hat{\mathbf{x}} = \mathbf{U}^\star(\mathbf{U}^\star)^\top\mathbf{x}\) is the projection onto the learned subspace.

Three anchors — if you can answer these, you can rebuild PCA from scratch:

1. Why does minimising reconstruction error equal maximising projected variance?
2. What is \(\mathbf{U}\mathbf{U}^\top\) and why is it the optimal denoiser?
3. Why does the optimal \(\mathbf{U}\) consist of top eigenvectors of \(\mathbf{X}\mathbf{X}^\top/N\)?

Interlude — The Spectral Theorem

Before moving to Section 2.2, we needed the spectral theorem, and then SVD. Rather than accept them as black boxes, I derived both from scratch.

Spectral Theorem

Statement: If \(\mathbf{M} \in \mathbb{R}^{n \times n}\) is symmetric, then \(\mathbf{M} = \mathbf{Q}\mathbf{\Lambda}\mathbf{Q}^\top\) where \(\mathbf{Q}\) is orthogonal and \(\mathbf{\Lambda}\) is diagonal with real entries.

Part 1 — Eigenvalues are real.

Me: Let \(\mathbf{M}\mathbf{v} = \lambda\mathbf{v}\) with \(\lambda \in \mathbb{C}\), \(\mathbf{v} \in \mathbb{C}^n\). Compute \(\bar{\mathbf{v}}^\top\mathbf{M}\mathbf{v}\) two ways.

Way 1: Using the eigenvalue equation directly:

Way 2: Take the complex conjugate of the whole expression. Since \(\mathbf{M}\) is real and symmetric (\(\mathbf{M}^* = \mathbf{M}\), \(\mathbf{M}^\top = \mathbf{M}\)):

But from \(\mathbf{M}\mathbf{v} = \lambda\mathbf{v}\), taking conjugates gives \(\mathbf{M}\bar{\mathbf{v}} = \bar{\lambda}\bar{\mathbf{v}}\), so:

Equating both computations of \(\bar{\mathbf{v}}^\top\mathbf{M}\mathbf{v}\) and its conjugate:

Part 2 — Eigenvectors of distinct eigenvalues are orthogonal.

Me: Take two eigenpairs \((\lambda_1, \mathbf{v}_1)\) and \((\lambda_2, \mathbf{v}_2)\) with \(\lambda_1 \neq \lambda_2\). Compute \(\mathbf{v}_1^\top\mathbf{M}\mathbf{v}_2\) two ways.

Way 1: Use \(\mathbf{v}_2\) is an eigenvector:

Way 2: Use symmetry of \(\mathbf{M}\) — transpose the expression (it’s a scalar so equals its transpose):

Equating:

Since \(\lambda_1 \neq \lambda_2\): \(\mathbf{v}_1^\top\mathbf{v}_2 = 0 \quad \blacksquare\)

SVD — Singular Value Decomposition

Statement: Any \(\mathbf{A} \in \mathbb{R}^{m \times n}\) can be written as \(\mathbf{A} = \mathbf{U}\mathbf{\Sigma}\mathbf{V}^\top\) where \(\mathbf{U} \in \mathbb{R}^{m\times m}\), \(\mathbf{V} \in \mathbb{R}^{n\times n}\) are orthogonal and \(\mathbf{\Sigma} \in \mathbb{R}^{m\times n}\) is diagonal with non-negative entries \(\sigma_1 \geq \sigma_2 \geq \dots \geq 0\).

Step 1 — Properties of \(\mathbf{A}^\top\mathbf{A}\) and \(\mathbf{A}\mathbf{A}^\top\).

Me:

Symmetry:

Non-negative eigenvalues: If \(\mathbf{A}^\top\mathbf{A}\mathbf{v} = \lambda\mathbf{v}\), left-multiply by \(\mathbf{v}^\top\):

Since \(\|\mathbf{A}\mathbf{v}\|^2 \geq 0\) and \(\|\mathbf{v}\|^2 > 0\), we get \(\lambda \geq 0\).

Shared nonzero eigenvalues: If \(\mathbf{A}^\top\mathbf{A}\mathbf{v} = \lambda\mathbf{v}\) with \(\lambda \neq 0\), left-multiply by \(\mathbf{A}\):

So \(\mathbf{A}\mathbf{v}\) is an eigenvector of \(\mathbf{A}\mathbf{A}^\top\) with the same eigenvalue \(\lambda\). And \(\mathbf{A}\mathbf{v} \neq \mathbf{0}\) since \(\|\mathbf{A}\mathbf{v}\|^2 = \lambda\|\mathbf{v}\|^2 > 0\).

Step 2 — Assembling SVD.

Me: Define \(\sigma_i = \sqrt{\lambda_i}\) (singular values). The eigenvectors \(\mathbf{v}_1, \dots, \mathbf{v}_n\) of \(\mathbf{A}^\top\mathbf{A}\) are orthonormal (spectral theorem). Define:

So \(\mathbf{A}\mathbf{v}_i = \sigma_i\mathbf{u}_i\). Stacking into matrices:

Right-multiplying by \(\mathbf{V}^\top\), and using \(\mathbf{V}\mathbf{V}^\top = \mathbf{I}\) (since \(\mathbf{V}\)’s columns are orthonormal eigenvectors of a real symmetric matrix):

Section 2.2 — Complete Dictionary Learning

The New Setting

Instead of data living on one subspace, it lives on a union of subspaces — each \(\mathbf{x}_i\) comes from one of \(K\) subspaces. The model:

where \(\mathbf{U} \in O(D)\) is a square orthogonal dictionary and \(\mathbf{z}\) is sparse. The word complete means the dictionary has exactly \(D\) columns — a full basis for \(\mathbb{R}^D\).

Why PCA Fails

Claude: Why does PCA fail here? What happens if you substitute \(\tilde{\mathbf{U}}\mathbf{Q}\) into the PCA objective for any orthogonal \(\mathbf{Q}\)?

Me: The PCA objective is \(\mathrm{tr}(\tilde{\mathbf{U}}^\top\mathbf{M}\tilde{\mathbf{U}})\). Substituting \(\tilde{\mathbf{U}}\mathbf{Q}\):

Using the cyclic property of trace — cycle \(\mathbf{Q}^\top\) to the right end:

since \(\mathbf{Q}\mathbf{Q}^\top = \mathbf{I}\) for orthogonal \(\mathbf{Q}\).

Conclusion: The PCA objective is rotation invariant — replacing \(\tilde{\mathbf{U}}\) with \(\tilde{\mathbf{U}}\mathbf{Q}\) gives identical objective value. If \(\mathbf{U}^\star\) gives sparse codes \(\mathbf{z}_i = (\mathbf{U}^\star)^\top\mathbf{x}_i\), then \(\mathbf{U}^\star\mathbf{Q}\) gives codes \(\mathbf{Q}^\top\mathbf{z}_i\) — which are generically not sparse.

The PCA objective never really PREFERS a sparse solution.

\(\ell^4\) Maximisation Promotes Sparsity

We need an objective that breaks rotation invariance and actively prefers sparse codes.

Geometric intuition: Consider the \(\ell^p\) unit ball:

• \(p=2\): circle (in 2D)
• \(p=4\): between circle and square — bulges toward coordinate axes
• \(p=\infty\): square — corners point exactly at coordinate axes

Maximising \(\|\mathbf{v}\|_4^4\) on the \(\ell^2\) sphere finds points that stick furthest into the corners of the \(\ell^4\) ball — exactly the coordinate axis directions, which are the sparse vectors.

Algebraic proof (I insisted on this rather than just intuition):

Maximise \(\sum_i z_i^4\) subject to \(\sum_i z_i^2 = 1\). Lagrangian:

So each \(z_i = 0\) or \(z_i = \pm\sqrt{\mu/2}\). If \(k\) entries are nonzero, the constraint gives \(k\cdot(\mu/2) = 1\), so \(\mu = 2/k\) and the objective equals \(1/k\).

• Maximising: set \(k=1\) → coordinate axis, value \(= 1\)
• Minimising: set \(k=n\) → uniform vector, value \(= 1/n\)

The \(\ell^4\) Objective and Gradient

The dictionary learning objective:

Here \(\tilde{\mathbf{A}}\) is our candidate for \(\mathbf{U}^\top\) — the inverse of the dictionary. When we find the right \(\tilde{\mathbf{A}}\), the transformed data \(\tilde{\mathbf{A}}\mathbf{x}_i \approx \mathbf{z}_i\) is sparse, maximising the \(\ell^4\) norm.

Computing the gradient:

Let \(\mathbf{B} = \tilde{\mathbf{A}}\mathbf{X} \in \mathbb{R}^{D\times N}\), so \(B_{pj} = \sum_k \tilde{A}_{pk}X_{kj}\).

In matrix form — index \(p\) picks a row of \(\mathbf{B}^{\odot 3}\), index \(q\) picks a row of \(\mathbf{X}\), summing over \(j\) contracts the \(N\) dimension:

where \(\odot 3\) denotes elementwise cube.

Projection onto Orthogonal Matrices

There is no closed-form solution to the \(\ell^4\) maximisation (it’s nonconvex), so we use projected gradient ascent: take a gradient step, then project back onto \(O(D)\).

What does “closest orthogonal matrix” mean? We minimise the Frobenius norm:

Me: Write \(\mathbf{M} = \mathbf{U}\mathbf{\Sigma}\mathbf{V}^\top\). Expand:

(using cyclic trace, \(\mathrm{tr}(\mathbf{A}) = \mathrm{tr}(\mathbf{A}^\top)\), and \(\mathbf{Q}^\top\mathbf{Q}=\mathbf{I}\))

Minimising over \(\mathbf{Q}\) is equivalent to:

by the cyclic property. Substituting \(\tilde{\mathbf{Q}} = \mathbf{U}^\top\mathbf{Q}\mathbf{V}\) (which is orthogonal since it’s a product of orthogonal matrices, verified by \(\tilde{\mathbf{Q}}^\top\tilde{\mathbf{Q}} = \mathbf{V}^\top\mathbf{Q}^\top\mathbf{U}\mathbf{U}^\top\mathbf{Q}\mathbf{V} = \mathbf{I}\)):

Therefore \(\mathbf{U}^\top\mathbf{Q}^\star\mathbf{V} = \mathbf{I}\), giving:

Geometric meaning: Drop the singular values, keep only the two rotations. The nearest orthogonal matrix sets all singular values to 1.

The MSP Algorithm

Putting gradient and projection together, the Matching, Stretching, and Projection (MSP) algorithm is:

where \(\mathbf{U}_t\mathbf{\Sigma}_t\mathbf{V}_t^\top\) is the SVD of \((\tilde{\mathbf{A}}_t\mathbf{X})^{\odot 3}\mathbf{X}^\top\). Under broad conditions this converges to the correct dictionary at a superlinear rate.

Compare this to power iteration for PCA:

Both are fixed-point iterations. MSP is the \(\ell^4\) analogue of power iteration.

Section 2.2 Retention Anchors

Anchor 4: Why does PCA fail to recover a sparse dictionary? (The objective is rotation invariant — replacing \(\mathbf{U}\) by \(\mathbf{U}\mathbf{Q}\) leaves the objective unchanged but destroys sparsity of the codes.)

Anchor 5: Why does \(\ell^4\) maximisation promote sparsity geometrically? (The \(\ell^4\) ball has corners pointing at coordinate axes. Maximising \(\ell^4\) norm on the \(\ell^2\) sphere finds directions that stick into those corners — the sparse directions.)

Anchor 6: What is the MSP iteration and where does each piece come from? (Gradient of \(\ell^4\) objective gives \((\tilde{\mathbf{A}}\mathbf{X})^{\odot 3}\mathbf{X}^\top\); projection onto \(O(D)\) via SVD gives \(\mathbf{U}\mathbf{V}^\top\).)

Anchor 7: Why is \(\mathbf{U}\mathbf{V}^\top\) the closest orthogonal matrix to \(\mathbf{M} = \mathbf{U}\mathbf{\Sigma}\mathbf{V}^\top\)? (Frobenius minimisation → cyclic trace → reduce to \(\max\mathrm{tr}(\mathbf{\Sigma}\tilde{\mathbf{Q}})\) → entries bounded by 1 → \(\tilde{\mathbf{Q}} = \mathbf{I}\) optimal → \(\mathbf{Q}^\star = \mathbf{U}\mathbf{V}^\top\).)