5

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.

Royi
  • 33,983
  • 4
  • 72
  • 179
  • Assume $v_n=1\,\forall\,n\in\mathbb{N}$. Both sides of the inequality become infinite; how do you deal with that case? – MBaz Nov 23 '16 at 22:52
  • the $v_n^{(k)}$ notation is sucky. why not stick with the original "$v_{n-k}$"? – robert bristow-johnson Nov 24 '16 at 06:14
  • 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$). – robert bristow-johnson Nov 24 '16 at 07:41
  • 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. – robert bristow-johnson Nov 24 '16 at 07:46
  • 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). – robert bristow-johnson Nov 24 '16 at 07:57
  • well, since $-\infty – robert bristow-johnson Nov 24 '16 at 18:27

3 Answers3

5

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.

Royi
  • 33,983
  • 4
  • 72
  • 179
2

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.

Maximilian Matthé
  • 5,982
  • 2
  • 10
  • 18
1

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.

Maximilian Matthé
  • 5,982
  • 2
  • 10
  • 18