Перегляд вихідного коду сторінки Ентропія Фур'є

'''Ентропія Фур'є''' ({{lang-en|Fourier entropy}}) або '''спектральна ентропія''' ({{lang-en|spectral entropy}})<ref name="gil" />  для функції <math>f: \{-1, 1\}^n \to \R</math> визначається як
:<math>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}</math>, 
де <math>\hat{f}: 2^{\{1, ..., n\}} \to \R</math><ref name="some_topics"/> позначає [[перетворення Фур'є]] від <math>f</math><ref name="upper_bounds"/>.

Нагадаємо що [[ентропія Шеннона]] для серії випадкових подій <math>x</math> має аналогічний вигляд:

:<math>\Eta(X) = -\sum_{i=1}^n {\mathrm{P}(x_i) \log_2 \mathrm{P}(x_i)},</math>

== Розклад Фур'є булевої функції ==
Для позначення [[булева алгебра|булевих значень]] 0 і 1, вибирають кодування -1, 1<ref name="odonnel_analysis" />. Кожна функція <math>f: \{-1, 1\}^n \to \R</math> може бути однозначно виражена як [[мультилінійна функція|мультилінійний]] многочлен (многочлен від багатьох змінних лінійний по кожній з них):
:<math>f(x) = \sum_{S \subseteq \{1, ..., n\}} C_S \prod_{i \in S} x_i</math>,
де кожен <math>C_S</math> є дійсним числом<ref name="some_topics"/>. (<math>\forall x: \prod_{i \in \empty} x_i = 1</math>) Це розклад Фур'є такої функції.

Коефіцієнт <math>C_S</math> зазвичай позначають як <math>\hat{f}(S)</math>, <math>\{1, ..., n\}</math> як <math>[n]</math>, а одночлен <math>\prod_{i \in S} x_i</math> як <math>\chi_S(x)</math>, тому часто можна бачити запис:
:<math>f(x) = \sum_{S \subseteq [n]} \hat f(S) \chi_S(x)</math>

== Приклади ==
Функція що повертає найменший з двох аргументів (по суті [[кон'юнкція]]):
:<math>min_2(x) = -\frac{1}{2} + \frac{1}{2}x_1 + \frac{1}{2} x_2 + \frac{1}{2} x_1 x_2</math><ref name="odonnel_analysis" />
:<math>E(min_2) = - 4 \cdot \frac{1}{2^2} \log_2 \frac{1}{2^2} = - \log_2 \frac{1}{4} = 2</math>

Функція від однієї змінної що завжди повертає 1: 
: <math>f(x) = 1</math>
: <math>E(f) = - 1 \log_2 1 = 0</math>

== Властивості ==
З [[Нерівність Єнсена|нерівності Єнсена]] можна вивести що найменше значення ентропії Фур'є - нуль<ref name="gil" />.

== Посилання ==
<references>
<ref name="odonnel_analysis">{{Cite book
| edition = 1 edition
| publisher = Cambridge University Press
| isbn = 978-1-107-03832-5
| last = O'Donnell
| first = Ryan
| title = Analysis of Boolean Functions
| location = New York, NY
| date = 2014-06-05
| url = http://www.contrib.andrew.cmu.edu/~ryanod/?p=207
| accessdate = 29 січня 2017
| archive-date = 2 лютого 2017
| archive-url = https://web.archive.org/web/20170202050811/http://www.contrib.andrew.cmu.edu/~ryanod/?p=207
}}</ref>
<ref name="upper_bounds">{{Cite journal
| doi = 10.1016/j.tcs.2016.05.006
| issn = 0304-3975
| volume = 654
| pages = 92–112
| last1 = Chakraborty
| first1 = Sourav
| last2 = Kulkarni
| first2 = Raghav
| last3 = Lokam
| first3 = Satyanarayana V.
| last4 = Saurabh
| first4 = Nitin
| title = Upper bounds on Fourier entropy
| journal = Theoretical Computer Science
| series = Computing and Combinatorics
| accessdate = 2017-01-29
| date = 2016-11-22
| url = http://www.imsc.res.in/~nitin/pubs/CKLS15-prelim.pdf
| archive-date = 15 січня 2017
| archive-url = https://web.archive.org/web/20170115222429/http://www.imsc.res.in/~nitin/pubs/CKLS15-prelim.pdf
}}</ref>
<ref name="some_topics">{{Cite conference
| publisher = ACM
| doi = 10.1145/1374376.1374458
| isbn = 978-1-60558-047-0
| pages = 569–578
| last = O'Donnell
| first = Ryan
| title = Some Topics in Analysis of Boolean Functions
| booktitle = Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing
| location = New York, NY, USA
| series = STOC '08
| accessdate = 2017-01-29
| date = 2008
| url = https://www.cs.cmu.edu/~odonnell/papers/analysis-survey.pdf
| archive-date = 9 грудня 2016
| archive-url = https://web.archive.org/web/20161209124002/http://www.cs.cmu.edu/~odonnell/papers/analysis-survey.pdf
}}</ref>
<ref name="gil">{{Cite web
| last = Kalai
| first = Gil
| title = The entropy/influence conjecture
| work = What's new
| accessdate = 2017-01-29
| date = 2007-08-17
| url = https://terrytao.wordpress.com/2007/08/16/gil-kalai-the-entropyinfluence-conjecture/
| archive-date = 14 жовтня 2016
| archive-url = https://web.archive.org/web/20161014053155/https://terrytao.wordpress.com/2007/08/16/gil-kalai-the-entropyinfluence-conjecture/
}}</ref>
</references>

[[Категорія:Перетворення Фур'є]]
[[Категорія:Булева алгебра]]