In the literature, I've seen the lasso problem phrased as the minimization of: $$\frac12x^tAx-x^tb+\lambda||x||_1$$ or of: $$\frac12||Ax-b||_2^2+\lambda'||x||_1=\frac12x^tA^tAx-x^tA^tb+b^tb+\lambda'||x||_1$$

If $\lambda=\lambda'=0$, then the second problem minimizes the norm of the gradient of the first, and the two problems are equivalent when $A$ is symmetric positive definite ($x=A^{-1}b$ is the solution to both). If $A$ is not symmetric positive definite then the first problem is no longer convex, while the second always is and can be treated by the standard coordinate/gradient/conjugate gradient descent methods (finding the solution of minimum norm $||x||_2$ when $A$ is singular).

How does this work when $\lambda,\lambda'$ are nonzero? Are the two problems equivalent for symmetric $A$ positive definite under some function $\lambda'=f(\lambda)$ (or can we get approximate equivalency of solutions)? It'd be quite convenient to substitute the first problem with the second when strict lasso penalization is wanted (no ridge) and $A$ is very ill-conditioned.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.