# Lower Bound on Weighted Sum of Auto Correlation

Tags:
1. Nov 23, 2016

### Drazick

1. The problem statement, all variables and given/known data

Given $v = {\left\{ {v}_{i} \right\}}_{i = 1}^{\infty}$ and defining ${v}_{n}^{\left( k \right)} = {v}_{n - k}$ (Shifting Operator).

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

Basically, a Weighted Sum of the Auto Correlation Functions must be greater then its value at Zero.
Namely, the Negative Values can not be summed to match the positive values.

2. Relevant equations
Probably some variant of Cauchy Schwartz inequality.
Maybe taking advantage of the Auto Correlation function being Symmetric.

3. The attempt at a solution
I understand that behind the scenes the correlations of the shifted versions cant' have negative value which is up to half of the norm of the vector $v$.
Yet I couldn't use it to prove the above.

Thank You.

2. Nov 25, 2016

### Drazick

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][1] is [Hermitian Function][2].

Using the definition of [Convolution][3] 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][4] 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.

[1]: https://en.wikipedia.org/wiki/Autocorrelation
[2]: https://en.wikipedia.org/wiki/Hermitian_function
[3]: https://en.wikipedia.org/wiki/Convolution
[4]: https://en.wikipedia.org/wiki/Convolution_theorem