How can we use the Singular Value Decomposition (SVD) for image compression?

[matqkks]

What is the best way of introducing singular value decomposition (SVD) on a linear algebra course? Why is it so important? Are there any applications which have a real impact?

 

[Robert1986]

Well, there are a lot of reasons the SVD is useful. One theoretical reason is the the singular values are the square roots of the eigenvalues of A^\top A and the number of non-zero singular values is equal to the rank of the matrix. So, the SVD provides a kind of connection between eigenvalues and rank - though not a direct connection. But, in addition to this, the SVD is just another way to decompose a matrix, and being able to decompose a matrix in several different ways usually makes proving things easier.

Two interesting applications of the SVD stand out to me (there are many more, but for some reason, these two are prominent in my mind right now.) You can describe bases for the image and null space of a matrix using the SVD and prove the fundamental theorem of linear algebra. Also, there is the concept of a pseudo inverse that is calculated from the SVD (there is a wikipedia article explaining this, or if you have the book Matrix Analysis or probably lots of other books there is an explanation.)

 

[Stephen Tashi]

If you think of a table of data for a function F(x,y) of two variables, a very simple data table is one with a pattern such as

Table For F(X,Y)

____________X_________
-------__01__02__03__04
-------------------------------
__01___02__09__11__10
Y_02___ 08__36__44__40
__03___14__63__77__70

because we can find row and column entries such that each table entry is the product of its associated row and column entry. For example above, the entries are:

___________A________
------__02__09__11__10
-------------------------------
__1___02__09__11__10
B_4___ 08__36__44__40
__7___14__63__77__70


An arbitrary function F(x,y) may not have a data table that is so simple. However, the data table for an arbitrary function can be written as a linear combination of such simple data tables. That's one way to look at the SVD.

This way of looking at things reveals how the SVD can be used as a simple method of image compression. If F(X,Y) is data for an image, we an approximate F(X,Y) by expressing F(X,Y) as a linear combination of simple data tables and then omit the tables which have small coefficients from the linear combination.