# Upper and lower bounds of a ratio involving vector norms

I'm working on a signal processing problem and need to analyze the following expression $$G = \frac{n}{\sum\limits_{i=1}^n |w_i|} \frac{ \sum\limits_{i=1}^n g_i w_i^2}{\sum\limits_{i=1}^n g_i |w_i|}$$ where $|\cdot|$ denotes the absolute value function, $g_i \in [0, \sqrt{n}]$ are positive signal values and $w_i \in \mathbb{R}$ are real-valued weights. The ratio $G$ compares the performance of two signal processing algorithms. The expression $G$ can be rewritten by means of the vectors $\mathbf{w} = (w_1,\ldots,w_n)^T$ and $\mathbf{g} = (g_1,\ldots,g_n)^T$ and vector norms as $$G = \frac{n}{||\mathbf{w}||_1} \frac{||\mathbf{w}||_{2,\mathbf{g}}^2}{||\mathbf{w}||_{1,\mathbf{g}}}$$ where $||\cdot||_1$ and $||\cdot||_2$ denote the standard $L_1$ and $L_2$ (Euclidean norm), respectively, and $||\mathbf{w}||_{p,\mathbf{g}}$ the weighted $L_p$ norm which is $$||\mathbf{w}||_{p,\mathbf{g}} = \left ( \sum\limits_{i=1}^n g_i |w_i|^p \right )^{1/p}$$

How can I give lower and upper bounds for $G$? When is $G=1$?

In a first approach I considered the simple case where the signal is constant, i.e. $g_1 = g_2 = ... = g_n$, so the signal cancels out and the expression $G$ becomes
$$G = \frac{n}{\sum\limits_{i=1}^n |w_i|} \frac{ \sum\limits_{i=1}^n w_i^2}{\sum\limits_{i=1}^n |w_i|} \, ,$$ which is the same as $$G = n \left ( \frac{ ||\mathbf{w}||_{2} }{ ||\mathbf{w}||_{1} } \right )^2 \, .$$ Since for the $L_1$ and $L_2$ vector norm the inequality $||\mathbf{w}||_{2} \leq ||\mathbf{w}||_{1} \leq \sqrt{n} ||\mathbf{w}||_{2}$ holds, the expression $G$ is bounded by $$1 \leq G \leq n \, .$$ Although the simple case looks similar to the original problem, I'm still stuck with the general problem where $g_1 \neq g_2 \neq \ldots \neq g_n$.

In a numerical simulation I evaluated $G$ for a large set of randomly generated vectors (uniformly distributed) with length $n=2, \ldots, 300$ and plotted the obtained minimum value for $G$. The plot increases monotonically from $\approx 0.21$ and seems to go asymptotically to $\approx 1.3$ for large $n$. In addition, $G = 1$ for $n \approx 22$.

How can I determine $n$, for which $G=1$, analytically?

-
You created random vectors for $\mathbf{w}$ and for $\mathbf{g}$, right? What kind of random number generator did you use? – k1next Jan 4 '13 at 20:06
@macydanim Yes, the numbers are chooses with a uniform probability distribution (with Mathematica) in the range $g_i \in [0,\sqrt{n}]$ and $w_i \in [-1,1]$ with $i=1, \ldots, n$. However, changing the range for $w_i$ does not change the result. – Robinaut Jan 5 '13 at 7:36

The sum in the numerator is the inner product of two vectors: $\bf{w}$ and let's call it $\bf{v}$ the vector with components $v_i=g_iw_i$. Then $$\sum_{i=1}^Ng_iw_i^2=\left||\bf{v}\dot\bf{w}\right||_2=||\bf{v}||_2||\bf{w}||_2|\cos\phi|$$ for some angle $\phi$. I've taken the absolute value because in this case we know the sum is non-negative.
Because $g_i\ge0$ the sums in the denominator are the $L_1$ norms of $\bf{v}$ and $\bf{w}$, i.e. $$\sum_{i=1}^Ng_i|w_i|=||\bf{v}||_1$$ so we get $$G=\frac{n||\bf{v}||_2||\bf{w}||_2}{||\bf{v}||_1||\bf{w}||_1}|\cos\phi|$$ assuming $\bf{v}$ and $\bf{w}$ are nonzero. (If $\bf{v}$ is the zero vector, the original expression for $G$ is undefined and so is this expression).
Using the same inequalities on the $L_1$ and $L_2$ norms as you used in your special case now applied to $\bf{v}$ as well as $\bf{w}$ gives $$|\cos\phi|\le G\le n|\cos\phi|$$ with $\phi=0$ only achieved in the special case where $g_i$ is constant over $i$ which makes vector $\bf{v}$ parallel to $\bf{w}$.
If we don't know the value of $\phi$, $|\cos\phi|$ can take any value in $[0,1]$ so the bound becomes $0\le G\le n$ with the lower bound only achieved at $\cos\phi=0$. With the constraint $g_i\ge0$ we can't actually make $\bf{v}$ and $\bf{w}$ orthogonal (quick demonstration: if $||\bf{v}||_1>0$ then $g_i|w_i|>0$ for some $i$ so the sum of non-negative terms $\sum g_iw_i^2$ is greater than 0, and so $|\cos\phi|>0$). Putting it all together the bound is $$0<G\le n$$ Of course in floating point a small enough $G$ will be rounded down to zero. I suspect there is some numerical error in your Monte Carlo work, because for $n=1$ the numerator of $G$ should equal the denominator giving $G=1$.
For $n=2$ the vectors $\bf{v}$ and $\bf{w}$ can be made almost orthogonal to each other, so you will be able to make $G$ arbitrarily close to $0$, at least until numerical issues kick in. That holds for $n>2$ as well: simply set $g_i=0$ for $i>2$ and you're back to the $n=2$ case. If I've understood the last part of the question correctly, the $n$ you are looking for doesn't exist: there is no $n$ large enough to guarantee $G\ge1$. What's probably happening is that for large $n$ the vectors where $G<1$ aren't being sampled, but if you ran the Monte Carlo for long enough (which might be a very long time!) or sampled from different distributions you would eventually find a value of $G<1$ for any $n\ge2$.
Your are right, I started the simulation for $n \geq 2$ and the minimum value for $G$ is $\approx 0.21$. – Robinaut Jan 6 '13 at 11:04