Comment by ChrisLomont | Hacker News Reader

Comment by ChrisLomont | Hacker News Reader

Parent Full thread

The FFT using real numbers is not lossless (except in certain numerically coincidental cases that are not mush practical use), but there are lossless approximations used routinely in compression to avoid error at this point.

For fixed input and output (say 8 bit to 8 bit data), it's easy to make lossless FFTs, since the final truncation or rounding can be designed to never lose information. So in these cases, even a FFT based on , say, IEEE 754 doubles can be made lossless when using integral input and output.

A similar example is converting 8 bit RGB to 0-1 floating point by dividing the color channel by 255.0, which is lossy as real numbers since the resulting floating point is truncated (except precisely for inputs 0 and 255). However, multiplying the result by 255.0, and rounding appropriately, you can recover each input without loss. So this is an example of a lossless transformation that has lossy steps in between. This can be done in almost any case you need to do it.

FFTs in compression are not used to lose values, but to change signal domain, where perhaps interesting and lossy things can be done.

Google lossless FFT or reversible FFT and dig around.

At the end of the day, however, it's not FFTs that are useful very much in compression. They're only used for signal changes at best, and they've been made obsolete for the most pary by other techniques.

Can you give some details re:

> The FFT using real numbers is not lossless

The DFT over the reals is invertible, right? How can it be invertible but not lossless?

> The FFT using real numbers is not lossless

FFTs use terms of the form e^(2 pi i k / n), and these terms cannot be represented exactly except in rare cases with finite precision floating point numbers (follows from Gelfand's Theorem).

Thus, as soon as you try to use or compute such a term, you've made an approximation, losing information.

The transform is approximately invertible using finite precision, and if your inputs are some fixed set you can make sure and do error analysis to ensure those terms come back out via careful rounding.

But the FFT, and it's inverse, involve infinitely precise real numbers that cannot be represented as floating point.

The DFT fails for the same reason.

However

As I explained above, if you have a limited set of inputs, say byte values 0-255, that get converted to floating point via these approximations, then the inverse approximation is applied, then the final values are appropriately rounded, you can make the DFT and FFT (and almost any approximation algorithm) on this limited subset of inputs 0-255.

As a simple example, consider turning a byte color channel 0-255 into a 32 bit float in 0.0f - 1.0f via dividing by 255.0. Now every one of the values except 0.0f and 1.0f are approximations, since the only exactly representable floats are dyadic (denominator is power of 2) and these denominators are 255 (no powers of 2).

So this is lossy. But the limited inputs means there are 255 different floats possible.

Now multiplying by 255.0, which is (int this case) not lossy on floats, puts each back to close to an integer (but not all are integers). Rounding to closest will restore the original 0255 byte values.

So the roundtrip is lossless here. But the same transforms dividing by 255.0f then multiplying by 255.0f are not lossless for all floating point inputs.

In each case for any algorithm, one needs to carefully design the inputs and outputs and transforms carefully to ensure it behaves as desired.

This is the tip of the iceberg when dealing with floating point algorithms :)

The DFT over the reals is not lossless. Using floats, for example, and applying it to max_float overflows, so cannot be inverted. It's not even bit invertible for almost any set of inputs. It's only invertible on very limited specialized sets of inputs

I find it very confusing that you seem to use "real number" and "floating point number" interchangeably.

Like this:

> The DFT over the reals is not lossless. Using floats, for example, and applying it to max_float overflows, so cannot be inverted.

I don't see why you make statements about the reals based on what happens with floats. They aren't the same, and the DFT exists independently of actually computing it.

Reply on news.ycombinator.com