Ентропія Фур'є

Ентропія Фур'є (Шаблон:Lang-en) або спектральна ентропія (Шаблон:Lang-en) для функції $f:\{-1,1{\}}^n\to ℝ$ визначається як

$E(f)=-\sum _{S\subseteq \{1,...,n\}}\widehat{f^2}(S){\log }_2\widehat{f^2}(S)=\sum _{S\subseteq \{1,...,n\}}\hat{f}(S{)}^2{\log }_2\frac{1}{\hat{f}(S{)}^2}$,

де $\hat{f}:2^{\{1,...,n\}}\to ℝ$ позначає перетворення Фур'є від $f$.

Нагадаємо що ентропія Шеннона для серії випадкових подій $x$ має аналогічний вигляд:

$\mathrm{H}(X)=-\sum _{i=1}^n\mathrm{P}(x_i){\log }_2\mathrm{P}(x_i),$

Розклад Фур'є булевої функції

Для позначення булевих значень 0 і 1, вибирають кодування -1, 1. Кожна функція $f:\{-1,1{\}}^n\to ℝ$ може бути однозначно виражена як мультилінійний многочлен (многочлен від багатьох змінних лінійний по кожній з них):

$f(x)=\sum _{S\subseteq \{1,...,n\}}{C}_S\prod _{i\in S}{x}_i$,

де кожен $C_S$ є дійсним числом. ($\mathrm{\forall }x:\prod _{i\in \mathrm{\varnothing }}{x}_i=1$) Це розклад Фур'є такої функції.

Коефіцієнт $C_S$ зазвичай позначають як $\hat{f}(S)$, $\{1,...,n\}$ як $[n]$, а одночлен $\prod _{i\in S}{x}_i$ як ${\chi }_S(x)$, тому часто можна бачити запис:

$f(x)=\sum _{S\subseteq [n]}\hat{f}(S){\chi }_S(x)$

Приклади

Функція що повертає найменший з двох аргументів (по суті кон'юнкція):

$mi{n}_2(x)=-\frac{1}{2}+\frac{1}{2}{x}_1+\frac{1}{2}{x}_2+\frac{1}{2}{x}_1{x}_2$

$E(mi{n}_2)=-4\cdot \frac{1}{2^2}{\log }_2\frac{1}{2^2}=-{\log }_2\frac{1}{4}=2$

Функція від однієї змінної що завжди повертає 1:

$f(x)=1$

$E(f)=-1{\log }_{2}1=0$

Властивості

З нерівності Єнсена можна вивести що найменше значення ентропії Фур'є - нуль.