Introdunction to Linear Algebra-第9章-Complex Vectors Matrices

[TOC]
《Introdunction to Linear Algebra》的第9章： Complex Vectors Matrices.

Real versus Complex:

$$ \mathbf{R} = \text { line of all real numbers}-\infty < x < \infty \quad \leftrightarrow \quad \mathbf{C} = \text { plane of all complex numbers } z = x + i y \\\\ |x| = \text { absolute value of } x \quad \leftrightarrow \quad|z|=\sqrt{x^{2}+y^{2}} = r = \text { absolute value (or modulus) of } z \\\\ 1 \text { and } -1 \text { solve }x^{2} = 1 \quad \leftrightarrow \quad z = 1, w, \ldots, w^{n-1} \text { solve } z^{n}=1 \text { where } w=e^{2 \pi i / n} \\\\ \text {The complex conjugate of } z = x + i y \text { is } \bar{z}=\boldsymbol{x}-\boldsymbol{i} \boldsymbol{y} . \quad|z|^{2}=x^{2}+y^{2}=z \bar{z} \text { and } \frac{1}{z}=\frac{\bar{z}}{|z|^{2}} \\\\ \text { The polar form of } z = x + i y \text { is } |z| e^{i \theta}=r e^{i \theta}=r \cos \theta+i r \sin \theta. \text { The angle has }\tan \theta=\frac{y}{x} \\\\ \mathbf{R}^{n}: \text { vectors with } n \text{ real components } \leftrightarrow \mathbf{C}^{n} : \text { vectors with } n \text { complex components} \\\\ \text { length: }\|x\|^{2}=x_{1}^{2}+\cdots+x_{n}^{2} \leftrightarrow \text { length: }\|\boldsymbol{z}\|^{2}=\left|z_{1}\right|^{2}+\cdots+\left|z_{n}\right|^{2} \\\\ \text { transpose: }\left(A^{\mathrm{T}}\right)_{i j}=A_{j i} \leftrightarrow \text { conjugate transpose: }\left(A^{\mathrm{H}}\right)_{i j}=\overline{A_{j i}} \\\\ \text { dot product}: \boldsymbol{x}^{\mathrm{T}} \boldsymbol{y}=x_{1} y_{1}+\cdots+x_{n} y_{n} \leftrightarrow \text { inner product}: \boldsymbol{u}^{\mathrm{H}} \boldsymbol{v}=\bar{u}_{1} v_{1}+\cdots+\bar{u}_{n} v_{n} \\\\ \text { reason for } A^{\mathrm{T}}:(A \boldsymbol{x})^{\mathrm{T}} \boldsymbol{y}=\boldsymbol{x}^{\mathrm{T}}\left(A^{\mathrm{T}} \boldsymbol{y}\right) \leftrightarrow \text { reason for } A^{\mathrm{H}}:(A \boldsymbol{u})^{\mathrm{H}} \boldsymbol{v}=\boldsymbol{u}^{\mathrm{H}}\left(A^{\mathrm{H}} \boldsymbol{v}\right) \\\\ \text { orthogonality}: \boldsymbol{x}^{\mathrm{T}} \boldsymbol{y}=0 \leftrightarrow \text { orthogonality}:\boldsymbol{u}^{\mathrm{H}} \boldsymbol{v}=0 \\\\ \text { symmetric matrices}: S=S^{\mathrm{T}} \leftrightarrow \text { Hermitian matrices}: S=S^{\mathrm{H}} \\\\ \boldsymbol{S}=\boldsymbol{Q} \boldsymbol{\Lambda} \boldsymbol{Q}^{-\mathbf{1}}=\boldsymbol{Q} \boldsymbol{\Lambda} \boldsymbol{Q}^{\mathrm{T}}( \text { real } \Lambda) \leftrightarrow \boldsymbol{S}=\boldsymbol{U} \boldsymbol{\Lambda} \boldsymbol{U}^{-1}=\boldsymbol{U} \boldsymbol{\Lambda} \boldsymbol{U}^{\mathrm{H}}(\text { real } \Lambda) \\\\ \text { skew-symmetric matrices}: K^{\mathrm{T}}=-K \leftrightarrow \text { skew-Hermitian matrices }K^{\mathrm{H}}=-K \\\\ \text { orthogonal matrices}: Q^{\mathrm{T}}=Q^{-1} \leftrightarrow \text { unitary matrices}: U^{\mathrm{H}}=U^{-1} \\\\ \text { orthonormal columns}: Q^{\mathrm{T}} Q=I \leftrightarrow \text { orthonormal columns}: U^{\mathrm{H}} U=I \\\\ (Q \boldsymbol{x})^{\mathrm{T}}(Q \boldsymbol{y})=\boldsymbol{x}^{\mathrm{T}} \boldsymbol{y} \text { and } \|Q \boldsymbol{x}\|=\|\boldsymbol{x}\| \leftrightarrow(U \boldsymbol{x})^{\mathrm{H}}(U \boldsymbol{y})=\boldsymbol{x}^{\mathrm{H}} \boldsymbol{y} \text { and } \|U \boldsymbol{z}\|=\|\boldsymbol{z}\| $$

9.1. Complex Numbers

单位圆:
In case $a^2 + b^2 = 1$, this says that $(a+ ib)^{- 1}$ is $a -ib$. On the unit circle, $1 / z$ equals $z$.Later we will say: $1/e^{i \theta}$ is $e^{-i \theta}$.

复数的表达形式:

1. 复平面上的点(向量): $a + bi$
2. the polar form: $re^{i \theta}$

If $z$ is at angle $\theta$, its conjugate $\bar{z}$ is at $2 \pi - \theta$ and also at $-\theta$.

The $n$th power of $z=r(\cos \theta+i \sin \theta)$ is $z^{n}=r^{n}(\cos n \theta+i \sin n \theta)$.

$r(\cos \theta+i \sin \theta)$ times $r^{\prime}\left(\cos \theta^{\prime}+i \sin \theta^{\prime}\right)=\boldsymbol{r} \boldsymbol{r}^{\prime}\left(\cos \left(\boldsymbol{\theta}+\boldsymbol{\theta}^{\prime}\right)+i \sin \left(\boldsymbol{\theta}+\boldsymbol{\theta}^{\prime}\right)\right) .$

通过泰勒展开理解复数$e^{i \theta}$:

$e^{x}=1+x+\frac{1}{2} x^{2}+\frac{1}{6} x^{3}+\cdots \quad$ becomes $\quad e^{i \theta}=1+i \theta+\frac{1}{2} i^{2} \theta^{2}+\frac{1}{6} i^{3} \theta^{3}+\cdots$
Euler’s Formula $e^{i \theta}=\cos \theta+i \sin \theta$ gives $z=r \cos \theta+i r \sin \theta=r e^{i \theta}$

The Discrete Fourier Transform uses $w = e^{2 \pi i/ n}$ and its powers.
$$
\text { Set } w=e^{2 \pi i / n} . \text { The nth powers of } 1, w, w^{2}, \ldots, w^{n-1} \text { all equal } 1
$$

9.2 Hermitian and Unitary Matrices

$$
\text { The length }|z| \text { is the square root of } \bar{z}^{\mathrm{T}} z=z^{\mathrm{H}} z=\left|z_{1}\right|^{2}+\cdots+\left|z_{n}\right|^{2}
$$

这么做的原因是对于复数,Instead of $(a+ bi)^2$ we want $a^2 + b^2$.

定义 The inner product of real or complex vectors $\boldsymbol{u}$ and $\boldsymbol{v}$ is $\boldsymbol{u}^{\mathrm{H}} \boldsymbol{v}:$

$$ \boldsymbol{u}^{\mathrm{H}} \boldsymbol{v}=\left[\begin{array}{lll} \bar{u}_{1} & \cdots & \bar{u}_{n} \end{array}\right]\left[\begin{array}{c} v_{1} \\\\ \vdots \\\\ v_{n} \end{array}\right]=\bar{u}_{1} v_{1}+\cdots+\bar{u}_{n} v_{n} $$

A zero inner product still means that the (complex) vectors are orthogonal.

The inner product of $A u$ with $v$ equals the inner product of $u$ with $A^{\mathrm{H}} v$ :
$A^{\mathrm{H}}$ is also called the “adjoint“ of $A \quad(A u)^{\mathrm{H}} v=u^{\mathrm{H}}\left(A^{\mathrm{H}} v\right)$

The conjugate transpose of $AB$​ is $(AB)^H = B^H A^H$​.

three crucial properties of all Hermitian matrices.

1. If $S = S^H$ and $z$ is any real or complex column vector, the number $z^H Sz$ is real.
   证明:$(z^H Sz)^H = z^H S^H (z^H )^H$ which is $z^H Sz$ again.

2. Every eigenvalue of a Hermitian matrix is real.

Proof Suppose $ S z=\lambda z $. Multiply both sides by $ z^{\mathrm{H}} $ to get $ z^{\mathrm{H}} S z=\lambda z^{\mathrm{H}} z $. On the left side, $ z^{\mathrm{H}} S z $ is real. On the right side, $ z^{\mathrm{H}} z $ is the length squared, real and positive. So the ratio $ \lambda=z^{\mathrm{H}} S z / z^{\mathrm{H}} z $ is a real number. Q.E.D.

3. The eigenvectors of a Hermitian matrix are orthogonal (when they correspond to different eigenvalues). If $ S \boldsymbol{z}=\lambda \boldsymbol{z} $ and $ S \boldsymbol{y}=\beta \boldsymbol{y} \text{ then } \boldsymbol{y}^{\mathrm{H}} \boldsymbol{z}=0 $.

Proof Multiply $ S \boldsymbol{z}=\lambda \boldsymbol{z} $ on the left by $ \boldsymbol{y}^{\mathrm{H}} $. Multiply $ \boldsymbol{y}^{\mathrm{H}} S^{\mathrm{H}}=\beta \boldsymbol{y}^{\mathrm{H}} $ on the right by $ \boldsymbol{z} $:

$$
\boldsymbol{y}^{\mathrm{H}} S \boldsymbol{z}=\lambda \boldsymbol{y}^{\mathrm{H}} \boldsymbol{z} \quad \text { and } \quad \boldsymbol{y}^{\mathrm{H}} S^{\mathrm{H}} \boldsymbol{z}=\beta \boldsymbol{y}^{\mathrm{H}} \boldsymbol{z} .
$$

The left sides are equal so $ \lambda \boldsymbol{y}^{\mathrm{H}} \boldsymbol{z}=\beta \boldsymbol{y}^{\mathrm{H}} \boldsymbol{z} $. Then $ \boldsymbol{y}^{\mathrm{H}} \boldsymbol{z} $ must be zero.

unitary matrix

Every matrix $Q$ with orthonormal columns has $Q^H Q = I$.
If $Q$ is square, it is a unitary matrix. Then $Q^H = Q^{- 1}$.

If $Q$ is unitary then $||Qz|| = ||z||$. Therefore $Qz = \lambda z$ leads to $ |\lambda| = 1$.

例子: Fourier matrix

it is not Hermitian. If you change $i$ to $-i$, you get a different matrix. Is $F$ unitary? Yes.

unitary 的好处之一在于方便逆运算:
When we multiply a vector by $F$, we are comput­ing its Discrete Fourier Transform. When we multiply by $F^{- 1}$, we are computing the inverse transform. The special property of unitary matrices is that $F^{- 1} = F^{H}$ The inverse
transform only differs by changing $i$ to $-i$:
$$
F^{-1}=F^{\mathrm{H}}=\frac{1}{\sqrt{3}}\left[\begin{array}{ccc}
1 & 1 & 1 \\
1 & e^{-2 \pi i / 3} & e^{-4 \pi i / 3} \\
1 & e^{-4 \pi i / 3} & e^{-2 \pi i / 3}
\end{array}\right]
$$

9.3 The Fast Fourier Transform

FFT 的概述:我们希望对信号/函数进行频域分析,因此需要通过 Fourier transform 把 $f(x)$ 变为 $ c_k e^{ikx}$. 当然有时候也需要进行逆变换.快速地进行正/逆 Fourier transform 即是 FFT 技术.

Roots of Unity and the Fourier Matrix

求解 special equation $z^n = 1$.The solutions $z$ are the “$n$th roots of unity.” They aren evenly spaced points around the unit circle in the complex plane.

FFT 的思路是通过减半的阶数来提升计算效率的.

首先证明正/逆都成立( matrix $F$ passes from “frequency space” to “physical space.”. $\bar{F}$ goes from physical space to frequency space.

以4阶为例子:
$$
F=\left[\begin{array}{cccc}
1 & 1 & 1 & 1 \\
1 & w & w^{2} & w^{3} \\
1 & w^{2} & w^{4} & w^{6} \\
1 & w^{3} & w^{6} & w^{9}
\end{array}\right]=\left[\begin{array}{cccc}
1 & 1 & 1 & 1 \\
1 & i & i^{2} & i^{3} \\
1 & i^{2} & i^{4} & i^{6} \\
1 & i^{3} & i^{6} & i^{9}
\end{array}\right]
$$

The matrix is symmetric ($F = F^T$ ). It is not Hermitian. But $1⁄2F$ is a unitary matrix.
因此可以求得 $F$ 的逆矩阵:

The columns of $F$ give $F^H F = 4I$. Its inverse is $1⁄4 F^H$ which is $F^{-1} = 1⁄4 F$.
因此 $F$ 的逆矩阵还是 $F$ 的标量倍,这也就意味着对逆变换我们也可以进行 FFT.

将 Fourier Transform 的一般形式表达如下:
The $n \times n$​ Fourier matrix contains powers of $w = e^{2 \pi /n}$.
$$
F_{n} \boldsymbol{c}=\left[\begin{array}{ccccc}
1 & 1 & 1 & \cdot & 1 \\
1 & w & w^{2} & \cdot & w^{n-1} \\
1 & w^{2} & w^{4} & \cdot & w^{2(n-1)} \\
\cdot & \cdot & \cdot & \cdot & \cdot \\
1 & w^{n-1} & w^{2(n-1)} & \cdot & w^{(n-1)^{2}}
\end{array}\right]\left[\begin{array}{c}
c_{0} \\
c_{1} \\
c_{2} \\
\cdot \\
c_{n-1}
\end{array}\right]=\left[\begin{array}{c}
y_{0} \\
y_{1} \\
y_{2} \\
\cdot \\
y_{n-1}
\end{array}\right]=\boldsymbol{y}
$$

Its columns are orthogonal, and $F^ n \bar{F}^n = nI$. Then
$F_n^{-1}$ is $\bar{F}_n/n$.
pattern in $F$:
The entry in row $j$, column $k$ is $w^{jk}$. Row zero and column zero contain $w^0 = 1$.
也可以使用 $\omega = e^{- 2\pi /N}$ 代替 $w$, 也就是说 $\bar{\omega} = w$. 由 $\omega$ 组成的为 $\bar{F}$.The matrix $\bar{F}$ with $\omega$’s computes Fourier coefficients. 这个过程可以理解为多项式插值的过程.
When a function $f(x)$ has period $2\pi$, and we change $x$ to $e^{i\theta}$.

Interpolation Find $c_{0}, \ldots, c_{n-1}$ so that $p(z)=f$ at $n$ points $z=1, \ldots, w^{n-1}$

where $z = e^{i\theta}$.

One Step of the Fast Fourier Transform

The key idea is to connect $F_n$ with the half-size Fourier matrix $F_{n/2}$.
$$
\begin{array}{ll}
\text { Factors } \\
\text { for FFT }
\end{array} \quad F_{4}=\left[\begin{array}{llll}
1 & & 1 & \\
& 1 & & i \\
1 & & -1 & \\
& 1 & & -i
\end{array}\right]\left[\begin{array}{llll}
1 & 1 & & \\
1 & i^{2} & & \\
& & 1 & 1 \\
& & 1 & i^{2}
\end{array}\right]\left[\begin{array}{lll}
1 & & & \\
& & 1 & \\
& 1 & & \\
& & & 1
\end{array}\right]
$$

$$ \boldsymbol{F}_{1024}=\left[\begin{array}{rr} I_{512} & D_{512} \\\\ I_{512} & -D_{512} \end{array}\right]\left[\begin{array}{ll} F_{512} & \\\\ & F_{512} \end{array}\right]\left[\begin{array}{c} \text { even-odd } \\\\ \text { permutation } \end{array}\right] $$

(One step of the FFT) Set $\boldsymbol{m}=\frac{1}{2} \boldsymbol{n}$. The first $m$ and last $m$ components of $\boldsymbol{y}=F_{n} \boldsymbol{c}$ combine the half-size transforms $y^{\prime}=F_{m} c^{\prime}$ and $y^{\prime \prime}=F_{m} c^{\prime \prime}$. From $n$ to $m=n / 2$ as $I \boldsymbol{y}^{\prime}+D \boldsymbol{y}^{\prime \prime}$ and $I \boldsymbol{y}^{\prime}-D \boldsymbol{y}^{\prime \prime}$ :
$$
\begin{aligned}
y_{j} &=y_{j}^{\prime}+\left(w_{n}\right)^{j} y_{j}^{\prime \prime}, & & j=0, \ldots, m-1 \\
y_{j+m} &=y_{j}^{\prime}-\left(w_{n}\right)^{j} y_{j}^{\prime \prime}, & & j=0, \ldots, m-1
\end{aligned}
$$
Split $c$ into $c^{\prime}$ and $c^{\prime \prime}$, transform them by $F_{m}$ into $y^{\prime}$ and $y^{\prime \prime}$, then these two equations reconstruct $y$.

Those formulas come from separating $c_{0} \ldots, c_{n-1}$ into even $ c_{2 k} $ and odd $ c_{2 k+1}: w $ is $ w_{n} $.

$$
\boldsymbol{y}=F \boldsymbol{c} \quad y_{j}=\sum_{0}^{n-1} w^{j k} c_{k}=\sum_{0}^{m-1} w^{2 j k} c_{2 k}+\sum_{0}^{m-1} w^{j(2 k+1)} c_{2 k+1} \text { with } m=\frac{1}{2} n
$$

The even $ c $'s go into $ \boldsymbol{c}^{\prime}=\left(\boldsymbol{c}_{0}, \boldsymbol{c}_{2}, \ldots\right) $ and the odd $ c $'s go into $ \boldsymbol{c}^{\prime \prime}=\left(\boldsymbol{c}_{1}, \boldsymbol{c}_{3}, \ldots\right) $. Then come the transforms $ F_{m} c^{\prime} $ and $ F_{m} c^{\prime \prime} $. The key is $ \boldsymbol{w}_{\boldsymbol{n}}^{2}=\boldsymbol{w}_{\boldsymbol{m}} $. This gives $ w_{n}^{2 j k}=w_{m}^{j k} $.

$$
y_{j}=\sum\left(w_{m}\right)^{j k} c_{k}^{\prime}+\left(w_{n}\right)^{j} \sum\left(w_{m}\right)^{j k} c_{k}^{\prime \prime}=y_{j}^{\prime}+\left(w_{n}\right)^{j} y_{j}^{\prime \prime}
$$.

The flow graph shows $c’$ and $c’’$ going through the half-size $F_2$. Those steps are called “butterfiies” from their shape.

The Full FFT by Recursion

递归思想:最终复杂度的降低:The final count for size $n = 2^l$ is reduced from $n^2$ to $\frac{1}{2} nl$.