Modeling and Simulation Group Meeting Old
The Entropic Uncertainty Principle and the Fast Fourier Transform
Speaker: Charles Peskin
Location: Warren Weaver Hall 1314
Date: Thursday, March 5, 2020, 12:30 p.m.
The entropic uncertainty principle for the discrete Fourier transform
states that for any nonzero u in C^n, H(u) + H(F_n(u)) >= log(n),
where H(u) is the entropy of the discrete probability distribution
P_j = |u_j|^2/||u||^2, and where F_n is the discrete Fourier transform
of order n. This is a special case of a known result , but the
proof of the general case requires functional analysis. Here, we give
an elementary proof of the special case (and moreover only for n
as a power of 2). The proof is based on the Fast Fourier Transform
 Dembo A, Cover TM, and Thomas JA 1991: Information Theoretic
Inequalities. IEEE Transactions on Information Theory
37(6):1501-1517, see Theorem 23 on page 1513.