Low-rank Approximation with SVD on a Kernel Matrix

Question

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?

Answer 1

Your work is an example of low rank approximation.

Solution

Use a threshold. 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.

Take the first 65 or the first 75. Pick a threshold.

Seeing the low rank approximation

A sequence of low rank approximations follows. We see the input image, the low rank approximation, the error, and the threshold for the spectrum. The image matrix has rank 266. Using a rank of 25 produces a reasonable approximation.