The traditional LASSO problem is given as \begin{align} \arg \min_x \frac{1}{2} || y - A x ||_2^2 + \lambda ||x||_1. \end{align} where $y \in \mathbb{R}^{P \times 1}$, $A \in \mathbb{R}^{P \times Q}$, and $x \in \mathbb{R}^{Q \times 1}$. The above problem can be solved using proximal gradient descent algorithms. Suppose, we have multiple observations and an objective function of the form \begin{align} \arg \min_x \frac{1}{2} \sum_{i=1}^N || y_i - A_i x ||_2^2 + \lambda ||x||_1. \end{align} How do we solve LASSO problem?

Edit: Changed it to proximal gradient

  • 2
    $\begingroup$ Your second problem looks like a special case of the first one, where the $A$ matrix has a block structure $A = [A_1; A_2; ...; A_N]$. $\endgroup$ – Michael Sep 8 '18 at 20:39
  • $\begingroup$ But if I convert it into block diagonal, $x$ will be modified to $[1,\ldots,1]^T \otimes x$. I will no longer be imposing sparsity on $x$ but on the modified $x$. $\endgroup$ – Maxtron Sep 8 '18 at 20:43
  • $\begingroup$ At first my comment said "block diagonal" but I quickly changed that, see my edited comment. It is a "block structure," not "block diagonal." $\endgroup$ – Michael Sep 8 '18 at 20:43
  • 2
    $\begingroup$ @Michael, I didn't see your comment and answered. Please feel free, you you'd like, to copy & paste my answer and I will delete mine. $\endgroup$ – Royi Sep 8 '18 at 21:13
  • 1
    $\begingroup$ Tangential comment, but when you say "gradient descent algorithms", I assume you mean "proximal gradient" perhaps, since the LASSO objective function is nondifferentiable. $\endgroup$ – littleO Sep 8 '18 at 21:51

You can recreate the original form by defining new matrices.

Let's define:

$$ \hat{A} = \left[ {A}_{1} ; {A}_{2}; \cdots ; {A}_{N} \right] $$

Namely concatenate the matrices on the vertical axis (One beneath the other, I used MATLAB style).

Do the same for the observation vector:

$$ \hat{y} = \left[ {y}_{1} ; {y}_{2}; \cdots ; {y}_{N} \right] $$

Now, just rewrite the problem:

$$ \arg \min_{x} \frac{1}{2} \sum_{i = 1}^{N} {\left\| {A}_{i} x - {y}_{i} \right\|}_{2}^{2} + \lambda {\left\| x \right\|}_{1} = \arg \min_{x} \frac{1}{2} {\left\| \hat{A} x - \hat{y} \right\|}_{2}^{2} + \lambda {\left\| x \right\|}_{1} $$

This you know how to solve :-).

  • $\begingroup$ Thanks, Royi. You are always helpful. :) $\endgroup$ – Maxtron Sep 8 '18 at 21:15

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.