15  The singular-value decomposition

The singular-value decomposition gives orthogonal matrix expansions and low-rank approximations, including image compression.

The SVD is a powerful linear algebra tool. In quantum chemistry it is used to compress electron-repulsion integrals, for example.

In this small exercise, we demonstrate its power applied to image compression. For this exercise, a good grayscale image is handy. You can find a nice picture of a parrot in Figure 15.1.

Recall first the Hilbert–Schmidt inner product on the set \(M(n,m,\mathbb{F})\) of matrices: \[\left\langle X,Y\right\rangle_\text{HS} = \operatorname{Tr}(X^H Y)\] The trace \(\operatorname{Tr}(A)\) is the sum of the diagonal elements of \(A\).

Recall also the SVD: For \(A \in M(n,m,\mathbb{F})\) and \(k = \min(n,m)\), there are unitary matrices \(U \in M(n)\) and \(V\in M(m)\) and singular values \(\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_k\geq0\) such that

\[ A = U \Sigma V^H = \sum_{i=1}^k \mathbf{u}_i \sigma_i \mathbf{v}_i^H. \]

Here \(\Sigma \in M(n,m,\mathbb{R})\) has the singular values in its upper \(k\times k\) diagonal block and zeros elsewhere. Removing unused columns gives the economical SVD

\[ A=U_{:,:k}\Sigma_{:k,:k}V_{:,:k}^H. \]

Figure 15.1: A parrot

Exercises

Exercise 15.1  

  1. How is the Hilbert–Schmidt inner product related to the Euclidean inner product and the standard Euclidean vector space?

  2. Show that \(\operatorname{Tr}(ABC) = \operatorname{Tr}(CAB)\) (cyclic invariance).

  3. Let \(\mathbf{u}_i\) and \(\mathbf{v}_i\) be the left and right singular vectors of a matrix \(A\). Show that the matrices \(X^{ij} = \mathbf{u}_i\mathbf{v}_j^H\) form an orthonormal set in the Hilbert–Schmidt inner product.

  4. Conclude that the SVD is an expansion of a matrix in an orthonormal basis.

The truncated SVD

\[ A^{(m)} = \sum_{i=1}^m \mathbf{u}_i \sigma_i \mathbf{v}_i^H \]

is the best approximation to \(A\) of rank at most \(m\) in the Hilbert–Schmidt norm:

\[ A^{(m)} = \mathop{\mathrm{arg\,min}}_{\operatorname{rank}(B)\leq m} \|B-A\|_{\text{HS}}. \]

  1. Write a Python program/notebook that reads an image file and converts it to a matrix \(A \in M(n,m,\mathbb{R})\). The module imageio can be useful.

  2. Continue writing the program, so it computes the truncated and full SVD of \(A\). You can use, say, scipy.linalg.svd to find the full SVD.

  3. Plot the singular values. Discuss.

  4. Show that the error in the Hilbert–Schmidt norm is \[\| A^{(m)} - A\|_\text{HS} = \sqrt{\sum_{i={m+1}}^k \sigma_i^2}.\]

  5. Make visualizations of the truncated SVD of the image \(A\), with various \(m\). Compute the relative error \(\| A^{(m)} - A\|_\text{HS} / \|A\|_\text{HS}\) for each \(m\) you consider. Discuss the image quality.