Using the Singular Value Decomposition for Image Compression
In this project, you’ll explore an application of a certain matrix decomposition, called the singular value
decomposition (SVD), to image compression. We will learn about the singular value decomposition later in
the course, but for now, you should know the main result:
Theorem 1. Any m × n matrix can be factored as A = UΣV
T
where U is an m × m orthogonal matrix, V
is an n × n orthogonal matrix, and Σ is an m × n matrix with entries σ
1
≥ σ
2
≥ · · · ≥ σ
r
down the main
diagonal and zeros elsewhere.
The r in the theorem is the rank of the matrix A
T
A. An orthogonal matrix is simply a matrix with
mutually orthogonal columns. Orthogonal matrices have the property that their inverses equal their
transposes. So we could equivalently write V
−1
in place of V
T
, though V
T
is generally used because it is
generally much easier to transpose a matrix than invert it. If the columns of U are called u
1
, u
2
, . . . , u
m
and
the columns of V are called v
1
, v
2
, . . . , v
n
, the theorem has equivalent statement that every matrix A can be
written
A = σ
1
u
1
v
T
1
+ σ
2
u
2
v
T
2
+ · · · + σ
r
u
r
v
T
r
.
This is the form of the SVD which is used in image compression. Image compression might be useful if you
have an image to transfer electronically, say over the internet or from a satellite transmission. Perhaps it is
possible to not transmit all of the data, but still transmit enough of it so that the essential information is
there and the image can be reconstructed sufficently on the receiving end. The SVD accomplishes this. The
idea is that since the σ
i
are ordered from large to small, we can get a good approximation to A by throwing
out the terms toward the end of the expansion
A = σ
1
u
1
v
T
1
+ σ
2
u
2
v
T
2
+ · · · + σ
r
u
r
v
T
r
.
The terms at the end of the expansion will likely be very small so we will not lose much information by
discarding them.
But why would you want to lose any information at all? Isn’t it preferable to use A instead of an
approximation to A? The issue is a practical one. In the context of image compression, A represents our
image file, which could be quite large. Instead of storing A, we can instead store only u
1
, u
2
, . . . , u
k
,
v
1
, v
2
, . . . , v
k
, and σ
1
, σ
2
, . . . , σ
k
. Then we can construct the approximation
A
k
= σ
1
u
1
v
T
1
+ σ
2
u
2
v
T
2
+ · · · + σ
k
u
k
v
T
k
from these. If k is small enough, this could mean less data storage.
If k is large enough so that A
k
is sufficiently close to A, then this compression procedure will give an
acceptable approximation to A with less data storage requirements.
1) Suppose A is an m × n matrix. To store all of A, we would have to store mn entries. How many entries
would we need to store if we used the approximation A
k
instead?
2) This technique only makes sense as an image compression tool if we have less to store by computing A
k
than we would if we just stored all of A. Otherwise, there would be absolutely no purpose in storing the
same amount of data or more to have an imperfect approximation to A instead of the real thing. Find a
condition on k (depending on n and m) so that the storage needs for the approximation A
k
are less than
the storage needs for A.
Now, it’s time to explore this image compression technique in practice. Is the condition given in problem 2
too prohibitive to be useful, or can you actually get a good approximation A
k
when you choose a k that
respects your bound? To answer this question, find an image, in color, that you want to work with. You’ll
have to import it into MATLAB to work with it. MATLAB will interpret your image as a giant matrix
where each pixel is a matrix entry. Actually, MATLAB will interpret your image as 3 giant matrices that
are layered on top of one another. One layer is for the red component of each pixel, the others for the green