Singular Value Decomposition: Image Compression

Singular value decomposition (SVD) is a matrix factorisation technique. It is a method to factorise any given m \times n matrix into 3 components, 2 rotation matricies U and V and a scale matrix D. Formally

    \[ A = UDV^T \]

  • U is the left-singular matrix (m \times m)
  • V is the right-singular matrix (n \times n)
  • D is the diagonal matrix consisting of the the leading singular values (m \times n) i.e. that square root of the eigenvalues of AA^T

There are a tonne of applications of SVD from principle components analysis to recommender systems. You can read about more applications on the wiki page . A common application is image compression. Here we’ll demonstrate this with a simple example.

Firstly we need an image to compres. I’ll choose Brent Hinds from Mastodon. Why? Mostly because Mastodon is the greatest metal band there is.

plot of chunk unnamed-chunk-1

 

For ease of computation the image will be converted to greyscale, that way we only have to deal with one matrix rather than 3. Using the svd() function the matrix interpretation of the image will be decomposed into the 3 component matricies. The image is then recreated by reducing the size of the component matrices by selecting a user defined number of leading singular values. The higher the number of singular values selected the more accurate the recreated image will be.

plot of chunk unnamed-chunk-2

 

Even with only using the first 5 leading singular values the image can be interpreted, although very blurry. At k>50 the image is very clearly reconstructed. By taking a set of leadiing singular values the full information contained in the image is being summarised by the subset. The higher the value of k, the more accurate the image is reconstructed. This is a pretty simple example using the built-in SVD function in R, but a neat one. There is a lot of detailed explanations on the web about SVD, but sometimes you just want to see it in action. In later posts I’ll look at other applications of SVD such as principle components analysis and recommender systems via gradient descent from scratch.

Follow me on social media: