Editing Discrete Fourier transform (section)

=== Uncertainty principles ===
==== Probabilistic uncertainty principle ====
If the random variable {{math|''X''<sub>''k''</sub>}} is constrained by
:<math>\sum_{n=0}^{N-1} |X_n|^2 = 1 ,</math>
then
:<math>P_n=|X_n|^2</math>
may be considered to represent a discrete [[probability mass function]] of {{mvar|n}}, with an associated probability mass function constructed from the transformed variable,
:<math>Q_m = N |x_m|^2 .</math>

For the case of continuous functions <math>P(x)</math> and <math>Q(k)</math>, the [[Heisenberg uncertainty principle]] states that
:<math>D_0(X)D_0(x)\ge\frac{1}{16\pi^2}</math>
where <math>D_0(X)</math> and <math>D_0(x)</math> are the variances of <math>|X|^2</math> and <math>|x|^2</math> respectively, with the equality attained in the case of a suitably normalized [[Gaussian distribution]]. Although the variances may be analogously defined for the DFT, an analogous uncertainty principle is not useful, because the uncertainty will not be shift-invariant. Still, a meaningful uncertainty principle has been introduced by Massar and Spindel.<ref name=Massar/>

However, the Hirschman [[entropic uncertainty]] will have a useful analog for the case of the DFT.<ref name=DeBrunner/> The Hirschman uncertainty principle is expressed in terms of the [[Entropy (information theory)|Shannon entropy]] of the two probability functions.

In the discrete case, the Shannon entropies are defined as
:<math>H(X)=-\sum_{n=0}^{N-1} P_n\ln P_n</math>
and
:<math>H(x)=-\sum_{m=0}^{N-1} Q_m\ln Q_m ,</math>
and the [[entropic uncertainty]] principle becomes<ref name=DeBrunner/>
:<math>H(X)+H(x) \ge \ln(N) .</math>

The equality is obtained for <math>P_n</math> equal to translations and modulations of a suitably normalized [[Kronecker comb]] of period <math>A</math> where <math>A</math> is any exact integer divisor of <math>N</math>. The probability mass function <math>Q_m</math> will then be proportional to a suitably translated [[Kronecker comb]] of period <math>B=N/A</math>.<ref name=DeBrunner/>

==== Deterministic uncertainty principle ====
There is also a well-known deterministic uncertainty principle that uses signal sparsity (or the number of non-zero coefficients).<ref name=Donoho/> Let <math>\left\|x\right\|_0</math> and <math>\left\|X\right\|_0</math> be the number of non-zero elements of the time and frequency sequences <math>x_0,x_1,\ldots,x_{N-1}</math> and <math>X_0,X_1,\ldots,X_{N-1}</math>, respectively. Then,
:<math>N \leq \left\|x\right\|_0 \cdot \left\|X\right\|_0.</math>
As an immediate consequence of the [[Arithmetic–geometric mean|inequality of arithmetic and geometric means]], one also has <math>2\sqrt{N} \leq \left\|x\right\|_0 + \left\|X\right\|_0</math>. Both uncertainty principles were shown to be tight for specifically chosen "picket-fence" sequences (discrete impulse trains), and find practical use for signal recovery applications.<ref name=Donoho/>