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

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