Principal Component Analysis (PCA) & Autoencoders

Recap & Introduction

Regression, classification, and SVMs are all supervised methods. They learn from labeled examples. We now turn to unsupervised learning, where the goal is to discover structure in data without labels.

The central technique is dimensionality reduction: finding low-dimensional representations that capture the essential variation in high-dimensional data. This page builds on eigenvalues and eigenvectors and the SVD from our linear-algebra section, and extends PCA to nonlinear settings using both kernels and neural networks.

Principal Component Analysis (PCA) is one of the most fundamental techniques in machine learning and statistics for dimensionality reduction. It provides a method to reduce the number of variables in high-dimensional datasets while retaining the most meaningful structure and variation present in the original data.

PCA begins by analyzing the covariance structure of the data. Given a dataset, we compute the covariance matrix to understand how different features co-vary. Since the covariance matrix is always symmetric and positive semi-definite, it can be orthogonally diagonalized. This is the finite-dimensional shadow of a more general result. That result is the spectral theorem for compact self-adjoint operators on Hilbert spaces, and it underlies the kernel PCA construction below. The resulting eigenvectors, called principal components (PCs), form an orthonormal basis that captures the directions of maximum variance. The corresponding eigenvalues indicate how much of the total variance is captured by each component.

By projecting the data onto the subspace spanned by the top \(k\) principal components (those associated with the largest eigenvalues), PCA identifies a lower-dimensional representation that retains as much variance as possible. This allows us to reduce dimensionality by discarding less informative directions (that is, those with small variance), thereby simplifying the dataset while minimizing information loss.

For example, if a dataset in \(\mathbb{R}^{10}\) has 3 principal components capturing 95% of the total variance, we can project the original data onto a 3D subspace. This projection preserves the dominant patterns and relationships in the data and filters out noise and redundancy. The transformed vectors in the low-dimensional space are known as latent representations.

While PCA is a powerful tool, it identifies directions of maximum variance using linear combinations of the original features. As a result, it may fail to uncover complex, nonlinear structures in the data.

Kernel PCA

Given an \(N \times D\) data matrix, PCA requires the eigenvectors of the \(D \times D\) covariance matrix \(\frac{1}{N} X^\top X\) of the centered data matrix \(X\). The factor \(\frac{1}{N}\) does not change the eigenvectors. If \(D \gg N\), working with the \(N \times N\) Gram matrix \(K = X X^\top\), whose entries are the inner products \(K_{ij} = x_i^\top x_j\), is much more efficient. In kernel PCA below, it becomes \(K = \Phi \Phi^\top\) with entries \(\langle \phi(x_i), \phi(x_j) \rangle\).

Kernel PCA (kPCA) is a nonlinear generalization of classical PCA that uses the kernel trick, which allows us to replace inner products \(x_i^\top x_j\) with a kernel function \(K_{ij} = \mathcal{K}(x_i, x_j)\). The spectral structure that makes this work is formalized by Mercer's theorem (for continuous positive-definite kernels on a compact domain) and, more generally, by the reproducing kernel Hilbert space (RKHS) construction developed in our functional-analysis section.

Kernel PCA implicitly replaces \(x_i\) with \(\phi(x_i) = \phi_i\). Let \(\Phi\) be the corresponding design matrix. Assuming the features are centered, the covariance matrix in feature space is represented by: \[ S_{\phi} = \frac{1}{N} \sum_i \phi_i \phi_i^\top. \]

The normalized eigenvectors of \(S_{\phi}\) with nonzero eigenvalues are given by: \[ V_{kPCA} = \Phi^\top U \Lambda^{-\frac{1}{2}} \] where the columns of \(U\) are orthonormal eigenvectors of the kernel (Gram) matrix \(K = \Phi \Phi^\top\) for its positive eigenvalues, which form the diagonal matrix \(\Lambda\). Indeed, since \(S_{\phi} = \frac{1}{N} \Phi^\top \Phi\), if \(K u = \lambda u\) with \(\lambda \gt 0\), then \[ \begin{align*} S_{\phi} \Phi^\top u &= \frac{1}{N} \Phi^\top K u \\\\ &= \frac{\lambda}{N} \Phi^\top u, \\\\ \|\Phi^\top u\|^2 &= u^\top K u = \lambda, \end{align*} \] so \(\Phi^\top u / \sqrt{\lambda}\) is a unit eigenvector of \(S_{\phi}\) with eigenvalue \(\lambda / N\).

Since \(\phi_i\) can be infinite dimensional, we cannot compute \(V_{kPCA}\) directly. Instead, we express the projection of a test vector \(x_*\) entirely in terms of kernel evaluations:

Note that using \(K = \Phi \Phi^\top\) is valid only if the features have zero empirical mean, \(\frac{1}{N} \sum_{i=1}^N \phi_i = 0\). However, the feature space can be infinite dimensional, so we cannot subtract off the mean. Here, we introduce the double centering trick.

Let the centered feature vector be \[ \tilde{\phi}_i = \phi(x_i) - \frac{1}{N} \sum_{j =1}^N \phi(x_j). \] Its Gram matrix is given by \[ \tilde{K}_{ij} = \tilde{\phi}_i^\top \tilde{\phi}_j. \]

Autoencoders

Data reconstruction serves as the primary quality control mechanism for dimensionality reduction. When we compress data from the original high-dimensional feature space \(\mathbb{R}^D\) to low-dimensional space \(\mathbb{R}^L\) (where \(L \lt D\)), we need to ensure that the essential structure and information of the original data are preserved. The reconstruction error provides a quantitative measure of information loss. If reconstruction is poor, the learned representation is inadequate for the task at hand.

Reconstruction ensures that the learned latent representation \(z = f_e(x)\) captures the most relevant and meaningful features of the data. The function \(f_e : \mathbb{R}^D \to \mathbb{R}^L\) is called the encoder. If the decoder \(f_d : \mathbb{R}^L \to \mathbb{R}^D\) can successfully reconstruct the original input \(x\) from \(z\), it demonstrates that \(z\) contains sufficient information about the underlying data structure.

The reconstruction function is \(r(x) = f_d \left(f_e(x) \right)\), and the encoder-decoder pair is trained to minimize the negative log-likelihood \(\mathcal{L}(\theta) = -\log p(x | r(x))\). For a Gaussian likelihood with fixed variance, this is the squared reconstruction error up to a positive factor and an additive constant. PCA is the case in which \(f_e\) and \(f_d\) are linear maps.

We can implement \(f_e\) and \(f_d\) by neural networks. This is called an autoencoder. In particular, a linear autoencoder is equivalent to PCA:

We state this classical result without proof. It rests on the best low-rank approximation property of the truncated SVD, which lies beyond this page. Without centering, the optimal subspace is determined by the second-moment matrix \(\frac{1}{N} \sum_{n} x_n x_n^\top\) instead of the covariance matrix.

Introducing nonlinearities lets the autoencoder represent curved low-dimensional structure that no linear projection can capture. Moreover, deep autoencoders scale to large datasets far better than kernel PCA, whose \(N \times N\) Gram matrix grows quadratically with the number of data points. In practical applications they have therefore become the more popular choice for nonlinear mapping.

Denoising Autoencoders

Denoising autoencoders (DAE) are a more regularized variant of standard autoencoders that add noise to the input during training, then learn to reconstruct the original, uncorrupted data. The theoretical consequence, stated below, is that the optimal denoiser implicitly learns the score function of the data distribution.

The training process involves corrupting the input \(x\) to produce \(\tilde{x}\), typically using Gaussian noise: \[ p_c (\tilde{x} | x) = \mathcal{N}(\tilde{x} | x, \sigma^2 I) \]

The model then minimizes the reconstruction error between its output \(r(\tilde{x})\) and the clean input \(x\): \[ \ell (x, r(\tilde{x})) = \| e \|_2^2 \] where \(e(x) = r(\tilde{x}) - x \) is the residual error for a sample \(x\).

This score function forms a vector field over the entire feature space. At each point, this vector field indicates the direction and magnitude to move toward regions of higher data density. The reconstruction process follows these vectors, effectively "flowing" corrupted points back to the data manifold along the steepest ascent of the probability landscape.

Data Manifolds in Our Demo

The autoencoder tab in our demo visualizes data manifolds. When the 2D data is compressed through a 1D bottleneck, every reconstruction lies on a single curve, the image of the decoder, so the network must fit the data with a 1-D curve. The Data & reconstruction panel shows each point mapped onto this learned curve. This is the autoencoder discovering and representing the intrinsic lower-dimensional structure of the data.

Note. Lipschitz continuity is a common regularity condition. A function \(f: (X, d_X) \to (Y, d_Y)\) is Lipschitz with constant \(L \geq 0\) if \(d_Y(f(x_1), f(x_2)) \leq L \, d_X(x_1, x_2)\) for all \(x_1, x_2 \in X\). The full development appears in our continuity page in the analysis section. It includes the hierarchy Lipschitz \(\Rightarrow\) uniformly continuous \(\Rightarrow\) continuous.

This means the function's output changes at most linearly with respect to the input. In autoencoders, Lipschitz continuity in the reconstruction map \(r(x)\) ensures stability. Small changes in input lead to small changes in reconstruction.

In the context of denoising autoencoders, enforcing or assuming Lipschitz continuity makes the learned vector field well-behaved. Under a Lipschitz condition, the flow of this vector field exists and is unique (the Picard-Lindelöf theorem, which we do not prove here), and the reconstructions cannot change sharply or unstably. This is essential when approximating the gradient \(\nabla_x \log p(x)\).

Manifolds

Intuitively, a manifold is a topological space that locally resembles Euclidean space near each point. Imagine a curved surface like a sphere. Zooming in on any small patch makes it look flat, like \(\mathbb{R}^2\). In machine learning, we often assume data lies on a low-dimensional manifold embedded in high-dimensional space.

This is the intuitive form sufficient for the manifold-hypothesis discussion that follows. The full differential structure (charts, atlases, smoothness) is developed rigorously in our smooth-manifold series.

The Manifold Hypothesis. Real-world high-dimensional data (for example, images and speech) tends to lie on or near a low-dimensional manifold embedded in the ambient space.

For example, each \(64 \times 64\) grayscale face image can be represented as a point in \(\mathbb{R}^{4096}\), but the set of "realistic" face images occupies only a small, structured region of this space. That region is likely a nonlinear manifold of much lower dimension, governed by factors such as pose, lighting, expression, and identity.

Dimensionality reduction reveals low-dimensional structure in data, but does not assign data points to groups. The clustering page addresses this complementary unsupervised task: partitioning data into meaningful groups without labels. We will see how K-means minimizes distortion in the original feature space, while spectral clustering leverages the graph Laplacian to discover clusters that respect the geometry of the data manifold.

Looking further ahead, the manifold hypothesis introduced here is the entry point to a much broader program. Tangent spaces, Riemannian metrics, and the maps between manifolds await in our manifold series, which generalizes the intuitive picture above. On the discrete side, sampled data on graph-structured domains motivate graph neural networks, whose spectral variants use the eigenstructure of the graph Laplacian as a learnable signal-processing primitive. Both threads converge in Geometric Deep Learning (GDL), where neural-network architectures are designed to respect the symmetries and geometric structure of the data they operate on.