Options (Affects News & Product results only):

 OS: Any Format: Any Include: ProductsDevelopersNewsForumsVideos
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.
KVRist

425 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?
KVRer

15 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.
KVRist

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

Because 7 8 9.
KVRist

425 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)