# Implementing complex LASSO in Matlab

I want to test LASSO in compressive sensing to reconstruct a sparse signal. I know how LASSO cost function looks like (and I'm fed up with graphs showing different types of norms, I understand exactly why we chose that kind of norm), but I don't know how to find its minimum. There's a function in Matlab https://au.mathworks.com/help/stats/lasso.html but it doesn't work with complex data. For that reason, I want to create my own LASSO function. I've been looking for how to find the minimum of LASSO cost function but find nothing. Can someone tell me where can I find the derivation so I can write my Matlab code?

Any help is appreciated.

Update: I've watched: https://www.youtube.com/watch?v=CjYz7z0usMo&list=PLE6Wd9FR--Ecf_5nCbnSQMHqORpiChfJf&index=22 in 47:00 it shows algorithm. Unfortunately, this is not for under-determined system.

One approach is to rephrase your problem so that it involves only real numbers. I'll work out the details below.

We want to minimize $$L(\beta) = \frac12 \| X \beta - y \|_2^2 + \lambda \| \beta \|_1$$ where $$X \in \mathbb C^{m \times n}$$ and $$y \in \mathbb C^m$$ are given. The optimization variable is $$\beta \in \mathbb C^n$$.

Let's decompose $$X, y$$, and $$\beta$$ as $$X = X_1 + i X_2, \quad y = y_1 + i y_2, \quad \beta = \beta_1 + i \beta_2$$ where $$X_1, X_2 \in \mathbb R^{m \times n}, y_1, y_2 \in \mathbb R^m$$, and $$\beta_1, \beta_2 \in \mathbb R^n$$, and $$i^2 = -1$$.

Note that \begin{align} X \beta &= (X_1 + i X_2)(\beta_1 + i \beta_2 ) \\ &= X_1 \beta_1 - X_2 \beta_2 + i(X_1 \beta_2 + X_2 \beta_1) \end{align} and so $$X \beta - y = X_1 \beta_1 - X_2 \beta_2 - y_1 + i(X_1 \beta_2 + X_2 \beta_1 - y_2).$$ It follows that \begin{align} \| X \beta - y\|_2^2 &= \| X_1 \beta_1 - X_2 \beta_2 - y_1\|_2^2 + \| X_1 \beta_2 + X_2 \beta_1 - y_2\|_2^2 \\ &= \left\| \begin{bmatrix} X_1 & -X_2 \\ X_2 & X_1 \end{bmatrix} \begin{bmatrix} \beta_1 \\ \beta_2 \end{bmatrix} - \begin{bmatrix} y_1 \\ y_2 \end{bmatrix} \right\|_2^2 \end{align} Also, $$\| \beta \|_1 = \sum_{j=1}^n \sqrt{\beta_{1j}^2 + \beta_{2j}^2}$$ where $$\beta_{1j} \in \mathbb R$$ and $$\beta_{2j} \in \mathbb R$$ are the $$j$$th components of $$\beta_1$$ and $$\beta_2$$, respectively.

So your optimization problem can be written as $$\tag{1} \text{minimize} \quad \frac12 \| \tilde X \tilde \beta - \tilde y \|_2^2 + \lambda \| \tilde \beta \|_{2,1}$$ where $$\tilde X = \begin{bmatrix} X_1 & -X_2 \\ X_2 & X_1 \end{bmatrix}, \quad \tilde y = \begin{bmatrix} y_1 \\ y_2 \end{bmatrix}, \quad \tilde \beta = \begin{bmatrix} \beta_1 \\ \beta_2 \end{bmatrix}$$ and $$\| \tilde \beta \|_{2,1} = \sum_{j=1}^n \sqrt{\beta_{1j}^2 + \beta_{2j}^2}.$$ The optimization variable is $$\tilde \beta \in \mathbb R^{2n}$$. Problem (1) is a group lasso problem, with a particular grouping of the variables in the vector $$\tilde \beta$$. It can be solved with any group lasso solver. If you want to implement your own group Lasso solver, it's not too hard to do that using the proximal gradient method.

• I'm wondering why the second norm in (1) is not the L1 norm? Jun 1 '20 at 12:54
• @AymenKareem The $\ell_1$-norm of the vector I'm calling $\tilde \beta$ is actually not equal to the $\ell_1$-norm of $\beta$. Do you agree with my earlier statement that $\| \beta \|_1 = \sum_{j=1}^n \sqrt{ \beta_{1j}^2 + \beta_{2j}^2}$? The $\ell_1$-norm of $\tilde \beta$ is equal to $\sum_{j=1}^n |\beta_{1j}| + |\beta_{2j}|$, which is not equal to $\| \beta \|_1$. Jun 1 '20 at 14:12
• Thank you @littleO. So this means we cannot use lasso function in Matlab for (1) because the norm in the second term is not identical to the norm in the classical LASSO. Right? Jun 1 '20 at 21:48
• @AymenKareem Yes, that's correct. You need a "group lasso" solver. It's not terribly difficult to implement one yourself. Here's a video I made about how to implement a lasso solver using the proximal gradient method. For "group lasso", you can do something quite similar, but since we have a different regularization term (not simply the $\ell_1$-norm) we have to use a different proximal operator. Jun 1 '20 at 21:59
• Thank you @littleO Jun 1 '20 at 22:03