Hacker News new | ask | show | jobs
by hebdo 3874 days ago
Random noise cannot be (on average) loselessly compressed, not even by 0.0000001% of the original size. To see that it is the case it is sufficient to notice that a compression algorithm is essentially a way to reorder all possible inputs, all at once, and then apply the pigeonhole principle. Kind of similar to the proof that if a loseless compression algorithm shortens at least one input, it must also extend at least one.

Claiming that there exists an algorithm that loselessly compresses random noise to 86% of the original size is just wrong.

1 comments

It could have been pink noise rather than white (an argument for using it here would be it has a more similar spectral content to music). Pink noise definitely compresses more though still maybe not that much.