# Modification of Standard LASSO Problem for $N$ Observations

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

• 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]$. – Michael Sep 8 '18 at 20:39
• 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$. – Maxtron Sep 8 '18 at 20:43
• At first my comment said "block diagonal" but I quickly changed that, see my edited comment. It is a "block structure," not "block diagonal." – Michael Sep 8 '18 at 20:43
• @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. – Royi Sep 8 '18 at 21:13
• Tangential comment, but when you say "gradient descent algorithms", I assume you mean "proximal gradient" perhaps, since the LASSO objective function is nondifferentiable. – 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 :-).

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