# Distribution (or Expectation) of Number of Non-Zero Coefficients in L1-Regularized Regression

Related to this question, suppose we're performing $$L1$$-regularized linear regression. For a given regularization coefficient $$\lambda$$, what is the distribution over the number of non-zero parameters? If that question is too hard, can anything be said about the expected number of non-zero parameters?

To add some notation, let $$A$$ be a real $$m \times n$$ matrix. The $$L1$$-regularized optimization problem is $$x^* = \text{argmin}_{x \in \mathbb{R}^N} \quad \frac12 \| Ax - b \|_2^2 + \lambda \| x \|_1$$

Question: For a given $$\lambda$$, what is the expected number of non-zero elements of $$x^*$$, or more generally, what is the distribution of non-zero elements of $$x^*$$ ?

Edit: Presumably one needs to place assumptions on $$A$$ and $$b$$ to make statements. I don't know what assumptions lead to what conclusions, so I'm trying to phrase this question as generally I can. All assumptions are welcome if they lead to nontrivial answers :)

For the orthonormal case, $$\ell^1$$-regularized linear regression (aka the Lasso) has a closed form solution, which makes this problem feasible.
To make the compuation easier, I take $$m=n$$ and $$A=I$$ in the following. This is not necessary for the approach to work, but it makes the formulas much simpler. We then have: $$x^*_j=sign(\hat{x}_j)\max\{0,|\hat{x}_j|-\lambda\}$$ Here, $$\hat{x}$$ is the minimizer of $$||Ax-b||_2^2$$, in our case $$\hat{x}=b$$. So, $$x^*_j\neq 0$$ if and only if $$|b_j|>\lambda$$. So, we found the exact condition which determines whether $$j$$ is in the support of $$x^*$$ or not.
To find the distribution of the number of non-zero parameters, we need to know what distribution $$b$$ has. If $$b$$ is not random, the support is a deterministic function of $$\lambda$$, described by the criterion above. Let's consider a random example. Take $$b_j=a_j+\epsilon_j$$, where $$a\in\mathbb{R}^m$$ is fixed (non-random) and $$\epsilon$$ is random (noise). Then, $$\mathbb{P}[x_j^*\neq 0] =\mathbb{P}[|a_j+\epsilon_j|>\lambda] =\mathbb{P}[a_j+\epsilon_j>\lambda]+\mathbb{P}[-a_j-\epsilon_j>\lambda]$$ $$=\mathbb{P}[\epsilon_j>\lambda-a_j]+\mathbb{P}[-\epsilon_j>\lambda+a_j]$$ Now, if the $$a_j$$ are identical for all $$j$$, you have a Binomial distribution with $$n$$ observations and probability-parameter $$\mathbb{P}[\epsilon_j>\lambda-a_j]+\mathbb{P}[-\epsilon_j>\lambda+a_j]$$. If not, you get a Poisson Binomial distribution, with $$n$$ observations and probability-parameters $$\mathbb{P}[\epsilon_1>\lambda-a_1]+\mathbb{P}[-\epsilon_1>\lambda+a_1],\ldots,\mathbb{P}[\epsilon_m>\lambda-a_m]+\mathbb{P}[-\epsilon_m>\lambda+a_m]$$