Back

Image Compression Demo

Original Image

Compressed Image

Singular Values: ALL

How does it work?

Every image can be represented as a matrix of pixels. For example, a greyscale image can be represented as a matrix of values between 0 and 255, where 0 represents a black pixel and 255 represents a white pixel. If the image is colored, then it can be represented by 3 matrices, one for each color channel (red, green, and blue).

For simplicity, let \(A\) be an \(m \times n\) matrix of rank \(r\) that represents a greyscale image. Using singular value decomposition, we can decompose \(A\) into the product of three matrices:

\(A = U \Sigma V^T\)

where \(U\) is an \(m \times r\) orthonormal matrix, \(\Sigma\) is an \(r \times r\) diagonal matrix, and \(V\) is an \(n \times r\) orthonormal matrix. The diagonal entries of \(\Sigma\) are called the singular values of \(A\). The singular values are ordered from largest to smallest.

We can approximate \(A\) by truncating the singular value decomposition to only include the \(k\) largest singular values:

\(A \approx U_k \Sigma_k V_k^T\)

where \(U_k\) is an \(m \times k\) orthonormal matrix, \(\Sigma_k\) is an \(k \times k\) diagonal matrix, and \(V_k\) is an \(n \times k\) orthonormal matrix. The diagonal entries of \(\Sigma_k\) are the \(k\) largest singular values of \(A\).

According to the Eckart-Young-Mirsky theorem, the truncated singular value decomposition is the best rank-\(k\) approximation of \(A\) in terms of the Frobenius norm.

Storage Space

Since the singular values are ordered from largest to smallest, the approximation will be better as \(k\) increases. However, the approximation will also require more storage space as \(k\) increases.

For example, if we have an \(m \times n\) matrix of rank \(r\), then the original matrix requires \(mn\) values to store. However, we can store the truncated singular value decomposition using \(k(m + n + 1)\) values. This is because we need \(k\) values to store the singular values, \(km\) values to store the entries of \(U_k\), and \(kn\) values to store the entries of \(V_k\).

Therefore, we can compress the image by storing the truncated singular value decomposition instead of the original matrix.