Linear Algebra for Deep Learning

Chapter Overview

Linear algebra forms the mathematical foundation of deep learning. Neural networks perform sequences of linear transformations interspersed with nonlinear operations, making matrices and vectors the fundamental objects of study. This chapter develops the linear algebra concepts essential for understanding how deep learning models transform data, how information flows through neural architectures, and how we can interpret the geometric operations these models perform.

Unlike a pure mathematics course, our treatment emphasizes the specific linear algebra operations that appear repeatedly in deep learning: matrix multiplication for transforming representations, dot products for measuring similarity, and matrix decompositions for understanding structure. We pay particular attention to dimensions and shapes, as tracking how tensor dimensions transform through operations is crucial for implementing and debugging deep learning systems.

Learning Objectives

After completing this chapter, you will be able to:

1. Represent data as vectors and transformations as matrices with clear understanding of dimensions
2. Perform matrix operations and understand their geometric interpretations
3. Calculate and interpret dot products as similarity measures
4. Understand eigendecompositions and singular value decompositions and their applications
5. Apply matrix norms and use them in regularization
6. Recognize how linear algebra operations map to neural network computations

Vector Spaces and Transformations

Vectors as Data Representations

In deep learning, we represent data as vectors in high-dimensional spaces. A vector $\vx \in \R^n$ is an ordered collection of $n$ real numbers, which we can interpret geometrically as a point in $n$-dimensional space or as an arrow from the origin to that point.

The dimension $n$ is the number of components in the vector. We write vectors as column vectors by default.

Linear Transformations

Linear transformations preserve vector space structure: they map lines to lines and preserve the origin ($T(\mathbf{0}) = \mathbf{0}$).

Matrices as Linear Transformations

Every linear transformation from $\R^n$ to $\R^m$ can be represented by an $m \times n$ matrix.

Matrix Operations

Matrix Multiplication

Computational Complexity of Matrix Operations

Understanding the computational cost of matrix operations is essential for designing efficient deep learning systems.

Batch Matrix Multiplication

Modern deep learning frameworks process multiple examples simultaneously using batched operations.

Transpose

Important properties:

Hardware Context for Matrix Operations

Understanding how matrix operations map to hardware is crucial for writing efficient deep learning code.

Memory Layout: Row-Major vs Column-Major

Matrices are stored in memory as one-dimensional arrays, and the layout significantly affects performance. In row-major order, used by C and PyTorch, rows are stored consecutively in memory. In column-major order, used by Fortran and MATLAB, columns are stored consecutively. For a matrix $\mA = \begin{bmatrix} a & b \\ c & d \end{bmatrix}$, row-major storage produces the sequence $[a, b, c, d]$ while column-major storage produces $[a, c, b, d]$.

# Good: Sequential memory access
for i in range(m):
    for j in range(n):
        result += A[i, j]  # Accesses consecutive memory

# Bad: Strided memory access  
for j in range(n):
    for i in range(m):
        result += A[i, j]  # Jumps across rows

GPU Acceleration and BLAS Libraries

Modern deep learning relies on highly optimized linear algebra libraries that provide standardized interfaces for common operations. The Basic Linear Algebra Subprograms (BLAS) standard defines three levels of operations: Level 1 for vector operations like dot products and norms with $O(n)$ complexity, Level 2 for matrix-vector operations like $\mA\vx$ with $O(n^2)$ complexity, and Level 3 for matrix-matrix operations like $\mA\mB$ with $O(n^3)$ complexity. Common CPU implementations include Intel MKL, OpenBLAS, and Apple Accelerate, while GPU implementations include NVIDIA cuBLAS and AMD rocBLAS. These libraries achieve near-peak hardware performance through careful optimization of memory access patterns, instruction scheduling, and hardware-specific features.

Compute-Bound vs Memory-Bound Operations

Dot Products and Similarity

Matrix Decompositions

Eigenvalues and Eigenvectors

Geometrically, an eigenvector is only scaled (not rotated) when $\mA$ is applied. The eigenvalue $\lambda$ is the scaling factor.

Singular Value Decomposition

Low-Rank Approximation and Model Compression

SVD enables efficient model compression by approximating matrices with lower-rank factorizations.

SVD in Modern Architectures

Low-rank matrix decompositions are also central to modern parameter-efficient fine-tuning methods such as LoRA, which adds low-rank updates $\Delta \mW = \mB\mA$ (with $\mB \in \R^{d \times r}$, $\mA \in \R^{r \times k}$, $r \ll \min(d,k)$) to frozen pre-trained weights, achieving $>$99\% parameter reduction. See Chapter~20 for details.

import torch

# Original weight matrix
W = torch.randn(512, 2048)

# Compute SVD
U, S, Vt = torch.linalg.svd(W, full_matrices=False)

# Rank-k approximation
k = 64
W_compressed = U[:, :k] @ torch.diag(S[:k]) @ Vt[:k, :]

# Factored form for efficient computation
W1 = U[:, :k] @ torch.diag(S[:k])  # 512 x 64
W2 = Vt[:k, :]                       # 64 x 2048

# Verify approximation
error = torch.norm(W - W_compressed, p='fro')
relative_error = error / torch.norm(W, p='fro')
print(f"Relative error: {relative_error:.4f}")

# Memory comparison
original_params = W.numel()
compressed_params = W1.numel() + W2.numel()
compression_ratio = compressed_params / original_params
print(f"Compression: {(1-compression_ratio)*100:.1f}

Norms and Distance Metrics

Norms are used in regularization to prevent overfitting by penalizing large weights.

import torch

# Vector norms
x = torch.tensor([3.0, 4.0])
l2_norm = torch.norm(x, p=2)  # 5.0
l1_norm = torch.norm(x, p=1)  # 7.0

# Matrix Frobenius norm
W = torch.randn(256, 784)
frob_norm = torch.norm(W, p='fro')

Practical Deep Learning Examples

Embedding Layers and Memory Requirements

Complete Transformer Layer Analysis

Understanding the full computational profile of a transformer layer---parameters, FLOPs, memory, and hardware utilization---is essential for practical deep learning engineering. Section~[ref] provides a comprehensive, self-contained worked analysis of BERT-base, the standard baseline configuration used as a running example throughout this textbook.

Common Dimension Errors and Debugging

import torch

# Problem: Shape mismatch in matrix multiplication
Q = torch.randn(32, 512, 768)  # [batch, seq_len, d_model]
K = torch.randn(32, 512, 768)

# Wrong: Q @ K gives error (768 != 512)
# scores = Q @ K  # Error!

# Correct: Transpose last two dimensions of K
scores = Q @ K.transpose(-2, -1)  # [32, 512, 512]

# Problem: Missing batch dimension
x = torch.randn(512, 768)  # Missing batch dimension
W = torch.randn(768, 3072)

# Add batch dimension
x = x.unsqueeze(0)  # [1, 512, 768]
output = x @ W      # [1, 512, 3072]

# Problem: Broadcasting confusion
x = torch.randn(32, 512, 768)
bias = torch.randn(768)

# This works due to broadcasting
output = x + bias  # bias broadcasts to [32, 512, 768]

# Explicit broadcasting (clearer)
output = x + bias.view(1, 1, 768)

BERT-base: A Canonical Worked Analysis

BERT-base has become the standard baseline configuration for transformer analysis. Its dimensions are adopted throughout this textbook as a running example for parameter counts, memory estimates, and computational costs. This section provides a self-contained reference; subsequent chapters cite these results rather than re-derive them.

Architecture Specification

Unless stated otherwise, worked examples use batch size $B = 32$ and full sequence length $n = 512$.

Parameter Count

Per encoder layer. Each layer has three components:

The feed-forward network contains approximately twice as many parameters as the attention mechanism ($4.7$M vs $2.4$M), despite attention being conceptually more complex. This is because the $4\times$ expansion to $d_{ff}$ creates two large weight matrices.

Complete model:

Embeddings account for $\sim$21\% of total parameters ($23$M out of $110$M), while the transformer layers account for $\sim$78\%. This ratio shifts with vocabulary size---a 50K-token vocabulary would push embeddings to 35\% of total parameters.

Dimension Tracking Through One Layer

Input: $\mX \in \R^{32 \times 512 \times 768}$ (batch $\times$ sequence $\times$ model dimension)

Multi-Head Attention:

Feed-Forward Network:

Activation Memory

Intermediate activations stored for backpropagation dominate training memory:

The attention scores alone ($B \times h \times n^2 \times 4$ bytes $= 402$~MB per layer) account for 57\% of per-layer activation memory, illustrating the quadratic cost of self-attention. Doubling the sequence length to $n = 1024$ would quadruple the attention memory to 1.6~GB per layer.

FLOPs Analysis

Counting each multiply-accumulate as 2 FLOPs:

Self-Attention (per layer):

Feed-Forward Network (per layer):

Totals:

The FFN accounts for 60\% of per-layer FLOPs, while the attention score computations ($\mQ\mK\transpose$ and $\mA\mV$) contribute only 10\%. For short sequences, optimizing FFN yields the largest gains; for long sequences, attention's $O(n^2)$ term becomes dominant.

Training Memory Budget

Activations dominate at $\sim$87\% of total memory, motivating gradient checkpointing (recompute activations during the backward pass, trading 20--30\% slower training for 50--70\% memory reduction). This is why training BERT-base requires GPUs with at least 16~GB of memory.

Hardware Timing (NVIDIA A100)

The A100 provides 312~TFLOPS FP16 with Tensor Cores and 1.6~TB/s memory bandwidth. At 70\% utilization:

Memory bandwidth check: Loading 110M parameters ($\times$ 4 bytes $= 440$~MB) takes $440/1600 \approx 0.28$~ms, comparable to compute time. For small batch sizes, BERT-base becomes memory-bandwidth bound rather than compute-bound; larger batches amortize parameter loading across more computation.

Exercises

Solutions

Full solutions for all exercises are available at \url{https://deeplearning.hofkensvermeulen.be}.