Sparse Autoencoders › Dictionary Learning Connection

Sparse autoencoders are closely related to the classical problem of dictionary learning in signal processing. Dictionary learning was originally developed for audio and image compression, where the goal is to represent signals as sparse combinations of basis atoms that are learned from data rather than defined analytically. The learned atoms capture the statistical regularities of the data domain: for natural images, these look like oriented edges; for music, they look like notes and chords.

Dictionary learning seeks a matrix $\mathbf{D} \in \mathbb{R}^{d \times m}$ (the dictionary) and sparse codes $\mathbf{Z} \in \mathbb{R}^{m \times n}$ (one column per data point) such that the reconstruction is accurate and each code is sparse.

Formally, the dictionary learning problem minimizes:

$$\min_{\mathbf{D}, \mathbf{Z}} \| \mathbf{X} - \mathbf{D} \mathbf{Z} \|_F^2 \quad \text{subject to } \| \mathbf{Z}[:, i] \|_0 \leq k \text{ for all } i$$

where:

• $\mathbf{X} \in \mathbb{R}^{d \times n}$: the matrix of $n$ data points (activation vectors stacked as columns)
• $\mathbf{D} \in \mathbb{R}^{d \times m}$: the overcomplete dictionary, with each column being a dictionary atom (a feature vector)
• $\mathbf{Z} \in \mathbb{R}^{m \times n}$: the sparse code matrix, one column per data point
• $\| \mathbf{Z}[:, i] \|_0 \leq k$: the sparsity constraint requiring at most $k$ non-zero entries per code vector
• $\| \cdot \|_F^2$: the squared Frobenius norm (sum of squared entries), measuring total reconstruction error

The classical approach alternates between a sparse coding step (fix $\mathbf{D}$, find sparse $\mathbf{Z}$ using matching pursuit or LASSO) and a dictionary update step (fix $\mathbf{Z}$, update $\mathbf{D}$ via K-SVD or gradient descent). SAEs reformulate this as a single end-to-end gradient descent problem: the encoder performs an approximate sparse coding step (using ReLU instead of an iterative solver), and the decoder columns are the learned dictionary.

The SAE approach sacrifices some theoretical optimality for practical scalability. Exact sparse coding via LASSO or matching pursuit on millions of activation vectors would be prohibitively expensive: each LASSO solve requires iterative optimization. The ReLU encoder provides an amortized approximation, learning to recognize which features are likely active from the input pattern alone, without iterating at inference time. A single forward pass gives a sparse code in $O(md)$ time, enabling training on the scale required for large language models.

It is worth understanding precisely what "amortization" means here. In classical dictionary learning, to find the sparse code for a new data point $\mathbf{x}$, you run an optimization procedure (e.g., basis pursuit or LASSO) from scratch for that specific input. This takes many iterations and scales poorly. An amortized approach trains a parametric function (the encoder) to predict the sparse code directly from the input. Once trained, the encoder runs in a single forward pass. The trade-off is that the encoder's approximation to the optimal sparse code is imperfect, particularly for unusual inputs that were not well-represented in the training distribution. This "amortization gap" is a known limitation of SAEs and motivates variants that run a few steps of optimization after the encoder's initial prediction.