KVR Audio

MackTuesday · Post by **MackTuesday** » Tue Apr 01, 2014 11:25 pm

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 · Post by **torusle** » Wed Apr 02, 2014 7:59 am

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

https://en.wikipedia.org/wiki/Moore%E2% ... udoinverse

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 · Post by **helium** » Wed Apr 02, 2014 9:40 am

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 · Post by **MackTuesday** » Wed Apr 02, 2014 4:20 pm

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.

Least Squares Question