Orthonormalization to use closed form Lasso solution

Question

Given the Lasso problem $$ min_\beta (Y-X\beta)^\top(Y-X\beta) \quad s.t. \|\beta\|_1\leq\lambda, $$ and assuming that X is orthonormal such that $X^\top X=I$, we know that the closed form solution can be written as $$ \hat{\beta}^{Lasso} = sgn(\hat{\beta}^{LS})(|\hat{\beta}^{LS}|-\lambda)_+, $$ where $\hat{\beta}^{LS}=X^\top Y$.

However, even if X is non-orthonormal, we can use a SVD transformation of $X^\top X$ to generate transformed data $\tilde{X}$ such that $\tilde{X}^\top \tilde{X} = I$, and apply the Lasso to the transformed data. In particular, consider the SVD: $$ X^\top X= Q\Delta Q^\top $$ and the transformed matrix $\tilde{X}=XQ\Delta^{-1/2}$, so that $\tilde{X}^\top \tilde{X} = I$.

Next, using the transformed data $(Y,\tilde{X})$, we get the orthonormalized estimate: $\hat{\tilde{\beta}}^{Lasso} = sgn(\hat{\tilde{\beta}}^{LS})(|\hat{\tilde{\beta}}^{LS}|-\lambda)$, where $\hat{\tilde{\beta}}^{LS} = \tilde{X}^\top Y$.

The non-orthonormalized estimate can be recovered as $\hat{\beta}^{Lasso} = Q\Delta^{-1/2}\hat{\tilde{\beta}}^{Lasso}$.

$\textbf{Question}$: This seems like a valid method of estimating the Lasso and such orthonormalization technique is used in the Group Lasso context (for e.g. in these lecture notes and in Wei, Huang and Li (2011)). However, I am unable to find anything that discusses this as a way to exploit the closed form solution for the Lasso. I am thinking that perhaps the SVD of a large data matrix might be computationally expensive relative to numerical/iterative methods. Are there any reasons why this is not done?

Answer 1

I found out the problem with the proposed estimation procedure thanks to suggestions from @Tim Mak.

The logic above essentially treats all the variables as belonging to one and only one group. The Lasso estimation above will hence pick either all variables or none. You can see this in that if $\hat{\tilde{\beta}}^{Lasso}$ contains at least 1 non-zero element, $\hat{\beta}^{Lasso}$ will not have any zero elements, and if $\hat{\tilde{\beta}}^{Lasso} = \mathbf{0}$, then $\hat{\beta}^{Lasso}= \mathbf{0}$.

The correct way to approach it, would be to treat each and every variable as belonging to its own group, and to do what is done in the Group Lasso literature.

Let $J$ be the number of variables and $x_j$ be the data column of the j-th variable. Transform the column: $\tilde{x}_j = (\sqrt{x_j^\top x_j})^{-1} x_j$, so that $\tilde{x}_j ^\top \tilde{x_j} = 1$.

Apply the coordinate descent algorithm in Yuan and Lin (2006) or Wei, Huang and Li (2011), to get $\hat{\tilde{\beta}}_j$ and apply the reverse transformation $\hat{\beta}^{Lasso}_j = (\sqrt{x_j^\top x_j})^{-1} \hat{\tilde{\beta}}_j$ for each variable $j$.

$\textbf{Conclusion}$ This still requires an iterative algorithm to calculate the (group) Lasso estimate, and hence it is not possible to exploit the closed form solution for the Lasso even with orthonormalization.