# Sparseness of a Vector

The sparseness of a vector is defined a follows: $$\psi(\textbf{x}) = \frac{\sqrt{n}-\frac{\left(\sum_{i} x_i \right)}{\sqrt{\sum_{i} x_{i}^{2}}}}{\sqrt{n}-1}$$

So $\psi(\textbf{x}) =0$ if $\sqrt{n} = \frac{\left(\sum_{i}x_i \right)}{\sqrt{\sum_{i} x_{i}^{2}}}$ or if $$\sqrt{n} \sqrt{\sum_{i} x_{i}^{2}} = \sum_{i} x_i$$

How does imply that all the $x_i$ are equal? Cauchy-Schwarz?

Likewise $\psi(\textbf{x}) = 1$ iff $\textbf{x}$ contains a single non-zero element. How does this follow? We know that $$\sqrt{n}-\frac{\left(\sum_{i} x_i \right)}{\sqrt{\sum_{i} x_{i}^{2}}} = \sqrt{n}-1$$

-

For the first part, yes, this follows from Cauchy-Schwarz. Let $v=(1,1,\ldots,1)$. By CS, $|x\cdot v|\leq \|v\| \|x\|=\sqrt{n}\|x\|$, with equality if and only if $x=\lambda v$ for some $\lambda$. Now note that one of the terms you are dealing with is just the length of $x$, and the other is $x\cdot v$. Combining this observation with what you already have, we see $\psi(x)=0$ if and only if $x$ is a multiple of $v$.

For the second question, we want to determine when $\psi(x)=1$ (N.B., I think the definition should be $$\psi(\textbf{x}) = \frac{\sqrt{n}-\frac{\left(\sum_{i} \left|x_i \right| \right)}{\sqrt{\sum_{i} x_{i}^{2}}}}{\sqrt{n}-1}$$ as this would guarantee the sparseness is always between $0$ and $1$. I will make this assumption in what follows. Note that without this change, the $\psi(-v)$ is greater than 2, when objectively, it is just as un-sparse as $v$).

By the work you've done above $\psi(x)=1$ if and only if $|x \cdot v|=\|x\|$. Dividing $x$ by $\|x\|$, we can assume that $x$ is a unit vector. Moreover, by the change I made to the definition, we may assume that each coordinate of $x$ is non-negative, that is $x\cdot e_i\geq 0$ for all $i$. We want to show that this implies that $1\leq x\cdot v$, with equality if and only if $x=e_i$ for some $i$.

Unfortunately, I don't know any slick proof. The best I can come up with is to reduce things to the 2 dimensional case, which is easy to prove with calculus (or geometry, if you are so inclined).

First, for the two variable case: we wish to show that if $(x,y)$ is in the first quadrant of some circle centered at the origin, then $x+y$ is minimized when one of the coordinates is $0$. This follows from convexity of the circle, but there are tons of other proofs.

For the general case, assume that $\|x\|=1$, $x\cdot e_i\geq 0$ for all $i$. If we are trying to minimize $x\cdot v$ and there are two nonzero coordinates, say $x_i$ and $x_j$, then we can find further reduce $x\cdot v$ by replacing one of the coordinates with $\sqrt{x_i^2+x_j^2}$ and the other with $0$. Thus, it is necessary that all but one of the coordinates be zero, so $x=e_i$ for some $i$. However, $e_i\cdot v=1$, and so they are all minima.

-
Regarding the case $\psi(x)=1$, squaring $\sum_i|x_i|=\sqrt{\sum_i x_i^2}$ yields $\sum_i x_i^2+\sum_{i\ne j} |x_i|\cdot|x_j|=\sum_i x_i^2$. Hence $\psi(x)=1$ implies $\sum_{i\ne j} |x_i|\cdot|x_j|=0$ which implies $|x_i|\cdot|x_j|=0$ for every $i\ne j$, that is, $x_i\ne0$ for at most one index $i$. QED. –  Did Jan 22 '12 at 9:21