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.

  • $\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
    Commented Nov 23, 2016 at 22:52
  • $\begingroup$ the $v_n^{(k)}$ notation is sucky. why not stick with the original "$v_{n-k}$"? $\endgroup$ Commented Nov 24, 2016 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$ Commented Nov 24, 2016 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$ Commented Nov 24, 2016 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$ Commented Nov 24, 2016 at 7:57

3 Answers 3


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)];


X = xcorr(v);

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

  • $\begingroup$ Have you looked on my proof? $\endgroup$
    – Royi
    Commented Jan 15, 2021 at 13:03

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.

  • $\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$ Commented Nov 24, 2016 at 7:18

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.

  • $\begingroup$ You should mark an answer. $\endgroup$
    – David
    Commented Jan 4, 2020 at 10:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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