Ентропія Фур'є
Ентропія Фур'є (англ. Fourier entropy) або спектральна ентропія (англ. spectral entropy)[1] для функції визначається як
- ,
де [2] позначає перетворення Фур'є від [3].
Нагадаємо що ентропія Шеннона для серії випадкових подій має аналогічний вигляд:
Для позначення булевих значень 0 і 1, вибирають кодування -1, 1[4]. Кожна функція може бути однозначно виражена як мультилінійний многочлен (многочлен від багатьох змінних лінійний по кожній з них):
- ,
де кожен є дійсним числом[2]. () Це розклад Фур'є такої функції.
Коефіцієнт зазвичай позначають як , як , а одночлен як , тому часто можна бачити запис:
Функція що повертає найменший з двох аргументів (по суті кон'юнкція):
Функція від однієї змінної що завжди повертає 1:
З нерівності Єнсена можна вивести що найменше значення ентропії Фур'є - нуль[1].
- ↑ а б Kalai, Gil (17 серпня 2007). The entropy/influence conjecture. What's new. Архів оригіналу за 14 жовтня 2016. Процитовано 29 січня 2017.
- ↑ а б O'Donnell, Ryan (2008). Some Topics in Analysis of Boolean Functions (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 978-1-60558-047-0. Архів оригіналу (PDF) за 9 грудня 2016. Процитовано 29 січня 2017.
- ↑ Chakraborty, Sourav; Kulkarni, Raghav; Lokam, Satyanarayana V.; Saurabh, Nitin (22 листопада 2016). Upper bounds on Fourier entropy (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.
- ↑ а б O'Donnell, Ryan (5 червня 2014). Analysis of Boolean Functions (вид. 1 edition). New York, NY: Cambridge University Press. ISBN 978-1-107-03832-5. Архів оригіналу за 2 лютого 2017. Процитовано 29 січня 2017.