What is a sparse vector and which role does the $l_0$ norm play?

Question

In a paper I read "define the sparsity of $\theta \in \mathbb{R}^J$ by its $l_0$ norm $\lVert \theta \lVert_0$". What is a sparse vector, which role does the $l_0$ norm play, and how is it defined?

Answer 1

As far as I know 0-norm, just counts the number of nonzero entries. Thus for a vector $v = (v_1,...,v_n)$ we would have that $\|v\|_0 = \sum_{v_i\neq 0}1 = \#$ of non-zero $v_i$.

Note: Some authors normalize $\|\cdot\|_0$ by diving by $n$ so that $0\leq\|\cdot\|_0\leq1$

A sparse vector is one that has very few non-zero entries. So the smaller the $\|v\|_0$ the more sparse the vector $v$.

Finally, it's worth pointing out that $\|\cdot\|_0$ does not obey the triangle inequality so is not actually a norm.

Answer 2

A sparse vector is a vector of big dimension (e.g., $x\in\mathbb{R}^n$ for large $n$), but with only very few non-zero coordinates. ("Morally $n$, actually $k$ coordinates.")

That's what the $\ell_0$ "norm" captures: it is exactly the number of non-zero coordinates: $$ \lVert x\rVert_0 = \lim_{\alpha\to 0^+} \lVert x\rVert_\alpha = \left(\sum_{k=1}^n \lvert x\rvert^\alpha\right)^{1/\alpha} = \sum_{k=1}^n \mathbb{1}_{(0,\infty)}(\lvert x\rvert) $$