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

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

${\displaystyle 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}}}}$,

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

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

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

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

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

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

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

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

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

Приклади

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

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

${\displaystyle E(min_{2})=-4\cdot {\frac {1}{2^{2}}}\log _{2}{\frac {1}{2^{2}}}=-\log _{2}{\frac {1}{4}}=2}$

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

${\displaystyle f(x)=1}$

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

Властивості

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

Посилання

1. Kalai, Gil (17 серпня 2007). . What's new. Архів оригіналу за 14 жовтня 2016. Процитовано 29 січня 2017.
2. O'Donnell, Ryan (2008). (PDF). Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing. STOC '08. New York, NY, USA: ACM. с. 569—578. doi:10.1145/1374376.1374458. ISBN . Архів оригіналу (PDF) за 9 грудня 2016. Процитовано 29 січня 2017.
3. Chakraborty, Sourav; Kulkarni, Raghav; Lokam, Satyanarayana V.; Saurabh, Nitin (22 листопада 2016). (PDF). Theoretical Computer Science. Computing and Combinatorics. 654: 92—112. doi:10.1016/j.tcs.2016.05.006. ISSN 0304-3975. Архів оригіналу (PDF) за 15 січня 2017. Процитовано 29 січня 2017.
4. O'Donnell, Ryan (5 червня 2014). (вид. 1 edition). New York, NY: Cambridge University Press. ISBN . Архів оригіналу за 2 лютого 2017. Процитовано 29 січня 2017.