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

Ентропія Фур'є (англ. Fourier entropy) або спектральна ентропія (англ. spectral entropy) для функції $f:\{-1,1\}^{n}\to \mathbb {R}$ визначається як

$E(f)=-\sum _{S\subseteq \{1,...,n\}}{\hat {f^{2}}}(S)\log _{2}{\hat {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 \mathbb {R}$ позначає перетворення Фур'є від $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 \mathbb {R}$ може бути однозначно виражена як мультилінійний многочлен (многочлен від багатьох змінних лінійний по кожній з них):

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

де кожен $C_{S}$ є дійсним числом. ($\forall x:\prod _{i\in \emptyset }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)$

Приклади

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

$min_{2}(x)=-{\frac {1}{2}}+{\frac {1}{2}}x_{1}+{\frac {1}{2}}x_{2}+{\frac {1}{2}}x_{1}x_{2}$

$E(min_{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$

Властивості

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