Modeling and Simulation Group Meeting

---

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.

Synopsis:

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 [1], 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
algorithm.

Reference

[1] 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.