# Derivation of Yule-Walker Equation for LPC

I have derived the Yule-Walker equation as shown below.

\begin{align} \hat s(n) &= -\sum_{k=1} ^ p a_k s(n-k)\\ e(n) &= s(n) - \hat s(n) = s(n) + \sum_{k=1}^pa_k s(n-k) \end{align}

In order to minimize the power of the error: $\displaystyle \frac{\partial E\left[\lvert e(n)\rvert^2\right]}{\partial{a_k}} = 0 \quad \text{and}\quad \lvert e(n)\rvert^2 = e(n)e^*(n)$

$$E\left[\left(s(n) + \sum_{k=1}^p a_k s(n-k)\right)e^*(n)\right]= E\left[s(n)e^*(n)\right] + \sum_{k=1}^p a_k E\left[s(n-k)e^*(n)\right]$$

\begin{align} &\frac{\partial E\left[\lvert e(n)\rvert^2\right]}{\partial{a_k}} = E\left[s(n-k)e^*(n)\right]=0\\ &E\left[s(n-k)\left(s^*(n)+\sum_{i=1}^p a^*_is^*(n-i)\right)\right]=0\\ &E\left[s(n-k)s^*(n)\right]+ \sum_{i=1}^p a^*_i E\left[s(n-k)s^*(n-i)\right]=0\\ &\sum_{i=1}^pa^*_i r(i-k) = -r(k) \end{align}

A few things confuse my mind. So I have 4 questions:

1. Is this derivation true?

2. I am not sure why we do the partial derivation in terms of $a_k$.

3. $e^*(n)$ includes $a^*_i$ coefficients, too. Why is $e^*(n)$ not affected by the derivation operation?

4. What is the meaning of all these complex conjugates here? How do they affect the numeric calculation?

• @Matt L. Shouldn't there be the multiplier $p$ in $\frac{\partial E[|e(n)|^2]}{\partial{a_k}} = pE[s E[s(n-k)e^*(n)]=0$ ? Thank you. – groove Jun 25 '13 at 20:44
• I removed it because if you have a sum $a_1b_1+a_2b_2\ldots +a_pb_p$ and you take the derivative w.r.t. $a_k$ you simply get $b_k$, regardless of the value $p$. – Matt L. Jun 25 '13 at 20:47
• @Matt L. Oh, I thought as if $E[\cdot]$ is constant. But how does the symbol $\sum_{k=1}^p$ disappear then? – groove Jun 25 '13 at 21:03
• If you take the derivative with respect to just one of the coefficients, then only one term in the sum remains after taking the derivative. Just look at the example in my previous comment. The derivative of $\sum_ia_ib_i$ w.r.t. $a_k$ is $b_k$, so the sum has disappeared. – Matt L. Jun 25 '13 at 21:09

1. Yes, your derivation is correct. There is just a minor inconsistency in your definition of the auto-correlation function $r(k)$. If you choose to define $$r(k) = E[s(n-k)s^*(n)]$$ then $E[s(n-k)s^*(n-i)]$ equals $r(k-i)$ or, equivalently, $r^*(i-k)$, but not $r(i-k)$. So the last equation should read $$\sum_{i=1}^pa^*_i r^*(i-k) = -r(k)$$
2. You take the derivative w.r.t. to $a_k$ because these are the coefficients that you can choose as to minimize the error. They are the unknowns in your problem.
3. The fact that $e^*(n)$ can be viewed as a constant when taking the derivative w.r.t. $a_k$ has to do with how computing the gradient w.r.t. complex variables works. It is equivalent to taking the derivatives w.r.t. to the real and imaginary part of the coefficients separately, but the complex technique is more elegant and easier (at least as soon as you understand it). I've explained this technique in this answer.
4. The complex conjugates just pop up because you consider $|e(n)|^2$ in your optimization objective: $|e(n)|^2=e(n)e^*(n)$. You wouldn't need them at all if you only considered real-valued coefficients $a_k$ and real-valued signals $s(n)$.