Solve Lasso using Quadratic Programming

Question

I want to solve a Lasso: \begin{equation} \text{minimize} \;\frac {1}{2}(y-Cx)^T(y-Cx) + \lambda\|x\|_1 \\ s.t. \\ Ax \leq b \end{equation} using QP: \begin{equation} \text{minimize} \;\frac {1}{2}x^TQx + c^Tx \\ s.t. \\ \tilde{A}x \leq \tilde{b} \end{equation} I want to use either this or this method. My problem is that in both cases, the matrix $Q$ is singular. Is there a way to formulate a lasso as a QP with a non-singular $Q$ matrix?

Answer 1

Are you using any kind of solver? Or are you planning on coding something yourself? Any convex solver will do the work for you, and if the dimension if not too high (~300-500) it will also do it very fast (since these use second order interior point methods - IPMs). If the problem is of a huge-scale, first order methods with acceleration, most notably FISTA will solve the problem fast. Anyhow there is no need to transform the problem to a quadratic one, no need to worry about singularity, and it can be easily and efficiently solved.