$\mathcal{Metric}\mathcal{Space}\mathcal{,}\mathcal{Vector}\mathcal{Space}\mathcal{,}\mathcal{Normed}\mathcal{Space}\mathcal{,}\mathcal{Inner}\mathcal{Product}\mathcal{Space}\mathcal{,}\mathcal{Hilbert}\mathcal{Space}$

Author:

$\mathcal{CrazyDog}$, Ph.D. in Electrical Engineering, NCTU, R.O.C.
email: [e-mail]
Date: 20250304

Copyright: CC BY-NC-SA

$$

$${\displaystyle }$$

站在巨人的肩膀

腦中真書藏萬卷，掌握文武半邊天

Mathematics (logic, calculus, linear algebra, probability, statistics), Data Structure, Algorithm, DSP, Micro-processor and OS 是內功心法

基礎要紮實

network programming, embedded system 是戰鬥工法

所有矩陣運算要注意電腦計算錯誤與overflow的可能性

家扶基金會

台灣之心愛護動物協會（Heart of Taiwan Animal Care, HOTAC）

有些圖取至 wiki, 感謝這些圖的創作者

學而不思則罔 思而不學則殆 學而後思則悟

簡單 整合 重要的 metric, norm, inner product, Schwarz inequality,

$L^p$ norm 引入

$cos(\theta )$ 相關性 等工程 物理等重要觀念

Metric Space (賦距空間)

Set

$X$ and define a function

$d:(X,X)\to R$

1. $d(x,y)\ge 0$
2. $d(x,y)+d(y,z)\ge d(x,z)$
3. $d(x,y)=d(y,x)$
4. $d(x,y)=0$ iff
   $x=y$

We say

$(X,d)$ is a metric space (賦距空間) with metric

$d(.,.)$.
e.g., Euclidean Space.

Distance between

$x\in X$ and the subset

$A\subset X$

$d(x,A)=lim inf\{d(x,y):y\in A\}$

Applications:

$d_p(x,y)=[\int |(x(t)-y(t)){|}^{p}dt{]}^{1/p}$,

$p=1,2,3,...$
is also a metric. (Minkowski Inequality) for good functions.

inner product

$<.,.>$ on vector space

$X$:

$x,y,z$ vectors

$\in X$

$<.,.>:X\otimes X\to$

$R$ or

$C$

1. $<x+y,z>=<x,z>+<y,z>$
2. $<\alpha x,y>=\alpha <x,y>$
3. $<x,y>=\overline{<y,x>}$
4. $<x,x>\ne 0$ when
   $x\ne 0$
   

Define norm:

$||x||=\sqrt{<x,x>}$

$\ge 0$

$||x+y|{|}_p\le ||x|{|}_p+||y|{|}_p$ triangle inequality

e.g.,

1. $\overrightarrow{x},\overrightarrow{y}\in R^n$,
   $<\overrightarrow{x},\overrightarrow{y}>=\sum _{i=1}^n{x}_i{y}_i$

2. $<f,g>\doteq {\int }_{I}fg$, where f, g real function on
   $I=[a,b]$ (interval)
   Remark.
   
   ${\int }_{I}fg$ : Lebesque integral (如果在 I 區間Riemann integral存在, 則兩個相等)
   e.g., Let
   $I=[0,1]$,
   $f(x)=x^2$,
   $g(x)=0$, if
   $x\in A=\{0,1/2,1/2^2,...\}$,
   $g(x)=1\in I-A$ then
   ${\int }_{I}f={\int }_{I}f(x)dx$ (Riemann integral) and
   ${\int }_{I}g=1$. Riemann integral
   $\int g(x)dx$ 不存在.

Probability Measure and Conditional Expectation
Functions are Vectors
3.

$<f,g>\doteq \int f\bar{g}$, where f, g are complex functions.

$||f||\doteq \sqrt{<f,f>}<\mathrm{\infty }$,

$L^2$ norm

$L^p$ norm=

$(\int |f{|}^p{)}^{\frac{1}{p}}$,

$1\le p<\mathrm{\infty }$,

$p\in N$

$L^2$ space (平方可積分函數),

$l^2$ space (平方和 有限 的數列) 用在 數位通訊, 量子力學 等

$L^2$ space is also a Hilbert space(特例:

$L^2,l^2$ ).

這裡

$\int$ 是 Lebesque Integral

Definition. A Hilbert space is a complete inner product space.

科學與工程 最重要的就是

$L^2,l^2$ space. 有距離 與角度 的觀念

Schwarz inequality in a unit circle of the Euclidean plane.

抽象空間(甚至是函數) 角度, e.g.,

$L^2$ space

Define

$cos(\theta )=\frac{<x,y>}{||x||||y||}\le 1$ when

$||x||||y||>0$, via Schwarz inequality

$||f_n-f|{|}_{L^2}\to 0$ can not imply

$f_n\to f$.

e.g., Gibbs phenomenon

Trace of a matrix

$A$ is a

$n\times n$ real matrix,

$tr(A)\doteq \sum _{i=1}^{n}A[i,i]$. Then

$tr(A+B)=tr(A)+tr(B)$

$tr(\alpha A)=\alpha tr(A)$

$tr(A^T)=tr(A)$

complex numbers

The inner product of matrices is given by

$tr(B^{\ast }A)$.

Let be a subfield of

$F$ (complex numbers). Then

$M_{m,n}(F)$ is an inner product space.
證明不難, 請自學

Matrices form an inner-product space

e.g.,

$<f,g>={\int }_{I}f(t)g(t)dt$ (Lebesque integral) is a inner product on

$L^2(I)$, where

$I=[a,b]$ and provided

${\int }_{I}fg$ exists .

For any interval

$I=[a,a+\delta t]\subset R$,

$\delta t>0$, the length (i.e., measure) of the interval =

$\delta t$.

Schwarz Inequality:

$<x,y>\le ||x||||y||$

with equality holding in the Cauchy–Schwarz Inequality if and only if

$x$ and

$y$ are linearly dependent.

The Schwarz inequality allows one to extend the notion of "angle between two vectors" to any real inner-product space.

Define

$cos(\theta )=\frac{<x,y>}{||x||||y||}\le 1$ when

$||x||||y||>0$

$cos(\theta )$ 代表 兩向量的相關性 (correlation)

Random Variables

Probability space

$(\mathrm{\Omega },F,P)$

$X,Y$ random variables, by Swartz inequality, we have the covariance inequality:

$<X,Y>\doteq E[XY]$, since

$E[XY]\doteq \int X(\omega )Y(\omega )dP$ (Lebesque integral)

$cov(X,Y)=<X-E[X],Y-E[Y]>$

$var(X)=E[(X-E[X]{)}^2]$

$var(X)var(Y)\ge cov(X,Y{)}^2$

$X=[X_1,...,X_n]$ random vector

covariance matrix(dispersion matrix)

$CO{V}_X(i,j)=E[[X_i-E[X_i][X_j-E[X_j]]$

eigenspace

$H$ is a Hibert space,

$U:H\to H$ bounded linear operator, there exists an elelmet

$x_0\ne 0$ with the property that

$U{x}_0=\lambda x_0$, then

$\lambda$ is the eigenvalue,

$x_0$ eigenvector. The eigenvectors belonging to a given eigenvalue

$\lambda$ form the eigenspace (or the characteristic space of

$U$)

$H_{\lambda }$ corresponding to

$\lambda$.

Lemma.

$H$ is a Hilbert space,

$U:H\to H$,

$Ux={\lambda }_{1}x$ and

$Ux={\lambda }_{2}x$,

${\lambda }_1\ne {\lambda }_2\ne 0$ then the eigensapce of

${\lambda }_1\mathrm{\perp }$ the eigensapce of

${\lambda }_2$.
Proof. Assume

$Ux={\lambda }_{1}x$,

$Uy={\lambda }_{2}y$.

$<x,y>=\frac{1}{{\lambda }_1}<Ux,y>=\frac{{\lambda }_2}{{\lambda }_1}<x,y>$, which is possible only if

$<x,y>=0$.

Rayleigh quotient

Any covariance matrix is symmetric and positive semi-definite and its main diagonal contains variances.

A square matrix is called positive definite if it is symmetric and all its eigenvalues

$\lambda$ are positive, that is

$\lambda >0$.

If

$A$ is positive definite, then it is invertible and

$detA>0$.

A real symmetric matrix

$A$ is positive definite if and only if

$x^{T}Ax>0$ for every column

$x\ne 0$ in

$R^n$.

e.g.,

$A=\left(\begin{array}{ccc}2& -1& 0\\ -1& 2& -1\\ 0& -1& 2\end{array}\right)$ is positive-definite.

$N=\left(\begin{array}{cc}1& 1\\ -1& 1\end{array}\right)$ is not positive-definite in

$C^2$ (and not in

$R^2$), since

$z^{\ast }Nz=2+2i$, where

$z=[1,i{]}^T$.

$M$ is a real-valued

$n\times n$ symmetric positive-definite matrix.
Let

$<x,My{>}_{R^n}=<x,y{>}_M=x^{T}My$ is an inner product.

Rayleigh quotient

$R(M,x)=\frac{<x,Mx>}{||x|{|}^2}$

$R(M,x)\in \{{\lambda }_{min},{\lambda }_{max}\}$ where

${\lambda }_{min},{\lambda }_{max}$ are respectively the smallest and largest eigenvalues of

$M$.

The geometric multiplicity of an eigenvalue is the dimension of the linear space of its associated eigenvectors (i.e., its eigenspace).

characteristic polynomial

$f_A(\lambda )=det(\lambda I-A)$

$A:R^n\to R^n$,

$dim(N(\lambda I-A))+dim(R(\lambda I-A))=n$, where
null space

$N(L)=\{x\in X:Lx=0\}$
and
range space

$R(L)=\{y=Lx:x\in X\}$
geometric multiplicity of

$\lambda =dim(N(\lambda I-A))$.

e.g.,
In multivariate statistics and probability theory, the scatter matrix is a statistic that is used to make estimates of the covariance matrix.

$M=CO{V}_X$

Scatter Matrix S

classification

Given n samples of m-dimensional data, represented as the

$m\times n$ matrix,

$x=[x_1,...,x_n]$, the sample mean is

$\overline{x}=\frac{1}{n}\sum _{i=1}^n{x}_i$
The scatter matrix is the

$m\times n$ positive semi-definite matrix

$S=\sum _{i=1}^n(x_i-\overline{x})(x_i-\overline{x}{)}^T$

Hermitian 矩陣特徵值的變化界定
Scatter matrix , Covariance and Correlation Explained
Scatter Plot

---

Applications:

數位通訊
機率統計
檢測與估計
machine learning

---

Assume

$I=[0,2\pi ]$,

$<f,g>={\int }_{I}f(t)g(t)dt$ and

$cos(\theta )=\frac{<f,g>}{||f||||g||}\le 1$ (i.e., f,g 也有抽象夾角觀念),

${\int }_0^{2\pi }cos(\omega t)sin(\omega t)$dt =0

Define

$e_x=cos(\omega t)/||cos(\omega t)||$ and

$e_y=sin(\omega t)/||sin(\omega t)||$ in

$[0,2\pi ]$.

$cos(\theta )=<e_x,e_y>=0$ and

$||e_x||=||e_y||=1$

$e_x,e_y$ 當一 vector space basis 就像

$R^2$一樣, 有 距離, 內積 與 角度 觀念的 vector space.

Probability space

$(\mathrm{\Omega },F,P)$
Ref. Probability measure and conditional expectation for EE
Assume

$n$ is noise and

$<f,g>=0,f,g\in L^2(\mathrm{\Omega }\otimes [0,T])$ (random processes, Stochastic Processes or random functions in

$[0,T]$). Implicity, we consider

$f,g\in L^{2}or{l}^2$ (Hilbert Space)

Correlation Receiver (

$<f,g>={\int }_0^{T}fg$)~Matched Filter Receiver

Assume

$<f,g>=0$.

1. $<f+n,f>=<f,f>+<n,f>=||f|{|}^2+<n,f>$
2. $<f+n,g>=<f,g>+<n,g>=<n,g>$

Notice that

$<f,h>\le ||f||||h||$ by Schwarz Inequality.

Assume

$f,g\in L^2$ or

$l^2$(random process,random sequence),

$<f,g>\doteq E[{\int }_0^{T}fgdt]=E[samplepathintegral]$.

$<n,f>\le ||n||||f||$ and

$<n,\frac{f}{||n||}>\le ||f||$ by inner product properity and Schwarz Inequality.

Let

$n^{{}^{\prime }}=<n,h>$ and

$||n^{{}^{\prime }}||=N=\sqrt{E}<\mathrm{\infty }$
Maximizing​ SNR(Signal-to-noise ratio)

$\frac{||<f,h>|{|}^2}{||n^{{}^{\prime }}|{|}^2}=\frac{averagesignalpower\times T}{averagenoisepower\times T}$ (digital communication) to get good performance.

$||<f,h>||\le ||f||||h||$, the two sides are equal if and only if

$f$ and

$h$ are linearly dependent, i.e.,

$h=\alpha f$,

$\alpha \ne 0$. Let

$g(t)=f(T-t)$,

$f\star g=<f,f>$ in

$[0,T]$

這是 基本的數位通訊Correlation Receiver or matched filter 的數學原理

---

Lineary Independent
A sequence of vectors

${\overrightarrow{v}}_1,{\overrightarrow{v}}_2,...,{\overrightarrow{v}}_k$ from a vector space V is said to be linearly dependent, if there exist scalars

$a_1,a_2,...,a_k$ not all zero, such that

$\sum _{i=1}^k{a}_i{\overrightarrow{v}}_i=0$. A set of vectors is linearly dependent if and only if one of them is zero or a linear combination of the others.

A sequence of vectors

${\overrightarrow{v}}_1,{\overrightarrow{v}}_2,...,{\overrightarrow{v}}_k$ is said to be linearly independent if it is not linearly dependent, that is, if the equation

$\sum _{i=1}^k{a}_i{\overrightarrow{v}}_i=0$ can only be satisfied by

$a_i=0$,

$i=1,2,...,k$.

The kernel of a linear map, also known as the null space or nullspace, is the linear subspace of the domain of the map which is mapped to the zero vector.
A linear map

$L:V\to W$ between two vector spaces

$V$ and

$W$

the kernel of

$L$:

$ker(L)=\{v\in V|L(v)=0\}\doteq L^{-1}(0)$

The image of

$L$:

$img(L)\doteq \{L(v):v\in V\}$

$W$ is a subspace of

$V$,

$img(L(W))=\{L(v):v\in W\}$.

e.g.,

$B=\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right)$

$ker(B-1I{)}^3=ker\left(\begin{array}{ccc}0& 0& 0\\ 0& 0& 0\\ 0& 0& 0\end{array}\right)=R^3$

$img(B)=R^3$
eigenvalues of

$B$: 1, 1, 1

$K_l\doteq ker(A-\lambda I{)}^l$, then

$0\ne K_1\subseteq K_2\subseteq K_3...$
Why?

rank

Assume

$f:V^m\to V^n$,

$f:\overrightarrow{x}\to A\overrightarrow{x},\overrightarrow{x}\in V^m$, where

$V^i$ is a

$i$-dimentional vector space,

$A$ is an

$n\times m$ matrix.
rank of

$f$= rank

$A\doteqdot dimf(V^m)$.

A sequence of vectors

$V(A)$ denotes the set of all (finite) linear combinations of the points in

$A$, i.e., the linear subspace spanned by

$A$ (or linear span of A~span(A), 線性生成空間).

e.g.,

$A=\{x_1,x_2,...x_n\}$,

$span(A)=\{x:x=\sum _{i=1}^n{\lambda }_i{x}_i,{\lambda }_i\in R\}$

Lemma.

$dimf(V^m)+dimker(f)=m$

Proof.

Let dim

$f^{-1}(0)=m-r$ and

$\{u_{r+1},...,u_m\}$ be a basis of

$f^{-1}(0)$. Then choose

$u_i,1\le i\le r$ such that

$\{u_1,...u_r,...,u_m\}$ is a basis of

$V^m$.
Claim

$f(u_1),...f(u_r)$ is a basis of

$f(V^m)$ and dim

$f(V^m)=r$.

$f(V^m)=span\{f(u_1),...,f(u_r),...,f(u_m)\}$. Since

$f(u_{r+1})=...=f(u_m)=0$, then

$f(V^m)=span\{f(u_1),...,f(u_r)\}$.

Claim

$f(u_1),...,f(u_r)$ are linearly independent.

Suppose

$\sum _{i=1}{\alpha }_{i}f(u_i)=0$. Then

$f(\sum _{i=1}{\alpha }_i{u}_i)=\sum f({\alpha }_i{u}_i)=0$ or

$\sum _{i=1}^r{\alpha }_i{u}_i\in f^{-1}(0)$. There exists a

${\alpha }_i,r+1\le i\le m$ such that

$\sum _{i=1}^r{\alpha }_i{u}_i+\sum _{i=r+1}^m{\alpha }_i{u}_i=0$. Since

$u_i,1\le i\le m$ are linearly independent then

${\alpha }_i=0,i=1,...,m$. Hence

$f(u_1),...,f(u_r)$ are linearly independent and dim

$f(V^m)=r$.

Corollary. Let

$f$ be a linear transformation of

$V^n$ (into itself). Then

$f$ is one-to-on if and only if

$f$ is onto.

Proof.

$f(x_1)=f(x_2)\iff f(x_1-x_2)=0$. If

$f^{-1}(0)=\{0\}$, then

$x_1=x_x$. Hence

$f$ ono-to-one. Conversly, it is trival.

$f^{-1}(0)=\{0\}\iff$

$dim{f}^{-1}(0)=0\iff dimf(V^n)=n\iff f(V^n)=V^n$.

Corollary.

$n\times m$ matrix

$A=(a_{ij})$. Let

${\overrightarrow{a}}_1,...,{\overrightarrow{a}}_m$ denote the column vectors of

$A$. For

$\overrightarrow{x}\in V^m,\overrightarrow{x}=[x_1,...x_m{]}^T$,

$f(\overrightarrow{x})=A\overrightarrow{x}=\sum _i{x}_i{\overrightarrow{a}}_i$ and

$f(V^m)=span\{\overrightarrow{a_1},...,\overrightarrow{a_m}\}$.

$rankA=$ the maximal number of linearly independent columns of

$A$

Corollary. Let

$n\times m$ matrix

$A$ and

$m\times l$ matrix B, we have

$rankAB\le rankA,rankB$, since

$rankAB=dimAB{V}^l\le dimA{V}^m=rankA$, and

$rankAB\le B{V}^l=rankB$.

Corollary.

$P,Q$ nonsingular (invertible), then

$rankPAQ=rankPA=rankAQ=rankA$.

Corollary. Let

$A$ be an

$m$ by

$n$ matrix. Then

$rank(A)=m$ iff rows of

$A$ are linearly independent.

Corollary.

$A,B$

$n\times m$ matrices.

$rank(A+B)\le rankA+rankB$, since

$rank(A+B)=dim(A+B)V^m\le dim(A{V}^m+B{V}^m)\le dimA{V}^m+dimB{V}^m=rankA+rankB$
這就是您 線代 解 rank 的方法之原理.

Let

$H$ be a Hilbert space,

$M$ is a subset of

$H$. Define

$M^{\mathrm{\perp }}$, the othogonal complemet of

$M$ by

$M^{\mathrm{\perp }}=\{x\in H:<x,y>=0forally\in M\}$.

Closed set
A set

$A$ in a metric space

$(X,d)$ is a closed set if and only if if every convergent sequence

$\{x_n\}$ with

$x_n\in A$ has it limit in

$A$.

e.g.,

$a_n=1-\frac{1}{n+1}$,

$n=1,2,....$,

$\underset{n\to \mathrm{\infty }}{lim}{a}_n=1$

$a_n\in (0,1)$, however

$1\notin (0,1)$, interrval (0,1) not closed set.

interval [0,1] is a closed set.

Projection theorem
Let

$M$ be any closed linear subspace of a Hilbert space

$H$, Then

$H=M+M^{\mathrm{\perp }}$ (linear subspace generated by

$\{M,M^{\mathrm{\perp }}\}$). Moreover, each

$x\in H$ can be expressed uniquely

$x=m+n$, where

$m\in M$ and

$n\in M^{\mathrm{\perp }}$ and

$||x|{|}^2=||m|{|}^2+||n|{|}^2$.

Let

$\hat{P}x=m$,

$\hat{P}$ projection operator. Then

$<\hat{P}x,n>=0$

Let

$A$ be a nonempty set in a linear space

$X$. The set is lineary independent if and only if for each

$x\ne 0$ in

$V(A)$, there is one and only one finite subset of

$A$, say

$\{x_1,x_2...x_n\}$, and a unique

$n-$tuple of nonzero scalars,

$\{a_1,a_2,...a_n\}$, such that

$x=a_1{x}_1+...+a_n{x}_n$.

$\{a_1,a_2,...a_n\}$: coordinates

$\{x_1,x_2...x_n\}$: basis

Hilbert projection theorem

e.g.,

$L^2$ and

$l^2$.

Operator Norm

$A:X\to Y$

$||A|{|}_p=su{p}_{x\ne 0}\frac{||Ax|{|}_p}{||x|{|}_p}$,

$1\le p\le \mathrm{\infty }$

1. $||A+B||\le ||A||+||B||$
2. $||AB||\le ||A||||B||$
3. $||A||=||A^{\ast }||$

$P$: projection operator, then

$P^2=P$ and

$||P||=1$.

3. $<x,y>=\overline{<y,x>}$

Definition. Let

$X$,

$Y$ be Hibert spaces,

$A:X\to Y$ bounded linear operator. The adjoint operator (共軛算子)

$A^{\ast }Y\to X$ is defined by the equation

$<x,A^{\ast }y{>}_X=<Ax,y{>}_Y$.

Remark (重要).

1. The adjoint may also be called the Hermitian conjugate.
2. Hermitian matrix (or self-adjoint matrix)
   $A=[a_{ij}]=[\overline{a_{ji}}]$
3. A square matrix
   $A$ is Hermitian if and only if it is unitarily diagonalizable with real eigenvalues, i.e.,
   $A=Q\mathrm{\Lambda }{Q}^{\ast }$ (spectral decomposition of A), where
   $\mathrm{\Lambda }$ is a diagonal matrix.
4. $A:H\to H$ is called self-adjoint if
   $A=A^{\ast }$.
5. $A:H\to H$ is a bounded self-adjoint operator iff
   $<x,Ax>=<Ax,x>=\overline{<x,Ax>}$ is real valued for all
   $x\in H$, since
   $<x,y>=\overline{<y,x>}$
6. $T:H\to H$ is a boundded linear transformation.
   $T$ is said to be normal if
   $T{T}^{\ast }=T^{\ast }T$.
7. If
   $T$ self-adjoint, then it is normal.
8. A square matrix
   $U\in C^{n\times n}$ is unitary if
   $U^{\ast }U=U{U}^{\ast }=I$.
9. A square matrix
   $U\in R^{n\times n}$ is orthogonal if
   $U^{T}U=U{U}^T=I$.

e.g.,

$A=\left(\begin{array}{ccc}1& 1& 0\\ 0& 1& 1\\ 1& 0& 1\end{array}\right)$

is normal, since

$A^{\ast }A=A{A}^{\ast }$ and its eigenvalues are

$2,\frac{1\pm i\sqrt{3}}{2}$.

$A$ is neither unitary, Hermitian, nor skew-Hermitian matrix.

$A=\left(\begin{array}{cc}2& 1+i\\ 1-i& 3\end{array}\right)$

$A$ is self-adjoint, and it can be checked (e.g., using the characteristic polynomial) that the eigenvalues of

$A$ are

$1,4$.

$B=\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 2\end{array}\right)$

$B$ is self-adjoint, and it can be checked (e.g., using the characteristic polynomial) that the eigenvalues of

$B$ are

$1,1,2$.
Geometric multiplicity of

$\lambda =1$ is

$2$.

Let

$T(x)=Ax$, then

$||T||$ is the square root of the largest eigenvalue of the symmetric matrix

$A^{T}A$, i.e.,

$||T||=sup\{\sqrt{\lambda }:\lambda eigenvalueof{A}^{\ast }A\}$.
Why?

e.g.,

$A=\left(\begin{array}{ccc}2& 0& 0\\ 3& 0& 2\end{array}\right)$
Then

$A^{T}A=\left(\begin{array}{ccc}13& 0& 6\\ 0& 0& 0\\ 6& 0& 4\end{array}\right)$
, which has eigenvalues

$\{0,1,16\}$, so

$||A||=4$

The normed space of all bounded linear operators from the

$X$ into

$Y$ is denoted

$B(X,Y)$.
Lemma 1.

$X,Y,Z$ Hilbert spaces,

$S\in B(X,Y)$ and

$T\in B(Y,Z)$, then

$||TS||\le ||T||||S||$.

Lemma 2. 類似您學過的矩陣運算

$X,Y,Z$ Hilbert spaces.

1. If
   $A_1,A_2\in B(X,Y)$,
   $(A_1+A_2{)}^{\ast }=A_1^{\ast }+A_2^{\ast }$.
2. If
   $\alpha \in R$,
   $(\alpha A{)}^{\ast }=\alpha A^{\ast }$
3. $A_1\in B(X,Y)$,
   $A_2\in B(Y,Z)$ then
   $(A_2{A}_1{)}^{\ast }=A_1^{\ast }{A}_2^{\ast }$.
4. If
   $A^{-1}$ exists, then
   $(A^{-1}{)}^{\ast }=(A^{\ast }{)}^{-1}$.
5. $(A^{\ast }{)}^{\ast }=A$

$H$ a Hilbert space,

$A\in B(X,X)$,

$A$ is said to be self-adjoint operator (自共軛算子) if

$A=A^{\ast }$.

$||A^{\ast }A||\le ||A^{\ast }||||A||=||A|{|}^2$

$A^{\ast }Ax=\lambda x$

軛:在車衡兩端扼住牛、馬等頸背上的曲木。

e.g.,

Covariance matrix

e.g.,

$A:R^n\to R^n$,

$A^T=A^{\ast }=A$,

$A^T$ transpose of

$A$.

e.g.,

$B=\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 2\end{array}\right)$

$B$ is a self-adjoint positive definite operator.

e.g.,
Fredholm (Volterrra) integral equation of the first kind
Let

$X=Y=L^2[0,1]$ and define

$Ax={\int }_0^{1}k(t,s)x(s)ds$,

$t\in [0,1]$ and

$||k(t,s)||<\mathrm{\infty }$ on

$[0,1]\otimes [0,1]$, where

$k(t,s)$ is called kernel function. Check

$<Ax,y>=\int x(t)\int k(s,t)y(s)dsdt$. Then

$A^{\ast }y=\int k(s,t)y(s)ds$.

FACT(重要):

1. Every linear operator definited on a finite dimentional normed space is compact(bounded operator, and so continuous).

2. For any matrix

   $A$, the eigenvalues of
   $A^{\ast }A$ are aways real and
   non-negative (in other words,
   $A^{\ast }A$ and
   $A{A}^{\ast }$ are positive definite).
   Proof. Assume
   $<x,x>=1$ and
   $<Sx,x>=<x,Sx>=\lambda =<Sx,x{>}^{\ast }={\lambda }^{\ast }$, then
   $0<<Ax,Ax>=x^{\ast }{A}^{\ast }Ax=\lambda <x,x>$.

3. Singular Value Decomposition(重要)
   Any matrix

   $A\in C^{m\times n}$ can be decomposed as
   $A=U\mathrm{\Sigma }V$ and
   $U\in C^{m\times m}$ and
   $V\in C^{n\times n}$ are unitary matrices. The matrix
   $\mathrm{\Sigma }\in C^{m\times n}$ is “diagonal,” with non-negative elements on the main diagonal. The non-zero elements of
   $\mathrm{\Sigma }$ are called the singular values of
   $A$, and satisfy
   $\sigma =\sqrt{i-theigenvalueof{A}^{\ast }A}$.
   Proof. Assume
   $rank(A)=m$. Since
   $A{A}^{\ast }$ is Hermitian, there exists a diagonal matrix
   $\mathrm{\Lambda }=diag({\lambda }_1,...,{\lambda }_m)=diag({\sigma }_1^2,...,{\sigma }_m^2)={\mathrm{\Sigma }}_1>0$ such that
   $U\mathrm{\Lambda }{U}^{\ast }=A{A}^{\ast }$.
   Let
   $V_1={\mathrm{\Sigma }}_1^{-1}{U}^{\ast }A$. Then
   $V_1^{\ast }{V}_1=I$. Construct
   $V=[V_1,V_2]\in C^{n\times n}$ by choosing the columns in
   $V_2$ so that
   $V$ is unitaary and
   $\mathrm{\Sigma }=[{\mathrm{\Sigma }}_1,0]\in R^{n\times n}$.
   $\mathrm{\Sigma }{V}^{\ast }={\mathrm{\Sigma }}_1{V}_1^{\ast }=U^{\ast }A$, i.e.,
   $A=U\mathrm{\Sigma }{V}^{\ast }$.

Proposition.
Let

$H_1$ and

$H_2$ be Hilbert spaces with inner product

$<.,.{>}_1$ and

$<.,.{>}_2$ respectively. Let

$L:H_1\to H_2$ be a boundded linear operator. Define the adjoint

$L^{\ast }:H_2\to H_1$ so that

$<y,Lx{>}_2=<L^{\ast }y,x{>}_1$ holds for all

$x\in H_1$ and all

$y\in H_2$.

1. $L^{\ast }$ is a boundded linear operator.
2. $||L||=||L^{\ast }||$
3. $L=L^{\ast \ast }$
4. $U:H_1\to H_2$ is unitary iff
   $U^{\ast }U=I_1$ and
   $U{U}^{\ast }=I_2$, where $I_i is the identity operator on
   $H_i$.

$A$ self-adjoint bounded linear operator on a real Hilbert space

$H$ .

$A$ is said to be positive semidefinite (positive definite) if

$<x,Ax>\ge 0(>0)$, for all

$x\in H$.

e.g.,

$(\mathrm{\Omega },F,P)$ is a probability space,

$X_i\in L^2(P)$ i.i.d.

$E[X_i^2]>0$ and

$E[X_i]=0$

(sample) covariance matrix (重要)

The covariance matrix

$[K_{X_i{X}_j}]=[E[X_i{X}_j]]$ is semi-positive definite and symmetric.

Proof: Positive semi-definiteness of the covariance matrix

Hence

$[K_{X_i{X}_j}]\overrightarrow{V}=\lambda \overrightarrow{V}$, the eigenvalue

$\lambda >0$ if

$[K_{X_i{X}_j}]$ is positive definite.

HOME WORK. Prove it.

Fact.

$||A||=||A^{\ast }||$ (需要 Hahn-Banach Theorem, 對EE太難)

Sample covariance matrix Q

For a sample of vectors

$x_i=(x_{i1},x_{i2},...,x_{ik}{)}^T,i=1,...,n$, where

$n$ is the sample size. Sample meam is

$\overline{x}=\frac{1}{n}\sum _{i=1}^n{x}_i$
Sample covariance matrix is

$q_{ik}=\frac{1}{n}\sum _{i=1}^n(x_i-\overline{x})(x_i-\overline{x}{)}^T$

Assume

$y\ne 0\in R^k$ and

$Q=[q_{ij}]$, then

$y^{T}Qy=\frac{1}{n}\sum _{i=1}^n((x_i-\overline{x})y{)}^2\ge 0$.

Sample covariance matrix is always positive semi-definite.

$L^2$ random process 經由 Karhunen–Loève theorem 也可得covariance matrix 用於 Principal component analysis

實務上 會有
MIT OpenCourseWare:
Singular values
Matrix Perturbations
Dynamic Systems And Control
Generalized eigenvalue problem
線代啟示錄

---

Geometric Analysis of Operator (投影運算子的幾何分析特性)

這觀念一定要懂, 這也是 Hilbert space 的重要 觀念, 也 很多證明 對 你們 太難, 我用 最簡單的 的 來解釋, 沒有 很好 的數學 應是 一堆 聽不懂的 "這很正常" 別 自責

Null space

$N(L)$

$L:X\to Y$ is a linear transformation,

$N(L)\doteq \{x\in X:Lx=0\}$
Range space

$R(L)$

$R(L)\doteq \{y=Lx:x\in X\}$

$P:H\to H$ is an orthongonal projection on a Hilbert space

$H$, then

1. P is a identity operator on
   $R(P)$ and
2. P is the zero operator on
   $N(P)$.

Hence,

$H=R(P)+N(P)$.

Let

$\{P_1,P_2,...P_m\}$ pojection operators,

$P_i{P}_j=0$ if

$i\ne j$,

$P_i\ne 0$, and

$I=\sum _{i=1}^m{P}_i$, then

$H=\sum _{i=1}^{m}R(P_i)$.

Assume

${\lambda }_i\in C$,

$i=1,2,..m$,

${\lambda }_i\ne {\lambda }_j$, if

$i\ne j$. Let

$L=\sum {\lambda }_i{P}_i$.

寫到 "連續" 學生就不懂了, 至少 有限維度(矩陣) 與 bounded (物理與工程應用) 是對的

Assume

$P_i$ continuious projection operator (e.g., finite dimentional projection operator, bounded operator, ODE, …), for any vector

$x\in H$, there exits

$x_i\in R(P_i)$ and

$Lx=\sum _{i=1}^m{\lambda }_i{x}_i$

Eigenvalue-Eigenvector

$\lambda x-Lx=0$ has a solution

${\lambda }_i$,

$i=1,...,m$(eigenvalue), then

$x_i\in R(P_i)$ (eigenvector) and

$R(P_i)=N({\lambda }_{i}I-L)$

$L\overrightarrow{x}=\lambda \overrightarrow{x}$
Intuitively, an eigenvector is a vector whose direction remains unchanged when a linear transformation is applied to it.

Riesz Representation Theory

$H$ is a Hilbert space and let

$I$ be a bounded linear functional (

$||l||<\mathrm{\infty }$) on

$H$. Then there is one and only one vector

$y\in H$ such that

$I(x)=<x,y>$ for all

$x\in H$.

e.g.,

$\overrightarrow{x}\in L^2[a,b],\overrightarrow{y}\in L^2[a,b]$,

$f(\overrightarrow{x})={\int }_{[a.b]}y(t)x(t)dt$. Then

$f$ is a linear functional and

$f=<x,y>$.

Hilbert Space 的連續線性泛函都可以表示成內積。
Remark. A linear operator is bounded if and only if it is continuous.

---

以電路而言,

$<f,g>$ 積分器 , 有沒有看出 SNR 的重要性而且用 power?

$l^2$ space

$x=\{x_k\},y=\{y_k\},k=1,2,...,n$

$<x,y>=\sum x_i{y}_i$ is an inner product on

$l^2$

---

Probability space

$(\mathrm{\Omega },\mathcal{F},P)$

$\mathrm{\Omega }\ne \varphi$ sample space

$\mathcal{F}$ is the

$\sigma$-field of subsets of sample space

$\mathrm{\Omega }$

$P:\mathcal{F}\to [0,1]$ probability measure with

$P(\varphi )=0$

$A\in \mathcal{F}$,

$A\subseteq \mathrm{\Omega }$ is an event

$X$ is a random variable(

$\mathcal{F}$-measurable function from

$\mathrm{\Omega }\to R$).

$P(X\le x)=Prob\{\omega \in \mathrm{\Omega }|X(\omega )\le x\}$

$X$,

$Y$

$\in L^2(\mathrm{\Omega },\mathcal{F},P)$ are random variables with

$E[X^2]<\mathrm{\infty }$ and

$E[Y^2]<\mathrm{\infty }$

$<X,Y>\doteq E[XY]$ is an inner product

$<X-EX,Y-EY>\doteq E[(X-E[X])E(Y-E[Y])]$ is an inner product

$||X||\doteq \sqrt{<X,X>}$ is the norm of

$X$

Markov's inequality

If X is a nonnegative random variable and a > 0,

$P(X\ge a)\le \frac{E[X]}{a}$

If

$\varphi$ is a monotonically increasing nonnegative function for the nonnegative reals, X is a random variable,

$a\ge 0$, and

$\varphi (a)>0$, then

$P(X\ge a)\le \frac{E[\varphi (X)]}{\varphi (a)}$

e.g.,

$P(|X|\ge a)\le \frac{E|X{|}^n}{a^n}$

Let

$Y=X-E[X]$, then Chebyshev's inequality.

顯示了隨機變數的「幾乎所有」值都會「接近」平均

函數 數列 隨機變數 也可看成 vector

$\sqrt{E[X^2]}$ is a norm if

$E[X^2]<\mathrm{\infty }$.

correlation coefficient

$X-E[X],Y-E[Y]$

correlation coefficient=

$\frac{<X-EX,Y-EY>}{||X-EX||||Y-EY||}$
:::

Hamming distance is a metric

Linear independence
Projection operator
basis
orthonormal basis
Independent random variables

…
請自行看 linear algebra, probability 書~寫起來很長, 若引入 measure theory 可以寫一本書了, 對一般資電又太難, wiki 沒有寫得很好

擴充 為 random vector:

If

$f\in L^2$ and

$f=a_1{e}_1+a_2{e}_2+...a_n{e}_n$,

$||e_i||=1$ and

$<e_i,e_j>=0$ if

$i\ne j$ (orthonormal basis,

$i=1,2,3...$)
then

$<f,e_i>=a_i$.

$f{\leftrightarrow }_{one-to-one}\overrightarrow{a}=(a_1,a_2,...,a_n)$, one-to-one mapping

e.g., QAM (Quadrature amplitude modulation)

$\overrightarrow{g_i}=a_{i1}\overrightarrow{e_1}+a_{i2}\overrightarrow{e_2}$

$\overrightarrow{g_i}\leftrightarrow (a_{i1},a_{i2})$

$\overrightarrow{g}=(g_1,g_2,...g_{64})$ ~64 QAM (Quadrature amplitude modulation) 原理
Why?

Wi-Fi 6/6E 1024 QAM
5th generation mobile networks (5G) 512-QAM or 1024-QAM
4G 256-QAM or 64-QAM

---

Assume

$\overrightarrow{f}=(f_1,f_2,...f_m)$ if

$f_i\in L^2$ and

$f_i=\sum _{j=1}^n{a}_{ij}{e}_j$. Then

${\overrightarrow{f}}^T=A{\overrightarrow{e}}^T$, where

$\overrightarrow{e}=(e_1,e_2,...e_n)$ and

$A=[a_{ij}]$

$\overrightarrow{f}\leftrightarrow [a_{ij}]$ one-to-one mapping

---

Homework:

$a_{ij}=?$
Hint:

$<f_i,e_k>$

estimation and prediction 基礎

用到機率 covariance matrix
因中文翻譯不同 請用 英文

$X_i$ is a random variable and

$E[X_i]=0$,

$\overrightarrow{X}=(X_1,X_2,...X_m)$ if

$X_i\in L^2$

e.g.,

$X^{\prime }=X-E[X]$ if

$E[X]\ne 0$

---

Concave vs. Convex

Jensen's inequality

$t\in [0,1]$,

$f(t_1{x}_1+(1-t_1)x_2)\le t_{1}f(x_1)+(1-t_1)f(x_2)$

​​​​(convex, concave 有些是反過來的 請自行確認)

If

$X$ is a random variable and

$\varphi$ is a convex function, then

$\varphi (E[X])\le E[\varphi (X)]$

e.g.,

1. $\varphi (x)=(x-C{)}^{+}=max\{x-C,0\}$,
   $C\ge 0$.
   $\varphi (x)$ is a increasing convex function on
   $[0,\mathrm{\infty })$

e.g.,
Let

$X$ be traffic rate and

$C$ bandwidth, then

$E[\varphi (X)]$ denotes the average loss rate. Assume

$X_1,...,X_n$ iid samples,

$\frac{\sum _{i=1}^n\varphi (X_i)\mathrm{\Delta }t}{n\mathrm{\Delta }t}\to E[\varphi (X)]$.

2. $\varphi (x)=-ln(1-x)$ increasing convex function on
   $[0,1)$

3. $\varphi (x)=-ln(x)$ decreasing convex function on
   $(0,1]$

If the function

$\varphi$ is concave, then

$\varphi (E[X])\ge E[\varphi (X)]$

Jensen's inequality (Random vector

$\overrightarrow{X}$)
Let

$\varphi$ be a convex function on a convex set

$C\subset R^n$,

$\overrightarrow{X}$ is a random vector with

$P(\overrightarrow{X}\in C)=1$, then

$E[\overrightarrow{X}]\in C$,

$E[\varphi (X)]$ exists and

$\varphi (E[\overrightarrow{X}])\le E(\varphi (\overrightarrow{X}))$.

---

linear time-invariant (LTI) system and convolotion

Let

$<\delta (t),f(t)>\doteq f(0)$, i.e.,

$f(0)=\int f(t)\delta (t)dt$ for EE (In fact, this is not the Riemann integral).

Then

$f(t)=<\delta (\tau -t),f(\tau )>$, by LTI properties.

Notice that

$f(t)=<\delta (\tau -t),f(\tau )>$ is incorrent if the system is not time-invariant.

---

Nyquist–Shannon sampling theorem— If a function

$x(t)$ contains no frequencies higher than

$W$ hertz, then it can be completely determined from its ordinates at a sequence of points spaced less than

$\frac{1}{2W}$, i.e., sample rate

$f_s>2W$

Ref. Principles of Digital Communication, by Robert G. Gallager

這本書 有難度, 沒老師教 不容易懂, 而且數學要有一定程度, 有用到 Lebesgue integration,

$L^2$ space, entropy, Markov chain, Viterbi algorithm ( dynamic programming algorithm) …

---

Let

$h(t)$ be the impulse responce

$\delta (t)$. Assume

$h(t)$ exists.

Assume

$f(t)$ is the band-limited input process of the LTI sysyem,
then the output porcess

$g(t)=<h(t-\tau ),f(\tau )>=<h(\tau ),f(t-\tau )>$

$=\int h(\tau )f(t-\tau )d\tau =\int h(t-\tau )f(\tau )d\tau$,
by LTI properties.

We define

$f\star h(t)=<h(t-\tau ),f(\tau )>$ as the convolution of

$f$ and

$h$.

$f\to \boxed{\text{LTI system: h(t)}}\to f\star h$

$(f\star g)\star h=f\star (g\star h)$

$f\star h=h\star f$

$f\star (g+h)=f\star g+f\star h$

Discrete time

Assume

$f(n)$ is the discrete time band-limited input process of the LTI sysyem.

Let

$\delta (n)=1$ if

$n=0$ and

$\delta (n)=0$ if

$n\ne 0$.

Let

$<\delta (n),f(n)>\doteq f(0)>$

$f(n)=<\delta (m-n),f(m)>$ by LTI properties.

$\delta (n)\to \boxed{\text{LTI system}}\to h(n)$

$f(n)\to \boxed{\text{LTI system: h(n)}}\to f\star h(n)$

Assume discrete time impulse response is given by

$h(n)$,
we define

$f\star h(n)=<h(n-m),f(m)>$ as the convolution of

$f$ and

$h$.

Then

$f\star h(n)$ is the output sequence of the LTI system by LTI properties.

Discrete Fourier transform (DFT)

$\overrightarrow{x}=\{x_0,x_1...,x_{N-1}\}$ complex numbers, DFT of

$\overrightarrow{x}{X}_k=\sum _{i=0}^{N-1}{x}_i{e}^{-2\pi jkn/N}$

$x_n=\frac{1}{N}\sum _{k=0}^{N-1}{X}_k{e}^{2\pi jkn/N}$

$\overrightarrow{u_k}=e^{2\pi kn/N},k=0,...,N-1$ form an orthogonal basis over the set of

$N$-dimensional complex vectors.
Claim

$<\overrightarrow{u_k},\overrightarrow{u_j}>=N{\delta }_{kj}$, i.e.,

$<\frac{\overrightarrow{u_k}}{\sqrt{N}},\frac{\overrightarrow{u_j}}{\sqrt{N}}>={\delta }_{kj}$, where

${\delta }_{kj}=1$ if

$k=j$ and

${\delta }_{kj}=0$ if

$k\ne j$.

Parseval's theorem

$<\overrightarrow{x},\overrightarrow{y}>=\frac{1}{N}<\overrightarrow{X},\overrightarrow{Y}>=\frac{1}{N}\sum _k{X}_k{Y}_k^{\ast }$

If we define DFT via

$\frac{1}{\sqrt{N}}\sum _{k=0}^{N-1}{X}_k{e}^{-2\pi jkn/N}$, then we have

$<\overrightarrow{x},\overrightarrow{y}>=<\overrightarrow{X},\overrightarrow{Y}>$

In practice, we can choose

$N$~

$2^n$

There are two main types of DFT errors: "aliasing" and “leakage"

Increase sampling rate +Window Function…

183–FFT系列：甚麼是洩漏leakage？窗函數window如何改善洩漏leakage？

n-dimentional DFT

$\overrightarrow{x}=[x_1,x_2,...,x_n]$

$\overrightarrow{n}=[n_1,n_2,...,n_n]$

$\overrightarrow{k}=[k_1,k_2,...,k_n]$

$N=N_1,N_2,...,N_n$,

$0\le k_i<N_i$

$F_{\overrightarrow{x}}(\overrightarrow{k})=\sum _{n1=0}^{N_1-1}...\sum _{n_n=0}^{N_n-1}{f}_{\overrightarrow{x}}(n_1,n_2...,n_n)exp(-2\pi j(\frac{n_1{k}_1}{N_1}+...+\frac{n_n{k}_n}{N_n})).$

$f_{\overrightarrow{x}}(\overrightarrow{n})=\frac{1}{N_1...N_n}\sum _{k_1=0}^{N_1-1}...\sum _{k_n=0}^{N_n-1}exp(2\pi j(\sum _{i=1}^n(n_i{k}_i/N_i)))$

2D Convolution Animation(by Michael Plotke)

Image Filtering and Edge Detection

Z-transform

The Z-transform converts a discrete-time signal, which is a sequence of real or complex numbers, into a complex frequency-domain (the z-domain or z-plane) representation.

Bilateral Z-transform

$X(z)=\sum _{n=-\mathrm{\infty }}^{\mathrm{\infty }}{x}_n{z}^{-n}$

Unilateral Z-transform

$X(z)=\sum _{n=0}^{\mathrm{\infty }}{x}_n{z}^{-n}$

inverse Z-transform

where

$C$ is a counterclockwise closed path encircling the origin and entirely in the region of convergence (ROC).

In control theory, a causal system (also known as a physical or nonanticipative system) is a system where the output depends on past and current inputs but not future inputs—i.e., the output

$y(t_0)$ depends only on the i[nput

$x(t)$ for values

$t\le t_0$.

Cauchy's integral formula

Image Analysis by Andrew Zisserman

---

Vector Integral Calculus

---

Q:
Assume input signal is

$f(t),t\in [0,T]$ and

$f(t)\in L^2[0,T]$, find a LTI filter to maximize SNR in

$[0,T]$ after the signal to the recever over a AWGN channel. Please see books, wiki or 通訊實驗matched filter結報…

A: matched filter.
Idea:

$<f+n,g>$ if

$g(t)=f(T-t)$, where

$n$ is a white noice. (Amplication is not good, because the noice for LTI system.)

$l^2[0,N-1]$ is also the same result.

---

這是數位通訊 的 基本原理 例如 QAM 等, 原來 你學的乘法器,積分器 是在進行 inner product, 所以很多研究所 入學考試 有 線性代數 ~因為重要

$e_i$ 已知, 只要 傳送

$a_i$ 接收端 能收到

$a_i$, 可還原

$f$

---

SNR (Signal-to-noise ratio) Why?

Parseval's Theorem for Hilbert space (e.g.,

$L^2,l^2$)

Define Fourier Transform of a real function g(x) as

$S(f)\doteq (\mathrm{\Phi }\circ g)(f)\doteq \int g(\xi )e^{-2\pi jf\xi }d\xi$, where

$f$ means frequency (not angular fequency).

Fourier inversion integral:

$g(t)=\int S(f)e^{2\pi jft}df$

F: frequency domain
T: time domain

Then we have

$||S(f)|{|}_{F^2}=||g|{|}_{T^2}$

and

$<g_1,g_2{>}_T=<\mathrm{\Phi }\circ g_1,\mathrm{\Phi }\circ g_2{>}_F=\int S_1(f)\overline{S_2(f)}df$.

$\mathrm{\Phi }:L_T^2\to L_F^2$ is a unitary operator.

${\mathrm{\Phi }}^{-1}={\mathrm{\Phi }}^{\ast }$, since let

$f_i=\mathrm{\Phi }(g_i)$,

$<g_1,{\mathrm{\Phi }}^{-1}(f_2){>}_T=<\mathrm{\Phi }(g_1),f_2{>}_F$.

Time scaling

Let

$a\in R,a\ne 0$, if

$h(x)=g(ax)$, then

$\mathrm{\Phi }\circ h(f)=\frac{1}{|a|}(\mathrm{\Phi }\circ g)(\frac{f}{a})$

Differentiation

$\mathrm{\Phi }(f^{{}^{\prime }})=2\pi jf\mathrm{\Phi }(f)$

$\mathrm{\Phi }(f^{(n)})=(2\pi jf{)}^n\mathrm{\Phi }(f)$

multi-dimensional Fourier Transform

$S(\overrightarrow{f})=(\mathrm{\Phi }\circ g)(\overrightarrow{f})\doteq \int g(\overrightarrow{\xi })e^{-2\pi j\overrightarrow{f}\cdot \overrightarrow{\xi }}d\overrightarrow{\xi }$

Fourier inversion integral:

$g(\overrightarrow{x})=\int S(\overrightarrow{f})e^{2\pi j\overrightarrow{f}\cdot \overrightarrow{x}}d\overrightarrow{f}$,

where

$\overrightarrow{a}\cdot \overrightarrow{b}=a_1{b}_1+a_2{b}_2+...a_n{b}_n$

Plancherel theory
The Fourier transform on very nice functions

$G(R^n)$ is an

$L^2$-isometry: more precisely, for any

$f,g\in G(R^n)$, we have

$<f,g>=<S(f),\overline{S(g)}>$

conservation of energy

Parseval's Theorem states that the total energy computed in the time domain must equal the total energy computed in the frequency domain. It is a statement of conservation of energy.

Parseval’s Theorem

matched filter, SNR, AWGN channel

Assume

$X(t)$ is a zero meam wide-sense stationary(WSS) random process. The auto-correlation function is given by

$R_{XX}(\tau )=R_{XX}(t_1-t_2)=E[X(t_1)X(t_2)]$.

Let

$P_X(f)=\mathrm{\Phi }(R_{XX})(f)$,

$P_X(f)$ is the power spectral density of

$X(t)$.

Let

$Y(t)$ is the output random process and the input process of a LTI system is

$X(t)$, which is a WSS random process, then

$Y(t)$ is also a WSS random process.

Principal Component Analysis (PCA) 主成分分析

Karhunen–Loève theorem(Karhunen-Loève Expansion)

$X(t)$ is a

$L^2$ random process.

$X(t)\in L^2(\mathrm{\Omega },F,P)$,

$E[X(t)]=0$, covariance function

$K_X(s,t)=E[X(s)X(t)]$,

$s,t\in [a,b]$. Let

$T_{K_X}:f\to T_{K_X}f={\int }_a^b{K}_X(s,.)f(s)ds$ be a linear operator

$L^2[a,b]\to L^2[a,b]$.
Since

$T_{K_X}$ is a linear operator, it makes sense to talk about its eigenvalues

${\lambda }_k$ and eigenfunctions

$e_k$, which are found solving the homogeneous Fredholm integral equation of the second kind

${\int }_a^b{K}_X(s,t)e_k(s)ds={\lambda }_k{e}_k(t)$

The covariance function

$K_X$ satisfies the definition of a Mercer kernel.
An important special case

1. $K_X(s,t)=K_X(t,s)$ symmetric continuous function
2. $K_X$ is said to be positive-definite if and only if
   $\sum \sum K(x_i,x_j)c_i{c}_j>0$ or all finite sequences of points
   $x_1,...,x_n$ of
   $[a,b]$ and all choices of real numbers
   $c_1,...,c_n$.

Remark. A

$N\times N$ symmetric real matrix

$A$ is said to be positive-definite if

$x^{T}Ax>0$ for all

$x\in R^N\ne 0$. Assume

$Ax=\lambda x$, then

$x^T\lambda x>0$, we have

$\lambda >0$.

e.g.,

$I=\left|\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right|$ is positive definite.

eigenvalue's geometric multiplicity

The geometric multiplicity of an eigenvalue is the dimension of the linear space of its associated eigenvectors (i.e., its eigenspace).

The dimension of the eigenspace

$E$ associated with

$\lambda$, or equivalently the maximum number of linearly independent eigenvectors associated with

$\lambda$, is referred to as the eigenvalue's geometric multiplicity

${\gamma }_A(\lambda )$. Because E is also the nullspace of

$(A-\lambda I)$, the geometric multiplicity of

$\lambda$ is the dimension of the nullspace of

$(A-\lambda I)$, also called the nullity of

$(A-\lambda I)$, which relates to the dimension and rank of

$(A-\lambda I)$ as

${\gamma }_A(\lambda )=n-rank(A-\lambda I)$

By Mercer's theorem(對EE 太難), there consequently exists a set

${\lambda }_k,e_k(t)$ of eigenvalues and eigenfunctions of

$T_{K_X}$ forming an orthonormal basis of

$L^2([a,b])$, and

$K_X$ can be expressed as

1. $K_X(s,t)=\sum _{k=1}^{\mathrm{\infty }}{\lambda }_k{e}_k(s)e_k(t)$.

2. $X(t)=\sum _{k=1}^{\mathrm{\infty }}{Z}_k{e}_k(t)$ converge in
   $L^2$

3. $Z_k={\int }_a^{b}X(t)e_k(t)dt$. Furthermore,

4. $E[Z_k]=0$ and
   $E[Z_i{Z}_j]={\delta }_{ij}{\lambda }_j$

5. Sorting the eigenvalues in decreasing order

   ${\alpha }_1\ge {\alpha }_2,...,\ge {\alpha }_n\ge ...$, where
   ${\alpha }_i\in \{{\lambda }_1,...,{\lambda }_n,...\}$

Implementing a Principal Component Analysis (PCA) 主成分分析

Discrete Fourier Transform(DFT)

$u_k=e^{\frac{2j\pi }{N}kn}$,

$n=0,1,...N-1$ form an orthogonal basis over the set of N-dimensional complex vectors.

$\overrightarrow{x}=[x_0,x_1,...x_{N-1}{]}^T$,

$\overrightarrow{u}=[u_0,u_1,...u_{N-1}{]}^T$

$X_k=<\overrightarrow{x},\overrightarrow{u}>={\overrightarrow{x}}^T{\overrightarrow{u}}^{\ast }$ is the DFT of

$\overrightarrow{x}$.

---

$\mathrm{\nabla }f(\overrightarrow{x})$ and mathematical optimization

Proof.
Assume

$\overrightarrow{x}\in R^n$, a hyperplane with a normal vector

$\overrightarrow{n}$ at

$\overrightarrow{n_0}$ is given by

$<\overrightarrow{x}-\overrightarrow{n_0},\overrightarrow{n}>=0$.

Hence

$<\overrightarrow{x}-\overrightarrow{n_0},\mathrm{\nabla }f(\overrightarrow{x})>=0$ defines a tanget plane.

$\mathrm{\nabla }f(\overrightarrow{x})$ is perpendicular to the level curve

$f(\overrightarrow{x})=c$ at

$\overrightarrow{n_0}$.
Q.E.D.

您可能要先假設存在性(困難的部分), 方法是對的 (wiki 寫的不一定是對的, 還有最好看英文的)
Lagrange multiplier

$\overrightarrow{x}=[x_1,x_2,...,x_n],\overrightarrow{\lambda }=[{\lambda }_1,...,{\lambda }_m],g_i(\overrightarrow{x})=0,i=1,...,m,\overrightarrow{g}(\overrightarrow{x})=[g_1,...,g_m]$. Find the local maxima and minima of

$f(\overrightarrow{x})$ via

Let

$L(\overrightarrow{x},\overrightarrow{\lambda })=f(\overrightarrow{x})-<\overrightarrow{\lambda },\overrightarrow{g}(\overrightarrow{x})>$

${▽}_{\overrightarrow{x},\overrightarrow{\lambda }}L(\overrightarrow{x},\overrightarrow{\lambda })=0$.

${\lambda }_1,...,{\lambda }_m$ Lagrange multiplier

Lagrange Multipliers~examples

Karush–Kuhn–Tucker conditions

---

Taylor series with remainder

The Taylor polynomials for

$ln(1+x)$ only provide accurate approximations in the range

$-1<x\le 1$. For

$x>1$, Taylor polynomials of higher degree provide worse approximations.

$f(x)=f(a)+f^{{}^{\prime }}(a)(x-a)+f^{{}^{″}}(x-a{)}^2/2!+R(h)$, where

$li{m}_{h\to 0}R(h)=0$.

$f:R^n\to R$, if there exists a linear functional

$L:R^n\to R$ and

$h:R^n\to R$ such that

$f(x)=f(a)+L(x-a)+h(x)||x-a||$, where

$\underset{x\to a}{lim}h(x)=0$ and

$L=df(a)$.

$df(a)(v)=\sum _{i=1}^n\frac{\partial f}{\partial x_i}{v}_i=<\mathrm{\nabla }f,v>$.

A linear functional on a real vector space

$V$ is a function

$T:V->R$, which satisfies the following properties

1. $T(v+w)=T(v)+T(w)$, and
2. $T(\alpha v)=\alpha T(v)$.

Taylor Polynomials of Functions of Two Variables

這本好書只適合 數學好的資電人士 (博士班以上)
Gâteaux derivative:
Optimization by Vector Space Methods: Luenberger, David G.

---

Affine transformation 仿射轉換,

$y=Ax+b$

Gateaux derivative
Optimization by Vector Space Methods: Luenberger, David G.

An affine transformation preserves:

1. collinearity between points: three or more points which lie on the same line (called collinear points) continue to be collinear after the transformation.

2. parallelism: two or more lines which are parallel, continue to be parallel after the transformation.

3. convexity of sets: a convex set continues to be convex after the transformation. Moreover, the extreme points of the original set are mapped to the extreme points of the transformed set.

4. ratios of lengths of parallel line segments

5. barycenters (center of mass) of weighted collections of points

比較好的書是 (會用到 functional analysis):
Optimization by Vector Space Methods, David G. Luenberger

The Laplacian of

$f$:

$\mathrm{\Delta }f=\sum _i\frac{{\partial }^2}{{\partial }^2{x}_i}f$. The Laplacian is invariant under all Euclidean transformations: rotations and translations.

邊緣偵測 - 拉普拉斯算子 ( Laplacian Operator )

OpenCV 基礎篇-邊緣檢測(edge detection)

---

Statistical Inference, detection and estimation

Linear regression(線性迴歸)

---

Least-Squeres Estimate and Projection Theorem

$y$ is am

$m$ vector and

$W=[w_1,w_2,...,w_n]$

$mxn$ matrix with linearly independent columns

$(m\ge n)$. Then there is a unique

$n$ vector

$\hat{\beta }$ which minimize

$||y-W\beta ||$ over all

$\beta$ and the estimator

$\hat{\beta }=(W^{T}W{)}^{-1}{W}^{T}y$ if the inverse matrix exists.

Proof.

By projection theorem and

$\{w_1,w_2,...w_n\}$ is linearly independent,

$z=\hat{p}y$ is the projection onto the span of

$\{w_1,w_2,...w_n\}$, where

$\hat{p}$ projection operator. Let

$y=x+z$, then

$<w_i,y>=<w_i,z>$,

$i=1,2,...,n$.
Hence

$W^{T}z=W^{T}y=W{W}^T\hat{\beta }$. If

$(W^{T}W{)}^{-1}$ exists, then

$\hat{\beta }=(W^{T}W{)}^{-1}{W}^{T}y$.

Gauss-Markov estimate
An

$n\times n$ symmetric real matrix

$M$ is said to be positive-definite if

$x^{T}Mx>0$ for all non-zero

$x$ in

$R^n$.

$ϵ$ is a r.v., e.g.,

$ϵ$~

$N(0,{\sigma }^2)$

$y=W\beta +ϵ$,

$E[ϵ]=0$ and

$Q=E[ϵ{ϵ}^T]$. Assume

$Q$ is positive definite.

Proof.

$<x,y{>}_Q:=x^{T}Qy=<x,Qy>$. Then

$<x,y{>}_Q$ is an inner product.
Hence we can find the estimator

$\hat{\beta }$ by projection theorem.

A square matrix

$A$

$A$ is Hermitian if and only if it is equal to its adjoint, that is, it satisfies

$<Ax,y>=<x,Ay>$, i.e.,

$A=A^H$,

$x,y\in C^n$.
e.g., Covariance (共變異數, 又稱協方差) matrix

$A$ square matrix

$A$ is Hermitian if and only if it is unitarily diagonalizable with real eigenvalues.

A matrix

$Q$ is positive-definite iff

$Q$ is symmetric or Hermitian, and all its eigenvalues are real and positive.
HW. Why?

The estimator is said to be unbiased if and only if

$E[\hat{\beta }]=E[\beta ]$

Kalman Filter (recursive estimation)
Probability space

$(\mathrm{\Omega },\mathcal{F},P)$
n-dimensional dynamic model of a random process on

$L^2(P)$

1. $x(k):\mathrm{\Omega }\to R^n,u(k):\mathrm{\Omega }\to R^n$,
   $x(k+1)=\mathrm{\Phi }(k)x(k)+u(k)$,
   $\mathrm{\Phi }(k)\sim n\times n$ matrix,
   $E[u(k)]=0$ and
   $E[u(k)u(l{)}^T]=Q(k){\delta }_{kl}$.
2. $\widehat{x(0)}$ initial estimate of the initial random vector
   $x(0)$
3. $P(0)=E[(\hat{x}(0)-x(0))(\hat{x}(0)-x(0){)}^T]$
4. Measurement of the process, assumed to be of the form
   $v(k)=M(k)x(k)+w(k)$, where
   $M(k)\sim m\times n$ matrix and
   $w(k)$ m-dimentsional measurement error having zero mean and
   $E[w(k)w(j{)}^T]=R(k){\delta }_{kj}$, where
   $R(k)$ positive definite.
5. $\hat{x}(k|j)$ the optimal estimate of
   $x(k)$ given the observation
   $v(0),v(1),...v(j)$. Let
   $V(j)=$ span
   $\{v(0),v(1),...,v(j)\}$
6. covariance matrix
   $P(k)=E[\hat{x}(k|k-1)-x[k]](\hat{x}(k|k-1)-x[k]{)}^T]$
7. Assume
   $u(k)$ is orthogonal to
   $v(k)$ and
   $x(k)$.
8. If
   $Y_1,Y_2\subseteq L^2(P)$, the projection of a vector
   $\beta$ onto
   $Y_1+Y_2=Y_1\oplus {\hat{Y}}_2$, where
   $\widehat{Y_2}$ is orthogonal to
   $Y_1$. Hence we can find the projection
   $\beta$ onto the subspace of
   $Y_1+Y_2$, denoted
   $\hat{\beta }$.
9. The optimal estimate of
   $\mathrm{\Phi }(k)x(k)$ is
   $\mathrm{\Phi }(k)\hat{x}(k|k)$, since
   $u(k)$ is orthogonal to
   $v(k)$ and
   $x(k)$.
10. Get the optimal estimate
    $\hat{x}(k+1)|k)$ of
    $x(k+1)=\mathrm{\Phi }(k)\hat{x}(k)+u(k)$, given the oservation
    $v(k)$.

Ref. Optimization by Vector Space Methods. David G. Luenberger

證明重點 就是 Projection Theorem 式子很長不想打字了

---

convex, concave 於優化時local minimum, local maximun 存在性 很重要 (注意 有些文章兩個 相反)

distribution function 有些左連續 有些右連續

concave function

---

convex function

convex set

non-convex set

Let f be a function of many variables defined on a convex set

$S$. Then

$f$ is convex if for all

$x\in S$, for all

$y\in S$ and all

$\alpha \in (0,1)$ we have

$f(\alpha x+(1-\alpha )y)\le \alpha f(x)+(1-\alpha )f(y)$

maximum likelihood test

likelihood: the chance that something will happen

In probability theory, odds provide a measure of the likelihood of a particular outcome, e.g.,

$odds=\frac{p}{1-p}$,

$p\in (0,1)$

$-ln(1-x)=x+\frac{x^2}{2}+\frac{x^3}{3}+...$ convex function on

$[0,1)$

$-ln(x)$ convex function on

$(0,1]$

log-convex
A function

$f(x):D\subset R^n\to R$ is log-convex if

$f(\theta x+(1-\theta )y)\le f(x{)}^{\theta }f(y{)}^{1-\theta }$, D is a convet set and

$0<\theta <1$, i.e.,

$logf(x)$ is convex on

$D$.

Key Point:

A function

$f$ of many variables defined on a convex set

$S$ is convex if and only if the set of points on or above its graph is convex:

$\{(x,y):x\in Sandy\ge f(x)\}$ is convex.

Jensen's inequality
A function

$f$ of many variables defined on a convex set

$S$ is convex if and only if for all

$n\ge 2$

$f({\lambda }_1{x}_1+...+{\lambda }_n{x}_n)\le {\lambda }_{1}f(x_1)+...+{\lambda }_{n}f(x_n)$ for all

$x_1\in S,...,x_n\in S$ and all

${\lambda }_1\ge 0,...,{\lambda }_n\ge 0$ with

$\sum {\lambda }_i=1$. Let

$y_i=f(x_i)$, then

$f(<\overrightarrow{\lambda },\overrightarrow{x}>)\le <\overrightarrow{\lambda },\overrightarrow{y}>$

3.3 Concave and convex functions of many variables

Bernoulli sampling

$B(k)=p^k(1-p{)}^{n-k}$

$f(k)=ln(B(k))=kln(p)+(n-k)ln(1-p)$

$p=0.1,n=100,f(k)$

$g(x)=x^k(1-x{)}^{n-k}$

$n=50,k=6,g(x)$

---

$S$ is a binary random variable with a-

$\mathbf{p}\mathbf{r}\mathbf{i}\mathbf{o}\mathbf{r}\mathbf{i}$ probabilities

$P(S=a_0)=p_0$ and

$P(S=a_1)=p_1$.
The receiver of a communication system receives a random variable

$S$ (maybe continuous random variable).

$\hat{S}$ denotes the estimator of

$S$.

The conditional densities

$f_{R|S}(R=r|a_i),i\in \{0,1\}$, are called

$\mathbf{l}\mathbf{i}\mathbf{k}\mathbf{e}\mathbf{l}\mathbf{i}\mathbf{h}\mathbf{o}\mathbf{o}\mathbf{d}\mathbf{s}$.

$f_R(r)=p_0{f}_{R|S}(r|a_0)+p_1{f}_{R|S}(r|a_1)$. The a-

$\mathbf{p}\mathbf{o}\mathbf{s}\mathbf{t}\mathbf{e}\mathbf{r}\mathbf{i}\mathbf{o}\mathbf{r}\mathbf{i}$ probability of

$S$ is given by

$p_{S|R}(a_i|r)=\frac{p_i{f}_{R|S}(r|a_i)}{f_R(r)}$ (Bayes' theorem).

Let

$\mathrm{\Lambda }(r)=\frac{f_{R|S}(r|a_0)}{f_{R|S}(r|a_1)}$ and threshold

$\eta =p_1/p_0$.

$\mathrm{\Lambda }(r)$ is called the

$\mathbf{l}\mathbf{i}\mathbf{k}\mathbf{e}\mathbf{l}\mathbf{i}\mathbf{h}\mathbf{o}\mathbf{o}\mathbf{d}$

$\mathbf{r}\mathbf{a}\mathbf{t}\mathbf{i}\mathbf{o}$.

$\hat{S}=a_0$ if

$\mathrm{\Lambda }(r)\ge \eta$.

$\hat{S}=a_1$ if

$\mathrm{\Lambda }(r)<\eta$.
This is called a

$\mathbf{m}\mathbf{a}\mathbf{x}\mathbf{i}\mathbf{m}\mathbf{u}\mathbf{m}\mathbf{l}\mathbf{i}\mathbf{k}\mathbf{e}\mathbf{l}\mathbf{i}\mathbf{h}\mathbf{o}\mathbf{o}\mathbf{d}\mathbf{t}\mathbf{e}\mathbf{s}\mathbf{t}$.

$\hat{S}$: maximum likelihood estimator

Probability of error

$P(e)$

$P(e|S=a_0)=P(\hat{S}=a_1|S=a_0)=P(\mathrm{\Lambda }(r)<\eta |S=a_0)$

$P(e|S=a_1)=P(\hat{S}=a_0|S=a_1)=P(\mathrm{\Lambda }(r)\ge \eta |S=a_1)$

Hence,

$P(e)=p_{0}P(\mathrm{\Lambda }(r)<\eta |S=a_0)+p_{1}P(\mathrm{\Lambda }(r)<\eta |S=a_1)$

實際上 要注意 Arithmetic Overflow

$\mathrm{\Lambda }(\lambda )$ is small,

$e.g.{10}^{-9}$

The log likelihood ratio,

$LLR(r)=ln(\mathrm{\Lambda }(r))$ is convenient for use with Gaussian noise with

$Z=N(0,N_0/2)$.

$V=S+Z$,

$f_{V|S}(v|a_0)=\frac{1}{\sqrt{(\pi N_0)}}exp(\frac{-(v-a_0{)}^2}{N_0})$

$\mathrm{\Lambda }(v)=exp(\frac{-(v-a_0{)}^2+(v-a_1{)}^2}{N_0})$
Hence,

$LLR(v)=\frac{(v-a_1{)}^2-(v-a_0{)}^2}{N_0}=\frac{||v-a_1|{|}^2-||v-a_0|{|}^2}{N_0}=\frac{2v{a}_0-2v{a}_1+a_1^2-a_0^2}{N_0}$

$R^N$ space
e.g.,

$\overrightarrow{S}=[S_0,S_1,...S_{N-1}]$ and

$\overrightarrow{R}=[R_0,R_1,...R_{N-1}]$. Assume

$\overrightarrow{(}R)=\overrightarrow{S}+\overrightarrow{Z}$, where

$\overrightarrow{Z}=[Z_0,Z_1,...,Z_{N-1}]$.

$Z_i$ iid random sequence with

$N(0,{\sigma }^2)$ distribution.

MAP (Maximum A Posterior Estimation)

$argma{x}_{x\in S}f(x)\doteq \{x\in S:f(s)\le f(x)foralls\in S\}$

e.g.,

$argma{x}_{x\in R}(1-|x|)=\{0\}$, i.e., at

$x=0$

Assume

$X_1,X_2,...,X_n$ IID,

${\hat{\theta }}_{MAP}=argma{x}_{\theta }f(\theta |X_1,X_2,...,X_n)=argma{x}_{\theta }f(X_1,X_2,...,X_n|\theta )g(\theta )/h(X_1,X_2,...,X_n)$

$=argma{x}_{\theta }\prod f(X_i|\theta )g(\theta )$, since IID.

Ref. Principles of Digital Communication, by Robert G. Gallager

---

Sufficient statistic 充分統計量
A statistic is a function

$T=f(X_1,X_2,···,X_n)$ of the random sample

$X_1,X_2,···,X_n$.

In statistics, a statistic is sufficient with respect to a statistical model and its associated unknown parameter if "no other statistic that can be calculated from the same sample provides any additional information as to the value of the parameter"

Roughly, given a set

$X$ of independent identically distributed data conditioned on an unknown parameter

$\theta$ , a sufficient statistic is a function

$T(X)$ whose value contains all the information needed to compute any estimate of the parameter (e.g., a maximum likelihood estimate).

A statistic

$t=T(X)$ is sufficient for underlying parameter θ precisely if the conditional probability distribution of the data

$X$, given the statistic

$t=T(X)$, does not depend on the parameter

$\theta$.

e.g., sample mean

$\hat{\mu }=T(\overrightarrow{X};\mu )=\frac{\sum _{i=1}^N{X}_i}{N}$

Suppose we have a statistical model, parameterized by a real number

$\theta$, giving rise to a probability distribution for observed data,

$P_{\theta }(x)=P(x\mid \theta )$, and a statistic

$\hat{\theta }$ which serves as an estimator of

$\theta$ based on any observed data

$x$.

where

$E_{x\mid \theta }[.]$ denotes expected value over the distribution

$P(x\mid \theta )$. An estimator is said to be unbiased if its bias is equal to zero for all values of parameter

$\theta$.

e.g.,
sample mean

$\hat{\mu }$: unbiased estimator.
sample variance I

$S^2=\frac{1}{N}\sum _{i=1}^N(X_i-\hat{\mu }{)}^2$: biased estimator, since

$E[S^2]=(1-\frac{1}{N}){\sigma }^2<{\sigma }^2$
sample variance II

$V^2=\frac{1}{N-1}\sum _{i=1}^N(X_i-\hat{\mu }{)}^2$ unbiased estimator.
statistic

$T_{max}=max\{X_1,...,X_N\}$
HW. Find

$E[T_{max}]$, if

$X_i$ iid and

$uinform(0,\theta )$.
A:

$\frac{N}{N+1}\theta$

Hint:

$\{\omega \in \mathrm{\Omega }|T_{max}(\omega )\le x\}$ if and only

$\{\omega \in \mathrm{\Omega }|X_i(\omega )\le x,foralli=1,...,N\}$

statistic

$T_{min}=min\{X_1,...,X_N\}$

Nonparametric statistics(無母數統計)

Nonparametric statistics is a type of statistical analysis that does not rely on the assumption of a specific underlying distribution (such as the normal distribution), or any other specific assumptions about the population parameters (such as mean and variance).

Fisher–Neyman factorization theorem

If the probability density function is

${ƒ}_{\theta }(x)$, then

$T$ is sufficient for

$\theta$ if and only if nonnegative functions

$g$ and

$h$ can be found such that

$f_{\theta }(x)=h(x)g_{\theta }(T(x))$ i.e. the density

$ƒ$ can be factored into a product such that one factor,

$h$, does not depend on

$\theta$ and the other factor, which does depend on

$\theta$, depends on

$x$ only through

$T(x)$.

e.g.,

$f(x_1,x_2,...,x_n;\lambda )=f(x_1;\lambda )...f(x_n;\lambda )$

Statistical Hypothesis Testing(統計假說檢定)

(a) A statistical hypothesis.
(b) A test of a hypothesis against an alternative hypothesis and the associated concept of the critical region of the test.
© The power of a test.

Definition 1. Let C be that subset of the sample space which, in accordance with a prescribed test, leads to the rejection of the hypothesis under consideration. Then C is called the critical region of the test.

Definition 2. The power function of a test of a statistical hypothesis

$H_0$ against an alternative hypothesis

$H_1$ is that function, defined for all distributions under consideration, which yields the probability that the sample point falls in the critical region

$C$ of the test, that is, a function that yields the probability of rejecting the hypothesis under consideration. The value of the power function at a parameter point is called the power of the test at that point.

Definition 3. Let

$H_0$ denote a hypothesis that is to be tested against an alternative hypothesis

$H_1$ in accordance with a prescribed test. The significance level of the test (or the size of the critical region C) is the maximum value (actually supremum) of the power function of the test when

$H_0$ is true.

Type II error (false negative, 偽陰性): the test result says you don’t have coronavirus, but you actually do.

偽陽性(明明沒確診卻誤判為有)和偽陰性(明明確診卻誤判為沒有)
（英語：False positives and false negatives）
type I error , type II error

Neyman-Pearson Theorem
Let

$\overrightarrow{X}=X_1,X_2...,X_n$ denote a random sample from a distribution with density function

$f(x;\theta )$. Then the joint p.d.f. of

$\overrightarrow{X}=X_1,X_2...,X_n$ is

$L(\overrightarrow{x};\theta )=f(x_1;\theta )....f(x_n;\theta )$. Let

$k>0$,

$\mathrm{\Omega }=\{\theta :\theta ={\theta }_1,{\theta }_2\}$. Let

$C$ be a subset of the sample space such that:

1. $\mathrm{\Lambda }(\overrightarrow{x};{\theta }_1,{\theta }_2)=\frac{L(\overrightarrow{x};{\theta }_1)}{L(\overrightarrow{x};{\theta }_2)}\le k$,
   $\overrightarrow{x}\in C$
2. $\frac{L(\overrightarrow{x};{\theta }_1)}{L(\overrightarrow{x};{\theta }_2)}\ge k$,
   $\overrightarrow{x}\in C^{\ast }$
3. power function 檢定力:
   $\alpha =P(\overrightarrow{X}\in C;H_0)$ ( the probability of falsely rejecting the
   $H_0$ hypothesis is
   $\alpha$, type I error, False positives, 偽陽性)
4. level of significance (significant level)
   $\alpha$ (顯著水平(顯著水準))

Then

$C$ is the best critical region of size

$\alpha$ for the simple hypothesis

$H_0:\theta ={\theta }_0$ against the

$H_1:\theta ={\theta }_1$

Example

$f(x;\theta )=\frac{1}{2\pi }exp(-(x-\theta {)}^2/2)$

$H_0:\theta ={\theta }_0=0$

$H_1:\theta ={\theta }_1=1$

$\mathrm{\Lambda }(\overrightarrow{x};0,1)=exp(-\sum x_i+2/n)$
If

$k>0$, then

$\sum x_i\ge n/2-lnk=c$
The ciritical region

$C=\{\overrightarrow{x}:\sum x_i\ge c\}$

Assume

$n$ samples,

$c_1=c/n$,

$\overline{X}=\sum _{i=1}^n{X}_i/n$ and

$\overline{X}$~

$n(0,1/n)$.

$P(\overline{X}\ge c_1;H_0)=\alpha$ (type I error), hence given

$\alpha$, one can find

$c_1$ and find the probabilty

$P(\overline{X}\ge c_1;H_1)=\frac{1}{\sqrt{2\pi 1/n}}$

${\int }_{c_1}exp(-(\overline{x}-1{)}^2/(2\times 1/n))$

1. density function
2. $H_0$
   $H_1$
3. level of significance
   $\alpha$ (顯著水準)
4. Type I error, Type II error
5. sample size

If

$n=25,\alpha =0.05$, then

$c_1$~

$0.329$,

$k$~

$exp(n/2-c_1)$ and the power of of the best test of

$H_0$ again

$H_1$ is 0.05 when

$H_0$ is true.

$P(\overline{X}\ge c_1;H_1)$~

$0.999$ when

$H_1$ is true.

Type II error:

$\beta =P(FailtoReject{H}_0|H_{0}isFalse)=1-P(\overline{X}\ge c_1;H_1)$

---

Proof.
If there is another critical region

$A$ of size

$\alpha$, then

claim

${\int }_{C}L({\theta }_2)-{\int }_{A}L({\theta }_2)\ge 0$

${\int }_{C}L({\theta }_2)-{\int }_{A}L({\theta }_2)$

$={\int }_{C\bigcap A}L({\theta }_2)+{\int }_{C\bigcap A^{\ast }}L({\theta }_2)-{\int }_{A\bigcap C}L({\theta }_2)-{\int }_{A\bigcap C^{\ast }}L({\theta }_2)$

$={\int }_{C\bigcap A^{\ast }}L({\theta }_2)-{\int }_{A\bigcap C^{\ast }}L({\theta }_2)$

Since

$L({\theta }_2)\ge \frac{1}{k}L({\theta }_1)$ at each point of

$C$ and

$L({\theta }_2)\le \frac{1}{k}L({\theta }_1)$ at each point of

$C^{\ast }$, then

${\int }_{C\bigcap A^{\ast }}L({\theta }_2)-{\int }_{A\bigcap C^{\ast }}L({\theta }_2)\ge \frac{1}{k}({\int }_{C\bigcap A^{\ast }}L({\theta }_{!})-{\int }_{A\bigcap C^{\ast }}L({\theta }_1))$

$=\frac{1}{k}({\int }_{C\bigcap A^{\ast }}L({\theta }_1)-{\int }_{C\bigcap A}L({\theta }_1)+{\int }_{C\bigcap A}L({\theta }_1)+{\int }_{A\bigcap C^{\ast }}L({\theta }_1))$

$=\frac{1}{k}({\int }_{C}L({\theta }_1)-{\int }_{A}L({\theta }_1))=0$. Hence

${\int }_{C}L({\theta }_2)-{\int }_{A}L({\theta }_2)\ge 0$

If the random variables are of the discrete type, the proof is the same, with integration replaced by summation.

Type I & Type II Errors | Differences, Examples, Visualizations

Neyman-Pearson Lemma: Definition

Introduction to Mathematical Statistics

Neyman–Pearson lemma

A First Course on Statistical Inference

Confidence interval(信賴區間)
Confidence Intervals
Understanding the Confusion Matrix (II)

Ref. Introduction to Mathematical Statistics, R. V. Hogg and A. T. Craig

---

Successive Approximation

Taylor's formula with remainder

TAYLOR’S THEOREM WITH REMAINDER

---

以前下課時間 很喜歡 問學生一問題 events A, B probability independent

$P(AB)=P(A)P(B)$. Why?

通常得到 有些說 定義, 很多茫茫然的眼神~

---

A:

$n$ 實驗次數

$n_A$ 發生 event

$A$ 的次數,

$n_B$ 發生 event

$B$ 的次數

$n_{AB}$ 發生

$A\cap B$ 的次數

$\frac{n_A}{n}\sim P(A)$

$\frac{n_B}{n}\sim P(B)$

$\frac{n_{A\cap B}}{n}\sim P(A\cap B)$,

如果 event

$B$ 的發生與否 不會 影響 對 event

$A$ 的統計, i.e.,

$\frac{n_{A\cap B}}{n_B}\sim P(A)$, when

$n_B\to \mathrm{\infty }$ (i.e., P(A|B)=P(A) conditional probability)

$n_{A\cap B}\sim \frac{n_B}{n}\frac{n_A}{n}$, as

$n_A,n_B,n\to \mathrm{\infty }$

Hence,

$P(AB)=P(A)P(B)$ events A, B probability independent

Probability measure by CrazyDog

---

還有 微積分 最重要的定理是什麼? Why?茫茫然…
A:
微積分基本定理（Fundamental theorem of calculus）

orthonormal basis 用在除了線性代數外你們哪門 課? 茫茫然…

$B$ is a orthonormal basis of

$H$ (

$L^2$ or

$l^2$) space, then

$\mathrm{\forall }\overrightarrow{x}\in H$,

$\overrightarrow{x}=\sum _{\overrightarrow{e}\in B}<\overrightarrow{x},\overrightarrow{e}>\overrightarrow{e}$.

Simulation:

Assumme

$X$ is a random variable,

$F_X(x)=P(X\le x)$.
Let (generalized inverse function)

$F_X^{-1}(u)=\underset{x}{inf}\{x|F_X(x)\ge u\}$, where

$0<u<1$.

Assume

$U$ is a uniform random variable on

$[0,1]$.
Then

$P(F^{-1}(U)\le x)=P(U\le x)=F_U(x)$.

e.g.,

$X$ exponential distribution,

$F_X(x)=1-e^{\lambda x}$.

$F_X^{-1}(u)=-ln(1-u)/\lambda$

Inverse transform sampling

---

Successive Approximation, Newton's Method, Fixed Point Theorem

Successive Approximation 重要的是 選擇 的初始值 能否 收斂 到 "正確解" 與 收斂 的效率

Definition. A sequence ${x_i } in a normed space is said to be a Cauchy sequence if

$||x_n-x_m||\to 0$ as

$n,m\to \mathrm{\infty }$.

Remark. If

$x_n\to x$, then

$||x_n-x_m||\le ||x_n-x||+||x-x_m||\to 0$.

Definition. A normed linear vector space

$X$ is complete if every Cauchy sequence from

$X$ has a limit in

$X$. A complete normed linear vector space is called a Banana space.

Remark. Hilbert space is complete.

contraction mapping

$X$ is a normed space,

$S\subseteq X,T:S\to S$. Then

$T$ is a contraction mapping if there exists

$\alpha \in [0,1)$ such that

$||T(x_1)-T(x_2)||\le \alpha ||x_1-x_2||$ for all

$x_1,x_2\in S$.

Contraction Mapping Theorem

$X$ is a Hilbert (or Banach) space,

$S\subseteq X$ and

$S$ is a closed set of

$X$. There is a unique

$x_0\in S$ satisfying

$x_0=T(x_0)$. Furthermore,

$x_0$ can be obtained by the method of Successive Approximation starting from an arbitary initial point in

$S$.

Proof. Select an arbitrary element

$x_1\in X$.
Let

$x_{n+1}=T(x_n)$, then

$||x_{n+1}-x_n||=||T(x_n)-T(x_{n-1})||\le \alpha ||x_n-x_{n-1}||$. Therefor,

$||x_{n+1}-x_n||\le {\alpha }^{n-1}||x_2-x_1||$. Then

$||x_{n+p}-x_n||\le ||x_{n+p}-x_{n+p-1}||+...+||x_{n+1}-x_n||$
Hence

$||x_{n+p}-x_n||\le \frac{{\alpha }^{n-1}}{1-\alpha }||x_2-x_1||$.

$\{x_n\}$ is a Cauchy sequence. Since

$S$ is closed and

$X$ is complete, there exists a

$x_0\in S$ such that

$x_n\to x_0$.

Claim

$x_0=T(x_0)$
Proof.

$||x_0-T(x_0)||=||x_0-x_n+x_n-T(x_0)||\le ||x_0-x_n||+||x_n-T(x_0)||\le ||x_0-x_n||+\alpha ||x_{n-1}-x_0||$. By appropriate choice of

$n$, the above inequality can be made arbitrarily small. Thus

$||x_0-T(x_0)||=0$;

$x_0=T(x_0)$.

Claim

$x_0$ is unique.
Proof.
Assume

$x_0$ and

$y_0$ are fixed points. Then

$||x_0-y_0||=||T(x_0)-T(y_0)||\le \alpha ||x_0-y_0||$. Thus

$x_0=y_0$.

Newton's Method

$x_{n+1}$ is a better approximation than

$x_n$ for the root

$x$ of the function

$f$ (blue curve)

wiki

Iteration typically improves the approximation
wiki

Solving an equation of the form

$P(x)=0$.

$x_{n+1}=x_n-\frac{P(x_n)}{P^{\prime }(x_n)}$

Let

$T(x)=x-[P^{\prime }(x){]}^{-1}P(x)$. A fixed point of

$T$ is the solution of

$P(x)=0$.

至於 擴充至 Hilbert (Banana) space, 對 EE 太難

---

Exterior algebra

Let

$V$ be a vector space over a field

$K$.
Let

$e_1,...,e_n$ be a basis of the vector space

$V$. Definition. The exterior algebra

$\mathrm{\Lambda }V$ is the vector space with basis formal symbols

$e_{i1}\mathrm{\Lambda }...\mathrm{\Lambda }{e}_{ia}$
where a ≥ 0 and

$i1<...<ia$ is a strictly increasing sequence. The exterior product is

$(e_{i1}\mathrm{\Lambda }...\mathrm{\Lambda }{e}_{ia})\mathrm{\Lambda }(e_{j1}\mathrm{\Lambda }...\mathrm{\Lambda }{e}_{jb})=(0or\pm e_{k1}\mathrm{\Lambda }...\mathrm{\Lambda }{e}_{ka+b})$
where in the first case the sequences

$i$ and

$j$ have an element in common.

$\mathrm{\Lambda }$ is called exterior product (or wedge product).

e.g.,

$\mathrm{\Lambda }{R}^3=K\oplus R\oplus {\mathrm{\Lambda }}^{2}R\oplus {\mathrm{\Lambda }}^{3}R$

The cross product (blue vector) in relation to the exterior product (light blue parallelogram). The length of the cross product is to the length of the parallel unit vector (red) as the size of the exterior product is to the size of the reference parallelogram (light red).

The Cartesian plane

$R^2$ is a real vector space equipped with a basis consisting of a pair of unit vectors

$e_x,e_y$.

$u,v,w$ vectors,

$\alpha ,s$ real numbers.

$v\mathrm{\Lambda }v=0$

$v\mathrm{\Lambda }u=-u\mathrm{\Lambda }v$

$(u+v)\mathrm{\Lambda }w=u\mathrm{\Lambda }w+u\mathrm{\Lambda }w$

$\alpha v\mathrm{\Lambda }su=\alpha s(v\mathrm{\Lambda }u)$

$v=a{e}_x+b{e}_y$,

$w=c{e}_x+d{e}_y$,

$v\mathrm{\Lambda }w=ac{e}_x\mathrm{\Lambda }{e}_x+bc{e}_y\mathrm{\Lambda }{e}_x+ad{e}_x\mathrm{\Lambda }{e}_y+bd{e}_y\mathrm{\Lambda }{e}_y=-bc{e}_x\mathrm{\Lambda }{e}_y+ad{e}_x\mathrm{\Lambda }{e}_y=$

$\left|\begin{array}{cc}a& b\\ c& d\end{array}\right|e_x\mathrm{\Lambda }{e}_y$.

平行四邊形 面積 =| ad-bc |

Such an area is called the signed area of the parallelogram.

Let

$u=u_1{e}_1+u_2{e}_2+u_3{e}_3,v=v_1{e}_1+v_2{e}_2+v_3{e}_3$ then

$u\mathrm{\Lambda }v=(u_1{v}_2-u_2{v}_1)e_1\mathrm{\Lambda }{e}_2+(u_2{v}_3-v_3{u}_2)e_2\mathrm{\Lambda }{e}_3+(u_3{v}_1-u_1{v}_3)e_3\mathrm{\Lambda }{e}_1$. Let

$w=w_1{e}_1+w_2{e}_2+w_3{e}_3$,

Determinant

$det=\left|\begin{array}{ccc}{u}_1& u_2& u_3\\ v_1& v_2& v_3\\ w_1& w_2& w_3\end{array}\right|$

$u\mathrm{\Lambda }v\mathrm{\Lambda }w=det{e}_1\mathrm{\Lambda }{e}_2\mathrm{\Lambda }{e}_3$

平行六面體的體積= | det |

$u_i\in R^n$ vectors,

$u_i=\sum a_{ij}{e}_j$.

$u_1\mathrm{\Lambda }{u}_2...\mathrm{\Lambda }{u}_n=\left|\begin{array}{ccc}{a}_{11}& a_{12}& ...\\ a_{21}& ...\\ ...\\ a_{n1}& ...\end{array}\right|e_1\mathrm{\Lambda }{e}_2...\mathrm{\Lambda }{e}_n$

oriented volume of

$u_i,i=1,2,...n$=

$$\left|\begin{array}{ccc}{a}_{11}& a_{12}& ...\\ a_{21}& ...\\ ...\\ a_{n1}& ...\end{array}\right|$$

Let

$R^n$ be an n-dimentional real vector space.

A form of degree 1 (or a 1-form) is a linear function

$\omega :R^n\to R$, i.e.,

$\omega ({\lambda }_1{\eta }_1+{\lambda }_2{\eta }_2)={\lambda }_1\omega ({\eta }_1)+{\lambda }_2\omega ({\eta }_2)$, where

${\lambda }_i\in R$ and

${\eta }_i\in R^n$.

2 form is a function on pairs of vectors

${\omega }^2:R^n\times R^n\to R$, which is bilinear and skew symmetric.

e.g., oriented area

$S({\eta }_1,{\eta }_2)=\left|\begin{array}{cc}{\eta }_{11}& {\eta }_{12}\\ {\eta }_{21}& {\eta }_{22}\end{array}\right|$ is a 2 form.

k form is a function of k vectors which is k-linear and antisymmetric.

$\omega ({\eta }_{i_1},...{\eta }_{i_k})=(-1{)}^v\omega ({\eta }_1,...{\eta }_k)$

$v=\{\begin{array}{c}0ifthepermulation{i}_1,...,i_{k}iseven;\\ 1ifthepermulation{i}_1,...,i_{k}isodd.\end{array}$

不懂 permulation 的請回憶 行列式

e.g., oriented volume on

$R^n$

Differentiable manifold (微分流形)

A chart is an open set

$U$ in the enclidean coordinate space

$\overrightarrow{q}=(q_1,...,q_n)$ together with a one-to-one mapping

$\varphi$ of

$U$ onto some subset of

$M$,

$\varphi :U\to \varphi U\subset M$.

A set

$M$ is given the structure of a differential manifold if

$M$ is provided with a finite or countable collection of charts, so that every point is represented in at least one chart.

1-form

$d{f}_x$ on the tanget space

$T{M}_x$

Let

$f:M\to R$ be a differentiable function on the manifold

$M$ (imagine a function of many variables

$f:R^n\to R$). The differential

$df{|}_x$ of

$f$ at

$x$ is a linear map

$d{f}_x:T{M}_x\to R$ of the tangent space to

$M$ at

$x$ into the real line.

tangent bundle

$TM={\cup }_{x}T{M}_x$

Definition. A 1-form on a manifold is a smooth map

$\omega :TM\to R$ of the tangent bundle of

$M$ to the line, linear on each tangent space

$T{M}_x$.

Differential k-form

Definition. A differential k-form

${\omega }^k{|}_x$ at a point

$x$ of a manifold

$M$ is an exterior k-form on the tangett space

$T{M}_x$ to

$M$ at

$x$, i,e, a k-linear skew-symmetric function of k vectors

${\eta }_1,...,{\eta }_k$ tanget to

$M$ at

$x$.

Theorem. Every differential k-form on

$R^n$ with a given coordinate system

$x_1,...,x_n$ can be written uniquely in the form

${\omega }^k=\sum _{i_1<...<i_k}{a}_{i_1,...i_k}(x)d{x}_{i_1}\mathrm{\Lambda }...\mathrm{\Lambda }{x}_{i_k}$ where the

$a_{i_1,...i_k}(x)$ are smooth functions on

$R^n$.

---

GF(2) Galois Field

In mathematics, a field is a set on which addition, subtraction, multiplication, and division are defined and behave as the corresponding operations on rational and real numbers do.

建構式數學教的是最基本的數學觀念 不是錯~只是 對於 國高中小 是考試與教育走火入魔, 感嘆~ 就像 兩個事件獨立一樣~對學生 叫做 定義

GF(2) GF:Galois field
The modulo-2 addition can be
implemented with an XOR (

$\oplus$) gate and the
modulo-2 multiplication can be implemented
with an AND (

$\otimes$) gate.

The set {0,1} together with modulo-2 addition
and multiplication is called a binary field ,
denoted GF(2).

Remark.

1. Every element
   $x$ of GF(2) satisfies
   $x\oplus x=0$ and therefore
   $-x=x$
2. $x,y\in GF(2)$,
   $x-y=x\oplus y$
3. $1\otimes 1=1$, the only invertible element is 1. (e.g., rational number
   $4\times (1/4)=1,1/4:=4^{-1},a/b:=a\times b^{-1},b\ne 0$)
4. Hence, GF(2) is a field.

Vector Space over GF(2)
A binary n-tuple

$\overrightarrow{a}=(a_1,a_2,...a_n)$
is an ordered sequence with components from GF(2).
Define an addition operation for any two binary
vector

$\overrightarrow{a}+\overrightarrow{b}=(a_1\oplus b_1,...,a_n\oplus b_n)$, where

$\oplus$=XOR.
Define a scalar multiplication between an element

$c$ in GF(2) and a binary n-tuple

$\overrightarrow{a}=(a_1,a_2,\dots ,a_n)$ as
follows:

$c\times \overrightarrow{a}=(c\otimes a_1,c\otimes a_2,...,c\otimes a_n)$, where

$\otimes$ = AND.

The set

$V^n$ together with the addition defined for any two binary n-tuple in

$V^n$ and the scalar multiplication defined between an element in GF(2) and a binary n-tuple in

$V^n$ is called a vector space over GF(2).

Hamming distance

$d(\overrightarrow{a},\overrightarrow{b})=\sum |a_i-b_i|=\sum |a_i\oplus b_i|$

HW:
Show that Hamming distance is a metric.

An (n,k) convolutional encoder (CE) will encode a k-bit input block into an n-bit ouput block, which depends on the current input block and the m preceding input blocks
A convolutional encoder is a discrete linear time-invariant system.

Remark. Why LTI system?
input of CE

$\overrightarrow{0}\to$ CE

$\to \overrightarrow{0}$
input of CE

$\delta (n)\to$ CE

$\to \overrightarrow{g}$
input of CE

$\delta (n-m)\to$ CE

$\to \overrightarrow{g}(n-m)$ and

$a\otimes \delta (n)\to$ CE

$\to a\otimes \overrightarrow{g}(n-m)$,

$a\in GF(2)$
since the convolutional encoder is finite state machine (FSM) with initial state

$\overrightarrow{0}$. Assume

$\overrightarrow{g}\in V^n$, then CE is a LTI system. Hence we can define impulse response of the CE.

(2,1) convolution encoder:

Assume discrete time impulse response is given by

$g^0(n)=[1,0,1,1]$ and

$g^1(n)=[1,1,1,1]$ over GF(2).

input sequence=

$\overrightarrow{U}$
output

$\overrightarrow{V^0}=g^0\star \overrightarrow{U}$ and

$\overrightarrow{V^1}=g^0\star \overrightarrow{U}$
output sequence=

$(V_0^0,V_0^1,V_1^0,V_1^1,...)$

Decoding convolutional codes:
Viterbi algorithm…by VLSI or Software

---

Statistical Inference (統計推論)

Formally, the partial derivative with respect to

$\theta$ of the natural logarithm of the likelihood function is called the score.

$s(X;\theta )$=score=

$\frac{\partial }{\partial \theta }logL(X|\theta )$.
e.g.,

$L(X|\theta )=\prod _{i=1}^N{f}_X(x|\theta )$,

$X_1,...,X_N$ iid.

$p(x_i|\mu ,\sigma )=\frac{1}{\sqrt{2\pi {\sigma }^2}}{e}^{-\frac{1}{2{\sigma }^2}(x_i-\mu {)}^2}$

$L(X|\mu ,\sigma )=\prod _{i}p(x_i|\mu ,\sigma )$

In general,

$\{f(\overrightarrow{x}|\theta \in \mathrm{\Theta })\}$,

$\mathrm{\Theta }$ is called the parameter space.

Maximum likelihood estimator (MLE)

$\hat{\theta }=argma{x}_{\theta }L(x|\theta )$
Therefore, MLE can be estimated by solving

$\frac{\partial }{\partial \theta }logL(X|\theta )$ or

${\mathrm{\nabla }}_{\overrightarrow{\theta }}log(L(X|\overrightarrow{\theta }))$ if it exists, since log(.) is a monotone increasing function and

$\frac{d}{dx}ln(f(x))=\frac{f(x{)}^{{}^{\prime }}}{f(x)}$,

$f(x)>0$.

HW.

$argma{x}_{x\in [0,2\pi ]}cos(x)=?$

The expected value (the first moment) of the score, evaluated at the true parameter value

$\theta$ , is 0.

1. $E[s(X;\theta )|\theta ]=0$
2. $I(\theta )=E[s(X;\theta {)}^2|\theta ]$

The Fisher information

$I(\theta )$is defined to be the variance of the score.

Proof.

$\frac{dlnf(x)}{dx}=\frac{f^{{}^{\prime }}(x)}{f(x)}$

$E[s(X;\theta )|\theta ]$

$=\int \frac{\partial }{\partial \theta }lnL(x|\theta )L(x|\theta )dx$

$=\int \frac{\frac{\partial L(x|\theta )}{\partial \theta }}{L(x|\theta )}L(x|\theta )dx=\frac{\partial }{\partial \theta }\int L(x|\theta )dx=0$

score vector

$\overrightarrow{\theta }=[{\theta }_1,...,{\theta }_n{]}^T$
the log-likelihood function

$L(x;\overrightarrow{\theta })$
score vector

$I(\overrightarrow{\theta })={\mathrm{\nabla }}_{\overrightarrow{\theta }}L(x;\overrightarrow{\theta })$
Under mild regularity conditions, the expected value of the score is equal to zero:

$E(I(\overrightarrow{\theta })|\overrightarrow{\theta })=0$

Score Function and Fisher Information Matrix
Fisher information

The information matrix is the covariance matrix of the score.
Fisher information matrix (FIM)

$\overrightarrow{\theta }=[{\theta }_1,...,{\theta }_n{]}^T$

$I(\overrightarrow{\theta })=(I[\theta ]{)}_{ij}=E[{\mathrm{\nabla }}_{\overrightarrow{\theta }}logL(X|\theta ){\mathrm{\nabla }}_{\overrightarrow{\theta }}logL(X|\theta )|\theta {]}^T]$

If

$T_{\theta }(X)$ is an unbiased estimator of

$\theta$
then the Cramér–Rao bound reduces to

$CO{V}_{\theta }(T_{\theta }(X))\ge I(\theta {)}^{-1}$

Cramér–Rao bound (Rao-Cramér inequality, Rao-Cramér lower bound)
Score Function and Fisher Information Matrix

---

Number Theory

4. Let

   $a,b,m\in Z$ with
   $m>0$. Then
   $a$ is said to be congruent to
   $b$ modulo
   $m$, denoted
   $a\equiv bmodm$ (同餘).

5. Every integer greater than

   $1$ has a prime divisor.

6. If

   $a$ is a composite number(合成數), there exist
   $a,b\in Z$ such that
   $n=ab$,
   $1<a<n,1<b<n,$ e.g.,
   $14=2\times 7.$

7. Let

   $n$ be a composite number(合成數). Then
   $n$ has a prime divisor
   $p$ with
   $p\le \sqrt{n}$.

8. $1$ 不是質數也不是 composite​ number. Every positive integer can be written as a product of prime numbers. e.g.,
   $60=(2^2)(3)(5)$. In general,
   $n=p_1^{a_1}...p_n^{a_n}$, if
   $n>1$ and
   $p_i$ prime numbers.

9. $a_i\in Z$,
   $a_1,...,a_n$ not all zero. If
   $(a_1,...,a_n)=1$,
   $a_1,...,a_n$ are said to be relative prime. If
   $(a_i,a_j)=1$ for all pairs $i,j $ with
   $i\ne j$, then
   $a_1,...,a_n$ are said to be pairwise relatively prime.

10. A set of integers such that every integer is congruent modulo

    $m$ to exactly one integer of the set is said to be a complete residue(餘數) system modulo
    $m$.
    e.g.,
    
    $\{0,1,...,m-1\}$ is a complete residue system modulo
    $m$.
    The set of integers {1,5} is a reduced residue system modulo 6.

11. $6a=6bmod3\nrightarrow a=bmod3$

12. $a,b,c\in Z$,
    $ca=cbmodm\leftrightarrow a\equiv bmod(m/(c,m))$

13. Definition: A arithmetric function is a function whose domain is the set of positive integer.

14. An arthmetric function (算術函數)

    $f$ is said to be multiplicate if
    $f(mn)=f(m)f(n)$ where
    $m$ and
    $n$ are relative prime positive numbers.

15. the least common multiple (最小公倍數) of two integers

    $a$ and
    $b$ =
    $lcm(a,b)=$ the smallest positive integer that is divisible by both
    $a$ and
    $b$

Definition. Let

$a,b\in Z$. A congruence of the form

$ax\equiv b\mathrm{mod}m$ is said to be a linear congruence in the variable

$x$ (一元線性同餘方程).

Definition. Let

$a,m\in Z$ with

$m>0$ and

$(a,m)=1$. The order of a modulo

$m$, denoted

$or{d}_{m}a$, is the least positive integer

$n$ for which

$a^n\equiv 1modm$.

Definition. Let

$r,m\in Z$ with

$m>0$ and

$(r,m)=1$. Then

$r$ is said to be a primitive root (原根) modulo

$m$ if

$or{d}_{m}r=\varphi (m)$.

e.g.,

$3$ is a primitive root modulo

$7$ since

$or{d}_{7}3=6=\varphi (7)$.

$2$ is a primitive root modulo

$13$,

$or{d}_{13}2=\varphi (13)$

$2$ is not a primitive root modulo

$7$, since

$or{d}_7=3\ne \varphi (7)$

Theorem. Let

$ax\equiv b\mathrm{mod}m$ and

$d=(a,m)$. If

$d\nmid b$, then the congruence has no solution in

$Z$; if

$d|b$, then the congruence has exactly

$d$ incongruent solutions modulo

$m$ in

$Z$.
Proof. Elementary Number Theory, chap 2.2, by STRAYER.

Definition. Any solution of the linear congruence in one variable

$ax\equiv 1\mathrm{mod}m$ to be said to be a (multiplicative) inverse of a modulo

$m$.

e.g., the inverse 5 mod 16= 13, since

$5\times 13mod16\equiv 1$

瑞士數學家 Euler 大師就是大師 腦袋不知裝時麼 寫下這 重要的理論 Public key, Priviate key 就是用到這定理

Euler's Theorem.

Let

$a,m\in Z$ with

$m>0$. If

$(a,m)=1$, then

$a^{\varphi (m)}\equiv 1modm$, where Euler phi-function (Eulur's totient function), denoted

$\varphi (n)$,

$\varphi (n)=|\{x\in Z:1\le x\le n;(x,n)=1\}|$.

Remark.
1.

$|S|$ cardinality of the set

$S$ (the number of elements of the set

$S$).

$\varphi (n)$ is the number of positive integers less than or equal to

$n$ that are relatively prime to

$n$. e.g.,

$\varphi (1)=1,\varphi (3)=2,\varphi (5)=4,\varphi (6)=2,\varphi (8)=4$
2.

$\varphi (p)=p-1$, if

$p$ is a prime number.
4.

$p,q$ two prime numbers, for

$n=pq$,

$\varphi (n)=\varphi (pq)=\varphi (p)\varphi (q)=(p-1)(q-1)$. Euler phi-finction

$\varphi (n)$ is multiplicative.
Proof.
Consider the matrix

$[kp+i],1\le i\le p,0\le k\le q-1$, if

$(p,i)=d>1$, then no entry of

$i$th-row is relatively prime to

$p$ (

$pq$), since if

$d>1$,then

$d|p$ and

$d|i$. Hence

$(p,i)=1$. Consider the row

$i$ with

$(p,i)=1$,

$[i,p+i,2p+i,...,(q-1)p+i]$, each of this intergers is relatively prime to

$p$.

$\varphi (q)$ of these integers are relatively prime to

$q$. Since

$\varphi (q)$ integers are relatively prime to

$p$, they are relatively prime to

$pq$. The residue system modulo

$\varphi (n)$ is

$[0,1,...,pq-1]$. The residues that are not relatively prime to

$n$ are the set

$\{p,2p,...,(q-1)p\}$, the set

$\{q,2q,...,(p-1)q\}$ and 0. Hence

$\varphi (n)=(pq)-[(q-1)+(p-1)+1]=\varphi (p)\varphi (q)$

5. $a^{\varphi (m)+1}\equiv amodm$

Proof. Let

$0<r_1,r_2,...r_{\varphi (m)}\le m$ and

$(r_i,m)=1,i=1,...,\varphi (m)$. Consider

$r_{i}a,r_{2}a,...r_{\varphi (m)}a$. Since

$(a,m)=1$, the inverse of

$a$ =

$a^{\prime }$. Hence if

$r_{i}a\equiv r_{j}a\mathrm{mod}m$ with

$i\ne j$ then

$r_{i}a{a}^{\prime }=r_{j}a{a}^{\prime }\mathrm{mod}m$,

$r_i\equiv r_{j}modm$. This is impossible. So the least non-negative resdiues modulo

$m$ of the integers

$r_{1}a,r_{2}a,...,r_{\varphi (m)}$. Then

$(r_{1}a)(r_{2}a)...(r_{\varphi (m)}a)\equiv r_1...r_{\varphi (m)}modm$. Hence

$m|a^{\varphi (m)}{r}_1...r_{\varphi }(m)-r_1...r_{\varphi (m)}$, since

$(r_1,...,r_{\varphi (m)},m)=1$, we have

$m|a^{\varphi (m)}-1$.

Compute Euler Phi-Function:
Theorem. Let

$p$ be a prime number and let

$0<a\in Z$, then

$\varphi (p^a)=p^a-p^{a-1}$
Proof. The positive integers not exceeding

$p^a$ that are not relatively prime to

$p^a$ are

$p,2p,3p,...p^{a-1}p$, hence

$\varphi (p^a)=p^a-p^{a-1}$.

Theorem. Let

$0<z\in Z$, then

$\varphi (n)=n{\sqcap }_{p|n,pprime}(1-\frac{1}{p})$.

e.g.,

$\varphi (12)=12{\sqcap }_{p|12,pprime}(1-\frac{1}{p})=12(1-1/2)(1-1/3)$

$504=2^3{3}^{2}7$,

$\varphi (504)=504(1-\frac{1}{2})(1-\frac{1}{3})(1-\frac{1}{7})=144$

Proof. Assume

$n>1$ and

$n=p_1^{a_{!}}...p_r^{a_r}$ with

$p_1,...,p_r$ distinct prime number and

$a_1...a_r$ postive integers. Then

$\varphi (n)=\varphi (p_1^{a_1}...p_r^{a_r})=\varphi (p_1^{a_1}...\varphi (p_r^{a_r})$ since Euler phi-finction is multiplicative. Thus

$\varphi (n)=(p_1^{a_1}-p_1^{a_1-1})...(p_r^{a_r}-p_r^{a_r-1})=n{\sqcap }_{p|n,pprime}(1-\frac{1}{p})$$

---

The RSA Encryption/Decryption Scheme

Let

$p$ and

$q$ be distinct odd prime number (typically, very large), let

$m=pq$ and let

$e$ be a positive integer such that

$(e,\varphi (m))=1$. The ordered pair

$\{e,m\}$ is the public key. Let

$d\equiv e^{-1}mod\varphi (m)$, then

$\{d,m\}$ is the private key.

Encryption
block

$P$ to a new block

$C$

$P^e\equiv Cmodm,0\le C<m$

Decryption

block

$C$ to block

$P$

$C^d\equiv Pmodm,0\le P<m$

Remark.

$ed=1\mathrm{mod}\varphi (m)\to$

$ed=k\varphi (m)+1$,

$C^d\equiv (P^e{)}^d\equiv P^{ed}\equiv P^{k\varphi (m)+1}\equiv P^{k\varphi (m)}P\equiv Pmodm$, by Euler's theorem.

Example.

1. select two prime numbers, p=7 and q=17

2. n=pq=119

3. $\varphi (n)=(p-1)(q-1)=96$

4. select

   $e$ is relative prime to
   $\varphi (n)=96$, e.g.,
   $e=5$.

5. $de\equiv 1mod96$ and
   $d<96$, then
   $d=77$.
   public key = {5,119}
   private ket ={77,119}

   Diffie-Hellman Key Exchange Algorithm
   

   
   
   

   1. Global Public Emements
      

      $q$ prime number,
      $\alpha <q$ and
      $\alpha$ is primitive root of
      $q$

   2. User A Key Generation
      Select priviate

      $X_A$,
      $X_A<q$
      Calculate Public
      $Y_A$,
      $Y_A\equiv {\alpha }^{X_A}modq$

   3. User B Key Generation
      Select priviate

      $X_B$,
      $X_B<q$
      Calculate Public
      $Y_B$,
      $Y_B\equiv {\alpha }^{X_B}modq$.

   4. Generation of Secret Key by User A
      

      $K\equiv Y_B^{X_A}modq$

   5. Generation of Secret Key by User B
      

      $K\equiv Y_A^{X_B}modq$

Ref. Cryptography and Network Security, by William Stallings

Ref. Introduction to Higher Mathematics, by Patrick Keef and David Guichard.

中國餘數定理, 孫子定理, 韓信點兵 (Chinese Remender Theorem)

Let

$m_1,m_2,...,m_n$ be pairwise relative prime positive numbers and let

$b_1,...b_n$ be any integers. The system of linear congruences in one variables given by

$x\equiv b_{1}mod{m}_1$

$x\equiv b_{2}mod{m}_2$
…

$x\equiv b_{n}mod{m}_n$
has a unigue solution modulo

$m_1{m}_2...m_n$.
Proof.
Existence
Let

$M=m_1{m}_2...m_n$ and let

$M_i=M/m_i$. Then

$(M_i,m_i)=1$ since they are pairwise relative prime positive numbers. Thus

$M_i{x}_i\equiv 1mod{m}_i$ has a soultion for each

$i$. Form

$x\equiv \sum _{i=1}^n{b}_i{M}_i{x}_i\equiv 0+0+...b_i+0...+0mod{m}_i\equiv b_{i}mod{m}_i$ for each

$i$.

Uniqueness
Let

$x^{\prime }$ be another solution. We have

$x^{\prime }\equiv b_{i}modm$.

$x\equiv x^{\prime }modm$. Then

$m_i|(x-x^{\prime })$ for all

$i$. Then

$M|(x-x^{\prime })$, from which

$x\equiv x^{\prime }modM$.

e.g.,

$x\equiv 2\mathrm{mod}3$

$x\equiv 1\mathrm{mod}4$

$x\equiv 3\mathrm{mod}5$

$M=(3)(4)(5)=60$,

$M_1=20,M_2=15,M_3=12$,

$x_1\equiv 2mod3$ ,

$x_2\equiv 3mod4$,

$x_3\equiv 3mod5$, then

$x=b_1{M}_1{x}_1+b_2{M}_2{x}_2+b_3{M}_3{x}_3\equiv 233\equiv 53mod60$

Tensor Product of Hilbert Spaces

Let

$H_1$ and

$H_2$ be Hilbert spaces over a filed

$K$, e.g.,

$R$. For each

${\varphi }_1\in H_1$,

${\varphi }_2\in H_2$, let

${\varphi }_1\otimes {\varphi }_2$ dentote conjugate (for complex number) bilinear form which acts on

$H_1\otimes H_2$ (tensor product) by

$({\varphi }_1\otimes {\varphi }_2)<{\psi }_1,{\psi }_2>=<{\psi }_1,{\varphi }_1{>}_{H_1}<{\psi }_2,{\varphi }_2{>}_{H_2}.$

Let

$E$ be the set of finite linear conbinations of such conjugate biliear forms; we define an inner product

$<{>}_E$ on

$E$ by defining

$<\varphi \otimes \psi ,\eta \otimes \mu {>}_E=<\varphi ,\eta ><\psi ,\mu >$ and extending by linearity to

$E$ (tensor: a multilinear mapping, multidimensional array…)
Fact 1.

$<,{>}_E$ is well defined and positive definite.
Fact 2. If

$\{{\varphi }_i\}$ and

$\{{\psi }_i\}$ are orthonormal bases for

$H_1$ and

$H_2$, then

${\varphi }_i\otimes {\psi }_i$ is an orthonormal basis for

$H_1\otimes H_2$.

Then we have tensor product:

$H_1\otimes H_2\otimes ...H_n$.
Fact 3.

$V\otimes (W\otimes U)\cong (V\otimes W)\otimes U$

$V\otimes K\cong K\otimes V\cong V$

Ref. Functional Analysis, M. Reed, B. Simon

---

Appendix

如果您數學程度不錯, 大數學家( Soviet and Russian mathematician) Vladimir Arnold 的書不錯(需 數學系程度)

"將數學嚴謹性與物理直覺相結合的清晰的寫作風格"
有助 別人理解

Mathematical Methods of Classical Mechanics, by V. I. Arnold
(此書也要有數學研究所程度, 適合 要念研究所與進攻博士的人)

大學部線代與機率推薦書(好像都是 數學系的~要有觀念不是計算, 計算與應用是幫助理解):

Linear Algebra:
Introduction to Linear Algebra, Gilbert Strang

Probability:
A First Course in Probability, Sheldon Ross

---

Ref.
Mathematical Methods and Algorithms for Signal Processing, by Todd Moon (Author), Wynn Stirling (Author)
Appendix 有簡潔的 measure theory

這書適合有心念研究所的同學 或 想加強自己能力的 資電人員, 我以前 用過 這本 教 estimation and prediction theory

---

Stochastic Processes, by Sheldon M. Ross (沒有用到 measure theory, 適合 EE, 資工 統計 應數 研究所)

Linear Operator Theory in Engineering and Science (Applied Mathematical Sciences, 40), by Arch W. Naylor (Author), George R. Sell (Author)

Real Analysis and Probability
Probability and Mathematical Statistics, by Robert B. Ash
(數研所程度, 較深)

有空再來 寫 神奇的 Dirac delta function

$\delta (t)$

當時

$\int$

$\delta$

$(t)dt=1$ Riemann integral, Lebesque integral 是不行的

天才物理學家,量子力學的奠基者之一 Paul Dirac

還有一位 Évariste Galois, Coding 的原理就是 年輕的 他 奠立的~現稱 Évariste Galois
年輕 20歲 鬥劍 過世

後來才有數學理論:

Schwartz distribution or generalized function

這三本書 需要數學系以上的基礎

Applied Functional Analysis (Dover Books on Mathematics) Reprint 版本
作者 D.H. Griffel (Author)
這對 EE 比較容易懂, Dover Books 的書 很多是 沒有 版權問題的 好書 重印, 不貴, 這本就是 評價 很高的書, 要修 數研所 的課 沒那麼簡單