Singular Value Decomposition

Unitary matrices and the Singular Value Decomposition (SVD) are two important concepts in linear algebra. In order to fully understand these concepts, we will need to first discuss orthogonality. Most materials are convered in Advanced Linear Algebra: Foundations to Frontiers taught by professor Robert van de Geijn. This is a brief summary over the important concepts covered in Chapter 2.

Components in the direction of a vector

By Pythagorean theorem, we know that \(b = \chi a + c\) where \(a\) is a unit vector orthogonal to \(c\) and \(\chi\) is a scaler. Then we have

\[a^T (b-\chi a) = 0\]

Solving it gives us \(\chi = \frac{a^T b}{a^T a}\). We have \(\frac{a^T b}{a^T a}a = \frac{a a^T}{a^T a}b\). And \(\frac{a a^T}{a^T a}\) can map vector \(b\) in the direction of \(a\). The orthogonal component of \(a\) can thus be calculated as \(I-\frac{a a^T}{a^T a}\).

The linear transformation can be simplified by letting \(\left\lVert a\right\rVert_{2}=1\) because this will render \(a^T a = 1\).

Unitary Matrix

A matrix \(U\) is said to unitary matrix is if \(U\) is a square matrix and satifies \(U^H U= I\).

In addition, unitary matrix has some nice properties. First, the product of a sequence of unitary matrix is also unitary matrix. This can be proven by first explore the product of \((U_0 U_1)^H (U_0 U_1)= I\), showing \(U_0 U_1\) is a unitary matrix, and then perform induction.

Unitary matrix also preserves length. This is done by showing \(\left\lVert Ux \right\rVert _2^2 = (Ux)^H (Ux) = x^H x= \left\lVert x \right\rVert _2^2\).

Change of orthonormal basis

We mentioned we can map a vector \(x\) another vector in the same direction as vector \(a\). Now we extend it to express a vector \(x\) using a set of orthonormal basis \(U\).

We know that \(x = Ix= UU^Tx=U(U^Tx)=u_0^Hxu_0+…+u_{m-1}^Hxu_{m-1}\). We notice that \(u_0^Hx\) is a scalor so we can write then equation as \(U(U^Tx)=a_0u_0+…+a_{m-1}u_{m-1}\). We successfully expressed the vector \(x\) based on the orthonormal basis.

TODO


Author | Edward Hu

Currently a student in University of Texas at Austin and conducting heterogeneous computing research.