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$.)
No comments:
Post a Comment