1
$\begingroup$

I'm teaching myself this regression stuff, so forgive me if this is a basic question. I can't seem to find a discussion of my particular problem.

So I'm least-squares-ing this overdetermined system $\textbf{Ax}=\textbf{b}$, and I'm interested in minimizing $||\textbf{x}||_1$.

Problem is, my $\textbf{A}^T\textbf{A}$ is singular, so I can't use Least Angle.

I don't know how many of the columns of $\textbf{A}$ are redundant without computing rank explicitly, and I don't really care anyway. I'd rather use that redundancy to get the best 1-norm I can.

Suggestions?

EDIT:

I'd settle for a minimized $||\textbf{x}||_2$.

Improve this question
$\endgroup$
  • $\begingroup$ Just a minor issue: If your $A^TA$ is singular, then obviously you aren't in the overdetermined case. $\endgroup$ – Wolfgang Bangerth Apr 2 '14 at 11:41
  • $\begingroup$ For example, $\textbf{A}$ might be 4096 by 72 but with a rank of only 67. All that's required for a singular $\textbf{A}^T\textbf{A}$ is linear dependence of the column vectors. $\endgroup$ – MackTuesday Apr 2 '14 at 15:48
  • $\begingroup$ I know. But then it's both an overdetermined and underdetermined problem if you have a 5-dimensional subspace in which the solution is not determined. $\endgroup$ – Wolfgang Bangerth Apr 3 '14 at 1:45
  • $\begingroup$ The terms "overdetermined" and "underdetermined" are used differently by various people. One definition is that $Ax=b$ with $A$ of size $m$ by $n$ is overdetermined if $m>n$, and underdetermined if $m<n$. Another definition is that the problem is underdetermined if $A$ has a nontrivial null-space and overdetermined if $R(A)$ is not $R^{m}$. $\endgroup$ – Brian Borchers Apr 3 '14 at 16:07
2
$\begingroup$

Minimizing the 2-norm of $x$ among all least squares solutions is relatively easy to do- this is the pseudoinverse solution. It can be computed using either a rank revealing version of the QR factorization of $A$ (there are specialized versions of this that work well on large and sparse $A$ matrices) or by using the Singular Value Decomposition. Since you're really more interested in minimizing $\| x \|_{1}$, I'll move on to answering that question.

The problem

$\min \| x \|_{1} $

subject to

$\| Ax-b \|_{2} \leq \delta$

is equivalent (with a suitable choice of $\lambda$) to the basis pursuit denoising problem (BPDN)

$\min \| Ax-b \|_{2}^{2} + \lambda \| x \|_{1}$

Minimizing $\| x \|_{1}$ has (in many circumstances) the effect of finding a sparse solution to the problem of approximating $Ax=b$. These sparse approximation problems have been extensively studied because of their application to problems of compressive sensing.

As a practical matter, you probably don't want to limit your $x$ to being an actual least squares solution but rather to set some tolerance on $\| Ax-b \|_{2}$. If for some reason you do need to have an $x$ that is actually a least squares solution, you can start by finding any least squares solution $\hat{x}$, then let $\delta=\| A \hat{x} - b\|_{2}$.

Algorithms for solving these sparse norm approximation problems are specialized enough that you're probably best off making use of existing software rather than trying to implement the algorithms yourself. I would recommend the list of software packages (as well as the many references to books and papers) at

http://dsp.rice.edu/cs

Improve this answer
$\endgroup$
  • $\begingroup$ My vectors were independent anyway! Turns out it was a precision problem. Thanks regardless. $\endgroup$ – MackTuesday Apr 3 '14 at 19:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.