Compression algorithm for statistical data with a desired outcome size

Question

I did some basic research on regular lossy and lossless compression algorithms but somehow I couldn't really figure the right direction for the information I need.

My basic problem is that I would like to compress a series of numbers with an unknown number of data points (can be 10, can also be a 1000). The numbers themselves are domain-specific in a way that I know what they mean. For example I have LAT/LONG from GPS-Data but also Degrees from a Gyroscope or Acceleration in G's from an Accelerometer.

What I am doing is basically whenever something changes for example in acceleration I store the value. At the end what I want to do is to compress this series of data by providing the maximum size of the compressed data which should then affect not the data itself but its actual accuracy. For example acceleration would always result in a simple diagram at the end with more or less accuracy depending on the provided output size.

Does something like that exists? Could you maybe throw me into the right direction?

The basic idea is to become independent from time (like store the accel value every XX seconds) and instead store all data changes. Then being able to set the "resolution" by time say if I then get this compressed data only every 10 minutes the data is less accurate (but still close enough) to then saying I get the compressed data every 1 minute.

I hope its understandable if not please let me know so I can try to explain the issue a little bit further.

Answer 1

I don't know of any scheme, but it's possible to define one, so I'll propose one here. In particular, one possibility would be to compress this into a piecewise-linear function, where you replacing a segment of data with a line (a piece), and where you choose which segments to do that to in a way that minimizes the loss. This might work well if your data contains occasional periods of activity followed by long stretches of inactivity.

Here is a candidate metric to measure how much loss is incurred by the compressed version of the data. Suppose you have data points $(x_i,y_i)$; and after compression and decompression you assign $\hat{y}_i$ to $x_i$. Then I suggest measuring the loss as

$$L = \sum_i (y_i - \hat{y}_i)^2.$$

Then it is possible to use dynamic programming to construct a piecewise linear approximation that uses $k$ pieces and, out of all such piecewise linear approximations, choose the one minimizes the loss $L$. In particular, let $A[i,j]$ denote the lowest-loss piecewise linear approximation for $x_1,\dots,x_i$, using at most $j$ pieces. Then we have a recursive relationship

$$A[i,j+1] = \min_{i_0} A[i_0,j] + \ell_{i_0+1,i}$$

where $\ell_{i_0+1,i}$ denotes the loss associated with the best-fit line going through points $(x_{i_0+1},y_{i_0+1}),\dots,(x_i,y_i)$ (can be found using linear regression). You can then fill in the entries of the $A$ matrix using dynamic programming and find the best piecewise linear approximation that uses $k$ pieces.

This lets you find the best piecewise linear approximation, given a maximum size $k$ for the compressed data (since the size of the compressed data is proportional to $k$). Of course, you can generalize this idea to use piecewise polynomial functions or some other form of approximation.

Answer 2

Does something like that exists? Could you maybe throw me into the right direction?

The basic idea is to become independent from time (like store the accel value every XX seconds) and instead store all data changes. Then being able to set the "resolution" by time say if I then get this compressed data only every 10 minutes the data is less accurate (but still close enough) to then saying I get the compressed data every 1 minute.

When talking about signals that change over time with a fixed sample rate your question actually has a proper mathematical answer. It can be beaten for very specific kinds of signals that have patterns in them you already know beforehand, but if it's a generalized signal over time without any further information, it's essentially as good as it gets.

And that answer is found in the Fourier transform. By first transforming your data from the time domain into the frequency domain you get all the power you desire. You become time-independent, and you can drop the coefficients that are above frequencies you care about. You can also downsample, using more/less bits for coefficients that are important/not important.