The FLAC audio codec is able to losslessly compress audio by removing redundancy from an audio signal with (forward) linear prediction and coding the residual of this prediction with a rice code. The reference implementation finds a good predictor by solving a matrix equation know as the Yule-Walker equations. This involves calculating the autocorrelation of a small portion of a signal and plugging it into these equations.
However, to remain fully lossless, all math involving samples has to be done with integers. To achieve this, the solution to the matrix equation mentioned above (which are the predictor coefficients) are stored in a fixed-point form in the FLAC file. Currently, these fixed-point coefficients are obtained by simply solving the matrix equation and rounding the coefficients (with some error distribution to have the predictor not over- or underpredict) but it seems to me there should be a better method, better incorporating the relations between those coefficients.
I took a course on linear algebra quite a few years ago, but computing integer solutions seems a bit beyond my grasp, which is why I've come here to ask for help. I think the problem I'm describing can be formulated as $Ax \approx b$ where $x/2^n \in\mathbb{Z}$. How large n is depends on the encoder settings (choosing this is actually also subject to optimization) and is generally between 4 and 14. I think the problem can also be formulated as $A(x/2^n) \approx b$ with $x\in\mathbb{Z}$.
Now I'm looking for methods to efficiently compute a good solution to this. Generally matrices are 12x12 (max 32x32). I've been looking at integer solutions to matrix equations, but I feel like it all went over my head. It looks like I'm trying to solve a closest vector problem (CVP) and I found something called Kannan's embedding that seems to be reasonably simple to implement.
So my questions are:
- Am I right that this is a closest vector problem
- Is Kannan's embedding a (computationally) efficient way to solve this? Should this be reasonably simple to implement?
- Is there a better way to solve this problem?