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 :)
 A: 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]
$$
Just a special case, but hope it helps!
