Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Consider the optimization problem

$$\min_x ||Ax||_1 + \lambda||x-b||^2,$$

where $A \in \mathbb{R}^{n \times n}$, $x,b \in \mathbb{R}^n$ and $\lambda$ is strictly greater than 0. (This problem is closely related to the "lasso" problem in basis pursuit.) Can anything be said about the value of $\lambda$ for which $Ax^*$ is sparsest? Clearly some values are bad: for instance, if $\lambda$ is huge and $b$ is dense then it is unlikely that $Ax^\star$ will be very sparse.

In other words: among all $\lambda > 0$ there is at least one value $\lambda^\star$ such that $||Ax^\star(\lambda)||_0$ is minimized. Are there, say, bounds on $\lambda^\star$ in terms of $A$ and $b$? I'd also be interested in results pertaining to basis pursuit or other similar problems.

Edit: I'm primarily interested in problems where ideal sparsity cannot be achieved, i.e., $||Ax^\star(\lambda^\star)||_0 > 0.$ (Assume that $A$ is square w/ full rank and $b \ne 0$.)

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

The ultimate sparseness occurs when $Ax^*(\lambda)=0$, which is the case when the minimizer $x^*$ is the projection of $b$ onto $\ker A$. For this to happen, $\lambda$ must be small enough so that the restriction of $A$ to the orthogonal complement of its kernel is bounded from below by a constant greater than $2\lambda \mathrm{dist}(b,\ker A)$. Here the lower bound for operator is understood in the $\ell^2\to\ell^1$ norm.

share|improve this answer
    
Thanks for your response; what you say is true. I should have mentioned that I'm interested in the case where A has full rank, hence Ax*=0 only when x*=0, which corresponds to lambda=0 (or b=0). –  TerronaBell Feb 8 '10 at 18:23
    
Ah, I see. It didn't occur to me that the l2->l1 norm bounded the directional derivatives at the origin. One question: since we want 2 lambda ||b||_2 < c, don't we want lambda < c/(2||b||_2) instead of lambda < c||b||_2/2? –  TerronaBell Feb 8 '10 at 22:06
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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