3
$\begingroup$

We start with an $m \times n$ matrix before SVD. After SVD, we have three matrices of sizes, $m \times m$, $n \times n$ and $m \times n$. How do we save space then if now we have three matrices instead of one and more numbers to store? Why are we talking here about dimensionality reduction? What are then the benefits of SVD?

$\endgroup$
  • 6
    $\begingroup$ SVD is not about saving space but decomposition of matrix into matrices which have desirable properties like unitarity and orthonormality. It turns out you can use SVD to do dimension reduction of the data (not saving space but reducing the dimensionality) by discarding the singular values below some defined threshold. $\endgroup$ – Pankaj Daga Oct 12 '16 at 6:33
  • 2
    $\begingroup$ Low-rank approximation $\endgroup$ – Rodrigo de Azevedo Oct 12 '16 at 8:20
  • 2
    $\begingroup$ I think you are possibly confusing dimension here with the amount of storage space in your computer. $\endgroup$ – mdewey Oct 12 '16 at 8:47
  • $\begingroup$ Suppose m x n(the total number of pixels) is fixed, and also number of singular values are fixed. What dimensions should your image have to save the most space from compression? $\endgroup$ – Simpleprint Nov 20 '16 at 14:00
  • 1
    $\begingroup$ See also What is the intuition behind SVD? $\endgroup$ – amoeba says Reinstate Monica Nov 20 '16 at 18:16
5
$\begingroup$

For example, here's a $512 \times 512$ B&W image of Lena:

Lena

We compute the SVD of Lena. Choosing the singular values above $1\%$ of the maximum singular value, we are left with just $53$ singular values. Reconstructing Lena with these singular values and the corresponding (left and right) singular vectors, we obtain a low-rank approximation of Lena:

enter image description here

Instead of storing $512^2$ values (each taking $8$ bits), we can store $2 \cdot (512 \cdot 53) + 53 = 54325$ values, which is approximately $20\%$ of the original size. This is one example of how SVD can be used to do lossy compression.


Here's the MATLAB code:

% open Lena image and convert from uint8 to double
Lena = double(imread('LenaBW.bmp'));

% perform SVD on Lena
[U,S,V] = svd(Lena);

% extract singular values
singvals = diag(S);

% find out where to truncate the U, S, V matrices
indices = find(singvals >= 0.01 * singvals(1));

% reduce SVD matrices
U_red = U(:,indices);
S_red = S(indices,indices);
V_red = V(:,indices);

% construct low-rank approximation of Lena
Lena_red = U_red * S_red * V_red';

% print results to command window
r = num2str(length(indices));
m = num2str(length(singvals));
disp(['Low-rank approximation used ',r,' of ',m,' singular values']);

% save reduced Lena
imwrite(uint8(Lena_red),'Reduced Lena.bmp');
$\endgroup$
  • $\begingroup$ How exactly do you get $2⋅(512⋅53)+53$ ? $\endgroup$ – Tejas Ramdas Nov 4 '16 at 11:48
  • $\begingroup$ Okay, $(512⋅53)$ each for $U$ and $V$ and another $53$ for $S$? $\endgroup$ – Tejas Ramdas Nov 4 '16 at 11:50
  • $\begingroup$ Yes, that is correct. $\endgroup$ – Rodrigo de Azevedo Nov 4 '16 at 11:54
  • $\begingroup$ On a slightly unrelated note, how is compression possible if the image is not square, resulting in $U$ and $V$ being of different sizes? $\endgroup$ – Tejas Ramdas Nov 4 '16 at 14:37
  • $\begingroup$ If the image is $m \times n$ and one uses $r$ singular values, then one needs to store $$m r + n r + r = (m + n + 1) r$$ values to compress the image. $\endgroup$ – Rodrigo de Azevedo Nov 4 '16 at 14:44
3
$\begingroup$

We talk about dimensionality reduction when you use the SVD as part of Principal Component Analysis and choose to use a subset of the available dimensions. Check out: Relationship between SVD and PCA. How to use SVD to perform PCA?

SVD can be used for an incredible amount of things, few of which relate to reducing dimensionality.

Examples of use off the top of my head: calculating pseudoinverses, solving least squares problems, analysing time-dependent concentrations in chemical reactions, X-ray scattering time series analysis, non-linear corrections on pixel array detectors, estimating the rank/finding the null space of a matrix, and inversion problems.

$\endgroup$
3
$\begingroup$

SVD decomposes the X matrix to U, S and V matrices where:

U * S * V' = X with V being orthagonal

There are few ways of using that matrices to reduce dimension. One of the most common ways is to choose the first desired number of columns(vectors) from The V matrix which has n x n size. Then the dimension reduction takes place as you do this:

T = X * V_with_selected_vectors

T is generally called scores and V matrix represents loadings.

EDIT: as mentioned in comments check this link for further information on V matrix: loadings and eigenvectors Also, this link provides a good start to SVD.

You can now use these scores with any kind of regression or classification. New samples must be projected to the same space using the same V. However, you should also take care of centering.

The main idea is projecting data in a way that the obtained scores explains the variance of the whole data in descending order. For instance, your first score vector may cover the 72% of the variance while the second score vector carries 12% of the variance and the third 5% so on... Thus, only a few number of principle components(the number of columns in score matrix) may account for almost all of the variance and since this score matrix has fewer variables(thus dimensions) many problems such as multicollinearity or computationally expensive tasks becomes easier to deal with.

One more thing to be noted is the explained variance is proportional with the corresponding eigenvalues that is contained in the S matrix with m x n size. For example, sum of the diagonal elements of S matrix divided by the square of the first element defines the explained variance of the first principle component.

There are many applications of SVD, the high multicollinearity of spectral data can be reduced using this method. Similarly, you can obtain black&white image from the RGB one by choosing a single principle component.

$\endgroup$
  • 2
    $\begingroup$ and V matrix represents loadings The more wise tradition is to call it (right) eigenvectors. "Loadings" term is better to reserve to the up-scaled (unstandardized) eigenvectors. $\endgroup$ – ttnphns Oct 12 '16 at 7:29
  • $\begingroup$ Yes, you are right. Since the question was actually about PCA, I just wanted to familiarize the OP with the terminology without being boring with few pages of information. $\endgroup$ – theGD Oct 12 '16 at 8:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.