srean
3 hours ago
At the root of the fast transform is the simple fact that
ax + bx = (a+b)x
Efficient decoding of LDPC codes also use the same idea. LDPCs were quite a revolution (pun intended) in coding/information theory.
On the other hand, something completely random, few days ago I found out that Tukey (then a Prof) and Feynman (then a student) along with other students were so enamored and intrigued by flexagons that they had set up an informal committee to understand them. Unfortunately their technical report never got published because the war intervened.
Strangely, it does not find a mention in Surely You're Joking.
rigtorp
an hour ago
How is belief propagation used for decoding LDPC codes related to FFT?
ajross
22 minutes ago
> At the root of the fast transform is the simple fact that
Actually... no? That's a constant factor optimization; the second expression has 75% the operations of the first. The FFT is algorithmically faster. It's O(N·log2(N)) in the number of samples instead of O(N²).
That property doesn't come from factorization per se, but from the fact that the factorization can be applied recursively by creatively ordering the terms.