Difference between revisions of "Fourier representation"
m (→Definition) |
Or elmackias (talk | contribs) (→Definition) |
||
| Line 1: | Line 1: | ||
| − | == | + | == General == |
Every Boolean function <math>f:\{-1,1\}^n \to \{-1,1\}</math> may be uniquely written as a multivariate polynomial: | Every Boolean function <math>f:\{-1,1\}^n \to \{-1,1\}</math> may be uniquely written as a multivariate polynomial: | ||
| Line 5: | Line 5: | ||
where <math>\hat{f}_S</math> are real numbers called the '''Fourier coefficients''' of <math>f</math>. | where <math>\hat{f}_S</math> are real numbers called the '''Fourier coefficients''' of <math>f</math>. | ||
| + | |||
| + | The set of functions <math>\{\underset{i\in S}{\prod}x_{i}|S\subseteq\{1,2,...,n\}\}</math> is an orthonormal basis of the vector space of all boolean functions <math>f:\{-1,1\}^{n}\to\mathbb{R}</math> with the inner product:<br><br> | ||
| + | <math><f,g>=2^{-n}\underset{x\in\{-1,1\}^{n}}{\sum}f(x)g(x)=\underset{x\sim\{-1,1\}^{n}}{\mathbb{E}}[f(x)g(x)]</math><br> | ||
| + | Therefore, Parseval's and Plancherel's identities holds: | ||
| + | |||
| + | <math><f,f>=\underset{S\in\{1,..,n\}}{\sum}\hat{f}(S)^{2}</math> | ||
| + | |||
| + | <math><f,g>=\underset{S\in\{1,..,n\}}{\sum}\hat{f}(S)\hat{g}(S)</math> | ||
TODO: Parseval | TODO: Parseval | ||
Revision as of 12:52, 23 September 2019
General
Every Boolean function [math]f:\{-1,1\}^n \to \{-1,1\}[/math] may be uniquely written as a multivariate polynomial:
[math] f(x) = \sum_{S \subseteq [n]} \hat{f}_S \prod_{i \in S} x_i [/math],
where [math]\hat{f}_S[/math] are real numbers called the Fourier coefficients of [math]f[/math].
The set of functions [math]\{\underset{i\in S}{\prod}x_{i}|S\subseteq\{1,2,...,n\}\}[/math] is an orthonormal basis of the vector space of all boolean functions [math]f:\{-1,1\}^{n}\to\mathbb{R}[/math] with the inner product:
[math]\lt f,g\gt =2^{-n}\underset{x\in\{-1,1\}^{n}}{\sum}f(x)g(x)=\underset{x\sim\{-1,1\}^{n}}{\mathbb{E}}[f(x)g(x)][/math]
Therefore, Parseval's and Plancherel's identities holds:
[math]\lt f,f\gt =\underset{S\in\{1,..,n\}}{\sum}\hat{f}(S)^{2}[/math]
[math]\lt f,g\gt =\underset{S\in\{1,..,n\}}{\sum}\hat{f}(S)\hat{g}(S)[/math]
TODO: Parseval
TODO: The Fourier weight at depth k is... The Fourier weight at depth >= k is...
Properties
- TODO. Start off with relation between Fourier weight and other complexity measures such as circuit size, sensitivity, decision tree depth.
