## Least Squares Question

MackTuesday
KVRist

434 posts since 11 Jul, 2004, from Southern California, USA
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?
torusle
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.
helium
KVRist

328 posts since 13 Nov, 2002, from Germany, Darmstadt
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.
MackTuesday
KVRist

434 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.

Moderator: Moderators (Main)