The new basis is usually called the Fourier basis.Any real-valued function can be written in the Fourier basis: F(a)Xa and the coefficients f(a)are called Fourier coefficients,computed by f(a)=E[f(x)xo(x)]. One useful fact about Fourier transform is that the multiplication in one domain becomes the convolution in the other.For f,g:{0,1)nR,their convolution f*g is defined by (f *g)(x)=E[f(y)g(x+y)]=E,[f(x +y)g(y)] In the Fourier domain,the definition is similar except for a normalization factor. -ga=∑foaa+m=∑fa+ma0. Fact.g=ffg=fg. One can define the tp-norm for f as usual: n,-rr)） When p =0,the quantity is the Fourier sparsity of f,i.e.the number of nonzero Fourier coefficients. Similarly,we can define an Lp-norm for f but note that it's more convenient to use the expectation instead of summation. llfllLp =(E.[lf(x)P)p An elegant fact is that fL lfleThe new basis is usually called the Fourier basis. Any real-valued function can be written in the Fourier basis: 𝑓 = ∑𝑓̂(𝛼)𝜒𝛼 𝛼 , and the coefficients 𝑓̂(𝛼) are called Fourier coefficients, computed by 𝑓̂(𝛼) = 𝐄𝑥 [𝑓(𝑥)𝜒𝛼 (𝑥)]. One useful fact about Fourier transform is that the multiplication in one domain becomes the convolution in the other. For 𝑓, 𝑔:{0,1} 𝑛 → ℝ, their convolution 𝑓 ⋆ 𝑔 is defined by (𝑓 ⋆ 𝑔)(𝑥) = 𝐄𝑦 [𝑓(𝑦)𝑔(𝑥 + 𝑦)] = 𝐄𝑦 [𝑓(𝑥 + 𝑦)𝑔(𝑦)] In the Fourier domain, the definition is similar except for a normalization factor. (𝑓̂ ⋆ 𝑔̂)(𝛼) = ∑𝑓̂(𝛽)𝑔̂(𝛼 + 𝛽) 𝛽 = ∑𝑓̂(𝛼 + 𝛽)𝑔̂(𝛽) 𝛽 . Fact. 𝑓𝑔̂ = 𝑓̂ ⋆ 𝑔̂, 𝑓̂⋆ 𝑔 = 𝑓̂𝑔̂. One can define the ℓ𝑝 -norm for 𝑓̂ as usual: ‖𝑓̂‖ ℓ𝑝 = (∑|𝑓̂(𝛼)| 𝑝 𝛼 ) 1/𝑝 When 𝑝 = 0, the quantity is the Fourier sparsity of 𝑓, i.e. the number of nonzero Fourier coefficients. Similarly, we can define an 𝐿𝑝 -norm for 𝑓 but note that it’s more convenient to use the expectation instead of summation. ‖𝑓‖𝐿𝑝 = (𝐄𝑥 [|𝑓(𝑥)| 𝑝]) 1/𝑝 An elegant fact is that ‖𝑓‖𝐿2 = ‖𝑓̂‖ ℓ2