1
$\begingroup$

Given a vector $ v $ with elements $ {\left\{ {v}_{n} \right\}}_{n = - \infty}^{\infty} $ and denoting $ {v}_{n}^{\left( k \right)} = {v}_{n - k} $, namely, a shifted vector by $ k $ elements (Mind the vector is infinitely long).

How could one prove that there exist $ \alpha > 0 $ such that:

$$ \sum_{k = -\infty}^{\infty} {2}^{- \left| k \right| } \left \langle {v}^{\left( 0 \right)}, {v}^{\left( k \right)} \right \rangle \geq \alpha {\left\| v \right\|}^{2} $$

One could see it a weighted sum of the Auto Correlation Function of the vector $ v $.

Hence can be written as:

$$ \sum_{k = -\infty}^{\infty} {2}^{- \left| k \right| } \sum_{n = -\infty}^{\infty} {v}_{n} {v}_{n - k} \geq \alpha {\left\| v \right\|}^{2} $$

My understanding of the question is that there some bounderay on how slow the Auto Correlation decays (There is nothing special about $ {2}^{-\left| k \right|} $ there, it can be replaced by any $ \frac{1}{c} > 1 $).

Thank You.

$\endgroup$
  • $\begingroup$ Assume $v_n=1\,\forall\,n\in\mathbb{N}$. Both sides of the inequality become infinite; how do you deal with that case? $\endgroup$ – MBaz Nov 23 '16 at 22:52
  • $\begingroup$ the $v_n^{(k)}$ notation is sucky. why not stick with the original "$v_{n-k}$"? $\endgroup$ – robert bristow-johnson Nov 24 '16 at 6:14
  • $\begingroup$ Royi, your response does not answer why you can't just replace it all with "$v_{n-k}$", but that is cosmetic. the real problem you have is defining the inner product when $k\ge 1$ then you will have an index for $v_n$ that is out of range ($n < 1$). $\endgroup$ – robert bristow-johnson Nov 24 '16 at 7:41
  • $\begingroup$ my suggestion is that you need to define $v_n$ for all $n\in\mathbb{Z}$, not just the positive integers. perhaps $v_n = 0$ for some known values of $n$. perhaps $v_n$ is a finite energy signal. or perhaps it is a finite power signal. or perhaps $v_n$ is periodic or stochastic. from such an axiom, you can explicitly express how the inner product is defined. $\endgroup$ – robert bristow-johnson Nov 24 '16 at 7:46
  • $\begingroup$ better yet (i dunno why i didn't say this at first), you should use current convention in DSP texts and replace all "$v_n$" with "$v[n]$" and save the subscripts for a different purpose (like a vector of signals). and lose that superscript completely (reserving it for exponents). $\endgroup$ – robert bristow-johnson Nov 24 '16 at 7:57
2
$\begingroup$

I add another answer, showing a counterexample to the claim.

Assume a sequence given by

$$ v_n=(-1)^n \text{ for } n=1\dots N\\ v_n=0 \text{ otherwise }. $$ Its autocorrelation $R_v[1]$ is negative with $$ R_v[1]<-R_v[0]/2 $$.

See this Matlab script:

n = 1:10;

v = [(-1).^n zeros(1,100)];

subplot(2,2,1);
stem(v);

subplot(2,2,2);
X = xcorr(v);
stem(xcorr(X));

[min(X), max(X)]

It provides this output:

ans =

    -9    10

plot output

Hence, there need to be some additional constraints on $v$ to make the assumption always valid.

$\endgroup$
1
$\begingroup$

This is only a partial answer.

Assume that $\|v\|^2<\infty$ (as has been questioned by MBaz). I suppose $\left<a,b\right>$ means inner product. Then $\left<v^{(0)},v^{(k)}\right>$ is the Autocorrelation $R_v[k]$. Further note, that $\|v\|^2=R_v[0]$ and that $|R_v[k]|<R_v[0]$.

Then, we can split the sum:

$$ \sum_{k=-\infty}^{\infty}2^{-|k|}R_v[k]=R_v[0]+\sum_{k=1}^{\infty}2^{-k}(R_v[k]+R_v[-k]) $$

If you have $R_v[k] > 0, \forall k$, the solution is trivial, e.g. $\alpha=1$ suffices. The problem appears, when the second term becomes negative. However, we can bound it:

$$ \sum_{k=1}^{\infty}2^{-k}(R_v[k]+R_v[-k])>-\sum_{k=1}^{\infty}2^{-k}2R_v[0]=-2R_v[0] $$

However, this bound is too small, yielding

$$ \sum_{k=-\infty}^{\infty}2^{-|k|}R_v[k]>-R_v[0]. $$

If you can encorporate some decay properties of the autocorrelation to make the bound more tight, the solution will be there.

$\endgroup$
  • $\begingroup$ It would have been good, if you already wrote what you had in the beginning. Then, I wouldn't have needed to have write my post. $\endgroup$ – Maximilian Matthé Nov 24 '16 at 7:18
1
$\begingroup$

Defining $ a \left[ k \right] = {2}^{- \left| k \right|} $.
Moreover, the Auto Correlation function of $ v $ defined as $ {r}_{vv} \left[ k \right] = \left \langle {v}^{\left( 0 \right)}, {v}^{\left( k \right)} \right \rangle = \sum_{n = -\infty}^{\infty} {v}_{n} {v}_{n - k} $.
Pay attention that Auto Correlation is Hermitian Function.

Using the definition of Convolution one could write:

$$ \left( {r}_{vv} \ast a \right) \left[ 0 \right] = \sum_{k = -\infty}^{\infty} {2}^{- \left| k \right| } \left \langle {v}^{\left( 0 \right)}, {v}^{\left( k \right)} \right \rangle $$

Using the Convolution Theorem one could write that:

$$ \left( {r}_{vv} \ast a \right) \left[ 0 \right] = \int_{- \pi}^{\pi} {R}_{vv} \left( \omega \right) A \left( \omega \right) d \omega $$

Where $ R \left( \omega \right) $ and $ {R}_{vv} \left( \omega \right) $ are the DTFT of $ {r}_{vv} \left[ k \right] $ and $ a \left[ k \right] $ respectively.

One should notice the DTFT of $ a \left[ k \right] $ is defined only one sided. Yet since its symmetrical it can well calculated:

$$ \begin{align*} A \left( \omega \right) & = DTFT \left\{ a \left[ k \right] \right\} = \sum_{k = -\infty}^{\infty} a \left[ k \right] {e}^{-j \omega k} = \sum_{k = 0}^{\infty} {2}^{-k} {e}^{-j \omega k} + \sum_{k = 0}^{\infty} {2}^{-k} {e}^{j \omega k} - 1 \\ & = \frac{1}{1 - 0.5 {e}^{-j \omega}} + \frac{1}{1 - 0.5 {e}^{j \omega}} - 1 = \frac{1 - {c}^{2}}{1 - 2 c \cos \left( \omega \right) + {c}^{2}} = \alpha > 0 \quad \forall c < 1 \end{align*} $$

In the above $ c = {2}^{-1} = 0.5 $ yet actually this will hold for any $ c < 1 $.

So the integral is given by:

$$ \begin{align*} \int_{- \pi}^{\pi} {R}_{vv} \left( \omega \right) A \left( \omega \right) d \omega & = \int_{- \pi}^{\pi} {R}_{vv} \left( \omega \right) \frac{1 - {c}^{2}}{1 - 2 \alpha \cos \left( \omega \right) + {c}^{2}} d \omega \\ & \geq \alpha \int_{- \pi}^{\pi} {R}_{vv} \left( \omega \right) d \omega = \alpha {\left\| v \right\|}^{2} \end{align*} $$

As requested.

By the way the result must be real since $ a \left[ k \right] $ is symmetric and $ {r}_{vv} $ is hermitian function and hence its transform is real.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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