Finding Coefficients to Construct a Vector Using Defined Basis

I am working on a project in MATLAB where I have a set of basis vectors, and am attempting to reconstruct a vector outside the test set used to generate the basis vectors (i.e. I'm trying to find the individual unique coefficients corresponding to the basis vectors for one vector, if that makes sense). Each vector has too many components and there are too many basis vectors to make this process feasible by hand. I know there is a way to find these coefficients using linear algebra, and perhaps generate them using a function in MATLAB, but I am a novice in both linear algebra and MATLAB and need help. Please let me know if my explanation was not clear, or if you have any guidance to solve my problem. Thanks in advance!

Answer 1

[Matt J]

Make the basis vectors the columns of a matrix A and then use mldivide,

coefficients=A\b

Here b is the column vector you are trying to reconstruct coefficients from.

[nms09]

Thank you! Just to clarify, how does using mldivide yield the coefficients I'm looking for?

[Matt J]

See the code above. A\b is the same as mldivide(A,b)

[Matt J]

Example:

A=rand(10,4); 
c=rand(4,1), %hypothetical coefficients

c = 4×1

0.5939 0.8503 0.5511 0.2837

b=A*c;

Now, we will recover c from b

cRecovered=A\b

cRecovered = 4×1

0.5939 0.8503 0.5511 0.2837

[nms09]

I did what you said - I have a 1382400x20 matrix A (there are 20 basis vectors of 1382400 components), and i had a 1382400x1 column vector b. I did coefficients = A\b and got a 20x1 column matrix, but then I tried to take the sum of every basis vector multiplied by it's respective generated coefficient, and somehow ended up with a) a matrix of the exact same number for every element, and b) negative numbers, which do not make sense in the context I'm working in. Is this the proper way to use this result, or am I doing something wrong?

Edit: I was able to fix the getting the same numbers part, i'm able to get unique values now, but when I try to compare the reconstructed vector to the original, they are not identical and i still have a few negative values - is this due to a limitation of the basis vectors i've generated, or is this a computation error i may be doing?

[Torsten]

If A is an (n x m) matrix (n>m) and b an arbitrary (n x 1) column vector, the line

coefficients = A\b

finds an (mx1) vector "coefficients" such that norm(A*coefficients - b) is minimized.

So you can't expect that A*coefficients = b exactly, but only that norm(A*coefficients - b) is minimal.

In order that A*coefficients = b is exactly satisfied, b must be in the span of the column space of A.

The probability for this with A being a 1382400x20 matrix is very low ( I guess approximately 20/1382400 ).

[nms09]

Is there a workaround for this such as a different way to reconstruct the vector, or a way to test if I can reconstruct the vector to some degree of accuracy at all?

For some background, each of the basis vectors is actually an image thats been turned into a column vector, and b is an extremely similar image from the same data set I am trying to reconstruct. I would think that b is within the span of A because the test set used to generate the column vectors of A, and b are from the same data set.

[Torsten]

If A\b gives you a vector "coefficients" such that A*coefficients = b is not satisfied, then there is no such vector "coefficients" with this property.

You can use "lsqlin" to set conditions on the vector "coefficients", e.g. that all components are >=0 or something similar. But this in general will make norm(A*coefficients-b) even greater.

Another test whether b can be represented as a linear combination of the column vectors of A is the rank test:

rank(A) must be equal to rank([A,b]).

The degree of accuracy with which the vector can be reconstructed is the (scaled) norm of

res = A*coefficients - b.

[Matt J]

I would think that b is within the span of A because the test set used to generate the column vectors of A, and b are from the same data set.

That doesn't sound like any kind of guarantee to me. Unless b was specifically generated as a linear combination of the A(:,i), you can't expect an exact reproduction.

[nms09]

So the ranks of the two matrices are different, does that mean that there is no way to solve this problem? Is there another way to check if the correct coefficents can be generated using A?

[Matt J]

The rank test proves that there is no exact solution.

But it's hard for us to know how big the reconstruction error is that you are seeing, and in what way it is serious. Why don't you show us both b and its approximate reconstruction as images, so we can understand the differences that are a problem for you.

[nms09]

Unfortunately due to security reasons I cannot share the actual image, but I actually divided b and its reconstruction and ended up with an image that had very distinct patterns that are problematic (if it was the same images the divided image would be a single shade of grey).

Could the problem be improved by maybe increasing the number of basis vectors? Or decreasing? I'm not sure if it's a computation issue or if the method has limitations in constructing an image to the accuracy I need.

[Torsten]

but I actually divided b and its reconstruction

Don't you have to subtract them (and then maybe divide the resulting vector by the norm of b) ?

[nms09]

Dividing the image gives how similar they are because its the ratio of each pixel, but I think subtracting is another method as well.

[Torsten]

But elementwise division can lead to a division by 0 in some places, doesn't it ?

[nms09]

Perhaps, but I've never come across an issue with dividing images, and also that wasn't really the point of this thread anyways - I know there's a distinct difference between the reconstructed image and the original, and I'm trying to figure out if a) it's a computation error or a limitation, and b) what possible solutions/other methods for this kind of reconstruction using a set of basis vectors would be.

[Matt J]

a) it's a computation error or a limitation, and b) what possible solutions/other methods for this kind of reconstruction using a set of basis vectors would be.

Both of those questions require us to see the target and reconstructed images, and perhaps a few of the basis images as well. Is there not an alternative example that you can work with that can be shared?

Note however, that is very unusual that you would be able to reconstruct a target image algebraically given only 20 basis images. The basis images would have to very much resemble the target image to the point where any objects depicted in the target image would have to be present in the basis images as well, in the exact same location and pose.

[Torsten]

I know there's a distinct difference between the reconstructed image and the original

If you divide by 0, there will be a distinct difference indicated between the reconstructed image and the original, although in reality, there might not be such a difference.

[nms09]

Torsten - I used subtraction as well and it yielded a similar distinct pattern to the image.

Matt - A similar example visually would be an image of a pond with overlapping ripples, whether the data set from which the basis is constructed is a set of many similar images of pond ripples. The external image is also an image of the same lake, same frame/shot, with ripples. When the image is reconstructed and compared to the original and divided or subtracted, the resulting difference image has distinct circular patterns that the original image had that the reconstructed image didn't catch. In this context every relevant image can be assumed to have been taken from the exact same frozen spot and the density of the ripples is the same from image to image where to the naked eye the images seen nearly identical (but each image differs from the next slighly). Also, the images are in black and white. Hopefully this example makes sense.