Low-rank Approximation with SVD on a Kernel Matrix

I have very little experience in linear algebra so please bear with me. Here's a little background of my issue. I'm working on a problem that utilizes a large kernel matrix, K. This matrix, when multiplied with 500 x 1 column vector A, results in a 500 x 1 column vector B as shown below:

A = K * B

The goal for this problem here is to find B given A and K. K is a 500x500 lower triangular matrix, so I can't take the inverse of it. Through some research, I was able to use SVD to break up K into into its singular values and calculate the inverse by

inv(K) = V * inv(S) * U'; B = inv(K) * A;

By filtering out some large singular values by setting values above a certain threshold to zero, I was able to recalculate an approximation for B. It seems like there are some high noise values in K.

Now that the previous problem has been taken care of, I'm working with another column vector, A1, which was calculated using the same kernel matrix K. However, A1 is a 100 x 1 column vector, so I can't perform the filtering as I did before. I was thinking about performing SVD on K and only keeping the 100 most important singular values and vectors, but would removing the left and right vectors in accordance with the values to be kept provide a good approximation of K in general? Going from 500 x 500 to a 100 x 100 matrix seems like a lot of data would be lost. In this case, how would one go about picking the most important values?

• Kindly consider adding the phrase low rank approximation to your title. Mar 28, 2017 at 21:01

Your work is an example of low rank approximation.

Solution

Use a threshold to exclude singular values which are numerically small. The singular value decomposition, by construction, sorts the singular values: $$\sigma_{1} \ge \sigma_{2} \ge \dots \ge \sigma_{\rho} > 0$$ Mathematically, you want the rank to be $$k$$, the numerical rank is $$\rho$$. The extraneous singular values are artifacts of finite precision arithmetic. What should be 0 is computed as a number near 0.

An example follows.

Seeing the low rank approximation

A sequence of low rank approximations follows.

A picture of Camille Jordan is converted to a grayscale matrix, and the singular value decomposition is computed. The singular value spectrum is shown on the far right, showing a variation of five orders of magnitude. The left most column is the original image provided for comparison.

The first row of images uses only the first singular value and represents a rank one approximation to the image.

The second row uses the first two singular values to form a rank two approximation.

And the process continues. The final row represents a rank 25 approximation to the original rank 266 image and uses less than 10% of the original singular values.

Information content

The matrix $$\mathbf{A}$$ is decomposed into three matrices, and their data content differs drastically: $$\mathbf{A} = \mathbf{U} \, \Sigma \, \mathbf{V}^{*}$$

Full image $$\mathbf{U}_{266 \times 266} \ \times \ \Sigma_{266 \times 266} \ \times \ \mathbf{V}^{*}_{266 \times 266}$$

Rank 25 approximation $$\mathbf{U}_{266 \times 25} \ \times \ \Sigma_{25 \times 25} \ \times \ \mathbf{V}^{*}_{25 \times 266}$$