Maximizing Sparsity in l1 Minimization? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T12:29:07Z http://mathoverflow.net/feeds/question/14245 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/14245/maximizing-sparsity-in-l1-minimization Maximizing Sparsity in l1 Minimization? fuzzytron 2010-02-05T07:32:24Z 2010-02-08T18:35:17Z <p>Consider the optimization problem</p> <p>$$\min_x ||Ax||_1 + \lambda||x-b||^2,$$</p> <p>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.</p> <p>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.</p> <p><em>Edit:</em> 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$.)</p> http://mathoverflow.net/questions/14245/maximizing-sparsity-in-l1-minimization/14461#14461 Answer by 002 for Maximizing Sparsity in l1 Minimization? 002 2010-02-07T04:37:53Z 2010-02-07T05:12:06Z <p>The ultimate sparseness occurs when $Ax^*(\lambda)=0$, which is the case when the minimizer <code>$x^*$</code> 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 <code>$2\lambda \mathrm{dist}(b,\ker A)$</code>. Here the lower bound for operator is understood in the <code>$\ell^2\to\ell^1$</code> norm.</p>