Minimzing L2-norm solution: rank deficiency

Hi all matlab GURUs (Tim Davis, John D’Errico, Bruno Luong and others) ,

1) I am working on L1-norm solver. However, in the split Bregman method, L1-problem is approximated as small L2-subproblems; so, I am talking about L2-norm minimization . The subproblem that I am solving is:

J(u) := |A*u - yo|^2 + tol^2 |D*u-y1|^2

Where yo and y1 keeps changing between various iterations.

2) Before solving this, I am converting it into single term L2-norm:

J(u) := |[A; D]*u – [yo; tol*y1]|^2 = |AF*u – b|^2

3) My matrices A, AF are sparse.

4) Quite frequently (20-30% of time, my solver which uses backslash operator runs into usual problem of “Rank deficiency”).

a. I tried “PSEUDOINVERSE” by Bruno. I believe that his code uses QR method. I calculate solution as

   xF = pseudoinverse(AF)*b;

But, even there I am running into the same trouble of rank deficiency. Some guidance regarding appropriate solver would be highly appreciated.

Regards, DK

[Matt J]

What's the question exactly? If your AF matrix is rank deficient, is it not natural that you should have problems? Why are you using rank deficient matrices?

[Dushyant]

To capture the physics of underlying problem, the system has to be underdetermined. However, the matrix A is not really rank deficient.

Actually, I am solving this smaller L2-norm problem in some iteration loop. Though matrices A,D stays the same yo and y1 gets recalculated. Sometimes it does not complain; sometimes it complains about rank deficient. I am yet to understand how yo and y1 could affect the rank of AF.

OR, How could “PSEUDOINVERSE” complain about rank deficiency?

Also, even with rank deficiency, I would be fine with some solution that minimize L2-norm

|u|.

[Matt J]

J(u) := [A; D]*u – [yo; tol*y1]^2 = AF*u – b^2

Looks like this should have AF=[A;tol*D]

I am yet to understand how yo and y1 could affect the rank of AF.

That sounds like a bug. You should use dbstop to trap examples {A,d,y0,y1} where it does and does not happen.

OR, How could “PSEUDOINVERSE” complain about rank deficiency?

Because it, too, uses backslash operations. Somehow, it wasn't successful in its factorization.

[Dushyant]

Never mind. It was a bug in my code.

Sorry for any inconvenience.