Transformation of Lasso to quadratic linear constrained form

326 Views Asked by At

The Lagrange formulation of the Lasso problem has the following form: $$\min_x ||Ax-b||_{2}^2+\lambda||x||_1$$ In the OSQP paper(A.5) by Stellato et al. there is the quadratic version $$\min_{x,t} y^\intercal y + \lambda \textbf{1}^\intercal t \\s.t. \ Ax-b=y, -t \leq x \leq t$$ where $t \in \mathbb{R}^n$. The paper says, these two formulations are equivalent. I see how we transform the first summand, but how follows this for the second summand? Intuitively I would say that the second summand in the quadratic version is more related to the $\ell_\infty $-norm than to the $\ell_1$-norm.