Measuring "concentration" in an expansion

Question

Suppose we have a vector $v \in \mathbb{R}^{n}$ which we expand in some orthonormal basis $\{g_{m}\}$ of $\mathbb{R}^{n}$: \begin{align*} v = \sum_{m=1}^{n} a_{m}g_{m} \end{align*} I want to measure how "concentrated" $v$ is in the basis $\{g_{m}\}$. To wit, I would like some measurement that is maximized when $a_{m} = 0$ for all but one $m$, and minimized when all the $a_{m}$ have the same magnitude. Is there a nice way to measure this "concentration" (preferably easily computed), and is there standard terminology for it?

Answer 1

The Gini coefficient is an excellent way to measurement sparsity. Here, we use the following definition of Gini coefficient: \begin{align*} G(v) := \frac{1}{n-1}\left[ \frac{2}{\left\| v\right\|_{1} } \sum_{i=0}^{n-1} (i+1)|v_i^{(s)}| - n - 1 \right] \end{align*} where $v_{i}^{(s)}$ is the $i$th coefficient of the vector $v$ sorted by increasing magnitude. Note that this definition differs from (say) Wikipedia's definition, which only applies it to wealth inequality, where each element is real and non-negative.

We have some nice properties of $G$:

• If $v_{j} \mapsto e^{i\theta_j}v_{j}$, we feel intuitively that the sparsity is unchanged, and indeed $G(v)$ is invariant under these phase changes.

• If $0 \ne \lambda \in \mathbb{C}$, it is easy to see that $G(\lambda v) = G(v)$ (changing units doesn't change sparsity).

• If $v_{j} = 0$ for all but one $j$, then $G(v) = 1$, which is the maxima of $G$. If all coefficients are of equal magnitude, then $G(v) = 0$, which is the minima of $G$.

• If $\Pi$ is a permutation of the elements of $v$, the $G(\Pi v) = G(v)$. (Permutations don't affect sparsity.) The particular way that the Gini coefficient achieves this is via sorting, which is not ideal due to it requiring $\mathcal{O}(n\log n)$ operations, but the invariance is indeed manifest.

• The property of the Gini coefficient not shared by the Hoyer measure (a normalized ratio of $\ell_1$ and $\ell_2$ norms) is its invariance under concatenation: $G(v\oplus v) = G(v)$. How much weight should be given to this property is unclear, especially given the sorting requirement.