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.

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?

Please help me with this problem, I am thankful for any idea! Many thanks in advance.

share|improve this question
    
You created random vectors for $\mathbf{w}$ and for $\mathbf{g}$, right? What kind of random number generator did you use? –  sonystarmap 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
add comment

1 Answer

up vote 2 down vote accepted

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

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