Least Angle when $\textbf{A}^T\textbf{A}$ is singular

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$.

• Just a minor issue: If your $A^TA$ is singular, then obviously you aren't in the overdetermined case. Apr 2 '14 at 11:41
• 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. Apr 2 '14 at 15:48
• 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. Apr 3 '14 at 1:45
• 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}$. Apr 3 '14 at 16:07

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

• My vectors were independent anyway! Turns out it was a precision problem. Thanks regardless. Apr 3 '14 at 19:10