pinv of a singular matrix

Hi,

I'm trying to solve for x in: Ax=b, but my A matrix is singular. An example of the A matrix is

-1  0  0  1  0  0  0
0  -1  1  0  0  0  0
0  1  -1  0  0  0  0
1  0  0  -1  0  0  0
0  1  0  0  -1  0  0
0  0  1  0  0  -1  0
0  0  0  1  0  0  -1

When I use pinv(A) to solve for x, I get spikes at intervals, and these intervals correspond to the spacing between 1's and -1's in the A matrix. An example is shown in the graph below:

Does anyone know why the spikes are there or how I can get rid of them? Or please suggest another decomposition technique or approach to solve the equation.

I know the way to get an exact (not approximate) solution is if I can make A non-singular. I've tried adding rows to A, each containing 1's and -1's with different number of 0 spacings but that doesn't make A full rank. I want 1's and -1's on each row because I need the b column vector to be a difference between 2 points in x. Please, any suggestion on how to make A non-singular is welcome.

Thanks!

[Walter Roberson]

I do not follow how the x axis shown here relates to pinv(A)*b ?

[Mike]

The x-axis is from pinv(A)*b where A is a 501 x 501 matrix. I gave the smaller (7 x 7) matrix example just to show the pattern of the matrix. In the smaller 7 x 7 example, the step size, between the -1's and 1's, is four, while the step size in the 501 x 501 is 100.

[Walter Roberson]

A is 7 x 7 or 501 x 501. pinv(A) is the same size. In order for pinv(A)*b to be computable, b could be a scalar, in which case the result would be the same size as A, not a scalar value between -0.8 and +0.8. Or b could be a 7 by N or 501 x N matrix (for the respective cases), in which case the result would be 7 x N or 501 x N. Even in the case where you are sending in a column vector, 7 x 1 or 501 x 1, the result is going to be a column vector, not a scalar between -0.8 and +0.8 . So I have no idea what your y axis is.

For your x axis, is the value being shown the "step size between the -1's and 1's" in your A matrix?

[Mike]

The result, pinv(A)*b, is a column vector, not a scalar, and the graph is from: plot(pinv(A)*b). The x-axis is the number of rows in A (501 in this case), and the distance between spikes is the step size between the -1's and 1's in the A matrix.

I'm sorry for being confusing, I think the confusion is I didn't specify what values I used for the b column vector.

Luckily though, I think I've found a way to solve the equation. The linear dependence between some rows/columns is what's making the A matrix rank-deficient. I added a very little noise to offset the symmetry and this made it non-singular. This way I can find the inverse...not the pseudo-inverse. Thanks Walter.

[John D'Errico]

Adding noise to your matrix will not really solve the problem. It will mask the issue. The issue is one of poor definition of your problem, leading to a singular matrix.

Answer 1

[Walter Roberson]

x = A\b;

[Mike]

x = A\b; gives NaN answer

[John D'Errico]

The matrix is singular. backslash would fail without question.

Answer 2

[John D'Errico]

The problem here is not pinv, but a lack of proper definition of the matrix you are trying to do the solution with. That matrix, and the problems you are having reflect a poorly posed problem. Sorry, but true.

Adding arbitrary rows to the matrix makes no sense at all, IF those rows do not mean something. A matrix is just a set of numbers in a regular form. And since only you know what those numbers mean, how the matrix as derived, then we will have a hard time helping you without more information from you.

Why does having a smooth curve there make sense? What is the meaning of that curve at all?

If I must guess, from the information you have bothered to give us, is that you expect a smooth curve out. Why? The crystal ball is sooooo foggy. HOWEVER........

You lack sufficient information in that matrix to ensure the result will be unique. That is one aspect of a singular problem. So IF you expect the result to be smooth across those boundaries, then adding a few CAREFULLY chosen rows to your matrix will help. (Think about the meaning of those rows as I have added them.)

A = [-1  0  0  1  0  0  0;
0  -1  1  0  0  0  0;
0  1  -1  0  0  0  0;
1  0  0  -1  0  0  0;
0  1  0  0  -1  0  0;
0  0  1  0  0  -1  0;
0  0  0  1  0  0  -1;
1    -2       1       0       0       0       0;
0     0       1       -2      1       0       0];
0     0       0       0       1       -2      1];

The right hand sides (elements of b) for those rows of A will be zeros.

Effectively, the idea is to provide additional information that the result be smooth. Add one such row to span each of your problem areas. I also added a similar row at the beginning, since you apparently also have this problem at each end.

Again, if I actually knew what you were doing or how you created the matrix, I might be able to offer a semi-intelligent answer. You get what you pay for.

[Mike]

Sorry John, I didn't mean to make it seem foggy, I thought I gave enough information to describe the problem I was having.

You are right, given the b column vector I used, I expected a smooth curve out. I didn't state the b column vector because it was a 501 x 1 vector (I've attached the b vector now).

Let's suppose the x vector is the radius of a rotationally symmetric surface, and what I can get out of a measurement is the difference between x, and a translated x. For example, if x= x(1), x(2),...,x(10), and a translation of 3 is used, then we could have

b(1) = x(4) - x(1)

b(2) = x(3) - x(2)

b(3) = x(2) - x(3)

b(4) = x(1) - x(4)

b(5) = x(2) - x(5)

b(6) = x(3) - x(6)

and so on. The right side of the above equations is A*x (where A is a design matrix), while the left side represents the b column vector. That's how I arrived at the equation Ax=b.

I tried the additional rows you suggested, they didn't remove the spikes but I like the idea of providing additional information to smoothen the result. The rows you suggested would be:

b(8) = x(1) -2*x(2) + x(3) = 0

b(9) = x(3) -2*x(4) + x(5) = 0

b(10) = x(5) -2*x(6) + x(7) = 0

Please correct me if I'm wrong, but I think your idea was to make transitions, around those spikes, less steep. E.g,. instead of

0 0 0 5 0 0 0, one could have 0 1 3 5 3 1 0. I'll think more about it and see if applying some interpolation might help with the spikes.

I found a way to directly solve for x in Ax=b; I added very little noise to offset the linear dependence between rows. This way, A becomes non-singular and x=A\b works. I hope I'm a bit clearer...thanks John.