1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Lower Bound on Weighted Sum of Auto Correlation

  1. Nov 23, 2016 #1
    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. jcsd
  3. Nov 25, 2016 #2
    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
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Lower Bound on Weighted Sum of Auto Correlation
  1. Lower sum/ upper sum (Replies: 1)

  2. Lower bound (Replies: 7)

Loading...