A matrix of size m × n is a grid of real numbers consisting of m rows and n columns. In linear algebra, a branch of mathematics, matrices of size m × n describe linear mappings from n-dimensional to m-dimensional space. The word linear roughly means that straight lines map to straight lines and the origin in n‑dimensional space maps to the origin in m‑dimensional space. When we have an (m × n)‑matrix A and a (n × k)‑matrix B, we can compute the product AB which is an (m × k)‑matrix. The mapping corresponding to AB is exactly the composition of the mappings corresponding to A and B respectively.
Singular Value Decomposition (SVD) states that every (m × n)‑matrix A can be written as a product
where U and V are orthogonal matrices and the the matrix Σ consists of descending non-negative values on its diagonal and zeros elsewhere. The entries σ1 ≥ σ2 ≥ σ3 ≥ … ≥ 0 on the diagonal of Σ are called the singular values (SVs) of A. Geometrically, Σ maps the j‑th unit coordinate vector of n‑dimensional space to the j‑th coordinate vector of m‑dimensional space, scaled by the factor σj. Orthogonality of U and V means that they correspond to rotations (possibly followed by a reflection) of m‑dimensional and n‑dimensional space respectively. Therefore only Σ changes the length of vectors.
We can decompose a given image into the three color channels red, green and blue. Each channel can be represented as a (m × n)‑matrix with values ranging from 0 to 255. We will now compress the matrix A representing one of the channels.
To do this, we compute an approximation to the matrix A that takes only a fraction of the space to store. Now here's the great thing about SVD: the data in the matrices U, Σ and V is sorted by how much it contributes to the matrix A in the product. That enables us to get quite a good approximation by simply using only the most important parts of the matrices.
We now choose a number k of singular values that we are going to use for the approximation. The higher this number, the better the quality of the approximation gets but also the more data is needed to encode it. We now take only the first k columns of U and V and the upper left (k × k)-square of Σ, containing the k largest (and therefore most important) singular values. We then have
The amount of data needed to store this approximation is proportional to the colored area:
compressed size = m × k + k + k × n = k × (1 + m + n)
(Actually, slightly less space is needed due to the orthogonality of U and V.) One can prove that this approximation is optimal in a certain sense.
This demo lets you choose the number of singular values k and see how this choice affects the quality of the approximation and the compression rate. Notice how for all photographs, the graph showing the singular values looks like a hyperbola: there are only a few really large SVs and a long tail of relatively smaller SVs. In contrast, for the random noise image the graph of SVs looks roughly linear.
SVD is routinely used in statistics for principal component analysis and in numerical simulations for reducing the order of models. For image compression, more sophisticated methods like JPG that take human perception into account generally outperform compression using SVD.
The computation of the SVD is performed on the client-side using WebAssembly. We use the algorithm implemented by the Rust library nalgebra. The SVDs of all three color channels are computed in parallel using one web worker for every channel. To provide the quick preview, we use a randomized algorithm to compute an approximate truncated SVD with 50 singular values. The user interface uses React, react-slick and noUiSlider. Thanks to the creators of all these great projects!
Built by Tim Baumann. Fork this project on GitHub.