Find unique values in a pseudo inverse based on SVD
8 views (last 30 days)
For the equation Ax = B, I can use the pseudo inverse of A * B to get the best estimate for x
Now A is not full rank and there's linearly dependent columns, so when performing pinv(A) * B, some of the X values may not be unique,
For example, consider that
1 2 0 0 0 0
2 4 0 0 0 0
0 0 1 0 0 1
0 0 0 1 0 0
0 0 0 0 1 0
Now if we calculate x by taking pinv of a
x = pinv(a) * b
But we know that the 1,2,3, and 6th values of x have no unique answers. How do we identify which values of x are not unique, preferably using SVD because we use SVD to perform the pseudo inverse anyways and it would save calculation steps for us.
John D'Errico on 10 Dec 2021
Edited: John D'Errico on 11 Dec 2021
Um, in general, ALL of the values in the computation will be non-unique. In some simple, RARE cases, that will not be true. How can we know? By understanding the linear algebra. When you have a singular problem with a rank deficiency, what does the solution look like? For example, with:
A = [1 2 0 0 0 0
2 4 0 0 0 0
0 0 1 0 0 1
0 0 0 1 0 0
0 0 0 0 1 0];
b =[1;3; 3; 4; 5];
First, what is the numerical rank of A? A is a 5x6 array.
This tells us that one of the rows of A can be written as a linear combination of the other rows, but also that two of the columns of A are linear combinations of the others. We wish to try to solve the problem A*X==b. Of course, there will often be no exact solution, but there is a simple test.
And this tells us that B does not live in the column space of A. So no linear combination of the columns of A can reproduce b exactly. The simple solution to finding the best approximation here is just
x0 = pinv(A)*b
But that will not be exact, as I claimed before.
Close, but no cigar. Since A is rank deficent by 1, but A has more columns than rows, the general solution for all possible solutions will be of the form
pinv(A)*b + s*N1 + t*N2
where s and t are unknown parameters, and N1 and N2 are vectors that span the nullspace of A. The functino null gives us that nullspade.
Anull = null(A)
So N1 and N2 are the two columns of Anull. As you can see, two rows of N1 and N2 are EXACTLY zero. We can therefore write the full solution to your problem as:
syms s t
x0 + Anull*[s;t]
ANY other (equally good) solution can be derived from that expression for some specific values of s and t. However the solution with minimum norm (what pinv yields) is the one where s=t=0. And there you should see that elements 3 and 4 of the complete solution are fully known. But all other elements will vary, essentially non-unique.
Is this the expected case, that is, is this usual? NO!!!!!! Almost always, you will expect to see all elements of your solution are not unique, because it will be rare for the nullspace vector(s) to have exactly zero rows. Here, we could identify those elements in advance, merely by looking at the nullspace vectors. Again, it is nothing you would normally expect.
For example, I'll create a randomly generated 5x6 array that has rank 4.
Ar = randn(5,4)*randn(4,6);
You can see that because A is the product of two arrays that are each at most rank 4, the product will also be rank 4 at most. Since they are randomly generated, the probability they will be of rank less than 4 has measure 0.
WHEW! That worked. ;-) Now lets look at the nullspace vectors for Ar.
And here you see that these vectors do not have rows that are entirely 0. And therefore, the solution will have no elements that are non-unique. I need not even generate that solution, but if it makes you happy...
vpa(pinv(Ar)*b + null(Ar)*[s;t],10)
where you should see that ALL elements of the general solution have multiples of both s and t in EVERY element. This is the result you would normally expect from a problem that was not probably cooked up as can be found in A.
Finally, could I have looked at A in advance, and understanding the linear algebra, have seen this to be the case by inspection? Well, yes. Technically, yes. But that would also rarely be the case, and since the simple solution is to just compute the nullspace vectors of A, there is no need to waste time trying to work it out by inspection.
More Answers (1)
Jon on 10 Dec 2021
I think that you can identify the "non-unique" components in your specific example, by looking at the last two columns of V (or equivalently the last two rows of V', where using the svd we have A = U*S*V'. The non-zero elements in the last two rows of V' are the "non-unique" components.