Dear All,
Assume the following system of equations:
Ax = b where b is the vector of data of size Nx1, x is the vector of unknown of size Nx1 and A is the matrix of coefficients of size NxN.
The solution is x = pinv(A)*b where pinv(A) is the pseudo inverse of A.
Now if A is of rank N-1, how do we solve of x? i know that infinite solutions exist but is there another approach of solving for x?
Thank you in advance.
In your case, if A is rank-deficient you have two problems:
- there might not be an exact solution at all. Since the range of A does not span the entire R^N but only an (N-1)-dimensional subspace, you can solve exactly for x only if b is in this subspace. Anything outside cannot be represented by A*x.
- at the same time there are infinitely many ("equally good") solutions since A has a non-empty null space, i.e., there is a one-dimensional subspace of vectors x that give A*x=0.
Interestingly, if you use the least squares solution pinv(A)*b, it provides a solution for both problems. For the first problem, it gives you the closest x, i.e., the one with the smallest error ||b-A*x||. At the same time, for the second problem, out of all solutions that share the smallest approximation error, it gives you the one with the smallest norm ("minimum-norm solution").
Depending on your application this may or may not be desirable. It depends on what you want to do with that x. You can use the degree of freedom also for other things, like minimizing another norm of x. LS is the simplest so if you just need any solution then it's really fine to use.
In your case, if A is rank-deficient you have two problems:
- there might not be an exact solution at all. Since the range of A does not span the entire R^N but only an (N-1)-dimensional subspace, you can solve exactly for x only if b is in this subspace. Anything outside cannot be represented by A*x.
- at the same time there are infinitely many ("equally good") solutions since A has a non-empty null space, i.e., there is a one-dimensional subspace of vectors x that give A*x=0.
Interestingly, if you use the least squares solution pinv(A)*b, it provides a solution for both problems. For the first problem, it gives you the closest x, i.e., the one with the smallest error ||b-A*x||. At the same time, for the second problem, out of all solutions that share the smallest approximation error, it gives you the one with the smallest norm ("minimum-norm solution").
Depending on your application this may or may not be desirable. It depends on what you want to do with that x. You can use the degree of freedom also for other things, like minimizing another norm of x. LS is the simplest so if you just need any solution then it's really fine to use.
You can apply the OMP algorithm which is usually used for signal recovery. It is a greed algorithm.
Please google "orthogonal matching pursuit" or check the artical math.mit.edu/~liewang/OMP.pdf the detail.
For the brief description,
Your A should be a N*(N-1) matrix, and b_star is the size (N-1)*1 vector without the last element of b, because the given A*x cannot get the last value for b.
And then, A*x = b_star can get a size N*1 size vector x. Now pick one column of A to get the minium residual error of b, you can get a vector x_star with size less than or equal to N.
Hope this is helpful.
The same solution that the one given by pinv(A)*b, consists in taking the orthogonal projection of b on the image of A (im(A)), in your case it seens quite easy since the dimension of Ker A is one. Then you sove the probem in the space im(A).
I expect that this an inverse problem. You probably need to bring more information to the problem - for example, probability distributions. See the SIAM book "Inverse Problem Theory" by A. Tarantola.
You may contact me at [email protected].
I suggest to have a look at matlab script available from the following website:
http://www.cs.berkeley.edu/~demmel/ma221_Fall04/Matlab/RankDeficient.m
http://www.cs.berkeley.edu/~demmel/ma221_Fall04/Matlab/RankDeficient.m
- Badges
- Science topic
- Similar topics
- Mathematics