Matrix values increasing after SVD, singular value decomposition

Question

I am trying to learn SVD for image processing... like compression.

My approach: get image as BufferedImage using ImageIO... get RGB values and use them to get the equivalent grayscale value (which lies within 0-255) and store it in a double[][] array. And use that array in SVD to compress it.

I am getting my USV matrices correctly... hope so. I get from U from AATranspose (AAT), and V from ATA.

Let me give an example

A is my original matrix.

A = 7.0     3.0     2.0
    9.0     7.0     5.0
    9.0     8.0     7.0
    5.0     3.0     6.0

U = -0.34598    -0.65267    -0.59969    -0.30771
    -0.57482    -0.27634     0.26045     0.72484
    -0.64327     0.21214     0.44200    -0.58808
    -0.36889     0.67280    -0.61415     0.18463

S = 21.57942    0.00000    0.00000
     0.00000    3.35324    0.00000
     0.00000    0.00000    2.02097
     0.00000    0.00000    0.00000

VT = -0.70573    -0.52432    -0.47649
     -0.53158    -0.05275     0.84536
     -0.46838     0.84989    -0.24149

So now I have to do outer product expansion, leaving out a few terms for compression. Lets call the truncated terms k.

When I let k = 1, and do outer product expansion with the singular values, this is what I get as my new matrix

B = 6.43235    4.03003    1.70732
    9.24653    6.55266    5.12711
    9.41838    7.24083    7.21571
    4.41866    4.05485    5.70027

As you can see, some values in B (which I think should be my final matrix after SVD) are greater than my original matrix.

A is just a test matrix. I would later try to compress a grayscale image, and there the values have to be 0-255. Anything > 255 wouldn't help me.

Where am I going wrong?

EDIT: k is the number of terms which I would be truncating. So when I say k = 1, the matrix I would be reconstructing would be:

A = u1 * S11 * vt1 + u2 * S22 + vt2

here u1 and u2 are column 1 and 2 of U, and vt1 and vt2 are row 1 and 2 of V.

TayTay TayTay · Accepted Answer · 2015-10-12T20:12:09

I actually asked a question like this very recently on Kaggle. Hopefully it will be relevant to your computer vision question... One thing I don't understand, though, is how you're reconstructing A' after the truncation of S. From my understanding, when your k=1, the truncated diagonal matrix will look like this:

21.57942    0.00000    0.00000
0.00000     0.00000    0.00000
0.00000     0.00000    0.00000
0.00000     0.00000    0.00000

And A', the approximation of what A may be without the more errant, low-energy singular values, can be reconstructed via A' = US'Vt. Here's my result for A':

5.268951 3.914582 3.557461
8.753958 6.503777 5.910449
9.796523 7.278353 6.614362
5.617932 4.173858 3.793084

Why there are some values that are higher than the original A matrix makes sense when you consider that both U and Vt have negative values that are now being zeroed-out when you multiply by the new S matrix.

Edit with an additional resource: check this question out as well.

Matrix values increasing after SVD, singular value decomposition

1 Answers