var graph = [{"group":"nodes","data":{"id":"def:Corr","name":"definition","text":"

Definition 22 (Correlation). Every definition of the convolution can be turned into a definition of the correlation by $R_{fg} = f* \\tilde g$ where $\\tilde g(x)=g(-x)$ . For the case of function of $R\\rightarrow \\mathbb{C}$ this gives

$R_{fg}(x) = \\int_{-\\infty}^{\\infty} f(u)g(u-x)du$

Remark: correlation is not commutative.

","parent":"sec:FCC","rank":"0","html_name":"def:Corr","summary":"

Definition 22 (Correlation). $R_{fg} = f* \\tilde g$

","hasSummary":true,"hasTitle":true,"title":"Correlation","height":276,"width":980},"classes":"l0","position":{"x":3344.664174192218,"y":8942.891041283066}},{"group":"nodes","data":{"id":"rem:GR","name":"remark","text":"

Remark 5 (General remarks).

The direction of arrows are sometimes more ’pedagogical’ than logical. For instance in the convolution section, every definition descend from the convolution on $\\mathbb{R}$ , but the convolution on $\\mathbb{R}$ could also be re-expressed as a limit of discrete and/or circular convolutions. For the Fourier sub-section, links are detailed in both directions.
Every formula can be made multidimensional. Integrals are replaced by multiple integrals, sums by multiple sums and the products $ab$ of two numbers become $a_1b_1+...+a_nb_n.$

","parent":"sec:FCC","rank":"0","html_name":"rem:GR","summary":"

Remark 5 (General remarks). Arrow directions + Multidimensional case

","hasSummary":true,"hasTitle":true,"title":"General remarks","height":273,"width":980},"classes":"l0","position":{"x":4606.020214642733,"y":8903.649734517832}},{"group":"nodes","data":{"id":"th:ExTI","name":"theorem","text":"

Theorem 9 (Exponential function and T.I. operators (!finish morph!)). Let $A$ be a $T.I.$ operator.

Let $e$ be an exponential function, that is to say $e(x)= e^{z x}$ for some $z\\in \\mathbb{C}$ . Assume that $e$ is in the domain of definition of $A$ . Since $\\varphi_{t_1}(e)(t_2)=e^{z t_1}e^{z t_2}$ , we have $(\\varphi_t\\circ A)(e)=A(\\varphi_t(e))= A(e^{z t }e) = e(t)A(e).$ In $x$ we get $A(e)(x+t) = e(t)A(e)(x)$ hence with $x=0$ , $A(e)(t)=A(e)(0)e(t)$ hence $e$ is an eigenfunction of eigenvalue $A(e)(0)$ .
Let $f$ be an eigenfunction of $\\varphi_t$ forall $t$ . We have for all $t$ $f(x+t)=\\varphi_t(f)(x)=\\lambda(t)f(x),$ hence, $f(0+t)=\\lambda(t)f(0).$ If $f(0)=0$ , then $f$ is null everywhere. If $f\\neq 0$ , then $f(x+t)=\\frac{f(t)f(x)}{f(0)}$ hence $g(x)=\\frac{f(x)}{f(0)}$ verifies $g(x+t)=g(t)g(x)$ and hence $g:E\\rightarrow \\mathbb{C}^*$ is a morphism.

","parent":"sec:TIOpe","rank":"0","html_name":"th:ExTI","summary":"

Theorem 9 (Exponential function and T.I. operators (!finish morph!)). The eigenfunctions of a T.I. operator $A$ are exponential functions $t\\mapsto e^{i\\alpha t}$ which lie in the domain of definition of $A$ .

","hasSummary":true,"hasTitle":true,"title":"Exponential function and T.I. operators (!finish morph!)","height":395,"width":980},"classes":"l0","position":{"x":7322.731965135108,"y":5045.927110898508}},{"group":"nodes","data":{"id":"th:ConvTI","name":"theorem","text":"

Theorem 10 (Convolutions are T.I.). Let $h:E\\rightarrow \\mathbb{C}$ with $E=\\mathbb{R}^n$ , $(\\mathbb{R}/\\mathbb{Z})^n$ , $\\mathbb{Z}^n$ or $(\\mathbb{Z}/k\\mathbb{Z})^n$ . Let $A$ the operator defined when it exists by $A(f)=f*h.$ $A$ is a T.I. operator. Show it in the case $E=\\mathbb{R}$ . We have $\\begin{aligned}\n\\varphi_t(A(f))(x)&=&\\varphi_t(f*h)(x)\\\\\n&=& (f*h)(x+t)\\\\\n &=& \\int_{-\\infty}^{\\infty} f(u)h(x+t-u)du\\\\\n&=&\\int_{-\\infty}^{\\infty} f(v+t)h(x-v)dv\\\\\n&=& (\\varphi_t(f)*h)(x)=A(\\varphi_t(f))(x).\\\\\\end{aligned}$ The proof is similar in the other cases.

","parent":"sec:TIOpe","rank":"0","html_name":"th:ConvTI","summary":"

Theorem 10 (Convolutions are T.I.). Given a function $h$ , the operator $f\\mapsto f*h$ is T.I.

","hasSummary":true,"hasTitle":true,"title":"Convolutions are T.I.","height":276,"width":980},"classes":"l0","position":{"x":5431.71662161616,"y":4496.318151068295}},{"group":"nodes","data":{"id":"th:TrFunCon","name":"theorem","text":"

Theorem 11 (Transfer function of convolutions operators). Let $h$ be a function with a Fourier transform $\\mathcal{F}(h)$ and let $A$ be the operator $A(f)=f*h$ . We already know from th.(Theorem 10) that $A$ has a transfer function $H$ . Results of section 2.3 on convolution theorems tell us that the transfer function of $A$ evaluated on imaginary numbers is the Fourier transform of $h$ : $H(2i\\pi \\nu)=\\mathcal{F}(h)(\\nu).$ Similar results hold with Fourier series or the discrete Fourier transform when $h$ is periodic or defined on a finite set. The arguments $2i\\pi\\nu$ and $\\nu$ should be adjusted to each setting and conventions. Prove the result for the case of Fourier series. The proof for the Fourier transform and the discrete Fourier transform follows the same pattern, though the case of the Fourier transform requires to use the formalism of distribution.

Let $h$ be a $T$ periodic function with Fourier series $(c_n(h))_{n\\in \\mathbb{Z}}$ , and $*$ be the circular convolution. Consider the $T$ periodic exponential function $e_k(t)=e^{2i\\pi \\frac{k}{T}t }$ with $k\\in \\mathbb{Z}$ . The Fourier series $(c_n(e_k))_{n\\in \\mathbb{Z}}$ of $e_k$ is a sequence where

$\\left\\{\n\\begin{array}{ll}%@{}ll@{}}\n c_n(e_k)=1, & \\text{if}\\ k=1 \\\\\n c_n(e_k)=0, & \\text{otherwise.}\n\\end{array}\\right.$

The product theorem says that $(e_k*h)(x) = \\sum_{n=-\\infty}^{n=+\\infty} c_n(e_k).c_n(h) e^{2i\\pi \\frac{n}{T}x }$

Note that

$\\left\\{\n\\begin{array}{ll}%@{}ll@{}}\n c_n(e_k).c_n(h)=1.c_k(h), & \\text{if}\\ n=k \\\\\n c_n(e_k).c_n(h)=0, & \\text{otherwise.}\n\\end{array}\\right.$ Hence

$(e_k*h)(x) = c_k(h) e^{2i\\pi \\frac{k}{T}x }=c_k(h)e_k(x)$ and $e_k$ is an eigenfunction of eigenvalue $c_k(h)$ : $H\\left(2i\\pi \\frac{k}{T}\\right)=c_k(h).$

","parent":"sec:TIOpe","rank":"0","html_name":"th:TrFunCon","summary":"

Theorem 11 (Transfer function of convolutions operators). Let $h$ be a function with a Fourier transform $\\mathcal{F}(h)$ and let $A$ be the operator $A(f)=f*h$ . The transfer function of $A$ evaluated on imaginary numbers is the Fourier transform of $h$ : $H(2i\\pi \\nu)=\\mathcal{F}(h)(\\nu)$

","hasSummary":true,"hasTitle":true,"title":"Transfer function of convolutions operators","height":541,"width":980},"classes":"l0","position":{"x":6653.027474376811,"y":3861.922134151624}},{"group":"nodes","data":{"id":"def:TrInOp","name":"definition","text":"

Definition 31 (T.I. operators). Operators are usually defined as a linear maps between spaces of functions. In our case, the set $E$ is $\\mathbb{R}^n$ , $(\\mathbb{R}/\\mathbb{Z})^n$ , $\\mathbb{Z}^n$ or $(\\mathbb{Z}/k\\mathbb{Z})^n$ , and let $\\mathcal{F}(E,\\mathbb{C})$ be the vector space of functions from $E$ to $\\mathbb{C}$ . Let $\\varphi_t:\\mathcal{F}(E,\\mathbb{C})\\rightarrow \\mathcal{F}(E,\\mathbb{C})$ be the operator ’translation by $t$ ’: $\\varphi_t(f)(x)=f(x+t).$ When $E=\\mathbb{R}^n$ , $\\varphi_t$ is defined for $t\\in \\mathbb{R}^n$ , but when $E=\\mathbb{Z}^n$ , $t$ should belong to $\\mathbb{Z}^n$ . In our case, we always take $t\\in E$ . Let $F$ and $G$ be subspaces of $\\mathcal{F}(E,\\mathbb{C})$ left stable by all translations. An operator $A:F\\rightarrow G$ is said to be translation invariant (T.I.) if and only if $\\forall t,\\quad A \\circ \\varphi_t = \\varphi_t \\circ A.$ In an informal way, we have $A(f(x+t))=A(f)(x+t)$ . Still informally, the operator $A$ does not make distinctions between the different locations of $E$ , it acts the same everywhere.

","parent":"sec:TIOpe","rank":"0","html_name":"def:TrInOp","summary":"

Definition 31 (T.I. operators). $A \\circ \\varphi_t = \\varphi_t \\circ A$

","hasSummary":true,"hasTitle":true,"title":"T.I. operators","height":282,"width":980},"classes":"l0","position":{"x":5873.092485873402,"y":4937.334272728404}},{"group":"nodes","data":{"id":"def:TranFun","name":"definition","text":"

Definition 32 (Transfer functions). Let $A$ be a T.I. operator. Recall that exponential functions which are in the domain of definition of $A$ are eigenfunctions of $A$ . Note $H(z)$ be the eigenvalue of the eigenfunction $x\\mapsto e^{z x}$ . In the context of signal processing, the function $H(z)$ is called the ’transfer function’. Consider the simple case of a function $f$ that can be decomposed as a linear componation of eigenfunctions $x\\mapsto e^{z x}$ , with $z$ varying in a finite set $S$ of complex numbers:

$f = \\sum_{z \\in S} \\alpha(z)\\left( x\\mapsto e^{z x}\\right)=x\\mapsto \\sum_{z \\in S} \\alpha(z)e^{z x}.$

Then $\\label{eq:TranFun}\nA(f)= \\sum_{z \\in S} \\alpha(z)A\\left(x\\mapsto e^{z x}\\right)=x\\mapsto \\sum_{z \\in S} \\alpha(z)H(z) e^{z x},$

Applying the operator to a function $f$ amounts to multiply the coefficients of the decomposition of $f$ over exponential functions with the transfer function $H$ . This result rely on the linearity of the operator $A$ and the finiteness of the sum. In the case of an infinite sum or an integral the linearity is not enough, but the result often remain valid provided that the quantities exists. This happens in particular with Fourier series or the Fourier transform, $f(x) = \\int_{-\\infty}^{+\\infty} F(\\nu)e^{2i\\pi\\nu x} d\\nu.$

The following informal calculation reproduce Eq.[eq:TranFun] in the context of Fourier transform.

$\\begin{aligned}\nA(f)&=&A\\left(x\\mapsto \\int_{-\\infty}^{+\\infty} F(\\nu)e^{2i\\pi\\nu x} d\\nu \\right) \\\\\n&=& \\int_{-\\infty}^{+\\infty} A\\left( x\\mapsto F(\\nu)e^{2i\\pi\\nu x} \\right)d\\nu \\\\\n&=& \\int_{-\\infty}^{+\\infty} H(2i\\pi\\nu)\\left( x\\mapsto F(\\nu)e^{2i\\pi\\nu x} \\right) d\\nu \\\\\n&=& x\\mapsto \\int_{-\\infty}^{+\\infty} H(2i\\pi\\nu) F(\\nu)e^{2i\\pi\\nu x} d\\nu \\\\\n&=& \\mathcal{F}^{-1}\\left(\\nu \\mapsto H(2i\\pi\\nu).F(\\nu) \\right).\\\\\\end{aligned}$

The equality $A(f)=\\mathcal{F}^{-1}\\left(\\nu \\mapsto H(2i\\pi\\nu).F(\\nu) \\right)$ is often true in practice when the Fourier transforms exists, but it should be checked case by case.

","parent":"sec:TIOpe","rank":"0","html_name":"def:TranFun","summary":"

Definition 32 (Transfer functions). T.I. operators have transfer functions $H(z)$ defined as the eigenvalues of the eigenfunctions $t\\mapsto e^{z t}$ .

","hasSummary":true,"hasTitle":true,"title":"Transfer functions","height":332,"width":980},"classes":"l0","position":{"x":7326.069599729622,"y":4469.610681516074}},{"group":"nodes","data":{"id":"rem:Cont","name":"remark","text":"

Remark 9 (General remarks). For simplicity reasons, results on T.I. operators are expressed in one dimensions but are true in any finite dimension.

","parent":"sec:TIOpe","rank":"0","html_name":"rem:Cont","summary":"

Remark 9 (General remarks). For simplicity reasons, results on T.I. operators are expressed in one dimensions but are true in any finite dimension.

","hasSummary":true,"hasTitle":true,"title":"General remarks","height":365,"width":980},"classes":"l0","position":{"x":5869.910069613311,"y":5364.724011420463}},{"group":"nodes","data":{"id":"rem:FinSup","name":"remark","text":"

Remark 10 (The case $\\{0,..,N-1 \\}\\rightarrow \\mathbb{C}$ ). Consider a function $Mask:\\mathbb{Z}\\rightarrow \\mathbb{C}$ and the operator $A_{\\mathbb{Z}}(f)=f*Mask$ where $*$ is the discrete convolution. Assume that the function $Mask$ is non-null on an integer interval $-M,..,M$ . It is often interesting in practice to define analogous of $A$ but for functions defined on a finite set, for instance $\\{0,N-1\\}$ . It is in particular the case for image and signal processing, where data are observed on a finite domains. There are two standard ways to define an operator $A_N$ mimicking $A$ for functions $\\{0,..,N-1 \\}\\rightarrow \\mathbb{C}$ . Consider now

$f:\\{0,..,N-1 \\}\\rightarrow \\mathbb{C}.$

Completion by $0$ . The function $f:\\{0,N-1\\}\\rightarrow \\mathbb{R}$ can be extended by $0$ before and after. The new function $\\bar f$ is given by $\\bar f(k\\notin \\{0,..,N-1 \\})=0$ and $\\bar f(k\\in \\{0,..,N-1 \\})=f(k)$ . It is then possible to define an operator $A^1_N$ by
\n
$A^1_N(f)(k\\in \\{0,..,N-1 \\}) = (\\bar f * Mask)(k),$ where $*$ is the discrete convolution.
Periodization. We interpret now $\\{0,..,N-1 \\}$ as $\\mathbb{Z}/n\\mathbb{Z}$ . We would like first to turn $Mask$ into a periodic function, and restrict it to the new function $\\bar Mask:\\{0,..,N-1 \\}\\rightarrow \\mathbb{C}$ . The operator $A^2_N$ is then defined as $A^2_N(f)(k\\in \\{0,..,N-1 \\}) = (f * \\bar Mask)(k),$
\n
but where $*$ is the discrete circular convolution. In order to obtain a relevant operator, $\\bar Mask$ should be constructed in the following way. Assume that the range of non null values $2M+1$ of $Mask$ is smaller than $N$ . Then we can wright $Mask_{per}(k) = \\sum_{n=-\\infty}^{+\\infty} Mask(k+nN),$ and define $\\bar Mask(k\\in \\{0,..,N-1 \\})=Mask_{per}(k)$ . In practice when $N$ is even, the indices $-\\frac{N}{2},..,-1$ are translated to indices $\\frac{N}{2},..,N-1$ .

When $k$ is far from the borders with respect to the support of the mask, that is to say $M<k$ and $k<N-M$ , it can be checked that all the different convolutions agree. Hence the operators $A^1_N$ and $A^2_N$ reproduce the behavior of $A_{\\mathbb{Z}}$ . However, $A^1_N$ and $A^2_N$ differ in the way they deal with border effects. It can be argued that $A^1_N$ has more meaning in practice than $A^2_N$ . Indeed, $A^2$ treats $\\{0,..,N-1\\}$ as $\\mathbb{Z}/n\\mathbb{Z}$ but the function $f$ has usually no physical reason to be periodic.
\nThe main difference between these operators are their spectral properties. Note that when $\\{0,..,N-1\\}$ is seen as $\\mathbb{Z}/n\\mathbb{Z}$ , $A^2_N$ is a translation invariant operator. Using the properties of the discrete circular convolution, we have

$A^2_N(f) = \\operatorname{DFT}^{-1}(\\operatorname{DFT}(f).\\operatorname{DFT}(\\bar Mask)).$

The use the fast Fourier transform algorithm (FFT) to compute the $\\operatorname{DFT}$ , can significantly decrease the computational complexity of $A^2_N$ compared with using the convolution formula. This makes $A^2_N(f)$ the most interesting choice in many applications.
\nOn the other hand, $A^1_N$ is strictly speaking not a translation invariant operator. This is because the convolution is with $\\bar f$ and not $f$ . Though $A^1_N$ could still be expressed as

$A^1_N(f) = \\mathcal{F}^{-1}(\\mathcal{F}(\\bar f).\\mathcal{F}(Mask)),$

where $\\mathcal{F}$ is a Fourier transform for functions $\\mathbb{Z}\\rightarrow \\mathbb{C}$ . We will not show it here but in that case, the functions $\\mathcal{F}(\\bar f)$ and $\\mathcal{F}(Mask)$ have a continuous support in the frequency domain. Evaluating $A^1_N(f)$ using this formula requires to evaluate the function $\\mathcal{F}(\\bar f)$ on an infinite number of points. Hence the Fourier transform is not an interesting strategy to compute $A^1_N(f)$ .
\nThe previous considerations can be informally interpreted as follow. In the ’completion by $0$ case’, the function $f:\\{0,..,N-1\\}\\rightarrow \\mathbb{C}$ is endowed in the bigger set of functions $\\mathbb{Z}\\rightarrow \\mathbb{C}$ . The operator $A^1_N$ is an interesting candidate to replace $A^\\mathbb{Z}$ , but the Fourier transform of functions $\\mathbb{Z}\\rightarrow \\mathbb{C}$ does not enable fast computations. On the other hand, in the ’periodization’ case, the arbitrary function $f:\\{0,..,N-1\\}\\rightarrow \\mathbb{C}$ ’is seen in the smaller sets of periodic functions’. This point of view is usually not entirely accurate on the borders but lead to fast computation using the FFT.
\nZero-padding. As pointed out in remark Remark 6 from the section on convolutions, in order to avoid the undesired border effects of the circular convolution of $A^2_N$ , the domain $\\{0,..,N-1\\}$ can be extended to $\\{0,..,2N-1\\}$ by adding zeros to $f$ and $Mask$ . Then operators $A^{1}_N$ and $A^{1}_N$ are the same.
\nAll the discussion remains valid in the multidimensional case $f:\\{0,..,N-1\\}^n\\rightarrow \\mathbb{C}$ . Convolutions are replaced by their multidimensional versions.

","parent":"sec:TIOpe","rank":"0","html_name":"rem:FinSup","summary":"

Remark 10 (The case $\\{0,..,N-1 \\}\\rightarrow \\mathbb{C}$ ). Let $Mask:\\mathbb{Z}\\rightarrow \\mathbb{C}$ and the operator $A_{\\mathbb{Z}}(f)=f*Mask.$ There are two standard ways to define an operator $A_N$ mimicking $A$ for functions $\\{0,..,N-1 \\}\\rightarrow \\mathbb{C}$ .

Completion by $0$ . $*$ is replaced with the discrete convolution.
Periodization. $*$ is replaced with the discrete circular convolution.

The second option leads to fast computations using the $FFT$ .

","hasSummary":true,"hasTitle":true,"title":"The case

\\{0,..,N-1 \\}\\rightarrow \\mathbb{C}

","height":848,"width":982},"classes":"l0","position":{"x":4745.357910248369,"y":3819.1752262180235}},{"group":"nodes","data":{"id":"def:SigmaA","name":"definition","text":"

Definition 43 ( $\\sigma$ -algebra). Let $\\Omega$ be a set and $\\mathcal{P}(\\Omega)$ be the set of its subsets. A $\\sigma$ -algebra $\\mathcal{A}$ on $\\Omega$ is a subset of $\\mathcal{P}(\\Omega)$ such that

$\\emptyset \\in \\mathcal{A}$
$\\forall X\\in \\mathcal{A}, X^{c}\\in \\mathcal{A}$
$\\forall X,Y\\in \\mathcal{A}, X\\cup Y\\in \\mathcal{A}$ ,

where $X^{c}$ refers to the complement of $X$ in $\\Omega$ . The two first axioms implies that $\\Omega\\in \\mathcal{A}$ .

","parent":"sec:Meas","rank":"0","html_name":"def:SigmaA","summary":"

$\\emptyset \\in \\mathcal{A}$
$\\forall X\\in \\mathcal{A}, X^{c}\\in \\mathcal{A}$
$\\forall X,Y\\in \\mathcal{A}, X\\cup Y\\in \\mathcal{A}$ ,

where $X^{c}$ refers to the complement of $X$ in $\\Omega$ . The two first axioms implies that $\\Omega\\in \\mathcal{A}$ .

","hasSummary":false,"hasTitle":true,"title":"

\\sigma

-algebra","height":205,"width":980},"classes":"l0","position":{"x":21374.655408924926,"y":8617.81610704642}},{"group":"nodes","data":{"id":"def:Borel","name":"definition","text":"

Definition 44 (Borel $\\sigma$ -algebra !check the vector space case!). On $\\mathbb{R}$ , the Borel $\\sigma$ -algebra is defined by countable union, intersection and complement of arbitrary open intervals $]a,b[$ . This definition extends to $\\mathbb{R}^n$ by taking products of intervals $]a_1,b_1[\\times ... \\times ]a_n,b_n[$ . This definition extends to arbitrary vector space of finite dimension by checking that the Borel $\\sigma$ -algebra is independent of the choice of the basis.

","parent":"sec:Meas","rank":"0","html_name":"def:Borel","summary":"

","hasSummary":false,"hasTitle":true,"title":"Borel

\\sigma

-algebra !check the vector space case!","height":303,"width":980},"classes":"l0","position":{"x":23402.866561490624,"y":7521.3676802287655}},{"group":"nodes","data":{"id":"def:Meas","name":"definition","text":"

Definition 45 (Measures). Let $\\Omega$ be a set with a $\\sigma$ -algebras $\\mathcal{A}$ . A measure is a function $\\mu:\\mathcal{A}\\rightarrow \\mathbb{R}$ such that

for a countable number of disjoint subsets $X_i\\in \\mathcal{A}$ , $\\mu ( \\cup_i X_i) = \\sum_i \\mu(X_i)$ . In particular for $2$ disjoints subests $X$ and $Y$ in $\\mathcal{A}$ , $\\mu (X \\cup Y) = \\mu(X)+\\mu(Y)$ .
$\\mu(\\emptyset)=0$
$\\forall X\\in \\mathcal{A}, \\mu(X)\\geq 0$ ,

When the last requirement is dropped, the measure is called a \"signed measure\". $(\\Omega,\\mathcal{A},\\mu)$ is called a measured space.

","parent":"sec:Meas","rank":"0","html_name":"def:Meas","summary":"

Definition 45 (Measures). Let $\\Omega$ be a set with a $\\sigma$ -algebras $\\mathcal{A}$ . A measure is a function $\\mu:\\mathcal{A}\\rightarrow \\mathbb{R}$ such that

for a countable number of disjoint subsets $X_i\\in \\mathcal{A}$ , $\\mu ( \\cup_i X_i) = \\sum_i \\mu(X_i)$ . In particular for $2$ disjoints subests $X$ and $Y$ in $\\mathcal{A}$ , $\\mu (X \\cup Y) = \\mu(X)+\\mu(Y)$ .
$\\mu(\\emptyset)=0$
$\\forall X\\in \\mathcal{A}, \\mu(X)\\geq 0$ ,

When the last requirement is dropped, the measure is called a \"signed measure\". $(\\Omega,\\mathcal{A},\\mu)$ is called a measured space.

","hasSummary":false,"hasTitle":true,"title":"Measures","height":198,"width":980},"classes":"l0","position":{"x":20265.49636334657,"y":7465.628481662133}},{"group":"nodes","data":{"id":"def:Measbl","name":"definition","text":"

Definition 46 (Measurable function). Let $E$ and $F$ be two sets with $\\sigma$ -algebras $\\mathcal{A}_E$ and $\\mathcal{A}_F$ . A function $f$ is measurable if and only if $\\forall Y\\in \\mathcal{A}_F, f^{-1}(Y)\\in \\mathcal{A}_E.$

","parent":"sec:Meas","rank":"0","html_name":"def:Measbl","summary":"

","hasSummary":false,"hasTitle":true,"title":"Measurable function","height":198,"width":980},"classes":"l0","position":{"x":21584.558365463217,"y":7710.896413858276}},{"group":"nodes","data":{"id":"def:LebInt","name":"definition","text":"

Definition 47 (Lebesgue integration !!deal with general case!!). Let $f$ be a measurable function from the measured space $(\\Omega,\\mathcal{A},\\mu)$ to a vector space $E$ endowed with the Borel $\\sigma$ -algebra $\\mathcal{B}_E$ . The Lebesgue integral of $f$ is noted $\\int_{\\Omega}f \\mathrm{d}\\mu.$

Give a precise definition in the case where $f$ is a \"step function\" taking a finite number of values $\\{a_1,..,a_n\\}$ . $\\int_{\\Omega}f \\mathrm{d}\\mu= \\sum_{i=1}^n a_i\\mu\\left(f^{-1}(\\{a_i\\})\\right).$ The general definition is a limit case of the integration of step functions.

","parent":"sec:Meas","rank":"0","html_name":"def:LebInt","summary":"

","hasSummary":false,"hasTitle":true,"title":"Lebesgue integration !!deal with general case!!","height":395,"width":980},"classes":"l0","position":{"x":21994.053917912363,"y":6855.319225843632}},{"group":"nodes","data":{"id":"rem:Dflt","name":"remark","text":"

Remark 11 (Default $\\sigma$ -algebras). In many case the choice of $\\sigma$ -algebra is not mentioned. Here are the default choices in standard situations:

$E=\\{1,..,N\\}$ , the default $\\sigma$ -algebra is $\\mathcal{P}(E)$
$E=\\mathbb{N}$ , the default $\\sigma$ -algebra is $\\mathcal{P}(E)$
$E=\\mathbb{R}$ , the default $\\sigma$ -algebra is the Borel $\\sigma$ -algebra
$E$ is a vector space, the default $\\sigma$ -algebra is the Borel $\\sigma$ -algebra,

","parent":"sec:Meas","rank":"0","html_name":"rem:Dflt","summary":"

Remark 11 (Default $\\sigma$ -algebras). In many case the choice of $\\sigma$ -algebra is not mentioned. Here are the default choices in standard situations:

$E=\\{1,..,N\\}$ , the default $\\sigma$ -algebra is $\\mathcal{P}(E)$
$E=\\mathbb{N}$ , the default $\\sigma$ -algebra is $\\mathcal{P}(E)$
$E=\\mathbb{R}$ , the default $\\sigma$ -algebra is the Borel $\\sigma$ -algebra
$E$ is a vector space, the default $\\sigma$ -algebra is the Borel $\\sigma$ -algebra,

","hasSummary":false,"hasTitle":true,"title":"Default

\\sigma

-algebras","height":205,"width":980},"classes":"l0","position":{"x":22755.728060176196,"y":8475.307295579609}},{"group":"nodes","data":{"id":"def:VectSpace","name":"definition","text":"

Definition 1 (Vector space). Let $K= \\mathbb{R}$ or $K=\\mathbb{C}$ . $(E,+,.)$ is a $K$ vector space if $+$ and $.$ are such that

$\\forall x,y\\in E,\\quad x+y \\in E$
$x+y=y+x$
$(x+y)+z=x+(y+z)$
$\\exists x, \\forall y, \\quad x+y=y$ ( $x=0$ )
$\\forall x,\\exists y, \\quad x+y=0$ ( $x=-y$ )
$\\forall \\alpha\\in K \\text{ and } x\\in E, \\quad \\alpha.x \\in E$
$\\alpha.(x+y)=\\alpha.x + \\alpha.y$
$(\\alpha+\\beta).x = \\alpha.x+\\beta.x$
$\\alpha.(\\beta.x) = \\alpha\\beta.x$

Elements of $E$ are called vectors, and elements of $K$ are called scalars.

","parent":"subsec:VectSpaces","rank":"0","html_name":"def:VectSpace","summary":"

Definition 1 (Vector space). Let $K= \\mathbb{R}$ or $K=\\mathbb{C}$ . $(E,+,.)$ is a $K$ vector space if $+$ and $.$ are such that

$\\forall x,y\\in E,\\quad x+y \\in E$
$x+y=y+x$
$(x+y)+z=x+(y+z)$
$\\exists x, \\forall y, \\quad x+y=y$ ( $x=0$ )
$\\forall x,\\exists y, \\quad x+y=0$ ( $x=-y$ )
$\\forall \\alpha\\in K \\text{ and } x\\in E, \\quad \\alpha.x \\in E$
$\\alpha.(x+y)=\\alpha.x + \\alpha.y$
$(\\alpha+\\beta).x = \\alpha.x+\\beta.x$
$\\alpha.(\\beta.x) = \\alpha\\beta.x$

Elements of $E$ are called vectors, and elements of $K$ are called scalars.

","hasSummary":false,"hasTitle":true,"title":"Vector space","height":198,"width":980},"classes":"l0","position":{"x":11579.396635227931,"y":11530.966101934808}},{"group":"nodes","data":{"id":"def:FreeSys","name":"definition","text":"

Definition 2 (Free system). Vectors $x_1,...,x_n\\in E$ are free if and only if $\\alpha_1.x_1+...+\\alpha_nx_n=0 \\Rightarrow \\forall i\\in \\{1,..,n\\},\\quad \\alpha_i = 0.$ The word \"independent\" is sometimes used instead of \"free\".

","parent":"subsec:VectSpaces","rank":"0","html_name":"def:FreeSys","summary":"

","hasSummary":false,"hasTitle":true,"title":"Free system","height":198,"width":980},"classes":"l0","position":{"x":12728.226213056792,"y":10844.920114152294}},{"group":"nodes","data":{"id":"def:GenSys","name":"definition","text":"

Definition 3 (Generating system). Vectors $x_1,...,x_n\\in E$ are generators of $E$ if and only if $\\forall x\\in E, \\exists \\alpha_i,\\quad \\alpha_1.x_1+...+\\alpha_nx_n=x$

","parent":"subsec:VectSpaces","rank":"0","html_name":"def:GenSys","summary":"

Definition 3 (Generating system). Vectors $x_1,...,x_n\\in E$ are generators of $E$ if and only if $\\forall x\\in E, \\exists \\alpha_i,\\quad \\alpha_1.x_1+...+\\alpha_nx_n=x$

","hasSummary":false,"hasTitle":true,"title":"Generating system","height":198,"width":980},"classes":"l0","position":{"x":13039.651455434217,"y":11250.710804583194}},{"group":"nodes","data":{"id":"def:Basis","name":"definition","text":"

Definition 4 (Basis). Vectors $x_1,...,x_n\\in E$ are a basis of $E$ if and only if they are both a free system and a generating system of $E$ . $n$ is called the dimension of $E$ .

","parent":"subsec:VectSpaces","rank":"0","html_name":"def:Basis","summary":"

Definition 4 (Basis). Vectors $x_1,...,x_n\\in E$ are a basis of $E$ if and only if they are both a free system and a generating system of $E$ . $n$ is called the dimension of $E$ .

","hasSummary":false,"hasTitle":true,"title":"Basis","height":198,"width":980},"classes":"l0","position":{"x":13974.238751330833,"y":10803.711804944005}},{"group":"nodes","data":{"id":"def:SubSpace","name":"definition","text":"

Definition 5 (Subspace). $V$ is a sub vector space of $E$ if and only if $V\\subset E$ and $\\alpha.x+\\beta.y\\in V$ for all $x,y\\in V$ and $\\alpha,\\beta\\in K$ .

","parent":"subsec:VectSpaces","rank":"0","html_name":"def:SubSpace","summary":"

Definition 5 (Subspace). $V$ is a sub vector space of $E$ if and only if $V\\subset E$ and $\\alpha.x+\\beta.y\\in V$ for all $x,y\\in V$ and $\\alpha,\\beta\\in K$ .

","hasSummary":false,"hasTitle":true,"title":"Subspace","height":198,"width":980},"classes":"l0","position":{"x":11013.555366699075,"y":10441.520276248375}},{"group":"nodes","data":{"id":"def:Span","name":"definition","text":"

Definition 6 (Span of a set of vectors). Let $x_1,..,x_k\\in E$ . The span of $x_1,..,x_k$ is the set generated by all the linear combinations: $\\operatorname{span}(\\{x_1,..,x_n\\}) = \\{ \\alpha_1 x_1 +...+ \\alpha_k x_k, \\alpha_i \\in K \\}.$ It can be checked that the span is a vector subspace of $E$ .
\nAlternatively the span of a matrix $A$ is defined as $\\operatorname{span}(A) = \\{ AX, X\\in K^n\\}.$

When the column of $A$ are the coordinate vectors of $x_1,..,x_k$ , the span of $A$ are the coordinates of the elements of $\\operatorname{span}(\\{x_1,..,x_n\\})$ .

","parent":"subsec:VectSpaces","rank":"0","html_name":"def:Span","summary":"

When the column of $A$ are the coordinate vectors of $x_1,..,x_k$ , the span of $A$ are the coordinates of the elements of $\\operatorname{span}(\\{x_1,..,x_n\\})$ .

","hasSummary":false,"hasTitle":true,"title":"Span of a set of vectors","height":198,"width":980},"classes":"l0","position":{"x":11856.999926963139,"y":9734.551872039543}},{"group":"nodes","data":{"id":"def:Coords","name":"definition","text":"

Definition 7 (Coordinates). When $e_1,...,e_n\\in E$ is a basis of $E$ it can be proved that each vector $x$ has a unique decomposition $x= \\alpha_1.e_1 + ... + \\alpha_n.e_n.$

$\\begin{pmatrix}\\alpha_1\\\\.\\\\.\\\\ \\alpha_n\\end{pmatrix}\\in K^n$ is called the coordinate vector of $x$ in the basis $e_1,...,e_n$ . $\\alpha_i$ is often noted $x_i$ , the coordinate vector becomes $\\begin{pmatrix}x_1\\\\.\\\\.\\\\ x_n\\end{pmatrix}$ . Warning: depending on the context, $x_i$ sometimes refers to a coordinate of $x$ , or to a vector among a set of vectors $x_1,...,x_n\\in E$ .

","parent":"subsec:VectSpaces","rank":"0","html_name":"def:Coords","summary":"

Definition 7 (Coordinates). When $e_1,...,e_n\\in E$ is a basis of $E$ it can be proved that each vector $x$ has a unique decomposition $x= \\alpha_1.e_1 + ... + \\alpha_n.e_n.$

","hasSummary":false,"hasTitle":true,"title":"Coordinates","height":198,"width":980},"classes":"l0","position":{"x":13145.822712594667,"y":10256.69575153816}},{"group":"nodes","data":{"id":"def:BasChg","name":"definition","text":"

Definition 8 (Basis change). Let $B=(e_1,...,e_n)$ and $B'=(e'_1,...,e'_n)$ be $2$ basis of $E$ . For $x\\in E$ note $X$ its coordinates in the first basis $B$ and $X'$ its coordinates in the basis $B'$ . They are related by $X = PX'$ where $P$ is a matrix whose $j$ -th column is the coordinate vector of $e'_j$ in the basis $B$ . $P$ is invertible and $X' = P^{-1}X.$

","parent":"subsec:VectSpaces","rank":"0","html_name":"def:BasChg","summary":"

","hasSummary":false,"hasTitle":true,"title":"Basis change","height":198,"width":980},"classes":"l0","position":{"x":13709.444224257108,"y":9660.009061561592}},{"group":"nodes","data":{"id":"rem:ExVectsp","name":"remark","text":"

Remark 1 (Common examples of vector spaces).

$K^n$ , $(\\alpha_1,..,\\alpha_n) + (\\beta_1,..,\\beta_n) =(\\alpha_1+\\beta_1,..,\\alpha_n+\\beta_n)$ $\\beta.(\\alpha_1,..,\\alpha_n) =(\\beta \\alpha_1,..,\\beta \\alpha_n)$
Set of functions from an arbitrary domain and taking values in $K$ , $(f+g)(x) = f(x)+g(x)$ $\\alpha.f(x) = \\alpha.f(x)$

","parent":"subsec:VectSpaces","rank":"0","html_name":"rem:ExVectsp","summary":"

Remark 1 (Common examples of vector spaces).

$K^n$ , $(\\alpha_1,..,\\alpha_n) + (\\beta_1,..,\\beta_n) =(\\alpha_1+\\beta_1,..,\\alpha_n+\\beta_n)$ $\\beta.(\\alpha_1,..,\\alpha_n) =(\\beta \\alpha_1,..,\\beta \\alpha_n)$
Set of functions from an arbitrary domain and taking values in $K$ , $(f+g)(x) = f(x)+g(x)$ $\\alpha.f(x) = \\alpha.f(x)$

","hasSummary":false,"hasTitle":true,"title":"Common examples of vector spaces","height":297,"width":980},"classes":"l0","position":{"x":13033.723852237516,"y":11823.87387793776}},{"group":"nodes","data":{"id":"def:Mat","name":"definition","text":"

Definition 9 (Matrix). A matrix is a $2$ -dimensional array containing elements of $K$ .

","parent":"subsec:Mats","rank":"0","html_name":"def:Mat","summary":"

Definition 9 (Matrix). A matrix is a $2$ -dimensional array containing elements of $K$ .

","hasSummary":false,"hasTitle":true,"title":"Matrix","height":198,"width":980},"classes":"l0","position":{"x":17282.57926982218,"y":8677.258398557675}},{"group":"nodes","data":{"id":"def:MatMul","name":"definition","text":"

Definition 10 (Matrix multiplication). Let $A$ matrix of size $m\\times n$ and $B$ a matrix of size $n\\times p$ . The matrix multiplication of $A$ and $B$ , noted $C=AB$ , is a matrix of size $m\\times p$ whose elements are defined by $C_{ij} = \\sum_{k=1}^n A_{ik}B_{kj}.$ Visual representation: $\\begin{pmatrix} \\\\ \n\\\\\nA_{i1}&..&A_{in} \\\\\n\\\\\n\\end{pmatrix} \n\\begin{pmatrix} \n&&B_{1j}&&\\\\\n&&.&&\\\\\n&&.&&\\\\\n&&B_{1n}&&\\\\\n\\end{pmatrix}\n=\\begin{pmatrix} \n&&&&\\\\\n&&&&\\\\\n&&C_{ij}&&\\\\\n&&&&\\\\\n\\end{pmatrix}.$

When $AB=I$ , where $I$ is a matrix with only ones on the diagonal, $A$ and $B$ are inverse to each others: $A=B^{-1}$ .

","parent":"subsec:Mats","rank":"0","html_name":"def:MatMul","summary":"

When $AB=I$ , where $I$ is a matrix with only ones on the diagonal, $A$ and $B$ are inverse to each others: $A=B^{-1}$ .

","hasSummary":false,"hasTitle":true,"title":"Matrix multiplication","height":198,"width":980},"classes":"l0","position":{"x":16417.779790079614,"y":8170.263532408395}},{"group":"nodes","data":{"id":"def:Trans","name":"definition","text":"

Definition 11 (Transpose). Let $M$ be a matrix. The transpose of $M$ is noted $M^T$ and defined by $M^T_{ij}=M_{ji}.$

Important properties: $(A+B)^T = A^T+B^T$ , $(AB)^T=A^TB^T$ , $(A^{-1})^T=(A^T)^{-1}$

","parent":"subsec:Mats","rank":"0","html_name":"def:Trans","summary":"

Definition 11 (Transpose). Let $M$ be a matrix. The transpose of $M$ is noted $M^T$ and defined by $M^T_{ij}=M_{ji}.$

Important properties: $(A+B)^T = A^T+B^T$ , $(AB)^T=A^TB^T$ , $(A^{-1})^T=(A^T)^{-1}$

","hasSummary":false,"hasTitle":true,"title":"Transpose","height":198,"width":980},"classes":"l0","position":{"x":16950.37013182701,"y":7548.4583757792325}},{"group":"nodes","data":{"id":"def:IsoKn","name":"theorem","text":"

Theorem 1 (Bijection with $K^n$ ). Let $E$ be a vector space of finite dimension. Take a basis $e_1,..,e_n$ of $E$ . The function which maps a vector $x\\in E$ to its coordinate vector $X\\in K^n$ is linear and bijective. Hence a basis $e_1,..,e_n$ identifies $E$ with $K^n$ .

","parent":"subsec:LinMaps","rank":"0","html_name":"def:IsoKn","summary":"

","hasSummary":false,"hasTitle":true,"title":"Bijection with

K^n

","height":211,"width":980},"classes":"l0","position":{"x":15687.967979063893,"y":11244.954099266317}},{"group":"nodes","data":{"id":"th:CompLinMaps","name":"theorem","text":"

Theorem 2 (Composition of linear maps). Let $E,F$ and $G$ be $K$ vector spaces of finite dimension with basis $e_1,..,e_n$ , $f_1,..,f_m$ , and $g_1,..,g_p$ . Let $f:E\\rightarrow F$ be a linear map of matrix $A$ and $g:F \\rightarrow G$ be a linear map of matrix $B$ . The matrix of the composition $h=g \\circ f$ is the matrix product $C=AB.$

","parent":"subsec:LinMaps","rank":"0","html_name":"th:CompLinMaps","summary":"

","hasSummary":false,"hasTitle":true,"title":"Composition of linear maps","height":297,"width":980},"classes":"l0","position":{"x":16105.7337414555,"y":9952.548597540048}},{"group":"nodes","data":{"id":"def:LinMap","name":"definition","text":"

Definition 12 (Linear map). A linear map $f$ between the $K$ vector spaces $E$ and $H$ is a function $f:E\\rightarrow H$ such that $\\forall x,y\\in E,\\forall \\alpha,\\beta\\in K, \\quad f(\\alpha.x+_E\\beta y) = \\alpha.f(x) +_H \\beta.f(y)$

","parent":"subsec:LinMaps","rank":"0","html_name":"def:LinMap","summary":"

","hasSummary":false,"hasTitle":true,"title":"Linear map","height":198,"width":980},"classes":"l0","position":{"x":16984.969239969676,"y":11523.917573857172}},{"group":"nodes","data":{"id":"def:MatMap","name":"definition","text":"

Definition 13 (Matrix of a linear map). Let $e_1,..,e_n$ be a basis of $E$ and $f_1,..,f_m$ be a basis of $H$ . The elements of the matrix $M$ of a linear map $f:E\\rightarrow H$ are $m_{ij} = f(e_j)_i,$ where $f(e_j)_i$ is the $i$ -th coordinate of $f(e_j)$ . Note that the matrix $M$ is of size $m\\times n$ .

Let $e'_1,..,e'_n$ and $f'_1,..,f'_m$ be two new basis of $E$ and $H$ . The matrix of $f$ in the new basis is $M'= Q^{-1} M P$ where the columns of $P$ are coordinates of the vectors $e'_i$ in the basis $e_i$ and the columns of $Q$ are coordinates of the vectors $f'_i$ in the basis $f_i$ .

","parent":"subsec:LinMaps","rank":"0","html_name":"def:MatMap","summary":"

","hasSummary":false,"hasTitle":true,"title":"Matrix of a linear map","height":198,"width":980},"classes":"l0","position":{"x":16830.563327358752,"y":10698.882412318088}},{"group":"nodes","data":{"id":"def:Eigen","name":"definition","text":"

Definition 14 (Eigenvectors and eigenvalues). Let $f$ be a linear map from $E$ to $E$ . An eigenvector $x$ is a non null vector such that $f(x)= \\lambda x$ for some scalar $\\lambda\\in K$ . $\\lambda$ is called an eigenvalue. Alternatively, let $M$ be a matrix. A non null column vector $X$ is called an eigenvector when $MX=\\lambda X$ for some scalar $\\lambda\\in K$ . $\\lambda$ is again called an eigenvalue.

","parent":"subsec:LinMaps","rank":"0","html_name":"def:Eigen","summary":"

","hasSummary":false,"hasTitle":true,"title":"Eigenvectors and eigenvalues","height":297,"width":980},"classes":"l0","position":{"x":18580.795461310972,"y":10255.738296787835}},{"group":"nodes","data":{"id":"def:DiagMap","name":"definition","text":"

Definition 15 (Diagonalizable map). A linear map $f$ is diagonalizable if there exists a basis of eigenvectors. In that basis, the matrix $M$ of $f$ is $M= \\begin{pmatrix} \\\\ \n\\lambda_1&&&\\\\\n&\\lambda_2&&\\\\\n&&.&\\\\\n&&&\\lambda_n\\\\\n\\end{pmatrix}$ where the $\\lambda_i$ are the eigenvalues of $f$ . Alternatively, a matrix $A$ is said diagonalizable if there exists invertible matrices $P$ and $Q$ such that $A=PDP^{-1}$ with $D$ a diagonal matrix.

","parent":"subsec:LinMaps","rank":"0","html_name":"def:DiagMap","summary":"

","hasSummary":false,"hasTitle":true,"title":"Diagonalizable map","height":198,"width":980},"classes":"l0","position":{"x":18743.398578871198,"y":9536.883217987297}},{"group":"nodes","data":{"id":"rem:MatMultVect","name":"remark","text":"

Remark 2 (Coordinates of the image). Let $f$ be a linear map of matrix $M$ and $x$ be a vector whose coordinate vector is $X$ . The coordinate vector $Y$ of $f(x)$ is given by the matrix product of $M$ and $X$ , $Y = MX.$

","parent":"subsec:LinMaps","rank":"0","html_name":"rem:MatMultVect","summary":"

","hasSummary":false,"hasTitle":true,"title":"Coordinates of the image","height":297,"width":980},"classes":"l0","position":{"x":17549.755638456132,"y":10218.094491526004}},{"group":"nodes","data":{"id":"def:Pyth","name":"theorem","text":"

Theorem 3 (Pythagore theorem). Let $e_1,...,e_n$ be an orthonormal basis. The norm of a vector $x$ is given by $\\|x\\|^2 = \\sum_i \\langle x,e_i \\rangle^2.$ It is a direct consequence of the linearity (or semi-linearity) of the inner product in both arguments.

","parent":"subsec:InnProd","rank":"0","html_name":"def:Pyth","summary":"

","hasSummary":false,"hasTitle":true,"title":"Pythagore theorem","height":198,"width":980},"classes":"l0","position":{"x":12778.889078858281,"y":6938.557194336066}},{"group":"nodes","data":{"id":"th:OrthProj","name":"theorem","text":"

Theorem 4 (Orthogonal projection on the span of independent vectors). Let $e_1,..,e_n$ be an orthonormal basis of the vector space $E$ . Let $x_1,..,x_k$ be $k$ independent vectors of $E$ and $V=\\operatorname{span}(\\{x_1,..,x_k\\}$ . The coordinates vector of the orthogonal projection of a vector $x\\in E$ on $V$ is $X_p = A(A^TA)^{-1}A^TX,$ where $A$ is the matrix whose columns are the coordinates of the vectors $x_i$ , and $X$ is the coordinate vector of $x$ .

","parent":"subsec:InnProd","rank":"0","html_name":"th:OrthProj","summary":"

","hasSummary":false,"hasTitle":true,"title":"Orthogonal projection on the span of independent vectors","height":395,"width":980},"classes":"l0","position":{"x":11869.63966158844,"y":8913.769158512221}},{"group":"nodes","data":{"id":"th:CauSch","name":"theorem","text":"

Theorem 5 (Cauchy-Schwartz inequality). Let $E$ be an vector space endowed with an inner product. For all $x,y\\in E$ , $\\langle x,y \\rangle \\leq \\|x\\|^2 \\|y\\|^2.$ The inequality is an equality if and only if $x=\\alpha y$ with $\\alpha \\in K$ .

","parent":"subsec:InnProd","rank":"0","html_name":"th:CauSch","summary":"

","hasSummary":false,"hasTitle":true,"title":"Cauchy-Schwartz inequality","height":297,"width":980},"classes":"l0","position":{"x":11674.786509972117,"y":7932.232740648682}},{"group":"nodes","data":{"id":"def:InnProd","name":"definition","text":"

Definition 16 (Inner product). Let $E$ be a vector space on $K=\\mathbb{R}$ . An inner product $\\varphi$ is a map $E\\times E\\rightarrow K$ such that

$\\forall x, \\varphi(x,.)$ and $\\varphi(.,x)$ are linear (bi-linearity)
$\\varphi(x,y)=\\varphi(y,x)$ (symmetry)
$\\forall x\\neq 0, \\varphi(x,x)> 0$ (positive definitness).

A real vector space of finite dimension with an inner product is called \"Euclidean\".
\nWhen $E$ is a vector space on $K=\\mathbb{C}$ , an inner product $\\varphi$ is a map such that

$\\forall x, \\varphi(x,.)$ is linear
$\\varphi(x,y)=\\overline{\\varphi(y,x)}$ (Hermitian symmetry)
$\\forall x\\neq 0, \\varphi(x,x)> 0$ (positive definitness).

The Hermitian symmetry implies that $\\varphi(x,x)$ is real, hence the last condition is meaningful. The linearity in the first argument and the Hermitian symmetry imply that $\\varphi(x,y+z)=\\varphi(x,y)+\\varphi(x,z)$ and $\\varphi(x,\\alpha y)=\\overline \\alpha\\varphi(x,y)$ . A complex vector space of finit dimension is called \"Hermitian\".
\nThe inner product is often noted $\\langle x,y \\rangle$ .
\nTwo vectors $x$ and $y$ are orthogonal when $\\langle x,y \\rangle = 0$ .

","parent":"subsec:InnProd","rank":"0","html_name":"def:InnProd","summary":"

Definition 16 (Inner product). Let $E$ be a vector space on $K=\\mathbb{R}$ . An inner product $\\varphi$ is a map $E\\times E\\rightarrow K$ such that

$\\forall x, \\varphi(x,.)$ and $\\varphi(.,x)$ are linear (bi-linearity)
$\\varphi(x,y)=\\varphi(y,x)$ (symmetry)
$\\forall x\\neq 0, \\varphi(x,x)> 0$ (positive definitness).

A real vector space of finite dimension with an inner product is called \"Euclidean\".
\nWhen $E$ is a vector space on $K=\\mathbb{C}$ , an inner product $\\varphi$ is a map such that

$\\forall x, \\varphi(x,.)$ is linear
$\\varphi(x,y)=\\overline{\\varphi(y,x)}$ (Hermitian symmetry)
$\\forall x\\neq 0, \\varphi(x,x)> 0$ (positive definitness).

","hasSummary":false,"hasTitle":true,"title":"Inner product","height":198,"width":980},"classes":"l0","position":{"x":13309.174662116091,"y":8564.514983015952}},{"group":"nodes","data":{"id":"def:Norm","name":"definition","text":"

Definition 17 (Norm). An inner product defines a vector norm by $\\| x \\|=\\sqrt{\\langle x,x \\rangle}.$

The norm of a vector is its distance to $0$ . The distance between $x$ and $y$ is the distance of $x-y$ to $0$ : $d(x,y)=\\|x-y\\|.$

Important formula: $\\|x-y\\|^2=\\|x\\|^2 + \\|y\\|^2 - 2\\langle x,y \\rangle$

","parent":"subsec:InnProd","rank":"0","html_name":"def:Norm","summary":"

Definition 17 (Norm). An inner product defines a vector norm by $\\| x \\|=\\sqrt{\\langle x,x \\rangle}.$

The norm of a vector is its distance to $0$ . The distance between $x$ and $y$ is the distance of $x-y$ to $0$ : $d(x,y)=\\|x-y\\|.$

Important formula: $\\|x-y\\|^2=\\|x\\|^2 + \\|y\\|^2 - 2\\langle x,y \\rangle$

","hasSummary":false,"hasTitle":true,"title":"Norm","height":198,"width":980},"classes":"l0","position":{"x":12030.956561613142,"y":8376.704379614777}},{"group":"nodes","data":{"id":"def:OrthBas","name":"definition","text":"

Definition 18 (Orthonormal basis). A basis $e_1,...,e_n$ is orthonormal when $\\forall i\\neq j, \\langle e_i,e_j\\rangle = 0$ $\\langle e_i,e_i\\rangle = 1.$

The $i$ -th coordinates of the vector $x$ in the orthonormal basis is $x_i = \\langle x, e_i\\rangle.$ Hence we have $x=\\sum_i \\langle x,e_i\\rangle e_i$ . To prove it, write $x=\\sum_i x_i e_i$ and take the inner product with each $e_j$ .

","parent":"subsec:InnProd","rank":"0","html_name":"def:OrthBas","summary":"

Definition 18 (Orthonormal basis). A basis $e_1,...,e_n$ is orthonormal when $\\forall i\\neq j, \\langle e_i,e_j\\rangle = 0$ $\\langle e_i,e_i\\rangle = 1.$

","hasSummary":false,"hasTitle":true,"title":"Orthonormal basis","height":198,"width":980},"classes":"l0","position":{"x":12831.735871276205,"y":7495.149102832393}},{"group":"nodes","data":{"id":"def:OrthFree","name":"definition","text":"

Definition 19 (Orthogonal implies free). If $k$ non $0$ vectors are orthogonal they are free. To prove it, assume that $\\alpha_1 x_1 +...+ \\alpha_k x_k = 0.$ Hence $\\langle \\alpha_1 x_1 +...+ \\alpha_k x_k, x_1 \\rangle = 0$ since by linearity $\\langle 0,x\\rangle = 0$ . Also, since $\\langle x_i,x_1\\rangle = 0$ for all $i>1$ , we get $\\langle \\alpha_1 x_1 +...+ \\alpha_k x_k, x_1 \\rangle=\\langle \\alpha_1 x_1 , x_1 \\rangle = \\alpha_1 \\| x_1 \\|^2=0$ , hence $\\alpha_1=0$ . We can repeat for each $\\alpha_i$ , which shows the result.

","parent":"subsec:InnProd","rank":"0","html_name":"def:OrthFree","summary":"

","hasSummary":false,"hasTitle":true,"title":"Orthogonal implies free","height":198,"width":980},"classes":"l0","position":{"x":13917.03077715624,"y":7833.184196598475}},{"group":"nodes","data":{"id":"def:InnMat","name":"definition","text":"

Definition 20 (Inner product matrix). Let $e_1,...,e_n$ be a basis. Let $M$ be the matrix whose elements are $M_{i,j} = \\langle e_i,e_j \\rangle.$ $M$ is called the matrix of the inner product. The inner product between two vectors $x$ and $y$ is given by $\\langle x,y \\rangle = X^TMY \\text{ (or } X^TM\\overline{Y} \\text{when the vector space is complex)},$ where $X$ and $Y$ are the coordinate vectors of $x$ and $y$ . The proof is an exercise.
\nConsider a new basis $e'_1,...,e'_n$ and let $P$ be the matrix whose columns are the coordinates of the vectors $e'_i$ in the original basis. Let $X'$ and $Y'$ be the coordinates of $x$ and $y$ in the new basis. Recall that $X=PX'$ . Hence we have $\\langle x,y \\rangle = Y'^T P^TMPX' \\text{ (or } Y'^T P^TM\\overline{PX'})$ and the matrix of the inner product in the new basis is $M' = P^TMP \\text{ (or } P^TM\\overline{P}).$ Note the difference with the change of basis of linear maps.

","parent":"subsec:InnProd","rank":"0","html_name":"def:InnMat","summary":"

","hasSummary":false,"hasTitle":true,"title":"Inner product matrix","height":198,"width":980},"classes":"l0","position":{"x":14654.663734697007,"y":8283.979878399488}},{"group":"nodes","data":{"id":"def:OrthProj","name":"definition","text":"

Definition 21 (Orthogonal projection). Let $E$ be a vector space with an inner product $\\langle .,. \\rangle$ and $V$ be a vector subspace of $E$ . Let $p\\in V$ . The condition $p=\\text{argmin}_{y\\in V} \\| x-y \\|.$ is equivalent to $\\forall y\\in V, \\langle x-p,y \\rangle=0.$ The proof is an exercise. When the condition is verified, $p$ is called the orthogonal projection of $x$ .

","parent":"subsec:InnProd","rank":"0","html_name":"def:OrthProj","summary":"

","hasSummary":false,"hasTitle":true,"title":"Orthogonal projection","height":198,"width":980},"classes":"l0","position":{"x":10762.815282086516,"y":8366.455920824794}},{"group":"nodes","data":{"id":"rem:InnOrthBas","name":"remark","text":"

Remark 3 (Inner product in orthogonal basis). Let $E$ be a real vector space. In an orthonormal basis the scalar product of $x$ and $y$ is given by $\\langle x,y \\rangle = \\sum x_i y_i,$ where the $x_i$ and $y_i$ are the coordinates of $x$ and $y$ . When $E$ is complex, the formula becomes $\\langle x,y \\rangle = \\sum x_i \\overline{y_i}.$ It can be shown directly using the linearity properties, or from the matrix expression of inner products.

","parent":"subsec:InnProd","rank":"0","html_name":"rem:InnOrthBas","summary":"

","hasSummary":false,"hasTitle":true,"title":"Inner product in orthogonal basis","height":297,"width":980},"classes":"l0","position":{"x":14510.027075352717,"y":7067.834403688812}},{"group":"nodes","data":{"id":"rem:OrthProjBas","name":"remark","text":"

Remark 4 (Projection in an orthonormal basis). Let $e_1,..,e_n$ be an orthonormal basis. Recall that for all $x\\in E$ , $x=\\sum_{i=1}^{n} \\langle x,e_i\\rangle e_i.$ The point $y=\\sum_{i=1}^{k} \\langle x,e_i\\rangle e_i.$ is the orthogonal projection of $x$ on the subspace generated by $e_1,..,e_k$ .

","parent":"subsec:InnProd","rank":"0","html_name":"rem:OrthProjBas","summary":"

","hasSummary":false,"hasTitle":true,"title":"Projection in an orthonormal basis","height":297,"width":980},"classes":"l0","position":{"x":10782.596613956468,"y":6946.372554210607}},{"group":"nodes","data":{"id":"def:ConvCont","name":"definition","text":"

Definition 23 (Convolution of $\\mathbb{R}$ ). Let, $f:\\mathbb{R}\\rightarrow \\mathbb{C}$ and $g:\\mathbb{R}\\rightarrow \\mathbb{C}$ , the convolution is defined as $\\forall x\\in \\mathbb{R},\\quad (f*g)(x) = \\int_{-\\infty}^{+\\infty} f(u)g(x-u)du$

","parent":"subsec:Conv","rank":"0","html_name":"def:ConvCont","summary":"

Definition 23 (Convolution of $\\mathbb{R}$ ). $\\forall x\\in \\mathbb{R},\\quad (f*g)(x) = \\int_{-\\infty}^{+\\infty} f(u)g(x-u)du$

","hasSummary":true,"hasTitle":true,"title":"Convolution of

\\mathbb{R}

","height":385,"width":980},"classes":"l0","position":{"x":3656.171782602364,"y":6611.864062671482}},{"group":"nodes","data":{"id":"def:ConvDisc","name":"definition","text":"

Definition 24 (Discrete convolution $(\\mathbb{Z})$ ). Let $(f_n)_{n\\in \\mathbb{Z}}$ and $(g_n)_{n\\in \\mathbb{Z}}$ be complex bilateral sequences:
\n $\\forall x\\in \\mathbb{Z},\\quad \\left((f_n)*(g_n)\\right)(x) = \\sum_{u=-\\infty}^{\\infty} f_ug_{x-u}$

This definition can be obtained from the continuous case using distributions. Let $f_s = f.\\sum_{u=-\\infty}^{\\infty} \\delta_{uT_s} \\quad \\text{ and }\\quad g_s = g.\\sum_{u=-\\infty}^{\\infty} \\delta_{uT_s},$ where $f$ and $g$ are the functions from the continuous definition and $T_s$ is a sampling period. Then

$(f_n)*(g_n)(x) = (f*g)(xT_e)$

","parent":"subsec:Conv","rank":"0","html_name":"def:ConvDisc","summary":"

Definition 24 (Discrete convolution $(\\mathbb{Z})$ ). $\\forall x\\in \\mathbb{Z},\\quad \\left((f_n)*(g_n)\\right)(x) = \\sum_{u=-\\infty}^{\\infty} f_ug_{x-u}$

","hasSummary":true,"hasTitle":true,"title":"Discrete convolution

(\\mathbb{Z})

","height":366,"width":980},"classes":"l0","position":{"x":3646.2432397097928,"y":7331.0800098771215}},{"group":"nodes","data":{"id":"def:ConvArr","name":"definition","text":"

Definition 25 (Convolution of arrays $(\\{0,...,N-1\\})$ ). (multiplication of polynomials):
\nLet $f$ and $g$ be two complex arrays of size $M$ and $N$ , with first index $0$ . Their convolution is an array of size $M+N-1$ , $\\forall x\\in \\{0,..,M+N-1\\},\\quad (f*g)(k) = \\sum_{u=\\max(0,n-N+1)}^{\\min(n,M-1)} f(u)g(x-u)$ Remark: this definition coincides with the multiplication of polynomials.
\n

This definition can also be deduced from the discrete convolution by defining $f_\\mathbb{Z}$ and $g_\\mathbb{Z}$ to be the sequences extending $f$ and $g$ by $0$ on all integers:

$\\forall x\\in \\{0,..,M+N-1\\},\\quad (f*g)(x) = (f_\\mathbb{Z}*g_\\mathbb{Z})(x)$

","parent":"subsec:Conv","rank":"0","html_name":"def:ConvArr","summary":"

Definition 25 (Convolution of arrays $(\\{0,...,N-1\\})$ ). $\\forall x\\in \\{0,..,M+N-1\\},\\quad (f*g)(k) = \\sum_{u=\\max(0,n-N+1)}^{\\min(n,M-1)} f(u)g(x-u)$

","hasSummary":true,"hasTitle":true,"title":"Convolution of arrays

(\\{0,...,N-1\\})

","height":435,"width":1235},"classes":"l0","position":{"x":3613.8255533884385,"y":8154.398100232943}},{"group":"nodes","data":{"id":"def:ConvCirc","name":"definition","text":"

Definition 26 (Circular convolution, or convolution of $\\mathbb{R}/\\mathbb{Z}$ ). Let $f$ and $g$ be periodic complex functions $f:\\mathbb{R}\\rightarrow \\mathbb{C}$ , $g:\\mathbb{R}\\rightarrow \\mathbb{C}$ , of period $T$ . Their convolution is defined as

$\\forall x\\in \\mathbb{R},\\quad (f*g)(x)= \\int_0^T f(u)g(x-u)du.$

It is possible to express the circular convolution using the linear convolution. Let $f$ and $g$ be $T$ periodic function and $p_T$ the indicator function (gate function) of $[0,T[$ ,

$\\forall x\\in \\mathbb{R},\\quad (circular)(f*g)(x)= (linear) \\left((f.p_T)*g\\right).$

This circular convolution can also be expressed for functions $f:[0,T[\\rightarrow \\mathbb{C}$ , $g:[0,T[\\rightarrow \\mathbb{C}$ as $\\forall x\\in [0,T[,\\quad (f*g)(x)= \\int_0^T f(u)g((x-u) \\mod T)du.$

","parent":"subsec:Conv","rank":"0","html_name":"def:ConvCirc","summary":"

Definition 26 (Circular convolution, or convolution of $\\mathbb{R}/\\mathbb{Z}$ ). $\\forall x\\in \\mathbb{R},\\quad (f*g)(x)= \\int_0^T f(u)g(x-u)du.$

","hasSummary":true,"hasTitle":true,"title":"Circular convolution, or convolution of

\\mathbb{R}/\\mathbb{Z}

","height":431,"width":980},"classes":"l0","position":{"x":4883.247163725782,"y":7043.810457638875}},{"group":"nodes","data":{"id":"def:ConvCircDisc","name":"definition","text":"

Definition 27 (Discrete circular convolution $(\\{0,...,N-1\\})$ ). Let $f$ and $g$ be two complex arrays of same size $N$ . Their circular convolution is defined as

$\\forall x\\in \\{0,..,N-1\\},\\quad (f*g)(x) = \\sum_{u=0}^{N-1} f(u)g(x-u \\mod N).$

","parent":"subsec:Conv","rank":"0","html_name":"def:ConvCircDisc","summary":"

Definition 27 (Discrete circular convolution $(\\{0,...,N-1\\})$ ). $\\forall x\\in \\{0,..,N-1\\},\\quad (f*g)(x) = \\sum_{u=0}^{N-1} f(u)g(x-u \\mod N).$

","hasSummary":true,"hasTitle":true,"title":"Discrete circular convolution

(\\{0,...,N-1\\})

","height":422,"width":1114},"classes":"l0","position":{"x":4842.945542025731,"y":7960.554286134175}},{"group":"nodes","data":{"id":"rem:ConvArrCirc","name":"remark","text":"

Remark 6 (Array convolution as a circular convolution). Let $f$ and $f$ be two arrays of size $M$ and $N$ . The different convolutions differ in the way they treat border effects. However, when the arrays are padded with enough zeros, the circular convolution becomes identical to the array convolution. Note $Pf$ and $Pg$ the extension of $f$ and $g$ by zeros such that $Pf$ and $Pg$ have size $N+M-1$ (the letter $P$ stands for zeros-padded). Then $\\text{array convolution}\\quad (Pf * Pg) = \\text{array convolution}\\quad (f * g).$

","parent":"subsec:Conv","rank":"0","html_name":"rem:ConvArrCirc","summary":"

Remark 6 (Array convolution as a circular convolution). Circular convolution of extended array $\\leftrightarrow$ array convolution

","hasSummary":true,"hasTitle":true,"title":"Array convolution as a circular convolution","height":322,"width":980},"classes":"l0","position":{"x":2287.4595593855984,"y":7685.409631665113}},{"group":"nodes","data":{"id":"def:FT","name":"definition","text":"

Definition 28 (Fourier transform). Remark: there exists different conventions for the normalization coefficients and the argument of the exponential.

Fourier
\n $f:\\mathbb{R}\\rightarrow \\mathbb{C}$ , $\\forall \\nu\\in \\mathbb{R},\\quad \\mathcal{F}(f)(\\nu) = \\int_{-\\infty}^{+\\infty} f(x)e^{-2i\\pi\\nu x} dx$
Inverse Fourier
\n $F:\\mathbb{R}\\rightarrow \\mathbb{C}$ , $\\forall x\\in \\mathbb{R},\\quad \\mathcal{F}^{-1}(F)(x) = \\int_{-\\infty}^{+\\infty} F(\\nu)e^{2i\\pi\\nu x} d\\nu$

For function $f$ in $\\mathcal{L}^1(\\mathbb{R})$ the Fourier transform can be expressed as a limit of Fourier coefficients,

$\\mathcal{F}(f)(\\nu) = \\lim_{T\\rightarrow \\infty} T.c_n \\left(f_T\\right),\\quad \\text{with } n=\\lfloor \\nu T \\rfloor ,$ where $\\lfloor x \\rfloor$ is the integer part of $x$ and $f_T$ is the function $f$ restricted to the interval $[-\\frac{T}{2},-\\frac{T}{2}[$ . Note that since the $c_n$ can be defined from the DFT, the Fourier transform can also be defined from the DFT.

","parent":"subsec:F","rank":"0","html_name":"def:FT","summary":"

Definition 28 (Fourier transform).

Fourier
\n $f:\\mathbb{R}\\rightarrow \\mathbb{C}$ , $\\forall \\nu\\in \\mathbb{R},\\quad \\mathcal{F}(f)(\\nu) = \\int_{-\\infty}^{+\\infty} f(x)e^{-2i\\pi\\nu x} dx$
Inverse Fourier
\n $F:\\mathbb{R}\\rightarrow \\mathbb{C}$ , $\\forall x\\in \\mathbb{R},\\quad \\mathcal{F}^{-1}(F)(u) = \\int_{-\\infty}^{+\\infty} F(\\nu)e^{2i\\pi\\nu x} d\\nu$

","hasSummary":true,"hasTitle":true,"title":"Fourier transform","height":808,"width":980},"classes":"l0","position":{"x":8575.29693013847,"y":6650.129022364675}},{"group":"nodes","data":{"id":"def:FS","name":"definition","text":"

Definition 29 (Fourier series).

Fourier
\nFor $n\\in \\mathbb{Z}$ , let $e_n:\\mathbb{R}\\rightarrow \\mathbb{C}$ be $T$ -periodic functions defined by $e_n(x)=e^{2i\\pi \\frac{n}{T}x}.$ $(e_n)_{n\\in \\mathbb{Z}}$ are normed and orthogonal to each other for the scalar product $\\langle f,g \\rangle = \\frac{1}{T}\\int_0^T f\\overline{g}.$ They form a \"Hilbert orthonormal basis\" of the vector space of complex functions $f$ $T$ -perdiodic and such that $\\int_0^T |f|^2<\\infty$ . The adjective \"Hilbert\" refers to the fact that it has an infinite (countable) number of vectors, unlike traditional basis. The Fourier coefficients are the coefficients in that basis. Let $f:\\mathbb{R}\\rightarrow \\mathbb{C}$ , $T$ periodic, $\\forall n\\in \\mathbb{Z},\\quad c_n(f) = \\langle f,e_n \\rangle =\\frac{1}{T} \\int_{0}^{T} f(x)e^{-2i\\pi \\frac{n}{T} x}dx$
Inverse Fourier
\n $(c_n)_{n\\in \\mathbb{Z}}$ , $f(x)= \\sum_{n=-\\infty}^{n=+\\infty} c_n e^{2i\\pi \\frac{n}{T} x}$

The Fourier coefficients can also be defined for non periodic functions $f:[a,a+T[\\rightarrow \\mathbb{C}$ .

The Fourier coefficient can be obtained from the Fourier Transform by the following way. Let $p_T$ be the indicator (gate function) of the interval $[0,T[$ ,

$c_n(f) =\\frac{1}{T} \\mathcal{F}(f.p_T)(\\frac{n}{T})$

The Fourier coefficient can also be obtained as a limit of the $\\operatorname{DFT}$ . Let

$f_N(x) = f\\left(x\\frac{T}{N}\\right), \\quad x \\in \\{0,...,N-1\\}.$

Then $\\begin{aligned}\nc_n(f) &=& \\frac{1}{T} \\int_{0}^{T} f(x)e^{-2i\\pi \\frac{n}{T} x}dx\\\\\n&=&\\lim_{N \\rightarrow \\infty} \\frac{1}{T}\\frac{T}{N} \\sum_{x=0}^{N-1} f\\left(x\\frac{T}{N}\\right)e^{-2i\\pi \\frac{n}{T} x\\frac{T}{N}}\\\\\n&=& \\lim_{N \\rightarrow \\infty} \\frac{1}{N} \\sum_{x=0}^{N-1} f\\left(x\\frac{T}{N}\\right)e^{-2i\\pi \\frac{n}{N} x}\\\\\n&=&\\lim_{N \\rightarrow \\infty} \\frac{1}{N} \\operatorname{DFT}\\left( f_N \\right)(k),\\quad \\text{with } k=n \\mod N\\\\\\end{aligned}$

The last line is obtained after noticing that $e^{-2i\\pi \\frac{n}{N} x}=e^{-2i\\pi \\frac{n+N}{N} x}$ and $e^{-2i\\pi \\frac{n}{N} x}=e^{-2i\\pi \\frac{n \\mod N}{N} x}$ .

","parent":"subsec:F","rank":"0","html_name":"def:FS","summary":"

Definition 29 (Fourier series).

Fourier
\n $\\forall n\\in \\mathbb{Z},\\quad c_n(f) = \\langle f,e_n \\rangle =\\frac{1}{T} \\int_{0}^{T} f(x)e^{-2i\\pi \\frac{n}{T} x}dx$
Inverse Fourier
\n $f(x)= \\sum_{n=-\\infty}^{n=+\\infty} c_n e^{2i\\pi \\frac{n}{T} x}$

","hasSummary":true,"hasTitle":true,"title":"Fourier series","height":693,"width":980},"classes":"l0","position":{"x":7408.464074026597,"y":7271.025032550924}},{"group":"nodes","data":{"id":"def:DFT","name":"definition","text":"

Definition 30 (Discrete Fourier Transform (DFT)).

Fourier
\nLet $N\\in \\mathbb{N}$ . Let $e_n:\\{0,..,N-1\\}\\rightarrow \\mathbb{C}$ be the function $e_n(x) = e^{2i\\pi \\frac{x}{N}}.$ The $e_n$ with $n\\in \\{0,..,N-1\\}$ form an orthonormal basis of functions $\\{0,..,N-1\\}\\rightarrow \\mathbb{C}$ for the scalar product
\n
$\\langle f,g \\rangle =\\frac{1}{N} \\sum_{k=0}^{N-1}f(x)\\overline{g(x)}.$
\n
Up to a scaling factor, the DFT is the decomposition in that basis. Let $f:\\{0,..,N-1\\}\\rightarrow \\mathbb{C}$ , $\\forall k\\in \\{0,..,N-1\\},\\quad \\operatorname{DFT}(f)(k) = N \\langle f,e_n\\rangle= \\sum_{u=0}^{N-1} f(u)e^{-2i\\pi \\frac{k}{N} u}$
Inverse Fourier
\nLet $F:\\{0,..,N-1\\}\\rightarrow \\mathbb{C}$ , $\\forall x\\in \\{0,..,N-1\\},\\quad \\operatorname{DFT}^{-1}(F)(x) = \\frac{1}{N} \\sum_{k=0}^{N-1} F(k)e^{2i\\pi \\frac{k}{N} x}$

Remarks: the normalization coefficient $\\frac{1}{N}$ appears here in the inverse DFT. This is a question of convention, it could be put in the direct DFT to be more consistent with the Fourier series formulation.
\n

The DFT can be defined from Fourier series or Fourier transform using distributions. Let $0<T_s$ be an arbitrary sampling period and $f$ be the distribution

$\\tilde f=\\sum_{x=0}^{N-1}f(x) \\delta_{xT_s}.$ When $\\tilde f$ is seen as supported in $[0,T[$ , we have the following relation with the Fourier series coefficients:

$\\operatorname{DFT}(f)(k) =N.T_s. c_k(\\tilde f).$ Note that the $N.T_s$ factor appears only due to the difference of convention between the Fourier series and the $\\operatorname{DFT}$ . When $\\tilde f$ is seen as supported on $[-\\infty,\\infty[$ , we can write

$\\operatorname{DFT}(f)(k) = \\mathcal{F}(f)\\left( \\frac{k}{N T_s} \\right),$

where the Fourier transform $\\mathcal{F}$ is generalized to distributions. Hence the frequency $k$ of the DFT relates to the frequency $\\frac{k}{N T_s}$ of the Fourier transform.

","parent":"subsec:F","rank":"0","html_name":"def:DFT","summary":"

Definition 30 (Discrete Fourier Transform (DFT)).

Fourier
\nThe letter $A$ stands for \"array\". $\\forall k\\in \\{0,..,N-1\\},\\quad \\operatorname{DFT}(f)(k) = N \\langle Af,Ae_n\\rangle= \\sum_{x=0}^{N-1} Af(x)e^{-2i\\pi \\frac{k}{N} x}$
Inverse Fourier
\nLet $f:\\{0,..,N-1\\}\\rightarrow \\mathbb{C}$ , $\\forall x\\in \\{0,..,N-1\\},\\quad \\operatorname{DFT}^{-1}(AF)(x) = \\frac{1}{N} \\sum_{k=0}^{N-1} AF(k)e^{2i\\pi \\frac{k}{N} x}$

","hasSummary":true,"hasTitle":true,"title":"Discrete Fourier Transform (DFT)","height":781,"width":1278},"classes":"l0","position":{"x":8486.033031064639,"y":8179.06956864164}},{"group":"nodes","data":{"id":"rem:GenRemFour","name":"remark","text":"

Remark 7 (General remarks).

The three types Fourier transformations are linear maps of vector spaces: $\\mathcal{F}(\\alpha f +\\beta g) = \\alpha\\mathcal{F}(f) +\\beta\\mathcal{F}(g)$ $c_n(\\alpha f +\\beta g) = \\alpha c_n(f) +\\beta c_n(g)$ $\\operatorname{DFT}(\\alpha f +\\beta g) = \\alpha \\operatorname{DFT}(f) +\\beta \\operatorname{DFT}(g).$ It is also true for the inverses.
Unlike the DFT or Fourier series, the Fourier transform cannot be seen as a decomposition in an orthonormal basis. A reason is that the functions $x\\rightarrow e^{i\\omega x}$ have an infinite norm for the inner product $\\int f\\bar g$ .

","parent":"subsec:F","rank":"0","html_name":"rem:GenRemFour","summary":"

Remark 7 (General remarks).

The three types Fourier transformations are linear maps
The Fourier transform is not a decomposition in an orthonormal basis.

","hasSummary":true,"hasTitle":true,"title":"General remarks","height":492,"width":980},"classes":"l0","position":{"x":8593.468807795278,"y":8930.27275164237}},{"group":"nodes","data":{"id":"th:prodTF","name":"theorem","text":"

Theorem 6 (Fourier Transform). Let $f:\\mathbb{R}\\rightarrow \\mathbb{C}$ and $g:\\mathbb{R}\\rightarrow \\mathbb{C}$ . We have: $\\mathcal{F}(f*g) = \\mathcal{F}(f).\\mathcal{F}(g)$ $\\mathcal{F}(f.g) = \\mathcal{F}(f)*\\mathcal{F}(g)$ $\\mathcal{F}^{-1}(f*g) = \\mathcal{F}(f)^{-1}.\\mathcal{F}^{-1}(g)$ $\\mathcal{F}^{-1}(f.g) = \\mathcal{F}^{-1}(f)*\\mathcal{F}^{-1}(g)$ where the convolution $*$ is defined as the convolution of $\\mathbb{R}$ .

","parent":"subsec:CT","rank":"0","html_name":"th:prodTF","summary":"

Theorem 6 (Fourier Transform). Fourier transform $\\leftrightarrow$ convolution on $\\mathbb{R}$

","hasSummary":true,"hasTitle":true,"title":"Fourier Transform","height":276,"width":980},"classes":"l0","position":{"x":6261.952606954309,"y":6691.136811077134}},{"group":"nodes","data":{"id":"th:prodS","name":"theorem","text":"

Theorem 7 (Fourier series). Let $f:\\mathbb{R}\\rightarrow \\mathbb{C}$ and $g:\\mathbb{R}\\rightarrow \\mathbb{C}$ be $T$ periodic functions. Then we have, $(c_n(f*g)) = T. (c_n(f)).(c_n(g)))$ $(c_n(f.g)) = (c_n(f))*(c_n(g)).$ where $f*g$ is a circular convolution and $(c_n(f))*(c_n(g))$ is a discrete convolution. Note $\\mathcal{F}^{-1}((c_n))$ the inverse Fourier of $c_n$ , $\\mathcal{F}^{-1}((u_n)*(v_n))=\\mathcal{F}^{-1}((u_n)).\\mathcal{F}^{-1}((v_n))$ $\\mathcal{F}^{-1}((u_n).(v_n))=\\frac{1}{T}\\mathcal{F}^{-1}((u_n))*\\mathcal{F}^{-1}((v_n))$ where $\\mathcal{F}^{-1}((u_n))*\\mathcal{F}^{-1}((v_n))$ is a circular convolutions and $(u_n)*(v_n)$ is a discrete convolution.

","parent":"subsec:CT","rank":"0","html_name":"th:prodS","summary":"

Theorem 7 (Fourier series). Fourier series $\\leftrightarrow$ circular ( $\\mathbb{R}/\\mathbb{Z}$ ) / discrete convolution

","hasSummary":true,"hasTitle":true,"title":"Fourier series","height":279,"width":980},"classes":"l0","position":{"x":6258.240960505095,"y":7355.199286445368}},{"group":"nodes","data":{"id":"th:prodDFT","name":"theorem","text":"

Theorem 8 (DFT). Let $Af$ and $Ag$ be complex arrays of size $N$ . Then we have $\\operatorname{DFT}(Af*Ag) = \\operatorname{DFT}(Af).\\operatorname{DFT}(Ag)$ $\\operatorname{DFT}(Af.Ag) = \\frac{1}{N}.\\operatorname{DFT}(Af)*\\operatorname{DFT}(Ag)$ $\\operatorname{DFT}^{-1}(Af*Ag) = N. \\operatorname{DFT}^{-1}(Af).\\operatorname{DFT}^{-1}(Ag)$ $\\operatorname{DFT}^{-1}(Af.Ag) = \\operatorname{DFT}^{-1}(Af)*\\operatorname{DFT}^{-1}(Ag)$ where the convolution $*$ is the discrete circular convolution.

","parent":"subsec:CT","rank":"0","html_name":"th:prodDFT","summary":"

Theorem 8 (DFT). Discrete Fourier transform $\\leftrightarrow$ circular (discrete) convolution

","hasSummary":true,"hasTitle":true,"title":"DFT","height":276,"width":980},"classes":"l0","position":{"x":6267.830374915837,"y":7848.467819309728}},{"group":"nodes","data":{"id":"rem:GenRemProd","name":"remark","text":"

Remark 8 (General remarks). The result expressed in this section are true when quantities exists, and when the order of integrals and sums can changed. Hence they must be confirmed case by case.

","parent":"subsec:CT","rank":"0","html_name":"rem:GenRemProd","summary":"

Remark 8 (General remarks). Results much be checked case by case

","hasSummary":true,"hasTitle":true,"title":"General remarks","height":273,"width":980},"classes":"l0","position":{"x":6267.391601097236,"y":6287.057872604234}},{"group":"nodes","data":{"id":"th:TranFunDer","name":"theorem","text":"

Theorem 12 (Transfer function of the derivative). Consider a function $f(x)=e^{zx}$ defined on $\\mathbb{R}$ , or $\\mathbb{R}/T\\mathbb{Z}$ . The derivative $f'$ exists for all $x$ and $f'(x)=ze^{zx}=z.f(x)$ . Hence, the transfer function of $D$ is simply $H(z) = z.$

It can be checked that the function $H(z)$ does not admit inverse Fourier transform (or inverse Fourier series), in the sens of functions. Hence we cannot write $D(f)=\\mathcal{F}^{-1}(2i\\pi \\nu \\mathcal{F}(f)(\\nu)) = \\mathcal{F}^{-1}(\\nu\\mapsto 2i\\pi \\nu)*f,$ at least in the sens of functions.

","parent":"subsec:DiffOp","rank":"0","html_name":"th:TranFunDer","summary":"

Theorem 12 (Transfer function of the derivative). The transfer function of $D$ is $H(z) = iz.$

","hasSummary":true,"hasTitle":true,"title":"Transfer function of the derivative","height":332,"width":980},"classes":"l0","position":{"x":7387.452722020224,"y":2315.164086156882}},{"group":"nodes","data":{"id":"def:Der","name":"definition","text":"

Definition 33 (Derivative). We say that a function $f:]a,b[\\rightarrow \\mathbb{R}$ is differential in $x$ if $\\lim_{h\\rightarrow 0} \\frac{f(x+h)-f(x)}{h}$ exists. We write then $f'(x)=\\lim_{h\\rightarrow 0} \\frac{f(x+h)-f(x)}{h},$ and $f'(x)$ is called the derivative of $f$ at point $x$ .
\nEquivalently, we can say that $f$ is differentiable in $x$ when there exists $\\alpha\\in \\mathbb{R}$ and $\\varepsilon_x$ $f(x+h) = f(x) + \\alpha.h + \\varepsilon_x(h)h$ where $\\varepsilon_x$ is such that $\\varepsilon_x(h\\rightarrow 0)=0$ . We have then $f'(x)=\\alpha$ . It can be checked that the derivation $D:f\\mapsto f'$ is a linear operator, invariant by translations. The derivative is often noted $\\frac{\\mathrm{d}f}{\\mathrm{d}x}(x)=f'(x)$ .

","parent":"subsec:DiffOp","rank":"0","html_name":"def:Der","summary":"

Definition 33 (Derivative). $f'(x)=\\frac{\\mathrm{d}f}{\\mathrm{d}x}(x)= \\lim_{h\\rightarrow 0} \\frac{f(x+h)-f(x)}{h}$

","hasSummary":true,"hasTitle":true,"title":"Derivative","height":332,"width":980},"classes":"l0","position":{"x":8735.929814648183,"y":2176.035907257376}},{"group":"nodes","data":{"id":"def:DirDer","name":"definition","text":"

Definition 34 (Directional derivative $( \\mathbb{R}^n \\rightarrow \\mathbb{R})$ ). Let $f:]a,b [^n\\rightarrow \\mathbb{R}$ . The directional derivative of $f$ at $x\\in ]a,b [^n$ in the direction $u\\in \\mathbb{R}^n$ is defined when it exists by $\\lim_{h\\rightarrow 0} \\frac{f(x+hu)-f(x)}{h}.$ We write then $\\frac{\\partial f}{\\partial u}(x) = \\lim_{h\\rightarrow 0} \\frac{f(x+hu)-f(x)}{h}.$ $\\frac{\\partial f}{\\partial u}(x)$ is also called a ’partial’ derivative. For a function $f:\\mathbb{R}^n \\rightarrow \\mathbb{R}$ and note $x_i$ the $i$ -th coordinate of $\\mathbb{R}^n$ vectors. The directional derivatives in the direction of the $i$ -th basis vectors is noted $\\frac{\\partial f}{\\partial x_i}(x).$

","parent":"subsec:DiffOp","rank":"0","html_name":"def:DirDer","summary":"

Definition 34 (Directional derivative $( \\mathbb{R}^n \\rightarrow \\mathbb{R})$ ). $\\frac{\\partial f}{\\partial u}(x) = \\lim_{h\\rightarrow 0} \\frac{f(x+hu)-f(x)}{h}.$

","hasSummary":true,"hasTitle":true,"title":"Directional derivative

( \\mathbb{R}^n \\rightarrow \\mathbb{R})

","height":343,"width":980},"classes":"l0","position":{"x":9163.85066889793,"y":1299.503587539544}},{"group":"nodes","data":{"id":"def:Differ1","name":"definition","text":"

Definition 35 (Differentials $( \\mathbb{R}^n \\rightarrow \\mathbb{R} )$ ). Let $f:]a,b [^n\\rightarrow \\mathbb{R}$ . We say that $f$ is differentiable in $x$ if there exists a linear map $\\mathrm{d}f_x: \\mathbb{R}^n \\rightarrow \\mathbb{R}$ and a function $\\varepsilon_x$ such that $f(x+u) = f(x) + \\mathrm{d}f_x(u) + \\varepsilon_x(u)u$ where $\\varepsilon_x$ is such that $\\varepsilon_x(h\\rightarrow 0)=0$ . $\\mathrm{d}f_x$ is called the differential of $f$ at $x$ .
\nIt can be checked that the $\\mathrm{d}f_x(u)$ is the directional derivative in the direction $u$ . Hence the matrix of $\\mathrm{d}f_x$ in the canonical basis of $\\mathbb{R}^n$ is given by $\\mathrm{d}f_x:\n\\begin{pmatrix}\n\\frac{\\partial f}{\\partial e_1}(x)&...&\\frac{\\partial f}{\\partial e_n}(x)\n\\end{pmatrix}$

","parent":"subsec:DiffOp","rank":"0","html_name":"def:Differ1","summary":"

Definition 35 (Differentials $( \\mathbb{R}^n \\rightarrow \\mathbb{R} )$ ). $\\mathrm{d}f_x:\n\\begin{pmatrix}\n\\frac{\\partial f}{\\partial e_1}(x)&...&\\frac{\\partial f}{\\partial e_n}(x)\n\\end{pmatrix}$

","hasSummary":true,"hasTitle":true,"title":"Differentials

( \\mathbb{R}^n \\rightarrow \\mathbb{R} )

","height":332,"width":980},"classes":"l0","position":{"x":8568.119567542746,"y":755.3430877744534}},{"group":"nodes","data":{"id":"def:DifferM","name":"definition","text":"

Definition 36 (Differentials $( \\mathbb{R}^n \\rightarrow \\mathbb{R}^m )$ ). The definition of the differential in the case $f:]a,b [\\rightarrow \\mathbb{R}$ can be directly generalized to the case $f:]a,b [^n\\rightarrow \\mathbb{R}^m$ . We say that $f:]a,b [\\rightarrow \\mathbb{R}^m$ is differentiable in $x$ if there exists a linear map $\\mathrm{d}f_x: \\mathbb{R}^n \\rightarrow \\mathbb{R}$ and a function $\\varepsilon_x$ such that $f(x+u) = f(x) + \\mathrm{d}f_x(u) + \\varepsilon_x(u)u$ where $\\varepsilon_x$ is such that $\\varepsilon_x(h\\rightarrow 0)=0$ . $\\mathrm{d}f_x$ is called the differential of $f$ at $x$ .
\nAssume that $f$ is differentiable. Note $f_i(x)$ the $i$ -th coordinate of $f(x)$ in the canonical basis of $\\mathbb{R}^m$ . $f_i$ is a function $]a,b [^n\\rightarrow \\mathbb{R}$ . Let $(e_i)$ be the canonical basis of $\\mathbb{R}^n$ . The matrix of $\\mathrm{d}f_x$ in the canonical the basis of $\\mathbb{R}^n$ and $\\mathbb{R}^m$ is $\\mathrm{d}f_x:\n\\begin{pmatrix}\n\\frac{\\partial f_1}{\\partial e_1}(x)&...&\\frac{\\partial f_1}{\\partial e_n}(x)\\\\\n.\\\\\n.\\\\\n.\\\\\n\\frac{\\partial f_m}{\\partial e_1}(x)&...&\\frac{\\partial f_m}{\\partial e_n}(x)\\\\\n\\end{pmatrix}$

","parent":"subsec:DiffOp","rank":"0","html_name":"def:DifferM","summary":"

Definition 36 (Differentials $( \\mathbb{R}^n \\rightarrow \\mathbb{R}^m )$ ). $f(x+u) = f(x) + \\mathrm{d}f_x(u) + \\varepsilon_x(u)u$

","hasSummary":true,"hasTitle":true,"title":"Differentials

( \\mathbb{R}^n \\rightarrow \\mathbb{R}^m )

","height":298,"width":980},"classes":"l0","position":{"x":8558.562142572166,"y":194.07915788554078}},{"group":"nodes","data":{"id":"def:GradCon","name":"definition","text":"

Definition 37 (Gradient (!add Riesz to inner prod + cauchy schwartz!)). Let $\\langle.,.\\rangle$ be the canonical inner product of $\\mathbb{R}^n$ . If $f:]a,b [^n\\rightarrow \\mathbb{R}$ is differentiable at $x$ , $\\mathrm{d}f_x$ is a linear map from $\\mathbb{R}^n$ to $\\mathbb{R}$ . Hence there is a vector, noted $\\nabla f_x$ such that $\\forall u\\in \\mathbb{R}^n,\\quad \\mathrm{d}f_x(u) = \\langle \\nabla f_x,u\\rangle.$ $\\nabla f_x$ is called the ’gradient’ of $f$ at $x$ . In the canonical basis the gradient vector is $\\nabla f_x=\n\\begin{pmatrix}\n\\frac{\\partial f}{\\partial e_1}(x)\\\\\n.\\\\\n.\\\\\n.\\\\\n\\frac{\\partial f}{\\partial e_n}(x)\n\\end{pmatrix}.$ Let $u$ be a vector of coordinates $(u_i)$ . We have that $\\mathrm{d}f_x(u) = \\begin{pmatrix}\n\\frac{\\partial f}{\\partial e_1}(x)&...&\\frac{\\partial f}{\\partial e_n}(x)\n\\end{pmatrix}.\n\\begin{pmatrix}\nu_1\\\\\n.\\\\\n.\\\\\n.\\\\\nu_n\\\\\n\\end{pmatrix}\n=\n(\\nabla f_x)^T.\n\\begin{pmatrix}\nu_1\\\\\n.\\\\\n.\\\\\n.\\\\\nu_n\\\\\n\\end{pmatrix}$

The gradient is the direction of steepest variation of the function. This can be shown as follow. The variation of the function between $f(x)$ and $f(x+u)$ is approximated by $\\mathrm{d}f_x(u) = \\langle \\nabla f_x,u\\rangle$ . The Cauchy Schwartz inequality implies that the vectors $u\\in \\mathbb{R}^n$ of unit norm ( $\\|u\\|=1$ ) which maximizes $\\langle \\nabla f_x,u\\rangle^2$ are when $u$ and $\\nabla f_x$ are colinear, that is to say $u= \\nabla f_x$ or $u= -\\nabla f_x$ .

","parent":"subsec:DiffOp","rank":"0","html_name":"def:GradCon","summary":"

Definition 37 (Gradient (!add Riesz to inner prod + cauchy schwartz!)). $\\nabla f_x=\n\\begin{pmatrix}\n\\frac{\\partial f}{\\partial e_1}(x)\\\\\n.\\\\\n.\\\\\n.\\\\\n\\frac{\\partial f}{\\partial e_n}(x)\n\\end{pmatrix}.$

","hasSummary":true,"hasTitle":true,"title":"Gradient (!add Riesz to inner prod + cauchy schwartz!)","height":658,"width":980},"classes":"l0","position":{"x":7425.253545827187,"y":729.7808136044371}},{"group":"nodes","data":{"id":"def:nthDer","name":"definition","text":"

Definition 38 (n-th order derivative). Composing the derivation operator $n$ times gives the ’ $n$ -th order derivative’ noted $f^{(n)}(x)=\\frac{\\mathrm{d}^n f}{\\mathrm{d} x^n}(x)=\\frac{\\mathrm{d} }{\\mathrm{d} x}\\left(...\\frac{\\mathrm{d}f }{\\mathrm{d} x}\\right)(x)$ A function for which the $n$ -th order derivative exists is called ’differentiable at the order $n$ ’.

","parent":"subsec:DiffOp","rank":"0","html_name":"def:nthDer","summary":"

Definition 38 (n-th order derivative). Composing the derivation operator $n$ times gives the ’n-th order derivative’: $f^{(n)}(x)=\\frac{\\mathrm{d}^n f}{\\mathrm{d} x^n}(x)=\\frac{\\mathrm{d}^n }{\\mathrm{d} x}(...\\frac{\\mathrm{d}f }{\\mathrm{d} x})(x)$

","hasSummary":true,"hasTitle":true,"title":"n-th order derivative","height":440,"width":980},"classes":"l0","position":{"x":10366.270358909627,"y":1364.0686261068784}},{"group":"nodes","data":{"id":"def:Lap","name":"definition","text":"

Definition 39 (Laplacian). Let $f$ be a function $f:\\mathbb{R}^n\\rightarrow \\mathbb{R}$ , twice differentiable. The Laplacian operator $\\Delta$ is defined as $\\Delta f (x) = \\sum_{i=1}^{n} \\frac{\\partial^2 f}{\\partial x^2_i}(x).$ In particular, in dimension $1$ and $2$ get $\\Delta f (x) = f^{(2)}(x) \\text{ and } \\Delta f (x) = \\frac{\\partial^2 f}{\\partial x^2_1}(x) + \\frac{\\partial^2 f}{\\partial x^2_2}(x).$

","parent":"subsec:DiffOp","rank":"0","html_name":"def:Lap","summary":"

Definition 39 (Laplacian). $\\Delta f (x) = \\sum_{i=1}^{n} \\frac{\\partial^2 f}{\\partial x^2_i}(x).$ In dimension $1$ and $2$ get $\\Delta f (x) = f^{(2)}(x) \\text{ and } \\Delta f (x) = \\frac{\\partial^2 f}{\\partial x^2_1}(x) + \\frac{\\partial^2 f}{\\partial x^2_2}(x).$

","hasSummary":true,"hasTitle":true,"title":"Laplacian","height":530,"width":980},"classes":"l0","position":{"x":9801.78921427882,"y":-302.15845593828703}},{"group":"nodes","data":{"id":"th:TranFunDisDer","name":"theorem","text":"

Theorem 13 (Transfer function of discrete derivatives). In the following, we define the derivative as $f'(x)=f(x+1)-f(x)$ . The discussion can be adapted to the other definitions. Consider the function $f(k)=e^{zk}.$ We have that $G(k)=H(z).f(k)$ , hence $G(0)=H(z).f(0)$ . And since $f(0)=1$ , $G(0)=H(z).$

From the definition of the gradient, $G(0)=f(0+1)-f(0)=e^{z. 1}-e^{z. 0}=e^z-1$ . Hence $\\begin{aligned}\n H(z)&=&e^z-1.\\\\\\end{aligned}$

Note that the transfer function of the continuous derivation $H_{cont}(z)=z,$ seems very different. However, consider the case where the samples of the discrete function are separated by $\\epsilon$ instead of $1$ . The discrete derivation become $G(k\\epsilon)=\\frac{f(k\\epsilon+\\epsilon)-f(k\\epsilon)}{\\epsilon},$ and the transfer function $H_{\\epsilon}(z)=\\frac{e^{\\epsilon.z}-1}{\\epsilon}.$ We have then $H_{\\epsilon}(z)\\rightarrow z= H_{cont}(z)$ when $\\epsilon \\rightarrow 0$ . Hence for all $z$ , the transfer function of the discrete case gets closer and closer to the one of the continuous case when $\\epsilon \\rightarrow 0$ . It is interesting to note for a fixed $\\epsilon$ , the values of $H_{\\epsilon}(z)$ and $H_{cont}(z)$ are closer and closer when $z\\rightarrow 0$ , and bigger and bigger when $z\\rightarrow \\infty$ . This means that discrete and continuous derivations tend to agree for functions $f$ containing only on low frequencies and give very different results for functions containing high frequencies. This is not a surprising behavior.

","parent":"subsec:DisDifOp","rank":"0","html_name":"th:TranFunDisDer","summary":"

Theorem 13 (Transfer function of discrete derivatives). The transfer function of the discrete derivative $f'(x)=f(x+1)-f(x)$ is $\\begin{aligned}\n H(z)&=&e^z-1\\\\\\end{aligned}$

","hasSummary":true,"hasTitle":true,"title":"Transfer function of discrete derivatives","height":386,"width":980},"classes":"l0","position":{"x":6104.503000925931,"y":2361.81373466607}},{"group":"nodes","data":{"id":"def:DisDer","name":"definition","text":"

Definition 40 (Discrete derivative). The discrete derivative is the analog of the continuous derivation but for functions defined on $\\mathbb{Z}$ , or $\\{0,...,N-1\\}$ . There are several ways to define it. Let $f:\\mathbb{Z}\\rightarrow \\mathbb{R}$ , the $3$ most common definitions are, $f'(x)=f(x+1)-f(x)$ $f'(x)=f(x)-f(x-1)$ $f'(x)= \\frac{f(x+1)-f(x-1)}{2} f(x+1)-f(x).$

","parent":"subsec:DisDifOp","rank":"0","html_name":"def:DisDer","summary":"

Definition 40 (Discrete derivative). Let $f:\\mathbb{Z}\\rightarrow \\mathbb{R}$ . A possible definition of the derivative is $f'(x)=f(x+1)-f(x)$

","hasSummary":true,"hasTitle":true,"title":"Discrete derivative","height":332,"width":980},"classes":"l0","position":{"x":6153.406129183674,"y":1843.942960056564}},{"group":"nodes","data":{"id":"def:GradDis","name":"definition","text":"

Definition 41 (Discrete gradient). Remark: as there are many ways to define the discrete derivative, there are many different ways to define the gradient. They can all be seen as approximations of the continuous definition. We assume here that the discrete derivative is defined as $f'(x)=f(x+1)-f(x)$ . The discrete gradient is defined in the same way as the continuous gradient: it is a vector that contains the directional derivatives in each coordinates.

one dimension
\nFor a function $f:\\mathbb{Z}\\rightarrow \\mathbb{R}$ , the discrete gradient $G:\\mathbb{Z}\\rightarrow \\mathbb{R}$ is the same as the discrete derivative $G(k)=f(k+1)-f(k).$ When the function if defined on a finite set, $f:\\{1,..,N\\}\\rightarrow \\mathbb{R}$ , this gradient function is only defined without ambiguities on $\\{1,..,N-1\\}$ . If we want to define the gradient on $\\{1,..,N\\}$ , the value in $N$ depends on a border convention. The same remark holds for higher dimensions.
two dimensions
\nFor a function $f:\\mathbb{Z}^2\\rightarrow \\mathbb{R}$ , the gradient is a function $G: \\mathbb{Z}^2\\rightarrow \\mathbb{R}^n$ which associates a vector of size $2$ to each point of the domain of $f$ : $G(i,j)\n=\n\\begin{pmatrix}\nG_1(i,j)\\\\\nG_2(i,j)\\\\\n\\end{pmatrix}\n=\n\\begin{pmatrix}\nf(i+1,j)-f(i,j)\\\\\nf(i,j+1)-f(i,j)\\\\\n\\end{pmatrix}.$
arbitrary dimensions
\nFor a function $f:\\mathbb{Z}^n\\rightarrow \\mathbb{R}$ , the gradient becomes $G(k_1,...,k_n)\n=\n\\begin{pmatrix}\nG_1(k_1,...,k_n)\\\\\n.\\\\\n.\\\\\n.\\\\\nG_n(k_1,...,k_n)\\\\\n\\end{pmatrix}\n=\n\\begin{pmatrix}\nf(k_1+1,...,k_n)-f(k_1,..,k_n)\\\\\n.\\\\\n.\\\\\n.\\\\\nf(k_1,...,k_n+1)-f(k_1,..,k_n)\\\\\n\\end{pmatrix}.$

","parent":"subsec:DisDifOp","rank":"0","html_name":"def:GradDis","summary":"

Definition 41 (Discrete gradient). $G(i,j)\n=\n\\begin{pmatrix}\nG_1(i,j)\\\\\nG_2(i,j)\\\\\n\\end{pmatrix}\n=\n\\begin{pmatrix}\nf(i+1,j)-f(i,j)\\\\\nf(i,j+1)-f(i,j)\\\\\n\\end{pmatrix}.$

","hasSummary":true,"hasTitle":true,"title":"Discrete gradient","height":374,"width":980},"classes":"l0","position":{"x":6150.334606657032,"y":716.1554667660994}},{"group":"nodes","data":{"id":"def:GradMask","name":"definition","text":"

Definition 42 (Derivative masks). We address the case of functions defined on $\\mathbb{Z}$ . For functions defined on $\\{0,..,N-1\\}$ , see the remark Remark 10 from the section on translation invariant operators.
\nLet $f:\\mathbb{Z}\\rightarrow \\mathbb{R}$ , and $Mask:\\mathbb{Z}\\rightarrow \\mathbb{R}$ with $Mask(0)=-1$ , $Mask(-1)=1$ and $Mask(k)=0$ everywhere else:

$Mask = \\begin{pmatrix} ..&0&1&-1&0&0&... \\end{pmatrix}$

It is possible to check that the discrete derivative of $f:\\mathbb{Z}\\rightarrow \\mathbb{R}$ , $f'(x)=f(x+1)-f(x)$ can be rewritten as

$G = f*Mask,$

where $*$ is the discrete convolution. The mask should be adapted to each definition of $f'$ . When $f$ is a function $\\mathbb{Z}^n\\rightarrow \\mathbb{R}$ the directional derivative can also be obtained using convolutions masks. In the case $f:\\mathbb{Z}^2\\rightarrow \\mathbb{R}$ , the horizontal directional derivatives is given by the convolution mask $Mask_x = \\begin{pmatrix}\n &&&.&&&\\\\\n &&&.&&&\\\\\n ..&0&0&0&0&0&...\\\\\n ..&0&1&-1&0&0&...\\\\\n ..&0&0&0&0&0&...\\\\\n &&&.&&&\\\\\n &&&.&&&\\\\\n \\end{pmatrix}$

","parent":"subsec:DisDifOp","rank":"0","html_name":"def:GradMask","summary":"

Definition 42 (Derivative masks). Let $f:\\mathbb{Z}\\rightarrow \\mathbb{R}$ $Mask = \\begin{pmatrix} ..&0&1&-1&0&0&... \\end{pmatrix}$ $f' = f*Mask.$ The construction can be adapted to the case $f:\\{0,N-1\\}\\rightarrow \\mathbb{R}$ and to the multi-dimensional case.

","hasSummary":true,"hasTitle":true,"title":"Derivative masks","height":488,"width":980},"classes":"l0","position":{"x":4736.114697313205,"y":1752.8311378577023}},{"group":"nodes","data":{"id":"def:ConfSp","name":"definition","text":"

Definition 48 (Configuration space / universe). The configuration space is usually noted $\\Omega$ . As its name indicates, the set $\\Omega$ contains all the possible configurations of a probabilistic model. Its elements are usually noted $\\omega$ , and we will call them ’elementary configurations’.
\nWarning : the name of the space $\\Omega$ and its elements $\\omega$ vary across contexts ans languages. $\\Omega$ is often called the ’sample space’ or ’universe’, and the elements $\\omega$ ’samples’,’outcomes’ or ’realizations’.
\n

Probabilistic models are very useful to analyse dice rolls and card games. What is a relevant configuration space

to model a dice roll ? $\\Omega = \\{1,2,3,4,5,6\\}$
to model $2$ dice rolls ? $\\Omega = \\{1,2,3,4,5,6\\} \\times \\{1,2,3,4,5,6\\}$
to model $n$ dice rolls ? What is the size of this configuration space? $\\Omega = \\{1,2,3,4,5,6\\}^n$ , which is of size $6^n$ .

What should we chose as configuration space when

the player draws one card ? $\\Omega_1 = \\mathcal{S}$
the player draws one card, puts it back and draws another card ? $\\Omega_2 = \\Omega_1 \\times \\Omega_1$
the player draws two cards without putting them back ? $\\Omega_2$ , or $\\Omega_2\\setminus \\{ (\\omega,\\omega), \\omega \\in \\Omega_1 \\}$

Assume a player draws $n$ cards without putting them back in the deck. What is the size of the smallest configuration space describing the possible results ? $52\\times (52-1)\\times (52-2)\\times ... \\times (52-n+1)=\\frac{52!}{(52-n)!}$

Note that when using Cartesian products, we have $(a,b)\\neq (b,a)$ . The order between the card draws is taken into account. In card games, the order in which cards are drawn is often not important. In that case, when drawing $2$ cards, we have $(a,b)\\sim (b,a)$ .

If we do not distinguish results up to permutations, what is the size of the configuration space when

the player draws one card ? $52$
the player draws $n$ cards, putting the card back in the deck before taking the next one ? $\\frac{52^n}{n!}$
the player draws $n$ cards without putting them back ? $\\frac{52!}{(52-n)!n!}=\n \\begin{pmatrix}52\\\\ n \\end{pmatrix}$

In this course we are particularly interested in signal and image processing problems.

What are the relevant configuration spaces when studying

real signals observed on $1000$ points ? $\\Omega = \\mathbb{R}^{1000}$
continuous real signals of duration $1$ second ? $\\Omega =C([0,1])$
$256\\times 256$ color images ? $\\Omega = \\mathbb{R}^{256\\times 256 \\times 3}$

","parent":"subsec:ConfProb","rank":"0","html_name":"def:ConfSp","summary":"

","hasSummary":true,"hasTitle":true,"title":"Configuration space / universe","height":468,"width":980},"classes":"l0","position":{"x":13393.03060830612,"y":5109.9275802798675}},{"group":"nodes","data":{"id":"def:Ev","name":"definition","text":"

Definition 49 (Events). When the configuration space $\\Omega$ is endowed with a $\\sigma$ -algebra $\\mathcal{A}$ , the elements of $\\mathcal{A}$ are called ’events’. For those unfamiliar with $\\sigma$ -algebra, ’events’ can be defined as subsets of $\\Omega$ .
\nExamples:

when $\\Omega$ is a $52$ card deck, ’the card is a diamond’, ’the card is a $2$ ’, are typical events.
when $\\Omega=\\mathbb{R}^{1000}$ is a set of signals, the event $\\{1\\}\\times \\mathbb{R}^{999}$ describes all the signals starting with $1$ .

","parent":"subsec:ConfProb","rank":"0","html_name":"def:Ev","summary":"

Definition 49 (Events). When the configuration space $\\Omega$ is endowed with a $\\sigma$ -algebra $\\mathcal{A}$ , the elements of $\\mathcal{A}$ are called ’events’. For those unfamiliar with $\\sigma$ -algebras, ’events’ can be defined as subsets of $\\Omega$ .

","hasSummary":true,"hasTitle":true,"title":"Events","height":425,"width":980},"classes":"l0","position":{"x":13427.542481071661,"y":4534.440071296909}},{"group":"nodes","data":{"id":"def:Prob","name":"definition","text":"

Definition 50 (Probability). A probability $P$ is a function which takes in input an event and returns a positive real number. It must verify the following axioms:

axiom 1: $P(\\Omega) = 1$
axiom 2: $P(A\\in \\Omega) \\geq 0$
axiom 3: for a countable number of disjoint events $A_i\\in \\mathcal{A}$ , $P ( \\cup_i A_i) = \\sum_i P(A_i)$ .

As direct consequences, we have:

consequence 1: $P(A^c) = 1-P(A)$
consequence 2: $P(\\emptyset) = 0$
consequence 3: $P(A\\cup B) = P(A)+P(B)-P(A\\cap B)$ . Hence if $A\\cap B=\\emptyset$ then $P(A\\cup B)=P(A)+P(B)$ .

Axioms 2-3 and consequence 2 are precisely axioms of measures, hence a probability is a measure.
\nInterpretation: the probability gives a notion of ’size’ to events. Given that the ’size’ of $\\Omega$ is $1$ , the size of events can be interpreted as the proportion they occupy in $\\Omega$ . Hence, the $P$ of probability can also be read as the $P$ of proportion.

","parent":"subsec:ConfProb","rank":"0","html_name":"def:Prob","summary":"

Definition 50 (Probability). A probability $P$ is a measure on a set $\\Omega$ such that $P(\\Omega) = 1.$

","hasSummary":true,"hasTitle":true,"title":"Probability","height":336,"width":980},"classes":"l0","position":{"x":13469.107194598806,"y":3928.411817425082}},{"group":"nodes","data":{"id":"def:ProbDen","name":"definition","text":"

Definition 51 (Probability density). Let $P$ be a probability on $\\mathbb{R}$ . We say that the function $f$ is the probability density of $P$ when

$\\forall A\\in \\mathbb{R},\\quad P(A)=\\int_A f(x)\\mathrm{d}x.$

Note that $P$ does not always have a density. Take for instance $P$ such that $P({0})=1$ : there are no functions $f$ verifying the above condition.

The following concerns reader familiar with $\\sigma$ -algebras.
\nStrictly speaking, in the previous definition $A$ must be a measurable set. In general the probability density is defined with respect to a reference measure. Let $P$ be a probability measure, and $\\mu$ be a reference measure on a set $E$ . Then $f$ is the density of $P$ with respect to $\\mu$ when $\\forall A\\in \\mathcal{A}_E,\\quad P(A)=\\int_E f\\mathrm{d}\\mu,$ where $\\mathcal{A}_E$ is the $\\sigma$ -algebra of $E$ . $f$ is noted $\\frac{\\mathrm{d}P}{\\mathrm{d}\\mu}$ .

","parent":"subsec:ConfProb","rank":"0","html_name":"def:ProbDen","summary":"

Definition 51 (Probability density).

","hasSummary":true,"hasTitle":true,"title":"Probability density","height":226,"width":980},"classes":"l0","position":{"x":14615.25950129798,"y":3942.3523070315723}},{"group":"nodes","data":{"id":"rem:IntProb","name":"remark","text":"

Remark 12 (Introductory remark). General remark: in most situations the word probability refers to a proportion. For instance, the question \"what is the probability of this event?\" can usually be interpreted as \"what is the proportion of the possible configurations in which that event occurs?\".

","parent":"subsec:ConfProb","rank":"0","html_name":"rem:IntProb","summary":"

","hasSummary":true,"hasTitle":true,"title":"Introductory remark","height":504,"width":980},"classes":"l0","position":{"x":12202.683927367605,"y":5429.029516520528}},{"group":"nodes","data":{"id":"rem:Ev","name":"remark","text":"

Remark 13 (Events and $\\sigma$ -algebra). Most of definitions and results of this section do not focus on measure theoretical aspects of probabilities. Hence, it can be read without knowledge of measure theory. In order to make statements at the same time rigorous and understandable without measure theory, we ’hide’ the $\\sigma$ -algebra behind the word ’event’. In all the section, an ’event’ $A$ of a set $E$ can be understood at $2$ levels:

for readers without notion of measure theory, $A$ is simply a subset of $E$
$E$ is assumed to be endowed with a $\\sigma$ -algebra $\\mathcal{A}$ , and the event $A$ is an element of $\\mathcal{A}$ .

","parent":"subsec:ConfProb","rank":"0","html_name":"rem:Ev","summary":"

Remark 13 (Events and $\\sigma$ -algebra). In all the section, an ’event’ $A$ of a set $E$ can be understood at $2$ levels:

for readers without notion of measure theory, $A$ is simply a subset of $E$
$E$ is assumed to be endowed with a $\\sigma$ -algebra $\\mathcal{A}$ , and the event $A$ is a element of $\\mathcal{A}$ .

","hasSummary":true,"hasTitle":true,"title":"Events and

\\sigma

-algebra","height":607,"width":980},"classes":"l0","position":{"x":12196.553096064195,"y":4609.336702454983}},{"group":"nodes","data":{"id":"rem:ProbAss","name":"remark","text":"

Remark 14 (Assignment of probabilities). To model real life situations, we assign probabilities to events which reflect what we known about the situation. The probabilities on the configuration space $\\Omega$ are usually assigned according to one of the two following principles.

Indistinguishability. Assume that in a certain experiment, the elements of $\\Omega$ are perfectly indistinguishable. The probability of an event $A$ is then given by the number of configuration $k$ in which it occurs ( $\\omega \\in A$ ) divided by the total number of configuration $n$ : $\\frac{k}{n}$ . It is for instance the case when we draw a card from a card game without seeing what is on the card: they are all indistinguishable.
Probabilities as frequencies. Assume that an experiment which outputs values in $\\Omega$ was repeated $n$ times. If $k$ of the outputs belongs to the event $A$ , the probability assigned to $A$ is the number $\\frac{k}{n}$ . This can be used to evaluate the probabilities of the outcome of an asymmetrical dice. We will come back to the link between probabilities and frequencies later in the course.

Independently from how they are assigned, probability values should always verifies the axioms of measures.
\n

Examples.
\nAssume that a dice is a perfect cube. All the faces are indistinguishable from each other, apart from the number they carry. In that case, it is relevant to assign probabilities according to the indistinguishability principle:

$P(\\{1\\}) = \\frac{1}{6}, P(\\{2\\}) = \\frac{1}{6},P(\\{3\\}) = \\frac{1}{6},$ $P(\\{4\\}) = \\frac{1}{6},P(\\{5\\}) = \\frac{1}{6},P(\\{6\\}) = \\frac{1}{6}.$

The distribution is called uniform. It is now possible to compute the probability of every event, using the axiom 3 (if $A\\cap B=\\emptyset$ then $P(A\\cup B)=P(A)+P(B)$ ):

$P\\left(\\{2,4,6\\}\\right) = P\\left(\\{2\\}\\cup\\{4\\}\\cup \\{6\\}\\right)=P(\\{2\\})+P(\\{4\\})+P(\\{6\\})=\\frac{1}{2}$

Assume now that our dice is a bit damaged. It is no longer perfectly symmetrical. Hence We cannot use the indistinguishability principle anymore. In that case a relevant approach is to perform many dice rolls and to assign probabilities according the frequency of apparition of number.

$P(\\{1\\}) = \\frac{k_1}{N}, P(\\{2\\}) = \\frac{k_2}{N},P(\\{3\\}) = \\frac{k_3}{N},$ $P(\\{4\\}) = \\frac{k_4}{N},P(\\{5\\}) = \\frac{k_5}{N},P(\\{6\\}) = \\frac{k_6}{N}.$

Exactly as before, the probability of other events is computed with the rule ’if $A\\cap B=\\emptyset$ then $P(A\\cup B)=P(A)+P(B)$ ’.

","parent":"subsec:ConfProb","rank":"0","html_name":"rem:ProbAss","summary":"

Remark 14 (Assignment of probabilities). Probability values are usually assigned either based either on an indistinguishability criterion, or from observed frequencies of a repeated experiment.

","hasSummary":true,"hasTitle":true,"title":"Assignment of probabilities","height":412,"width":980},"classes":"l0","position":{"x":12258.913898509865,"y":3919.3695181741937}},{"group":"nodes","data":{"id":"rem:AbsConf","name":"remark","text":"

Remark 15 (Abstract configuration space). In many cases $\\Omega$ is difficult to describe. In such case, random variables are particularly useful. Consider a machine that produces cables. The cables produced are not all strictly identical, the length, the weight, the breaking load,... fluctuate from one cable to another. The number of parameters characterising the cable is very large, and might even not be known precisely. In that case it is not possible to properly characterize our configuration space $\\Omega$ . We will not try to describe $\\Omega$ , we only suppose its existence. Each parameter of the cables can be represented by a random variable. For example, the length is a variable $L:\\Omega\\rightarrow \\mathbb{R}$ , the section a variable S, ..... Then, we are not really interested in the full configuration space $\\Omega$ and the probability on $\\Omega$ , but by the joint law of the random variables corresponding to interesting parameters.

","parent":"subsec:ConfProb","rank":"0","html_name":"rem:AbsConf","summary":"

Remark 15 (Abstract configuration space). In many cases $\\Omega$ is difficult to describe. We will not try to describe $\\Omega$ , we only suppose its existence. We are not really interested in the full configuration space $\\Omega$ and the probability on $\\Omega$ , but by the joint law of the random variables corresponding to interesting parameters.

","hasSummary":true,"hasTitle":true,"title":"Abstract configuration space","height":514,"width":980},"classes":"l0","position":{"x":14700.381605505565,"y":4791.199530686157}},{"group":"nodes","data":{"id":"def:RV","name":"definition","text":"

Definition 52 (Random variables). Introduce first the idea behind the definition. Build a configuration space representing the possible ages of $2$ persons. A natural choice is $\\Omega = \\mathbb{R} \\times \\mathbb{R}$ where the first coordinate represents the possible ages of the first person,and the second the possible age of the second person ( $\\Omega = \\mathbb{R}_+ \\times \\mathbb{R}_+$ is also a natural choice).
\n

The coordinate function $age_1:\\Omega \\rightarrow \\mathbb{R}$ ,

$age_1\\left(\\omega=(\\omega_1,\\omega_2)\\right)=\\omega_1$

’extracts’ the age of the first person out of an elementary configuration $\\omega$ . Similarly, the coordinate function $age_2:\\Omega \\rightarrow \\mathbb{R}$ ,

$age_2\\left(\\omega=(\\omega_1,\\omega_2)\\right)=\\omega_2$

’extracts’ age of the second person. The functions $age_1$ and $age_2$ are called random variables.
\nThe coordinates functions $age_1$ and $age_2$ extracts interesting quantities from the elementary configuration. However, there are other interesting quantities which are not coordinate functions. For instance, for an elementary configuration $\\omega$ , we can be interested in the average age of the $2$ persons. We can define the function $average:\\Omega \\rightarrow \\mathbb{R}$ ,

$average\\left(\\omega=(\\omega_1,\\omega_2)\\right) = \\frac{\\omega_1+\\omega_2}{2}$

The function $average$ is also called a random variable.
\nDefinition:
\nMore generally, a random variable $X$ taking values in a space $E$ is a function $X:\\Omega\\rightarrow E$ . In particular, integer random variables are functions $X:\\Omega\\rightarrow \\mathbb{N}$ and real random variables are functions $X:\\Omega\\rightarrow \\mathbb{R}$ . The only requirement for a function on $\\Omega$ to be called a ’random variable’ is to be measurable: if $A$ is an event of $E$ , $X^{-1}(A)$ must be an event of $\\Omega$ . This restriction only has importance when not all subsets are events.
\nConsider the following dice roll game. If the number is even, the player gains $1$ euro, and if the number is odd he loses $1$ euro. The function $Gain:\\Omega=\\{1,2,3,4,5,5\\}\\rightarrow \\{-1,1\\}$ , $G(1)=G(3)=G(5)=-1$ $G(2)=G(4)=G(6)=1$ is a random variable.

Assume that we roll a dice $n$ times. The configurations space that describes all the possible results is $\\Omega = \\{1,2,3,4,5,6\\}^n$ . Let $X_i$ be the $i$ -th coordinate function on $\\Omega$ . For instance,

$X_1\\left( (3,2,3,...,6) \\right) = 3.$ These random variables ’extract’ the result of the $i$ -th roll out of the elementary configuration. We can also construct the random variables $Gain_i = Gain \\circ X_i$ : the gain at the $i$ -th roll.

","parent":"subsec:RV","rank":"0","html_name":"def:RV","summary":"

Definition 52 (Random variables). A random variable $X$ valued in $E$ is a ’measurable’ function defined on the configuration space $\\Omega$ and valued in $E$ : $X:\\Omega \\rightarrow E$

","hasSummary":true,"hasTitle":true,"title":"Random variables","height":423,"width":980},"classes":"l0","position":{"x":16543.63804116524,"y":4285.242966345903}},{"group":"nodes","data":{"id":"def:RVLaw","name":"definition","text":"

Definition 53 (Law of a random variables). Let $\\Omega$ be a configuration space with a probability $P$ , and $X$ be a random variable taking values in a set $E$ . Recall that $P$ is a function that takes in input an event of $\\Omega$ and associates its probability. The random variable transports the probability $P$ to the set $E$ . The probability of a set $A$ in $E$ is determined by the probability of the subset of $\\Omega$ whose image by $X$ are in $A$ .
\nLet $P_X$ be a probability on $E$ defined as follow. For $A$ an event in $E$ , $P_X(A) = P\\left(X^{-1}(A)\\right).$ $P_X$ is called the law of the random variable $X$ . The measurable assumption on $X$ ensures that $X^{-1}(A)$ is an event of $\\Omega$ . Remarks:

instead of $P_X(A)$ , we often write $P(X\\in A)$ (the probability that the value of the random variable $X$ falls in $A$ ).
$E$ can be viewed as another configuration space with a probability $P_X$

Cumulative distribution

Assume $X$ is a real random variable. The probability $P_X$ can be represented by its cumulative distribution $F_X$ , which is function $F_X:\\mathbb{R}\\rightarrow \\mathbb{R}$ is defined by $F_X(a) = P_X\\left(]-\\infty,a]\\right).$

All the information on $P_X$ is contained in $F_X$ . Since the cumulative distribution is a function $\\mathbb{R}\\rightarrow \\mathbb{R}$ , sometimes it is conceptually simpler to manipulate $F_X$ than the probability itself which is a function from the subsets of $\\mathbb{R}$ to $\\mathbb{R}$ .
\n

What do we know about $\\lim_{x\\rightarrow \\infty} F_X(x)$ ? $\\lim_{x\\rightarrow \\infty} F_X(x)=1$
How do we compute $P_X([a,b])$ from $F_X$ ? $P_X([a,b]) = F_X(b)-F_X(a)$
Can we have $x<y$ and $F_X(x)>F_X(y)$ ? No!
If for $x\\in [0,1]$ , $F_X(x)=x$ , what is $P_X([2,3])$ ? $P_X([2,3])=0$

Density of the random variable

When the law $P_X$ has a density $f$ , the density is called the density of the random variable $X$ and is often noted $f_X$ .
\nFor a real random variable $X$ ,

show that $\\int_{-\\infty}^{+\\infty}f_X(x)dx=1$ $\\int_{-\\infty}^{+\\infty}f_X(x)dx = P_X([-\\infty,+\\infty])=1$
show that $f_X=F_X'$ . $F_X(x)= P_X\\left(]-\\infty,x]\\right) = \\int_{-\\infty}^{x}f_X(u)du$ Hence the result.

","parent":"subsec:RV","rank":"0","html_name":"def:RVLaw","summary":"

Definition 53 (Law of a random variables). Let $X:\\Omega \\rightarrow E$ be a random variable. For $A$ an event in $E$ , define $P_X(A) = P\\left(X^{-1}(A)\\right).$ $P_X$ is called the law of the random variable $X$ .

","hasSummary":true,"hasTitle":true,"title":"Law of a random variables","height":442,"width":980},"classes":"l0","position":{"x":15903.778546829752,"y":3703.1538379753565}},{"group":"nodes","data":{"id":"def:JoinRV","name":"definition","text":"

Definition 54 (Joint random variables). Consider $2$ random variables $X:\\Omega \\rightarrow E$ and $Y:\\Omega \\rightarrow F$ . The random variable $Z:\\Omega \\rightarrow E\\times F$ , $Z=(X,Y)$ is called the joint random variable. The law $P_{Z}=P_{(X,Y)}$ of $Z$ is called the joint law (or joint probability distribution).
\n

Example.
\nConsider the case of $n$ dice rolls. Let $\\Omega = \\{1,2,3,4,5,6\\}^n$ and $X_i$ be the $i$ -th coordinate function, and let $P$ be the uniform probability distribution. Consider now the joint random variable $Z:\\Omega \\rightarrow \\{1,2,3,4,5,6\\}^2,\\quad Z=(X_1,X_2).$

What is the law of $Z$ ? $P_Z(\\{(a,b)\\})=P(Z^{-1}(\\{(a,b)\\}))=P(\\{a\\}\\times \\{b\\} \\times \\{1,2,3,4,5,6\\}^{n-2})$ Hence $P_Z(\\{(a,b)\\})=\\frac{Card(\\{1,2,3,4,5,6\\}^{n-2})}{Card(\\{1,2,3,4,5,6\\}^{n})}= \\frac{6^{n-2}}{6^n}=1/36$ .
\n

$\\rightarrow P_Z$ is uniform on $\\{1,2,3,4,5,6\\}^2$ .

","parent":"subsec:RV","rank":"0","html_name":"def:JoinRV","summary":"

","hasSummary":true,"hasTitle":true,"title":"Joint random variables","height":535,"width":980},"classes":"l0","position":{"x":16412.728588815913,"y":2993.8869510895343}},{"group":"nodes","data":{"id":"def:Marg","name":"definition","text":"

Definition 55 (Concept of marginal). Give an informal description of the concept of marginal. Some mathematical objects defined on the Cartesian product $E\\times F$ naturally give rise to similar objects defined on $E$ and $F$ by ’forgetting’ the other coordinate. The objects defined in this manner on $E$ and $F$ are called marginal.
\nAs we will see, ’forgetting’ the other coordinate is opposed to conditioning, where the other coordinate is fixed to a particular value.

","parent":"subsec:Marg","rank":"0","html_name":"def:Marg","summary":"

","hasSummary":true,"hasTitle":true,"title":"Concept of marginal","height":514,"width":980},"classes":"l0","position":{"x":12166.850463373075,"y":2844.9599406535326}},{"group":"nodes","data":{"id":"def:MargProb","name":"definition","text":"

Definition 56 (Marginal probability). Let $P_{E\\times F}$ be a probability on the Cartesian product $E\\times F$ . The marginal probability on $E$ is defined by $P_E(A) = P_{E\\times F}(A,F)$ and the marginal on $F$ by $P_F(B) = P_{E\\times F}(E,B).$ When $P_{E\\times F}$ has a density $f_{E\\times F}$ with respect to a reference measure on ${E\\times F}$ , the marginal densities are defined by $f_E(x) = \\int_{x\\times F} f_{E\\times F}(x,y)\\mathrm{d}y \\text{ and } f_F(y) = \\int_{E\\times y} f_{E\\times F}(y,x)\\mathrm{d}x.$

","parent":"subsec:Marg","rank":"0","html_name":"def:MargProb","summary":"

","hasSummary":true,"hasTitle":true,"title":"Marginal probability","height":494,"width":980},"classes":"l0","position":{"x":12774.067271971502,"y":2160.2187117665944}},{"group":"nodes","data":{"id":"def:MargRV","name":"definition","text":"

Definition 57 (Marginal random variables). Given a random variable $Z$ valued in a Cartesian product $E\\times F$ , the projections on $E$ and $F$ define ’marginals’. Let $Z=(X,Y),$ $X$ is called the marginal random variable on $E$ and $Y$ the marginal random variable on $F$ . The law of $X$ and $Y$ are called the \"marginal laws\", or \"marginal probabilities\" of the law $P_Z$ . The laws are given by $P_X(A) = P_{Z}((A,F)) \\text{ and } P_Y(A) = P_{Z}((E,A)).$ When the laws have densities, $f_X(x) = \\int_{x\\times F} f_{Z}(x,y)\\mathrm{d}y \\text{ and } f_Y(y) = \\int_{E\\times y} f_{Z}(y,x)\\mathrm{d}x.$

","parent":"subsec:Marg","rank":"0","html_name":"def:MargRV","summary":"

Definition 57 (Marginal random variables). Let $Z:\\Omega\\rightarrow E\\times F$ be a random variable, and let $X$ and $Y$ be the random variables corresponding to each coordinate: $Z=(X,Y).$ $X$ is called the marginal random variable on $E$ and $Y$ the marginal random variable on $F$ .

","hasSummary":true,"hasTitle":true,"title":"Marginal random variables","height":524,"width":980},"classes":"l0","position":{"x":12137.531799873219,"y":1425.528800121085}},{"group":"nodes","data":{"id":"th:Bayes","name":"theorem","text":"

Theorem 14 (Bayes Theorem). The definition of conditional densities can be rewritten as something called the \"Bayes theorem\": $P(B|A)P(A) = P(A|B)P(B) = P(A\\cap B)$

","parent":"subsec:Cond","rank":"0","html_name":"th:Bayes","summary":"

Theorem 14 (Bayes Theorem). $P(B|A)P(A) = P(A|B)P(B) = P(A\\cap B)$

","hasSummary":true,"hasTitle":true,"title":"Bayes Theorem","height":283,"width":980},"classes":"l0","position":{"x":17173.002711062174,"y":1012.9142665309903}},{"group":"nodes","data":{"id":"def:CondProb","name":"definition","text":"

Definition 58 (Conditional probability). Consider a probability $P$ on the set of configurations $\\Omega$ . Given a event $A$ with $P(A>0)$ , the idea of conditioning with respect to $A$ is to focus on the configurations $\\omega \\in A$ and forget about the configurations $\\omega \\notin A$ . We would like to define a new probability which respects the proportions of the events included in $A$ and gives zero probability to event which do not intersect $A$ .
\nLet $A$ be an event of $\\Omega$ , with $P(A)>0$ . We define the probability conditional to the event $A$ by $P_A(B) = \\frac{P(B\\cap A)}{P(A)}.$ $P_A(B)$ is called the probability of $B$ given $A$ , and is usually noted $P(B|A)$ .
\nExercise: check that $P_A$ is a probability on $\\Omega$

","parent":"subsec:Cond","rank":"0","html_name":"def:CondProb","summary":"

Definition 58 (Conditional probability). We define the probability conditional to the event $A$ by $P_A(B) = \\frac{P(B\\cap A)}{P(A)}.$ $P_A(B)$ is called the probability of $B$ given $A$ , and is usually noted $P(B|A)$ .

","hasSummary":true,"hasTitle":true,"title":"Conditional probability","height":502,"width":980},"classes":"l0","position":{"x":17123.201347644594,"y":1608.387855598545}},{"group":"nodes","data":{"id":"def:CondProbRV","name":"definition","text":"

Definition 59 (Conditional laws of a joint variable). We address here the particular case of conditional laws of a joint random variable. Let $X:\\Omega \\rightarrow E$ and $Y:\\Omega \\rightarrow F$ be two random variables. The law $P_Z$ of the joint random variable $Z=(X,Y)$ is a probability on $E\\times F$ . This joint probability on $E\\times F$ can be conditioned by imposing that one of the variables lies in a given set. In particular, when $P_{(X,Y)}(E\\times \\{y\\})>0$ it is possible to condition by the event $E\\times \\{y\\}$ . We obtain then a probability on $E\\times \\{y\\}\\subset E\\times F$ , interpreted as a probability on $E$ . The conditional probability knowing $Y=y$ is usually written $P(X\\in A |Y=y)= \\frac{P_{(X,Y)}(A\\times \\{y\\})}{P_{(X,Y)}(E\\times \\{y\\})}=\\frac{P_{(X,Y)}(A\\times \\{y\\})}{P_Y(\\{y\\})}.$

We recognized the term $P_{(X,Y)}(E\\times \\{y\\})=P_Y(\\{y\\})$ , which is the marginal distribution on $F$ evaluated on $\\{y\\}$ .

When densities exist, the conditional density is $f(x|Y=y) = \\frac{f_{(X,Y)}(x,y)}{f_Y(y)}$ as long as the marginal density $f_Y(y)>0$ .

","parent":"subsec:Cond","rank":"0","html_name":"def:CondProbRV","summary":"

Definition 59 (Conditional laws of a joint variable). $P(X\\in A |Y=y)= \\frac{P_{(X,Y)}(A\\times \\{y\\})}{P_{(X,Y)}(E\\times \\{y\\})}=\\frac{P_{(X,Y)}(A\\times \\{y\\})}{P_Y(\\{y\\})}.$

","hasSummary":true,"hasTitle":true,"title":"Conditional laws of a joint variable","height":345,"width":980},"classes":"l0","position":{"x":16121.82435700667,"y":742.0546539898808}},{"group":"nodes","data":{"id":"th:JLIV","name":"theorem","text":"

Theorem 15 (Joint law of independent variables ). When $X$ and $Y$ are independent, we have the two important results:

the joint probability of $(X,Y)$ is $P_{(X,Y)}=P_XP_Y$
the conditional probabilities $P(X\\in A | Y = y)$ are independent of $y$ and $P(X\\in A | Y = y) = P_X(A),$ in other words the marginal and conditional are the same for all $y$ . The same is true when conditioning on $X$ .

The proofs are exercises.

","parent":"subsec:Ind","rank":"0","html_name":"th:JLIV","summary":"

Theorem 15 (Joint law of independent variables ). $P_{(X,Y)}=P_XP_Y$ $P(X\\in A | Y = y) = P_X(A),$

","hasSummary":true,"hasTitle":true,"title":"Joint law of independent variables ","height":338,"width":980},"classes":"l0","position":{"x":14311.227641064226,"y":-1037.0753394813926}},{"group":"nodes","data":{"id":"def:IndEv","name":"definition","text":"

Definition 60 (Independent events). Two events $A$ and $B$ are called independent when $P(A\\cap B) =P(A)P(B)$

Interpretation when $P(A)>0$ : the proportion of $B\\cap A$ in $A$ is the same as the proportion of $B$ in $\\Omega$ $\\frac{P(B\\cap A)}{P(A)} = \\frac{P(B)}{P(\\Omega)}=P(B).$ In other words, conditioning probabilities to the event $A$ does not change the probability of $B$ .
\n

When $P(B)>0$ , the same can be said about the proportion of $A\\cap B$ in $B$ .

","parent":"subsec:Ind","rank":"0","html_name":"def:IndEv","summary":"

Definition 60 (Independent events). Two events $A$ and $B$ are called independents when $P(A\\cap B) = P(A)P(B).$

","hasSummary":true,"hasTitle":true,"title":"Independent events","height":336,"width":980},"classes":"l0","position":{"x":13940.301973467818,"y":396.39492473894427}},{"group":"nodes","data":{"id":"def:IndRV","name":"definition","text":"

Definition 61 (Independent random variables). We say that $2$ random variables are independent when an information on one of them does not affect the other. This translates to the following definition.
\nTwo random variables $X:\\Omega \\rightarrow E$ and $Y:\\Omega \\rightarrow F$ are independent when : $\\forall A\\subset E,B\\subset F,\\quad X^{-1}(A) \\text{ and } Y^{-1}(B) \\text{ are independent events in } \\Omega.$

Recall that it means that when $P(Y^{-1}(B))>0$ , conditioning the probability $P$ on $\\Omega$ to $Y^{-1}(B)$ does not affect the probability of $X^{-1}(A)$ . The other direction holds when $P(X^{-1}(A))>0$ .
\n

","parent":"subsec:Ind","rank":"0","html_name":"def:IndRV","summary":"

Definition 61 (Independent random variables). Two random variables $X:\\Omega \\rightarrow E$ and $Y:\\Omega \\rightarrow F$ are independent when : $\\forall A\\subset E,B\\subset F,\\quad X^{-1}(A) \\text{ and } Y^{-1}(B) \\text{ are independent events in } \\Omega.$

","hasSummary":true,"hasTitle":true,"title":"Independent random variables","height":379,"width":1232},"classes":"l0","position":{"x":14337.070950072977,"y":-98.7174819388315}},{"group":"nodes","data":{"id":"def:IndExp","name":"theorem","text":"

Theorem 16 (Independence and expectation). When $X$ and $Y$ are two independent variables, we have that $\\mathbb{E}(XY) = \\mathbb{E}(X)\\mathbb{E}(Y).$ When the laws have densities, the result is given by the following computation: $\\begin{aligned}\n\\mathbb{E}(XY) &=& \\int \\int xy f_{(X,Y)}dxdy \\\\\n&=& \\int \\int xy f_X(x)f_Y(y)dxdy\\\\\n&=& \\int xf_X(x)dx \\int yf_Y(y)dy\\end{aligned}$

","parent":"subsec:MomRV","rank":"0","html_name":"def:IndExp","summary":"

Theorem 16 (Independence and expectation). When $X$ and $Y$ are two independent variables, we have that $\\mathbb{E}(XY) = \\mathbb{E}(X)\\mathbb{E}(Y).$

","hasSummary":true,"hasTitle":true,"title":"Independence and expectation","height":379,"width":980},"classes":"l0","position":{"x":18372.05589195286,"y":41.302104565725244}},{"group":"nodes","data":{"id":"def:StdProp","name":"theorem","text":"

Theorem 17 (Properties of variance). Show as a first exercise that variance can also be written as $v(X)=\\mathbb{E}(X^2)-\\mathbb{E}(X)^2$ .
\nShow that:

$v(aX+b)=a^2v(X)$
when $X$ and $Y$ are independent, $v(X+Y)=v(X)+v(Y)$ .

Hence, when $X_1,...,X_n$ are independent variables with identical distributions, $v\\left(\\frac{1}{n}\\sum_i X_i\\right)=\\frac{1}{n^2}v\\left(\\sum_i X_i\\right) = \\frac{1}{n^2}\\sum_i v(X_i)=\\frac{1}{n}v(X_1)\\xrightarrow[n\\rightarrow \\infty]{} 0$

This is a very important result: summing independent and identically distributed (i.i.d) variables reduces the variance in $\\frac{1}{n}$ and the standard deviation in $\\frac{1}{\\sqrt{n}}$ .

","parent":"subsec:MomRV","rank":"0","html_name":"def:StdProp","summary":"

Theorem 17 (Properties of variance). $v(X)=\\mathbb{E}(X^2)-\\mathbb{E}(X)^2$ $v(aX+b)=a^2v(X)$ when $X$ and $Y$ are independent, $v(X+Y)=v(X)+v(Y)$ .

","hasSummary":true,"hasTitle":true,"title":"Properties of variance","height":455,"width":980},"classes":"l0","position":{"x":18398.953449215493,"y":-619.6713064174974}},{"group":"nodes","data":{"id":"def:Expe","name":"definition","text":"

Definition 62 (Expectation). Let $\\Omega=\\{1,2\\}$ with $P(\\{1\\})=\\frac{1}{10}$ and $P(\\{2\\})=\\frac{9}{10}$ . Let $X$ be a real random variable, $X:\\Omega \\rightarrow \\mathbb{R}$ . For each elementary configuration $\\omega$ , $X$ takes the value $X(\\omega)$ . The ’expectation’ of $X$ is the ’average’ value of the $X(\\omega)$ with respect to the probabilities of the $\\{\\omega\\}$ . In our example: $\\mathbb{E}(X) = X(1).P(\\{1\\}) + X(2).P(\\{2\\}) = 1\\times \\frac{1}{10} + 2\\times \\frac{9}{10}.$

If $\\Omega=\\{1,2,...,N\\}$ , the average of a random variable $X:\\Omega \\rightarrow \\mathbb{R}$ becomes:

$\\mathbb{E}(X) = \\sum_{i\\in\\Omega} X(i)\\times P({i}).$

Now consider the case $\\Omega=\\mathbb{R}$ , with a probability $P$ of density $f$ . The formula for the expecation becomes $\\mathbb{E}(X) = \\int_{-\\infty}^{+\\infty} X(\\omega) f(\\omega)d\\omega.$ Note that in that case, the expectation exists only when the integral exists.

There is a definition of the expectation which does not depend on the nature of $\\Omega$ . The expectation (average / mean) of $X$ is defined by $\\mathbb{E}(X) = \\int_{\\Omega} X(\\omega)dP(\\omega).$

The rigorous definition requires what is called ’Lebesgue integrals’. Hoewever, the intuitive meaning of the formula is clear. When $\\Omega$ is discrete, the integral becomes a sum over $\\Omega$ . When $\\Omega$ is continuous and that $P$ has a density, $dP(\\omega)$ becomes $f(\\omega)d\\omega$ .
\nRemember that the random variable $X:\\Omega \\rightarrow \\mathbb{R}$ transports the probability $P$ defined on $\\Omega$ to a probability $P_{X}$ defined on $\\mathbb{R}$ .

$X$ is in fact discrete, it takes values on $\\mathbb{Z}\\subset \\mathbb{R}$ . We have $\\int_{\\Omega} X(\\omega)dP(\\omega)= \\sum_{i\\in \\mathbb{Z}} i.P_X(\\{i\\}).$ Exercise: show this formula when $\\Omega = \\mathbb{Z}$ .
The probability $P_X$ has a density $f_X$ . We have $\\int_{\\Omega} X(\\omega)dP(\\omega)= \\int_{-\\infty}^{+\\infty} xf_X(x)dx$ Exercise: show this formula when $\\Omega = \\mathbb{R}$ , $P$ has a density $f$ and $X$ is a diffeomorphism.

The set of random variables $X:\\Omega \\rightarrow \\mathbb{R}$ is a vector space ( $(X+Y)(\\omega)=X(\\omega)+Y(\\omega)$ ). The set of random variables such that $\\int_{\\Omega} X(\\omega)dP(\\omega)$ exists is called $L^1(\\Omega)$ , it is again a vector space. Since integrals are linear, the expectation $\\mathbb{E}:L^1(\\Omega)\\rightarrow \\mathbb{R}$

$X \\mapsto \\mathbb{E}(X)=\\int_{\\Omega} X(\\omega)dP(\\omega)$ is a linear application from $L^1(\\Omega)$ to $\\mathbb{R}$ . In other words, we have the fundamentals properties: $\\mathbb{E}(\\alpha X) = \\alpha \\mathbb{E}(X) \\quad \\text{ and } \\quad \\mathbb{E}(X+Y) = \\mathbb{E}(X) + \\mathbb{E}(Y).$

","parent":"subsec:MomRV","rank":"0","html_name":"def:Expe","summary":"

Definition 62 (Expectation). The general definition of the expectation of a random variable $X:\\Omega\\rightarrow \\mathbb{R}$ is $\\mathbb{E}(X) = \\int_{\\Omega} X(\\omega)dP(\\omega).$ in particular, when $\\Omega = \\{1,..,N\\}$ , $\\mathbb{E}(X) = \\sum_{i\\in\\Omega} X(i)\\times P({i})=\\sum_{i\\in \\mathbb{Z}} i.P_X(\\{i\\}),$ and when $\\Omega = \\mathbb{R}$ , $\\mathbb{E}(X) = \\int_{-\\infty}^{+\\infty} X(\\omega) f(\\omega)d\\omega=\\int_{-\\infty}^{+\\infty} xf_X(x)dx.$

","hasSummary":true,"hasTitle":true,"title":"Expectation","height":799,"width":980},"classes":"l0","position":{"x":18366.371663039306,"y":1162.4577397102996}},{"group":"nodes","data":{"id":"def:ScalRV","name":"definition","text":"

Definition 63 (Inner products on random variables). The expectation enables to define an important inner product on random variables. It provides a norm and a notion of angles between random variables. Let $X:\\Omega \\rightarrow \\mathbb{R}$ and $Y:\\Omega \\rightarrow \\mathbb{R}$ be $2$ random variables. When it exists, we can define $\\langle X,Y \\rangle = \\mathbb{E}(XY)= \\int_{\\Omega} X(\\omega)Y(\\omega)dP(\\Omega),$ where $XY$ is understood as the product of the functions $X$ and $Y$ .

The set of random variables $X$ such that $\\int_{\\Omega} X(\\omega)^2dP(\\omega)$ exists is called $L^2(\\Omega)$ . $L^2(\\Omega)$ is a vector space.
\nExercise: show that $\\langle.,.\\rangle$ is an inner product on $L^2(\\Omega)$ .
\nConsider the important case of $2$ independent random variables $X$ and $Y$ with zero mean. Then $\\langle X,Y\\rangle =0.$ Hence the strong link between independence and orthogonality. Note however that the converse is not always true: we can find centered random variables $X$ and $Y$ with $\\langle X,Y\\rangle =0$ which are not independent.

","parent":"subsec:MomRV","rank":"0","html_name":"def:ScalRV","summary":"

Definition 63 (Inner products on random variables). $\\langle X,Y \\rangle = \\mathbb{E}(XY)= \\int_{\\Omega} X(\\omega)Y(\\omega)dP(\\Omega),$

","hasSummary":true,"hasTitle":true,"title":"Inner products on random variables","height":422,"width":980},"classes":"l0","position":{"x":19899.27127201591,"y":741.8116466487754}},{"group":"nodes","data":{"id":"def:Cov","name":"definition","text":"

Definition 64 (Covariance (dimension 1)). Given a random variable $X$ note $X_{c} = X-\\mathbb{E}(X)$ the ’centered’ variable. The covariance between two variables $X$ and $Y$ is the scalar product between their centered versions.
\nWhen it exists, the covariance between $X:\\Omega\\rightarrow \\mathbb{R}$ and $Y:\\Omega\\rightarrow \\mathbb{R}$ is defined by $cov(X,Y)=\\langle X_{c},Y_{c}\\rangle = \\mathbb{E}\\left( (X-\\mathbb{E}(X))(Y-\\mathbb{E}(Y)) \\right).$

We have that $v(X)=cov(X,X)$ .

","parent":"subsec:MomRV","rank":"0","html_name":"def:Cov","summary":"

Definition 64 (Covariance (dimension 1)). $cov(X,Y)=\\langle X_{c},Y_{c}\\rangle = \\mathbb{E}\\left( (X-\\mathbb{E}(X))(Y-\\mathbb{E}(Y)) \\right).$

","hasSummary":true,"hasTitle":true,"title":"Covariance (dimension 1)","height":297,"width":980},"classes":"l0","position":{"x":19930.787327169135,"y":160.3847155789902}},{"group":"nodes","data":{"id":"def:Std","name":"definition","text":"

Definition 65 (Standard deviation / variance). The variance and standard deviation measure how a random variable varies around its mean. The deviation from the mean is given by the Euclidean norm of the centered variable $X_{c} = X-\\mathbb{E}(X)$ . when they exists, the variance is defined by,

$v(X)= \\mathbb{E}\\left((X-\\mathbb{E}(X))^2\\right)=cov(X,X)=\\|X_c\\|^2,$

and the standard deviation by

$\\sigma(X)=\\sqrt{v(X)} =\\|X_c\\|.$

","parent":"subsec:MomRV","rank":"0","html_name":"def:Std","summary":"

Definition 65 (Standard deviation / variance). $v(X)= \\mathbb{E}\\left((X-\\mathbb{E}(X))^2\\right),$ $\\sigma(X)=\\sqrt{v(X)} = \\sqrt{ \\mathbb{E}\\left((X-\\mathbb{E}(X))^2\\right)}.$

","hasSummary":true,"hasTitle":true,"title":"Standard deviation / variance","height":416,"width":980},"classes":"l0","position":{"x":19621.80213564521,"y":-573.1885588548129}},{"group":"nodes","data":{"id":"def:CovM","name":"definition","text":"

Definition 66 (Covariance matrix)). Consider $n$ random variables $X_i:\\Omega \\rightarrow \\mathbb{R}$ . The variables can be put in a column vector $\\bm X=(X_1,..,X_n)$ . $\\bm X$ is then a random variable $\\bm X:\\Omega \\rightarrow \\mathbb{R}^n$ . Such random variables are often called random vectors.
\nFor a random column vector $\\bm X:\\Omega \\rightarrow \\mathbb{R}^n$ , when it exists the covariance matrix is defined by $cov(\\bm X)=\\mathbb{E}(\\bm X_{c} \\bm X_{c}^t)= \\mathbb{E}\\left((\\bm X-\\mathbb{E}(\\bm X))(\\bm X-\\mathbb{E}(\\bm X))^T\\right).$

$\\mathbb{E}\\left( \\begin{pmatrix} X_1-\\mathbb{E}(X_1)\\\\ X_2 -\\mathbb{E}(X_2)\\\\ . \\\\ . \\\\ X_n-\\mathbb{E}(X_n) \\end{pmatrix}\\begin{pmatrix} X_1-\\mathbb{E}(X_1)& X_2 -\\mathbb{E}(X_2)& . & . & X_n-\\mathbb{E}(X_n) \\end{pmatrix} \\right)$ $=$ $\\begin{pmatrix} \n\\mathbb{E}\\left( ( X_1-\\mathbb{E}(X_1) )( X_1-\\mathbb{E}(X_1) )\n\\right) &.&.& \\mathbb{E}\\left( ( X_1-\\mathbb{E}(X_1) )( X_n-\\mathbb{E}(X_n) ) \\right) \\\\\n.&&&.\\\\\n.&&&.\\\\\n\\mathbb{E}\\left( ( X_n-\\mathbb{E}(X_n) )( X_1-\\mathbb{E}(X_1) )\n\\right) &.&.& \\mathbb{E}\\left( ( X_n-\\mathbb{E}(X_n) )( X_n-\\mathbb{E}(X_n) ) \\right) \\\\\n\\end{pmatrix}$

Hence we can see that $cov(X)_{ij}=cov(X_{i},X_{j})=\\langle X_{i,c},X_{j,c} \\rangle$ .
\nWhen $\\bm X$ is a line vector, the definition becomes $cov(\\bm X)=\\mathbb{E}(\\bm X_{c}^t\\bm X_{c}).$

","parent":"subsec:MomRV","rank":"0","html_name":"def:CovM","summary":"

Definition 66 (Covariance matrix)). Consider $n$ random variables $X_i:\\Omega \\rightarrow \\mathbb{R}$ . The variables can be put in a column vector $\\bm X=(X_1,..,X_n)$

","hasSummary":true,"hasTitle":true,"title":"Covariance matrix","height":338,"width":980},"classes":"l0","position":{"x":20418.20378469191,"y":-1072.7316180751332}},{"group":"nodes","data":{"id":"def:WLLN","name":"theorem","text":"

Theorem 18 ((Weak) Law of large numbers !finish iid!). Let $X_1,...,X_n,...$ be an infinite sequence i.i.d real random variables of mean $\\mu$ . The empirical means are the random variables $\\bar X_n = \\frac{X_1+..+X_n}{n}.$ For all $\\epsilon>0$ , we have $P(|\\bar X_n-\\mu |>\\epsilon)\\xrightarrow[n\\rightarrow \\infty]{} 0.$

We will not prove this result, but it can be intuitively understood in a simple way when the variable have variances. First, note that $\\mathbb{E}(\\bar X)=\\mathbb{E}(X_1)=\\mu$ . Then, remember that $v\\left(\\bar X=\\frac{1}{n}\\sum_i X_i\\right)\\xrightarrow[n\\rightarrow \\infty]{} 0.$ Hence the empirical mean $\\bar X$ is more and more concentrated around its mean $\\mu$ , which means that the probability $P(|\\bar X_n-\\mu |>\\epsilon)$ should be smaller and smaller.

","parent":"subsec:LLN","rank":"0","html_name":"def:WLLN","summary":"

Theorem 18 ((Weak) Law of large numbers !finish iid!).

","hasSummary":true,"hasTitle":true,"title":"(Weak) Law of large numbers !finish iid!","height":297,"width":980},"classes":"l0","position":{"x":16413.042621379984,"y":-2186.5815533798905}},{"group":"nodes","data":{"id":"sec:LA","name":"section","text":"","rank":"0","html_name":"sec:LA","hasSummary":false,"hasTitle":false,"height":100,"width":980},"classes":"l0","position":{"x":14753.106930478858,"y":9770.0607479875}},{"group":"nodes","data":{"id":"titlesec:LA","name":"sectionTitle","text":"

Linear algebra

","parent":"sec:LA","rank":"0","html_name":"sec:LA","hasSummary":false,"hasTitle":false,"height":561,"width":1250},"classes":"l0","position":{"x":15251.947598908304,"y":12488.748941764392}},{"group":"nodes","data":{"id":"sec:FCC","name":"section","text":"","rank":"0","html_name":"sec:FCC","hasSummary":false,"hasTitle":false,"height":100,"width":980},"classes":"l0","position":{"x":5458.492997493175,"y":7893.861778089176}},{"group":"nodes","data":{"id":"titlesec:FCC","name":"sectionTitle","text":"

Fourier, Convolution and Correlation

","parent":"sec:FCC","rank":"0","html_name":"sec:FCC","hasSummary":false,"hasTitle":false,"height":1022,"width":1516},"classes":"l0","position":{"x":6070.582696672855,"y":9153.16568357412}},{"group":"nodes","data":{"id":"sec:TIOpe","name":"section","text":"","rank":"0","html_name":"sec:TIOpe","hasSummary":false,"hasTitle":false,"height":100,"width":980},"classes":"l0","position":{"x":6919.291003777886,"y":4471.199618819243}},{"group":"nodes","data":{"id":"titlesec:TIOpe","name":"sectionTitle","text":"

Translation invariant operators

","parent":"sec:TIOpe","rank":"0","html_name":"sec:TIOpe","hasSummary":false,"hasTitle":false,"height":792,"width":1417},"classes":"l0","position":{"x":8883.724097307402,"y":4635.4707260975465}},{"group":"nodes","data":{"id":"sec:DiffOp","name":"section","text":"","rank":"0","html_name":"sec:DiffOp","hasSummary":false,"hasTitle":false,"height":100,"width":980},"classes":"l0","position":{"x":7551.192528111416,"y":1286.450679389157}},{"group":"nodes","data":{"id":"titlesec:DiffOp","name":"sectionTitle","text":"

Differential operators

","parent":"sec:DiffOp","rank":"0","html_name":"sec:DiffOp","hasSummary":false,"hasTitle":false,"height":561,"width":1395},"classes":"l0","position":{"x":8889.318218063834,"y":2886.559814716601}},{"group":"nodes","data":{"id":"sec:Meas","name":"section","text":"","rank":"0","html_name":"sec:Meas","hasSummary":false,"hasTitle":false,"height":100,"width":980},"classes":"l0","position":{"x":22234.269516961438,"y":7896.252214189441}},{"group":"nodes","data":{"id":"titlesec:Meas","name":"sectionTitle","text":"

Measures theory

","parent":"sec:Meas","rank":"0","html_name":"sec:Meas","hasSummary":false,"hasTitle":false,"height":561,"width":1273},"classes":"l0","position":{"x":24064.54267057631,"y":8862.18520253525}},{"group":"nodes","data":{"id":"sec:Prob","name":"section","text":"","rank":"0","html_name":"sec:Prob","hasSummary":false,"hasTitle":false,"height":100,"width":980},"classes":"l0","position":{"x":16277.867792282563,"y":1748.0584128393234}},{"group":"nodes","data":{"id":"titlesec:Prob","name":"sectionTitle","text":"

Probabilities

","parent":"sec:Prob","rank":"0","html_name":"sec:Prob","hasSummary":false,"hasTitle":false,"height":331,"width":1550},"classes":"l0","position":{"x":16356.192235909653,"y":5692.698379058537}},{"group":"nodes","data":{"id":"subsec:VectSpaces","name":"subsection","text":"","parent":"sec:LA","rank":"0","html_name":"subsec:VectSpaces","hasSummary":false,"hasTitle":false,"height":100,"width":980},"classes":"l0","position":{"x":12493.897059014955,"y":10834.568404340866}},{"group":"nodes","data":{"id":"titlesubsec:VectSpaces","name":"subsectionTitle","text":"

Vector spaces

","parent":"subsec:VectSpaces","rank":"0","html_name":"subsec:VectSpaces","hasSummary":false,"hasTitle":false,"height":169,"width":980},"classes":"l0","position":{"x":11032.53029978813,"y":12031.627747120141}},{"group":"nodes","data":{"id":"subsec:Mats","name":"subsection","text":"","parent":"sec:LA","rank":"0","html_name":"subsec:Mats","hasSummary":false,"hasTitle":false,"height":100,"width":980},"classes":"l0","position":{"x":17086.411266588824,"y":8265.076922654986}},{"group":"nodes","data":{"id":"titlesubsec:Mats","name":"subsectionTitle","text":"

Matrices

","parent":"subsec:Mats","rank":"0","html_name":"subsec:Mats","hasSummary":false,"hasTitle":false,"height":169,"width":980},"classes":"l0","position":{"x":17763.04274309803,"y":9004.19546953074}},{"group":"nodes","data":{"id":"subsec:LinMaps","name":"subsection","text":"","parent":"sec:LA","rank":"0","html_name":"subsec:LinMaps","hasSummary":false,"hasTitle":false,"height":100,"width":980},"classes":"l0","position":{"x":17215.683278967546,"y":10711.510666246777}},{"group":"nodes","data":{"id":"titlesubsec:LinMaps","name":"subsectionTitle","text":"

Linear maps

","parent":"subsec:LinMaps","rank":"0","html_name":"subsec:LinMaps","hasSummary":false,"hasTitle":false,"height":169,"width":980},"classes":"l0","position":{"x":16890.61421535985,"y":11908.638114506259}},{"group":"nodes","data":{"id":"subsec:InnProd","name":"subsection","text":"","parent":"sec:LA","rank":"0","html_name":"subsec:InnProd","hasSummary":false,"hasTitle":false,"height":100,"width":980},"classes":"l0","position":{"x":12708.739508391762,"y":7954.5708563614135}},{"group":"nodes","data":{"id":"titlesubsec:InnProd","name":"subsectionTitle","text":"

Inner products

","parent":"subsec:InnProd","rank":"0","html_name":"subsec:InnProd","hasSummary":false,"hasTitle":false,"height":169,"width":980},"classes":"l0","position":{"x":14495.95155335858,"y":8766.363082609456}},{"group":"nodes","data":{"id":"subsec:Conv","name":"subsection","text":"","parent":"sec:FCC","rank":"0","html_name":"subsec:Conv","hasSummary":false,"hasTitle":false,"height":100,"width":980},"classes":"l0","position":{"x":3595.949252973721,"y":7460.855180934309}},{"group":"nodes","data":{"id":"titlesubsec:Conv","name":"subsectionTitle","text":"

Convolutions

","parent":"subsec:Conv","rank":"0","html_name":"subsec:Conv","hasSummary":false,"hasTitle":false,"height":169,"width":980},"classes":"l0","position":{"x":2273.952963921711,"y":8425.846299197136}},{"group":"nodes","data":{"id":"subsec:F","name":"subsection","text":"","parent":"sec:FCC","rank":"0","html_name":"subsec:F","hasSummary":false,"hasTitle":false,"height":100,"width":980},"classes":"l0","position":{"x":8021.748552545618,"y":7711.200887003522}},{"group":"nodes","data":{"id":"titlesubsec:F","name":"subsectionTitle","text":"

Fourier

","parent":"subsec:F","rank":"0","html_name":"subsec:F","hasSummary":false,"hasTitle":false,"height":169,"width":980},"classes":"l0","position":{"x":7475.231691469583,"y":9011.496901521983}},{"group":"nodes","data":{"id":"subsec:CT","name":"subsection","text":"","parent":"sec:FCC","rank":"0","html_name":"subsec:CT","hasSummary":false,"hasTitle":false,"height":100,"width":980},"classes":"l0","position":{"x":6263.035667710466,"y":7199.18445415821}},{"group":"nodes","data":{"id":"titlesubsec:CT","name":"subsectionTitle","text":"

Convolution Theorems

","parent":"subsec:CT","rank":"0","html_name":"subsec:CT","hasSummary":false,"hasTitle":false,"height":169,"width":980},"classes":"l0","position":{"x":6263.057121854839,"y":8171.311035712188}},{"group":"nodes","data":{"id":"subsec:DiffOp","name":"subsection","text":"","parent":"sec:DiffOp","rank":"0","html_name":"subsec:DiffOp","hasSummary":false,"hasTitle":false,"height":100,"width":980},"classes":"l0","position":{"x":8876.861540464926,"y":957.0028151092976}},{"group":"nodes","data":{"id":"titlesubsec:DiffOp","name":"subsectionTitle","text":"

Differential operators (continuous case)

","parent":"subsec:DiffOp","rank":"0","html_name":"subsec:DiffOp","hasSummary":false,"hasTitle":false,"height":239,"width":980},"classes":"l0","position":{"x":10265.349643524034,"y":2232.9755917479156}},{"group":"nodes","data":{"id":"subsec:DisDifOp","name":"subsection","text":"","parent":"sec:DiffOp","rank":"0","html_name":"subsec:DisDifOp","hasSummary":false,"hasTitle":false,"height":100,"width":980},"classes":"l0","position":{"x":5444.760413248439,"y":1682.9165409097325}},{"group":"nodes","data":{"id":"titlesubsec:DisDifOp","name":"subsectionTitle","text":"

Discrete differential operators

","parent":"subsec:DisDifOp","rank":"0","html_name":"subsec:DisDifOp","hasSummary":false,"hasTitle":false,"height":169,"width":980},"classes":"l0","position":{"x":5349.19460384174,"y":2760.1776150533656}},{"group":"nodes","data":{"id":"subsec:ConfProb","name":"subsection","text":"","parent":"sec:Prob","rank":"0","html_name":"subsec:ConfProb","hasSummary":false,"hasTitle":false,"height":100,"width":980},"classes":"l0","position":{"x":13448.46735078488,"y":4698.229628990624}},{"group":"nodes","data":{"id":"titlesubsec:ConfProb","name":"subsectionTitle","text":"

Configurations and probabilities

","parent":"subsec:ConfProb","rank":"0","html_name":"subsec:ConfProb","hasSummary":false,"hasTitle":false,"height":239,"width":980},"classes":"l0","position":{"x":13791.694952880101,"y":5571.589739807056}},{"group":"nodes","data":{"id":"subsec:RV","name":"subsection","text":"","parent":"sec:Prob","rank":"0","html_name":"subsec:RV","hasSummary":false,"hasTitle":false,"height":100,"width":980},"classes":"l0","position":{"x":16231.081813234416,"y":3736.742929949278}},{"group":"nodes","data":{"id":"titlesubsec:RV","name":"subsectionTitle","text":"

Random Variables

","parent":"subsec:RV","rank":"0","html_name":"subsec:RV","hasSummary":false,"hasTitle":false,"height":169,"width":980},"classes":"l0","position":{"x":16566.38507963908,"y":4670.598908809021}},{"group":"nodes","data":{"id":"subsec:Marg","name":"subsection","text":"","parent":"sec:Prob","rank":"0","html_name":"subsec:Marg","hasSummary":false,"hasTitle":false,"height":100,"width":980},"classes":"l0","position":{"x":12455.79953592236,"y":2247.726441018981}},{"group":"nodes","data":{"id":"titlesubsec:Marg","name":"subsectionTitle","text":"

Marginals

","parent":"subsec:Marg","rank":"0","html_name":"subsec:Marg","hasSummary":false,"hasTitle":false,"height":169,"width":980},"classes":"l0","position":{"x":12184.695106224906,"y":3255.424081916877}},{"group":"nodes","data":{"id":"subsec:Cond","name":"subsection","text":"","parent":"sec:Prob","rank":"0","html_name":"subsec:Cond","hasSummary":false,"hasTitle":false,"height":100,"width":980},"classes":"l0","position":{"x":16647.413534034422,"y":1351.3941439416058}},{"group":"nodes","data":{"id":"titlesubsec:Cond","name":"subsectionTitle","text":"

Conditioning

","parent":"subsec:Cond","rank":"0","html_name":"subsec:Cond","hasSummary":false,"hasTitle":false,"height":169,"width":980},"classes":"l0","position":{"x":17154.284822312693,"y":2056.733633893331}},{"group":"nodes","data":{"id":"subsec:Ind","name":"subsection","text":"","parent":"sec:Prob","rank":"0","html_name":"subsec:Ind","hasSummary":false,"hasTitle":false,"height":100,"width":980},"classes":"l0","position":{"x":14201.686461770398,"y":-195.4099234936357}},{"group":"nodes","data":{"id":"titlesubsec:Ind","name":"subsectionTitle","text":"

Independence

","parent":"subsec:Ind","rank":"0","html_name":"subsec:Ind","hasSummary":false,"hasTitle":false,"height":169,"width":980},"classes":"l0","position":{"x":13942.47290294537,"y":738.7554924941212}},{"group":"nodes","data":{"id":"subsec:MomRV","name":"subsection","text":"","parent":"sec:Prob","rank":"0","html_name":"subsec:MomRV","hasSummary":false,"hasTitle":false,"height":100,"width":980},"classes":"l0","position":{"x":19392.287723865607,"y":160.11306081758323}},{"group":"nodes","data":{"id":"titlesubsec:MomRV","name":"subsectionTitle","text":"

Moments of random variables

","parent":"subsec:MomRV","rank":"0","html_name":"subsec:MomRV","hasSummary":false,"hasTitle":false,"height":169,"width":980},"classes":"l0","position":{"x":19978.181943275064,"y":1429.0085676484198}},{"group":"nodes","data":{"id":"subsec:LLN","name":"subsection","text":"","parent":"sec:Prob","rank":"0","html_name":"subsec:LLN","hasSummary":false,"hasTitle":false,"height":100,"width":980},"classes":"l0","position":{"x":16391.615276470766,"y":-1865.428969093652}},{"group":"nodes","data":{"id":"titlesubsec:LLN","name":"subsectionTitle","text":"

Laws of large numbers and central limit theorem

","parent":"subsec:LLN","rank":"0","html_name":"subsec:LLN","hasSummary":false,"hasTitle":false,"height":239,"width":980},"classes":"l0","position":{"x":16362.187931561548,"y":-1507.2763848074137}},{"data":{"id":"def:Corrsubsec:Conv","source":"subsec:Conv","target":"def:Corr","type":"strong","visibility":1}},{"data":{"id":"th:ExTIdef:TrInOp","source":"def:TrInOp","target":"th:ExTI","type":"strong","visibility":1}},{"data":{"id":"th:ConvTIdef:TrInOp","source":"def:TrInOp","target":"th:ConvTI","type":"strong","visibility":1}},{"data":{"id":"th:ConvTIsubsec:Conv","source":"subsec:Conv","target":"th:ConvTI","type":"strong","visibility":0}},{"data":{"id":"th:TrFunConsubsec:CT","source":"subsec:CT","target":"th:TrFunCon","type":"strong","visibility":0}},{"data":{"id":"th:TrFunConth:ConvTI","source":"th:ConvTI","target":"th:TrFunCon","type":"strong","visibility":1}},{"data":{"id":"th:TrFunCondef:TranFun","source":"def:TranFun","target":"th:TrFunCon","type":"strong","visibility":1}},{"data":{"id":"def:TranFundef:TrInOp","source":"def:TrInOp","target":"def:TranFun","type":"strong","visibility":1}},{"data":{"id":"def:TranFunth:ExTI","source":"th:ExTI","target":"def:TranFun","type":"strong","visibility":1}},{"data":{"id":"rem:Contdef:TrInOp","source":"def:TrInOp","target":"rem:Cont","type":"strong","visibility":1}},{"data":{"id":"rem:FinSupth:TrFunCon","source":"th:TrFunCon","target":"rem:FinSup","type":"strong","visibility":1}},{"data":{"id":"rem:FinSuprem:ConvArrCirc","source":"rem:ConvArrCirc","target":"rem:FinSup","type":"strong","visibility":0}},{"data":{"id":"def:Boreldef:SigmaA","source":"def:SigmaA","target":"def:Borel","type":"strong","visibility":1}},{"data":{"id":"def:Measdef:SigmaA","source":"def:SigmaA","target":"def:Meas","type":"strong","visibility":1}},{"data":{"id":"def:Measbldef:SigmaA","source":"def:SigmaA","target":"def:Measbl","type":"strong","visibility":1}},{"data":{"id":"def:LebIntdef:Meas","source":"def:Meas","target":"def:LebInt","type":"strong","visibility":1}},{"data":{"id":"def:LebIntdef:Measbl","source":"def:Measbl","target":"def:LebInt","type":"strong","visibility":1}},{"data":{"id":"def:LebIntdef:Borel","source":"def:Borel","target":"def:LebInt","type":"strong","visibility":1}},{"data":{"id":"rem:Dfltdef:SigmaA","source":"def:SigmaA","target":"rem:Dflt","type":"strong","visibility":1}},{"data":{"id":"rem:Dfltdef:Borel","source":"def:Borel","target":"rem:Dflt","type":"strong","visibility":1}},{"data":{"id":"def:FreeSysdef:VectSpace","source":"def:VectSpace","target":"def:FreeSys","type":"strong","visibility":1}},{"data":{"id":"def:GenSysdef:VectSpace","source":"def:VectSpace","target":"def:GenSys","type":"strong","visibility":1}},{"data":{"id":"def:Basisdef:GenSys","source":"def:GenSys","target":"def:Basis","type":"strong","visibility":1}},{"data":{"id":"def:Basisdef:FreeSys","source":"def:FreeSys","target":"def:Basis","type":"strong","visibility":1}},{"data":{"id":"def:SubSpacedef:VectSpace","source":"def:VectSpace","target":"def:SubSpace","type":"strong","visibility":1}},{"data":{"id":"def:Spandef:SubSpace","source":"def:SubSpace","target":"def:Span","type":"strong","visibility":1}},{"data":{"id":"def:Spansubsec:Mats","source":"subsec:Mats","target":"def:Span","type":"strong","visibility":1}},{"data":{"id":"def:Coordsdef:Basis","source":"def:Basis","target":"def:Coords","type":"strong","visibility":1}},{"data":{"id":"def:BasChgdef:Coords","source":"def:Coords","target":"def:BasChg","type":"strong","visibility":1}},{"data":{"id":"def:BasChgdef:MatMul","source":"def:MatMul","target":"def:BasChg","type":"strong","visibility":1}},{"data":{"id":"rem:ExVectspdef:VectSpace","source":"def:VectSpace","target":"rem:ExVectsp","type":"strong","visibility":1}},{"data":{"id":"def:MatMuldef:Mat","source":"def:Mat","target":"def:MatMul","type":"strong","visibility":1}},{"data":{"id":"def:Transdef:Mat","source":"def:Mat","target":"def:Trans","type":"strong","visibility":1}},{"data":{"id":"def:Transdef:MatMul","source":"def:MatMul","target":"def:Trans","type":"strong","visibility":1}},{"data":{"id":"def:IsoKndef:Basis","source":"def:Basis","target":"def:IsoKn","type":"strong","visibility":1}},{"data":{"id":"def:IsoKndef:LinMap","source":"def:LinMap","target":"def:IsoKn","type":"strong","visibility":1}},{"data":{"id":"th:CompLinMapsdef:MatMul","source":"def:MatMul","target":"th:CompLinMaps","type":"strong","visibility":1}},{"data":{"id":"th:CompLinMapsdef:MatMap","source":"def:MatMap","target":"th:CompLinMaps","type":"strong","visibility":1}},{"data":{"id":"def:LinMapdef:VectSpace","source":"def:VectSpace","target":"def:LinMap","type":"strong","visibility":1}},{"data":{"id":"def:MatMapdef:LinMap","source":"def:LinMap","target":"def:MatMap","type":"strong","visibility":1}},{"data":{"id":"def:MatMapdef:Coords","source":"def:Coords","target":"def:MatMap","type":"strong","visibility":1}},{"data":{"id":"def:MatMapsubsec:Mats","source":"subsec:Mats","target":"def:MatMap","type":"strong","visibility":1}},{"data":{"id":"def:Eigendef:LinMap","source":"def:LinMap","target":"def:Eigen","type":"strong","visibility":1}},{"data":{"id":"def:Eigensubsec:Mats","source":"subsec:Mats","target":"def:Eigen","type":"strong","visibility":1}},{"data":{"id":"def:DiagMapdef:Eigen","source":"def:Eigen","target":"def:DiagMap","type":"strong","visibility":1}},{"data":{"id":"rem:MatMultVectdef:MatMap","source":"def:MatMap","target":"rem:MatMultVect","type":"strong","visibility":1}},{"data":{"id":"def:Pythdef:OrthBas","source":"def:OrthBas","target":"def:Pyth","type":"strong","visibility":1}},{"data":{"id":"th:OrthProjdef:Span","source":"def:Span","target":"th:OrthProj","type":"strong","visibility":1}},{"data":{"id":"th:OrthProjdef:OrthProj","source":"def:OrthProj","target":"th:OrthProj","type":"strong","visibility":1}},{"data":{"id":"th:CauSchdef:Norm","source":"def:Norm","target":"th:CauSch","type":"strong","visibility":1}},{"data":{"id":"def:InnProddef:VectSpace","source":"def:VectSpace","target":"def:InnProd","type":"strong","visibility":1}},{"data":{"id":"def:InnProddef:LinMap","source":"def:LinMap","target":"def:InnProd","type":"strong","visibility":1}},{"data":{"id":"def:Normdef:InnProd","source":"def:InnProd","target":"def:Norm","type":"strong","visibility":1}},{"data":{"id":"def:OrthBasdef:InnProd","source":"def:InnProd","target":"def:OrthBas","type":"strong","visibility":1}},{"data":{"id":"def:OrthBasdef:Norm","source":"def:Norm","target":"def:OrthBas","type":"strong","visibility":1}},{"data":{"id":"def:OrthFreedef:InnProd","source":"def:InnProd","target":"def:OrthFree","type":"strong","visibility":1}},{"data":{"id":"def:InnMatdef:InnProd","source":"def:InnProd","target":"def:InnMat","type":"strong","visibility":1}},{"data":{"id":"def:InnMatsubsec:Mats","source":"subsec:Mats","target":"def:InnMat","type":"strong","visibility":1}},{"data":{"id":"def:OrthProjdef:Norm","source":"def:Norm","target":"def:OrthProj","type":"strong","visibility":1}},{"data":{"id":"def:OrthProjdef:SubSpace","source":"def:SubSpace","target":"def:OrthProj","type":"strong","visibility":1}},{"data":{"id":"rem:InnOrthBasdef:OrthBas","source":"def:OrthBas","target":"rem:InnOrthBas","type":"strong","visibility":1}},{"data":{"id":"rem:InnOrthBasdef:InnMat","source":"def:InnMat","target":"rem:InnOrthBas","type":"strong","visibility":1}},{"data":{"id":"rem:OrthProjBasdef:OrthProj","source":"def:OrthProj","target":"rem:OrthProjBas","type":"strong","visibility":1}},{"data":{"id":"rem:OrthProjBasdef:OrthBas","source":"def:OrthBas","target":"rem:OrthProjBas","type":"strong","visibility":1}},{"data":{"id":"def:ConvDiscdef:ConvCont","source":"def:ConvCont","target":"def:ConvDisc","type":"strong","visibility":1}},{"data":{"id":"def:ConvArrdef:ConvDisc","source":"def:ConvDisc","target":"def:ConvArr","type":"strong","visibility":1}},{"data":{"id":"def:ConvCircdef:ConvCont","source":"def:ConvCont","target":"def:ConvCirc","type":"strong","visibility":1}},{"data":{"id":"def:ConvCircDiscdef:ConvCirc","source":"def:ConvCirc","target":"def:ConvCircDisc","type":"strong","visibility":1}},{"data":{"id":"def:ConvCircDiscdef:ConvDisc","source":"def:ConvDisc","target":"def:ConvCircDisc","type":"strong","visibility":1}},{"data":{"id":"rem:ConvArrCircdef:ConvCircDisc","source":"def:ConvCircDisc","target":"rem:ConvArrCirc","type":"strong","visibility":1}},{"data":{"id":"rem:ConvArrCircdef:ConvArr","source":"def:ConvArr","target":"rem:ConvArrCirc","type":"strong","visibility":1}},{"data":{"id":"def:FTdef:FS","source":"def:FS","target":"def:FT","type":"strong","visibility":1}},{"data":{"id":"def:FTdef:DFT","source":"def:DFT","target":"def:FT","type":"strong","visibility":1}},{"data":{"id":"def:FSdef:FT","source":"def:FT","target":"def:FS","type":"strong","visibility":1}},{"data":{"id":"def:FSdef:DFT","source":"def:DFT","target":"def:FS","type":"strong","visibility":1}},{"data":{"id":"def:FSdef:OrthBas","source":"def:OrthBas","target":"def:FS","type":"strong","visibility":0}},{"data":{"id":"def:DFTdef:FS","source":"def:FS","target":"def:DFT","type":"strong","visibility":1}},{"data":{"id":"def:DFTdef:FT","source":"def:FT","target":"def:DFT","type":"strong","visibility":1}},{"data":{"id":"def:DFTdef:OrthBas","source":"def:OrthBas","target":"def:DFT","type":"strong","visibility":0}},{"data":{"id":"th:prodTFdef:ConvCont","source":"def:ConvCont","target":"th:prodTF","type":"strong","visibility":1}},{"data":{"id":"th:prodTFdef:FT","source":"def:FT","target":"th:prodTF","type":"strong","visibility":1}},{"data":{"id":"th:prodSdef:ConvCirc","source":"def:ConvCirc","target":"th:prodS","type":"strong","visibility":1}},{"data":{"id":"th:prodSdef:ConvDisc","source":"def:ConvDisc","target":"th:prodS","type":"strong","visibility":1}},{"data":{"id":"th:prodSdef:FS","source":"def:FS","target":"th:prodS","type":"strong","visibility":1}},{"data":{"id":"th:prodDFTdef:ConvCircDisc","source":"def:ConvCircDisc","target":"th:prodDFT","type":"strong","visibility":1}},{"data":{"id":"th:prodDFTdef:DFT","source":"def:DFT","target":"th:prodDFT","type":"strong","visibility":1}},{"data":{"id":"th:TranFunDerdef:Der","source":"def:Der","target":"th:TranFunDer","type":"strong","visibility":1}},{"data":{"id":"th:TranFunDerdef:TranFun","source":"def:TranFun","target":"th:TranFunDer","type":"strong","visibility":0}},{"data":{"id":"def:DirDerdef:Der","source":"def:Der","target":"def:DirDer","type":"strong","visibility":1}},{"data":{"id":"def:Differ1def:Der","source":"def:Der","target":"def:Differ1","type":"strong","visibility":1}},{"data":{"id":"def:Differ1def:DirDer","source":"def:DirDer","target":"def:Differ1","type":"strong","visibility":1}},{"data":{"id":"def:DifferMdef:Differ1","source":"def:Differ1","target":"def:DifferM","type":"strong","visibility":1}},{"data":{"id":"def:GradCondef:Differ1","source":"def:Differ1","target":"def:GradCon","type":"strong","visibility":1}},{"data":{"id":"def:nthDerdef:Der","source":"def:Der","target":"def:nthDer","type":"strong","visibility":1}},{"data":{"id":"def:Lapdef:nthDer","source":"def:nthDer","target":"def:Lap","type":"strong","visibility":1}},{"data":{"id":"def:Lapdef:DirDer","source":"def:DirDer","target":"def:Lap","type":"strong","visibility":1}},{"data":{"id":"th:TranFunDisDerdef:DisDer","source":"def:DisDer","target":"th:TranFunDisDer","type":"strong","visibility":1}},{"data":{"id":"th:TranFunDisDerth:TranFunDer","source":"th:TranFunDer","target":"th:TranFunDisDer","type":"strong","visibility":1}},{"data":{"id":"th:TranFunDisDerth:TrFunCon","source":"th:TrFunCon","target":"th:TranFunDisDer","type":"strong","visibility":0}},{"data":{"id":"def:DisDerdef:Der","source":"def:Der","target":"def:DisDer","type":"strong","visibility":1}},{"data":{"id":"def:GradDisdef:GradCon","source":"def:GradCon","target":"def:GradDis","type":"strong","visibility":1}},{"data":{"id":"def:GradDisdef:DisDer","source":"def:DisDer","target":"def:GradDis","type":"strong","visibility":1}},{"data":{"id":"def:GradMaskdef:DisDer","source":"def:DisDer","target":"def:GradMask","type":"strong","visibility":1}},{"data":{"id":"def:GradMaskrem:FinSup","source":"rem:FinSup","target":"def:GradMask","type":"strong","visibility":0}},{"data":{"id":"def:ConfSprem:IntProb","source":"rem:IntProb","target":"def:ConfSp","type":"strong","visibility":1}},{"data":{"id":"def:Evdef:ConfSp","source":"def:ConfSp","target":"def:Ev","type":"strong","visibility":1}},{"data":{"id":"def:Probdef:Meas","source":"def:Meas","target":"def:Prob","type":"strong","visibility":0}},{"data":{"id":"def:Probdef:Ev","source":"def:Ev","target":"def:Prob","type":"strong","visibility":1}},{"data":{"id":"def:ProbDendef:Prob","source":"def:Prob","target":"def:ProbDen","type":"strong","visibility":1}},{"data":{"id":"def:ProbDendef:LebInt","source":"def:LebInt","target":"def:ProbDen","type":"strong","visibility":0}},{"data":{"id":"rem:Evdef:Ev","source":"def:Ev","target":"rem:Ev","type":"strong","visibility":1}},{"data":{"id":"rem:ProbAssdef:Prob","source":"def:Prob","target":"rem:ProbAss","type":"strong","visibility":1}},{"data":{"id":"rem:AbsConfdef:ConfSp","source":"def:ConfSp","target":"rem:AbsConf","type":"strong","visibility":1}},{"data":{"id":"rem:AbsConfsubsec:RV","source":"subsec:RV","target":"rem:AbsConf","type":"strong","visibility":1}},{"data":{"id":"def:RVLawdef:RV","source":"def:RV","target":"def:RVLaw","type":"strong","visibility":1}},{"data":{"id":"def:JoinRVdef:RV","source":"def:RV","target":"def:JoinRV","type":"strong","visibility":1}},{"data":{"id":"def:JoinRVdef:RVLaw","source":"def:RVLaw","target":"def:JoinRV","type":"weak"}},{"data":{"id":"def:Margdef:CondProbRV","source":"def:CondProbRV","target":"def:Marg","type":"weak"}},{"data":{"id":"def:MargProbdef:Marg","source":"def:Marg","target":"def:MargProb","type":"strong","visibility":1}},{"data":{"id":"def:MargRVdef:Marg","source":"def:Marg","target":"def:MargRV","type":"strong","visibility":1}},{"data":{"id":"def:MargRVdef:MargProb","source":"def:MargProb","target":"def:MargRV","type":"weak"}},{"data":{"id":"def:MargRVdef:RVLaw","source":"def:RVLaw","target":"def:MargRV","type":"weak"}},{"data":{"id":"th:Bayesdef:CondProb","source":"def:CondProb","target":"th:Bayes","type":"strong","visibility":1}},{"data":{"id":"def:CondProbRVdef:JoinRV","source":"def:JoinRV","target":"def:CondProbRV","type":"strong","visibility":1}},{"data":{"id":"def:CondProbRVdef:CondProb","source":"def:CondProb","target":"def:CondProbRV","type":"strong","visibility":1}},{"data":{"id":"def:CondProbRVdef:MargRV","source":"def:MargRV","target":"def:CondProbRV","type":"strong","visibility":1}},{"data":{"id":"th:JLIVdef:IndRV","source":"def:IndRV","target":"th:JLIV","type":"strong","visibility":1}},{"data":{"id":"th:JLIVdef:MargRV","source":"def:MargRV","target":"th:JLIV","type":"strong","visibility":1}},{"data":{"id":"th:JLIVdef:CondProbRV","source":"def:CondProbRV","target":"th:JLIV","type":"strong","visibility":1}},{"data":{"id":"def:IndRVsubsec:RV","source":"subsec:RV","target":"def:IndRV","type":"strong","visibility":1}},{"data":{"id":"def:IndRVdef:IndEv","source":"def:IndEv","target":"def:IndRV","type":"strong","visibility":1}},{"data":{"id":"def:IndExpdef:Expe","source":"def:Expe","target":"def:IndExp","type":"strong","visibility":1}},{"data":{"id":"def:IndExpdef:IndRV","source":"def:IndRV","target":"def:IndExp","type":"strong","visibility":1}},{"data":{"id":"def:StdPropdef:Std","source":"def:Std","target":"def:StdProp","type":"strong","visibility":1}},{"data":{"id":"def:StdPropdef:IndRV","source":"def:IndRV","target":"def:StdProp","type":"weak"}},{"data":{"id":"def:Expedef:RV","source":"def:RV","target":"def:Expe","type":"strong","visibility":1}},{"data":{"id":"def:Expedef:LebInt","source":"def:LebInt","target":"def:Expe","type":"strong","visibility":0}},{"data":{"id":"def:ScalRVdef:Expe","source":"def:Expe","target":"def:ScalRV","type":"strong","visibility":1}},{"data":{"id":"def:ScalRVdef:IndExp","source":"def:IndExp","target":"def:ScalRV","type":"weak"}},{"data":{"id":"def:Covdef:ScalRV","source":"def:ScalRV","target":"def:Cov","type":"strong","visibility":1}},{"data":{"id":"def:Stddef:Cov","source":"def:Cov","target":"def:Std","type":"strong","visibility":1}},{"data":{"id":"def:CovMdef:Cov","source":"def:Cov","target":"def:CovM","type":"strong","visibility":1}},{"data":{"id":"def:WLLNdef:Std","source":"def:Std","target":"def:WLLN","type":"strong","visibility":1}},{"data":{"id":"sec:TIOpesec:LA","source":"sec:LA","target":"sec:TIOpe","type":"strong","visibility":1}},{"data":{"id":"sec:DiffOpsec:TIOpe","source":"sec:TIOpe","target":"sec:DiffOp","type":"strong","visibility":1}},{"data":{"id":"sec:Probsec:Meas","source":"sec:Meas","target":"sec:Prob","type":"strong","visibility":1}},{"data":{"id":"sec:Probsec:LA","source":"sec:LA","target":"sec:Prob","type":"strong","visibility":1}},{"data":{"id":"subsec:Fsec:LA","source":"sec:LA","target":"subsec:F","type":"strong","visibility":0}},{"data":{"id":"subsec:RVsubsec:ConfProb","source":"subsec:ConfProb","target":"subsec:RV","type":"strong","visibility":1}},{"data":{"id":"subsec:RVdef:Measbl","source":"def:Measbl","target":"subsec:RV","type":"strong","visibility":0}},{"data":{"id":"subsec:Margsubsec:ConfProb","source":"subsec:ConfProb","target":"subsec:Marg","type":"strong","visibility":1}},{"data":{"id":"subsec:Margdef:JoinRV","source":"def:JoinRV","target":"subsec:Marg","type":"strong","visibility":1}},{"data":{"id":"subsec:Margdef:RVLaw","source":"def:RVLaw","target":"subsec:Marg","type":"weak"}},{"data":{"id":"subsec:Condsubsec:ConfProb","source":"subsec:ConfProb","target":"subsec:Cond","type":"strong","visibility":1}},{"data":{"id":"subsec:Inddef:Prob","source":"def:Prob","target":"subsec:Ind","type":"strong","visibility":1}},{"data":{"id":"subsec:Inddef:CondProb","source":"def:CondProb","target":"subsec:Ind","type":"weak"}},{"data":{"id":"subsec:LLNsubsec:MomRV","source":"subsec:MomRV","target":"subsec:LLN","type":"strong","visibility":1}}];