# Weighted Sum of Auto Correlation - Lower Bound

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.

• 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}$"? Nov 24 '16 at 6: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$). Nov 24 '16 at 7: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. Nov 24 '16 at 7: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). Nov 24 '16 at 7:57

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.

• You should mark an answer. Jan 4 '20 at 10:21

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


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

• Have you looked on my proof?
– Royi
Jan 15 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.

• 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. Nov 24 '16 at 7:18