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.
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