Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$$

share|improve this question
add comment

1 Answer

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.