Minimzing L2-norm solution: rank deficiency

2 views (last 30 days)
Dushyant on 30 Jun 2014
Commented: Dushyant on 30 Jun 2014
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

Show 1 older comment
Dushyant on 30 Jun 2014
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 on 30 Jun 2014
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 on 30 Jun 2014
Never mind. It was a bug in my code.
Sorry for any inconvenience.