Login / Register  0 items | $0.00New @ What is KVR? Submit News Advertise

Least Squares Question

DSP, Plug-in and Host development discussion.

Moderator: Moderators (Main)

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

Postby MackTuesday; Tue Apr 01, 2014 3:25 pm Least Squares Question

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

Postby torusle; Tue Apr 01, 2014 11:59 pm Re: Least Squares Question

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
 
324 posts since 13 Nov, 2002, from Germany, Darmstadt

Postby helium; Wed Apr 02, 2014 1:40 am Re: Least Squares Question

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.
Why is 6 afraid of 7

Because 7 8 9.
MackTuesday
KVRist
 
431 posts since 11 Jul, 2004, from Southern California, USA

Postby MackTuesday; Wed Apr 02, 2014 8:20 am Re: Least Squares Question

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)

Return to DSP and Plug-in Development