What is KVR Audio? | Submit News | Advertise | Developer Account

Options (Affects News & Product results only):

OS:
Format:
Include:
Quick Search KVR

"Quick Search" KVR Audio's Product Database, News Items, Developer Listings, Forum Topics and videos here. For advanced Product Database searching please use the full product search. For the forum you can use the phpBB forum search.

To utilize the power of Google you can use the integrated Google Site Search.

Products 0

Developers 0

News 0

Forum 0

Videos 0

Search  

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
 
17 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
 
323 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