Solving a large under-determined system of linear equations

[FrankST]

Dear All,

I have a linear system of equations such as Ax = b where A is a m-by-n matrix and m < n and A is a full rank matrix (rank(A) = m).

Since there are infinitely many solutions to this problem, I was looking for different methods to solve this problem. As I understood I can pose this problem as the following:

minimize 2-norm of x subject to: Ax = b

And I realized I can use pseudo inverse to find x . Here is my question:

1- Is the way I posed the problem correct or if there is an alternative way?

2- If A is a large and sparse matrix (like 30,000 by 200,000 matrix) is there a more efficient method to solve this problem (iterative methods) ?

3- If I want to impose additional constraints such that 0 <= x's <= 1 how can I do that ?



Thanks for your help,

Frank

 

[algebrat]

1. not sure, but i'll side with you

2. maybe the method below would give you something for the computer. problem with iterating, is how long before it converges? you have a formula for that?

3. i think you want to look for minimizing least squares with constraints, which will change the formulas a little from your everyday least squares problem. you have to be careful though, because there's a million and one minimizing with constraint types of problems. if you don't make sure that you have the appropriate hypothesis met, you'll be pretty much wrong. for instance, keep in mind that your constraint is an inequality constraint, not an equality constraint.