Everything about matrix factorizations

Matrix factorizations are the pinnacle results of linear algebra.

From theory to applications, they are behind many theorems, algorithms, methods. However, it is easy to get lost in the vast jungle of decompositions.

This post is about how to make sense of them! We are going to study three matrix factorizations:

1. the LU decomposition,
2. the QR decomposition,
3. and the Singular Value Decomposition (SVD).

First, we'll take a look at LU.

The LU decomposition

Let's start at the very beginning: linear equation systems. Linear equations are surprisingly effective in modeling real-life phenomena: economic processes, biochemical systems, etc.

To simplify the notation, we can represent linear equations in a matrix form:

$$Ax = b, \quad A \in \mathbb{R}^{n \times n}, \quad b \in \mathbb{R}^n.$$

$\textstyle A$ holds the coefficients, $\textstyle x$ holds the solution. How can we solve such an equation?

By multiplying the equations with scalars and subtracting them from each other, we can (usually) transform the system into an upper triangular form. This is called Gaussian elimination.

This resulting system is easy to solve: solve the last equation, then move up progressively. As it turns out, Gaussian elimination is equivalent to multiplying $\textstyle A$ by a lower diagonal matrix!

This gives the famous LU decomposition, factoring $\textstyle A$ into the product of a lower and an upper diagonal matrix.

Thus, LU is the same as solving a linear equation. The LU decomposition can be performed whenever Gaussian elimination can, and it is vital in many applications, for instance, computing determinants or inverting matrices.

The QR decomposition

There are more than one ways to think about matrices. Previously, we viewed them as linear equations, but we can think about them as a horizontal stack of column vectors.

We can put these column vectors into the Gram-Schmidt orthogonalization process, yielding a set of orthonormal vectors that span the same space.

Just like Gaussian elimination, the Gram-Schmidt process can also be "vectorized", allowing us to use the resulting orthonormal system to factorize $\textstyle A$ into the product of an orthogonal and an upper diagonal matrix.

Voila! This is the gist of QR decomposition. Again, there are tons of applications, but the most significant one is the famous QR algorithm, using the QR decomposition to find the eigenvalues and the eigenvectors of arbitrary matrices.

The Singular Value Decomposition

The Singular Value Decomposition (or SVD in short) is undoubtedly one of the pinnacle results of linear algebra, omnipresent in computer science and machine learning. For instance, the famous PCA algorithm is a version of SVD.

To understand the SVD, we should view matrices as linear transformations. In essence, a linear transformation is a distortion of the underlying vector space, as illustrated below.

Although linear transformations can be complex, they are built from a few basic building blocks: rotations, reflections, stretchings. A combination of rotations + reflections corresponds to a matrix whose columns are orthogonal. Stretchings correspond to diagonal matrices.

On the level of transformations, SVD says that every transformation is a composition of

1. a rotations + reflections combo,
2. a stretching,
3. and a final rotations + reflections combo,

in that order.

Translating it to the language of matrices, we obtain the factorization of $\textstyle A$ into orthogonal and diagonal matrices. This is an extremely strong result. Like the prime factorization theorem of integers, just for matrices. (SVD works for non-square matrices as well.)

SVD is everywhere in linear algebra. For instance, we can

1. generalize the notion of the inverse matrix to non-square matrices,
2. reduce the dimensionality of data,
3. approximate matrices with low-rank ones,

and many more.