I've got an overdetermined Ax=b. I want to least-squares-ify it. But the columns of A are not linearly independent. So A* A is singular.

This is fine because I can deal with an infinitude of solutions. I just have to pick one.

I'd like to pick one that minimizes the 1-norm of the solution. The problem is that Least Angle and its variants all assume a non-singular A* A.

I don't want to discard columns of A a priori because I want to consider them all when minimizing the 1-norm.

Suggestions?

## Least Squares Question

4 posts
• Page

**1**of**1**- KVRer
- 19 posts since 12 Jan, 2012

The standard way to solve such problems is to use the Moore-Penrose pseudoinverse:

https://en.wikipedia.org/wiki/Moore%E2%80%93Penrose_pseudoinverse

If you don't have a matrix package that can calculate it for you I suggest to start using the iterative construction method as shown in the wiki article. Then - if you get results - switch to the SVD method. The SVD method is much more numerical stable.

https://en.wikipedia.org/wiki/Moore%E2%80%93Penrose_pseudoinverse

If you don't have a matrix package that can calculate it for you I suggest to start using the iterative construction method as shown in the wiki article. Then - if you get results - switch to the SVD method. The SVD method is much more numerical stable.

- KVRist
- 431 posts since 11 Jul, 2004, from Southern California, USA

torusle wrote:The standard way to solve such problems is to use the Moore-Penrose pseudoinverse

Thanks, but can the pseudoinverse be constructed on a column-deficient matrix? In the Wikipedia section on QR decomposition, it explicitly assumes full rank, but nowhere does it describe a method that definitely will work on deficient matrices. In all of the literature I've seen, the phrase "assuming full rank" appears over and over again, but I can't find anything that says, "this one will work on any matrix", or, "if your matrix is deficient, you can do this instead".

helium wrote:Are you sure you want to minimize the 1-norm and not the 2-norm? The Moore-Penrose pseudoinverse will minimize the 2-norm i.e. least squares as you say in the subject.

I want to minimize the 2-norm of the error, but I want to minimize the 1-norm of x. This is reasonable because A is deficient, which means there is an infinitude of vectors x that all have the same minimized error. Then I get to pick the x that I like best.