Truncated SVD and LoRA for Neural Network Compression

Welcome to the third lesson in our module on matrix decompositions. In our previous sessions, we derived the Singular Value Decomposition (SVD) and used it to analyze the fundamental properties of a matrix, such as its rank, the geometry of its four fundamental subspaces, and its numerical stability via the condition number. We ended with the tantalizing idea of "effective rank," suggesting that many large matrices are, in essence, simpler than they appear.

Today, we will formalize this notion by exploring low-rank approximation using truncated SVD. You will learn how to construct the best possible low-rank approximation of a matrix and understand the theorem that guarantees its optimality. We'll then discuss principled methods for choosing the approximation rank. Finally, we will connect this classical linear algebra technique directly to the forefront of modern deep learning by examining Low-Rank Adaptation (LoRA), a parameter-efficient method for fine-tuning large models.

The "Why" and "How" of Low-Rank Approximation

The core idea behind low-rank approximation is that the essential information in many high-dimensional datasets and transformations is concentrated in a lower-dimensional structure. A matrix of rank $k$ can be fully described by $k$ linearly independent rows or columns. If a large $m \times n$ matrix $A$ can be well-approximated by a rank- $k$ matrix, where $k ≪ m, n$ , we can achieve significant benefits.

The following notes from a Stanford CS course provide excellent motivation for why we pursue low-rank approximations.

The Singular Value Decomposition (SVD) and Low-Rank ...

These notes introduce the concept and provide clear motivations for its use.

Please read the section titled "Low-Rank Matrix Approximations: Motivation" (page 3). Pay attention to the three primary reasons discussed: data compression, de-noising, and the application to fine-tuning large machine learning models, which explicitly mentions LoRA.

The motivation is compelling, but how do we find the "best" low-rank approximation? The SVD provides a direct and elegant answer. Recall that the SVD can be written as a sum of rank-one matrices:

A = i = 1 \sum r σ_{i} u_{i} v_{i}^{T}

where $r$ is the rank of $A$ , and the singular values are ordered $σ_{1} \geq σ_{2} \geq \dots \geq σ_{r} > 0$ . Since the largest singular values correspond to the most significant components of the matrix, a natural strategy for approximation is to simply discard the terms associated with small singular values.

This leads to the truncated SVD. To get a rank- $k$ approximation $A_{k}$ , we keep only the first $k$ terms of the sum:

A_{k} = i = 1 \sum k σ_{i} u_{i} v_{i}^{T}

In matrix form, this is equivalent to truncating the SVD matrices themselves: $A_{k} = U_{k} Σ_{k} V_{k}^{T}$ , where $U_{k}$ is $m \times k$ , $Σ_{k}$ is $k \times k$ , and $V_{k}^{T}$ is $k \times n$ .

This diagram illustrates the process of truncating the SVD. We select a cutoff rank 'k', keeping the top k singular values and their corresponding singular vectors. This results in the approximation $A_k = U_k \Sigma_k V_k^T$.

This isn't just an intuitive heuristic; it's provably the best possible rank- $k$ approximation. The Eckart-Young-Mirsky theorem states that for a given rank $k$ , the matrix $A_{k}$ constructed from the truncated SVD is the closest rank- $k$ matrix to $A$ . The "closeness" is measured by matrix norms, such as the Frobenius norm ( $∥ A - A_{k} ∥_{F}$ ) or the spectral norm.

The following reading formalizes this construction and states the optimality theorem.

The Singular Value Decomposition (SVD) and Low-Rank ...

This text provides a clear walkthrough of the SVD-based construction and its optimality.

First, quickly review the definition of SVD and its representation as a sum of rank-1 matrices in the section "Definitions" (page 4-5). This reinforces the structure we will truncate. Then, read the section "Low-Rank Approximations from the SVD" (page 6-7). This section details the construction of A_k and explicitly states its optimality in Fact 5.1, which is the Eckart-Young theorem.

Why It Works: Energy Concentration

The reason truncated SVD is so effective lies in how the singular value spectrum of real-world data often behaves. A small number of components tend to capture a disproportionately large amount of the total variance or "energy" of the matrix. The energy of a matrix is proportional to the sum of its squared singular values, $\sum σ_{i}^{2}$ .

The left plot shows a typical singular value spectrum, with a steep drop-off separating a few large "signal" singular values from a long tail of small "noise" values. The right plot shows the cumulative energy, demonstrating that a small number of components (e.g., k=5 or k=21) can capture the vast majority (e.g., 90% or 99%) of the matrix's total energy.

This concentration of energy means we can discard a large number of singular values (and their corresponding vectors) while losing very little of the information that defines the matrix's structure. This is the essence of lossy compression and de-noising.

Choosing the Optimal Rank $k$

The most critical practical question is: how do we choose the truncation rank $k$ ? A naive approach might be to plot the singular values (a "scree plot") and look for an "elbow" where the values drop off, or to set $k$ such that we retain a certain percentage (e.g., 99%) of the total energy. These are useful heuristics, but we can do better.

A more rigorous approach, developed by Matan Gavish and David Donoho, frames the problem as separating a low-rank signal from random noise. By understanding the distribution of singular values of a pure noise matrix, we can set an optimal hard threshold that provably de-noises the data.

The following video provides an excellent explanation of this advanced technique. Given your background, you'll appreciate the shift from simple heuristics to a method grounded in random matrix theory.

SVD and Optimal Truncation

This video from Steve Brunton introduces and explains the Gavish-Donoho optimal truncation method.

First, watch the introduction which frames the problem and discusses the common heuristic methods, which the presenter rightly notes can be unreliable. Next, watch the segment that explains the core idea. The key insight is to define a "noise floor" based on the singular value spectrum of a random Gaussian matrix and truncate everything that falls below it. Finally, watch the discussion of two practical cases. The second case—an unknown noise level in a rectangular matrix—is particularly powerful. It shows how the median singular value can be used to estimate the noise variance and thus determine the optimal threshold, even when the noise level is unknown.

Application in Deep Learning: Low-Rank Adaptation (LoRA)

Now we arrive at the connection to your goal of implementing key papers. Low-rank approximation isn't just a tool for data compression; it's the engine behind one of the most popular techniques for efficiently fine-tuning massive pre-trained models like GPT-3: Low-Rank Adaptation (LoRA).

The challenge of fine-tuning a model with billions of parameters is immense. Storing and training a full copy of the model for each downstream task is prohibitively expensive. The LoRA paper hypothesizes that the change in the weight matrix during fine-tuning, $Δ W$ , has a low "intrinsic rank." That is, the adaptation can be captured by a low-rank update.

Instead of learning a dense $Δ W$ , LoRA freezes the original pre-trained weights $W_{0}$ and injects a trainable low-rank decomposition into the model. Specifically, it represents the update as the product of two much smaller matrices, $B$ and $A$ , such that $Δ W = B A$ .

For a layer with forward pass $h = W_{0} x$ , the adapted forward pass becomes:

h = (W_{0} + Δ W) x = (W_{0} + B A) x = W_{0} x + (B A) x

Here, if $W_{0}$ is $d \times d$ , we choose $B$ to be $d \times r$ and $A$ to be $r \times d$ , where the rank $r$ is very small (e.g., 4, 8, or 16). We only train the parameters of $B$ and $A$ , dramatically reducing the number of trainable parameters from $d^{2}$ to $2 d r$ .

The following video provides a superb visual and code-based explanation of LoRA.

LoRA: Low-Rank Adaptation of Large Language Models - Explained visually + PyTorch code from scratch

This video by Umar Jamil gives a clear, from-scratch explanation of LoRA, including its motivation and connection to SVD.

First, watch the section explaining the problem LoRA solves. This will set the context by highlighting the computational and storage burdens of full fine-tuning. Next, see how LoRA works mechanically in the segment from how LoRA works. Pay close attention to the diagram showing the frozen weights W and the parallel, trainable branch with matrices B and A. Finally, watch the crucial section that explains the low-rank hypothesis. This part connects directly back to our lesson, explaining that LoRA's effectiveness relies on the idea that the weight update matrix is rank-deficient. The video even uses a simple SVD example to demonstrate the concept, perfectly tying everything together.

This application is a beautiful example of a classical numerical linear algebra concept being applied to solve a cutting-edge problem in deep learning. The intuition that large matrices can be represented by simpler, lower-rank structures is the common thread that runs from data compression to efficient model adaptation.

Conclusion

In this lesson, we have formalized the concept of low-rank approximation and seen its power and elegance.

Key Takeaways:

The truncated SVD, $A_{k} = U_{k} Σ_{k} V_{k}^{T}$ , is constructed by keeping the top $k$ singular values and vectors.
The Eckart-Young-Mirsky theorem guarantees that this is the optimal rank- $k$ approximation for a matrix in terms of Frobenius and spectral norms.
The effectiveness of this approximation stems from the fact that the "energy" or "information" in many matrices is concentrated in their first few singular components.
The choice of rank $k$ can be made systematically by separating signal from noise, for which methods like Gavish-Donoho provide a principled approach beyond simple heuristics.
LoRA directly applies this principle to deep learning, by modeling the update to a weight matrix, $Δ W$ , as a low-rank matrix $B A$ , enabling dramatic savings in trainable parameters during fine-tuning.

In our next lesson, we will turn our attention to another fundamental decomposition: eigendecomposition. While SVD is a general tool for any matrix, eigendecomposition applies to square matrices and reveals a different set of geometric properties related to invariant directions. This will be foundational for understanding concepts like the curvature of loss landscapes via the Hessian matrix and Principal Component Analysis (PCA).

Recommended resources

The "Why" and "How" of Low-Rank Approximation

Why It Works: Energy Concentration

Choosing the Optimal Rank k

Application in Deep Learning: Low-Rank Adaptation (LoRA)

Conclusion

Choosing the Optimal Rank $k$