Difference between revisions of "Fourier representation"

From Boolean Zoo
Jump to: navigation, search
(The Fourier Weight)
m (Some useful identities:)
 
(2 intermediate revisions by 2 users not shown)
Line 6: Line 6:
 
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>
+
The set of functions <math>\{\underset{i\in S}{\prod}x_{i}|S\subseteq [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>
+
<math>\left<f,g\right>=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>
+
=== The Fourier Weight ===
  
<math><f,g>=\underset{S\in\{1,..,n\}}{\sum}\hat{f}(S)\hat{g}(S)</math>
+
For <math>f:\{-1,1\}^{n}\to\mathbb{R}</math> and <math>0\leq k\leq n</math> the Fourier weight of <math>f</math> at degree <math>k</math> (or depth <math>k</math>) is:
  
TODO: Parseval
+
<math>W^{k}[f]=\underset{S\subseteq\{1,...n\},|s|=k}{\sum\hat{f}(S)^{2}}</math>
  
TODO: The Fourier weight at depth k is... The Fourier weight at depth >= k is...
+
=== Some useful identities ===
  
== The Fourier Weight ==
+
Parseval's identity: <math>\left<f,f\right>=\underset{S\in [n]}{\sum}\hat{f}(S)^{2}</math>
  
For <math>f:\{-1,1\}^{n}\to\mathbb{R}</math> and <math>0\leq k\leq n</math> the Fourier weight of <math>f</math> at degree <math>k</math> (or depht <math>k</math>) is:
+
Plancharel's identity: <math>\left<f,g\right>=\underset{S\in [n]}{\sum}\hat{f}(S)\hat{g}(S)</math>
  
<math>W^{k}[f]=\underset{S\subseteq\{1,...n\},|s|=k}{\sum\hat{f}(S)^{2}}</math>
+
The convolution theorem: <math>\widehat{f * g}(S) = \widehat{f}(S) \widehat{g}(S)</math>, where <math>(f*g)(x) = \mathbb{E}_{y}\left[f(y)g(x \circ y) \right]</math> (where <math>\circ</math> is bit-wise multiplication).
  
 
== Properties ==  
 
== Properties ==  

Latest revision as of 09:13, 15 November 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 [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]\left\lt f,g\right\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]

The Fourier Weight

For [math]f:\{-1,1\}^{n}\to\mathbb{R}[/math] and [math]0\leq k\leq n[/math] the Fourier weight of [math]f[/math] at degree [math]k[/math] (or depth [math]k[/math]) is:

[math]W^{k}[f]=\underset{S\subseteq\{1,...n\},|s|=k}{\sum\hat{f}(S)^{2}}[/math]

Some useful identities

Parseval's identity: [math]\left\lt f,f\right\gt =\underset{S\in [n]}{\sum}\hat{f}(S)^{2}[/math]

Plancharel's identity: [math]\left\lt f,g\right\gt =\underset{S\in [n]}{\sum}\hat{f}(S)\hat{g}(S)[/math]

The convolution theorem: [math]\widehat{f * g}(S) = \widehat{f}(S) \widehat{g}(S)[/math], where [math](f*g)(x) = \mathbb{E}_{y}\left[f(y)g(x \circ y) \right][/math] (where [math]\circ[/math] is bit-wise multiplication).

Properties

  • TODO. Start off with relation between Fourier weight and other complexity measures such as circuit size, sensitivity, decision tree depth.

References