flac dev - Sep 2018 - Confusion about linear prediction within flac

Hi,

I'm researching lossless compression for a highschool mathematics
research essay and am fairly confused about how the linear prediction
coefficients are solved for within flac.

As far as I understand, Levinson Durbin Recursion is used to solve for
these coefficients, however, what I don't understand is what the
toeplitz matrix is composed of. I found sources using samples from
within the time series to construct a linear system: 
http://practicalcryptography.com/miscellaneous/machine-learning/linear-prediction-tutorial/

However, talkbox, a scikit for signal proccessing (
https://github.com/cournape/talkbox/tree/master/scikits/talkbox/linpred
), first autocorrolates the signal using discrete inverse Fourier
transforms which then passes it to the levinson durbin algorithm.

I would really appriciate an explanation or information on a good
resource to learn more about how the prediction coefficients are solved
for.

Once the lpc coefficients have been solved, as far as I understand you
must also store part of original signal with length equal to the
prediction order since you need the previous samples to predict the
next sample of which only the residual is known. For the next values
the  residual is used to retrieve the original value which is fed into
the predction model to further reconstruct the time series. Is this
correct?

Kind Regards,
Robin Decker

Robin Patrick Decker wrote:
> I would really appriciate an explanation or information on a good
> resource to learn more about how the prediction coefficients are solved
> for.
The Wikipedia page on this subject is not terrible:
https://en.wikipedia.org/wiki/Linear_prediction

The very high-level answer is that if want to choose your coefficients 
to minimize the mean squared error of the prediction, then you get a 
least-squares problem where the matrix you're inverting is just the 
auto-correlation matrix of your signal (the Yule-Walker equations). The 
discrete Fourier transform is just a computationally efficient means of 
computing the auto-correlation, at least if your order is sufficiently high.
> Once the lpc coefficients have been solved, as far as I understand you
> must also store part of original signal with length equal to the
> prediction order since you need the previous samples to predict the
> next sample of which only the residual is known. For the next values
> the  residual is used to retrieve the original value which is fed into
> the predction model to further reconstruct the time series. Is this
> correct?
Yes.

Thank you for the clarification. It has helped tremendously!

I'm a little unsure about how the autocorrolation is calculated. For
the calculation of the autocorrolation with lag i, x(n)x(n-i) is looped
and summed through from n = 0 to the length of the original signal.
This summation is then divided by the length of the signal (I'm
assuming this is what expected value means?). i is then increased from
1 to p (model order) to create an array of autocorrolations with
different lags. Am I understanding this correctly?

Thanks again for all the help.

Kind Regards,
Robin

On Sun, 2018-09-09 at 13:01 -0700, Timothy B. Terriberry
wrote:
> Robin Patrick Decker wrote:
> > I would really appriciate an explanation or information on a good
> > resource to learn more about how the prediction coefficients are
> > solved
> > for.
> 
> The Wikipedia page on this subject is not terrible:
> https://en.wikipedia.org/wiki/Linear_prediction
> 
> The very high-level answer is that if want to choose your
> coefficients 
> to minimize the mean squared error of the prediction, then you get a 
> least-squares problem where the matrix you're inverting is just the 
> auto-correlation matrix of your signal (the Yule-Walker equations).
> The 
> discrete Fourier transform is just a computationally efficient means
> of 
> computing the auto-correlation, at least if your order is
> sufficiently high.
> 
> > Once the lpc coefficients have been solved, as far as I understand
> > you
> > must also store part of original signal with length equal to the
> > prediction order since you need the previous samples to predict the
> > next sample of which only the residual is known. For the next
> > values
> > the  residual is used to retrieve the original value which is fed
> > into
> > the predction model to further reconstruct the time series. Is this
> > correct?
> 
> Yes.