1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ I'm wondering why the second norm in (1) is not the L1 norm? $\endgroup$
    – William
    Jun 1 '20 at 12:54
  • 1
    $\begingroup$ @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$. $\endgroup$
    – littleO
    Jun 1 '20 at 14:12
  • $\begingroup$ 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? $\endgroup$
    – William
    Jun 1 '20 at 21:48
  • 1
    $\begingroup$ @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. $\endgroup$
    – littleO
    Jun 1 '20 at 21:59
  • $\begingroup$ Thank you @littleO $\endgroup$
    – William
    Jun 1 '20 at 22:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.