Mathematics

复数

代数表示，z=a+bi，其中a为实部，b为虚部。

坐标表示，以复平面为承载：

  • 复平面，以直角（Rectangular）坐标系/笛卡尔（Cartesian）坐标系为例，X坐标轴为实轴，Y坐标轴为虚轴。复数用(a,b)（X坐标、Y坐标）来表示，向量(a,b)称为复向量。向量模长为复数模长（Modulus），又称强度（Magnitude），幅值（Amplitude，电子学常用），|z| = \sqrt{a^2+b^2)} = \sqrt{z*z^*}。
  • 复平面，以极坐标系（Polar）为例，复数用(r,\theta)（半径坐标和角坐标）来表示，半径为复数模长，极角为复数幅角（Argument），又称角度（Angle）。对应复向量，半径为复向量的模长，极角为极轴（即实轴）逆时针方向到复向量的夹角。

除代数表示、坐标表示外还有：

  • 三角表示，z = r(cos\theta+isin\theta)。其中r为模长，\theta为幅角。
  • 指数表示，z = re^{i\theta}。根据欧拉公式e^{i\theta}=cos\theta+isin\theta。其中e^{i\theta}或i\theta称为相位（Phase），有时直接称\theta为相位。相同的复数可以有不同的相位，如e^{i2\pi}, e^{i4\pi}。

代数表示适合加减法，指数表示适合乘除法，复平面坐标表示适合理解几何意义。
以z_1=a+bi=r_1e^{i\theta_1}, z2=c+di=r_2e^{i\theta_2}复数运算的几何意义：

  • 加减法的几何意义按照向量加减来理解。
  • 复数乘法，z_1*z_2 = r_1*r_2 * e^{i(\theta_1+\theta_2)}，相当于模长相乘，幅角相加，相位相加。
  • 复数除法，z_1/z_2 = r_1/r_2 * e^{i(\theta_1-\theta_2)}，相当于模长相除，幅角相减，相位相减。
  • z_1*z_2^* = (a+bi)(c-di) = \frac{(a+bi)(c-di)*(c+di)}{c+di} = z_1/z_2 * |z_2|^2 = r_1*r_2 * e^{i(\theta_1-\theta_2)}，相当于模长相乘，幅角相减，相位相减。

复函数在定义域上可导，称作全纯（Holomorphic）/可解析（Analytic）

空间

欧几里得空间：满足可依据距离和角表达的特定联系的点所成的集合。

向量空间：线性代数里的概念，指一组向量及相关的运算（向量加法、标量乘法），以及对运算的限制（封闭性、结合律）。

内积空间：Inner product space，线性代数里的概念，是增加了内积（标量积）的向量空间。内积涉及向量的夹角、长度及正交性，内积是点积的抽象。又称准希尔伯特空间（pre-Hilbert space）,由内积定义的距离完备化之后可得希尔伯特空间。

希尔伯特空间：Hilbert space，是完备的内积空间（带有内积的完备向量空间）。是有限维欧几里得空间的一个推广（在高等数学教科书中也被称为欧几里得空间），使之不局限于实数的情形和有限的维数，但又不失完备性（而不像一般的非欧几里得空间那样破坏了完备性）。也是一个内积空间，其上有距离和角的概念（及由此引申而来的正交性与垂直性的概念）。此外，希尔伯特空间还是一个完备的空间，其上所有的柯西序列会收敛到此空间里的一点，从而微积分中的大部分概念都可以无障碍地推广到希尔伯特空间中。

向量

正交性：两个向量的内积（标量积）为0。

乘法

向量乘法，设a和b为线性无关的两个(m,)维向量（方向不相同也不相反，否则外积为0）：

  • 点乘/点积/内积/标量乘（Dot Product，Inner Product, Scalar Product），a \cdot b = c为标量，即对应元素积的和，或a \cdot b = |a||b|cos\theta。
  • 叉乘/叉积/外积/向量积（Cross Product, Outer Prodcut, Vector Product），a \times b = c，b \times a = -c，c是一个(m,)维的向量（a和b所在平面的法向量）。模长为|a \times b| = |a||b|sin\theta（构成的平行四边形的面积），方向遵守右手定则。c的坐标可用a和b坐标按乘法分配律计算得到。

向量夹角：两个向量方向之间的夹角，即将起点重合后较小的夹角，<180度。
右手定则：在右手坐标系中，右手四指从a以向量夹角转向b时，竖起的大拇指的方向即为c的方向。
右手坐标系：基向量x,y,z满足x \times y=z, y \times z=x, z \times x=y（反过来则得负），x \times y = y \times z = z \times x = 0。

矩阵乘法，设A为(m,n)矩阵，B为(m,n)矩阵，C为(n,o)矩阵，D为(p,q)矩阵：

  • 矩阵乘A \cdot C是一个(m,o)矩阵。
  • 按元素积（Elementwise Product）/Hadamand积A \odot D或A * D是一个(m,n)矩阵。
  • 克罗内克积A \otimes D是一个(mp,nq)分块矩阵。

秩

矩阵A的列秩是A的线性独立的纵列的极大数目（极大线性无关组），表示为r(A)，rk(A)或rank(A)。

设 A 为m*n矩阵。若A 至少有一个r阶非零子式，而其所有r+1阶子式全为零，则称 r为A的秩。

矩阵的列秩和行秩总是相等的，因此它们可以简单地称作矩阵A的秩。表示为r(A)，rk(A)或rank(A)。等于向量组A生成的子空间的维数。

一个m*n的矩阵，如果秩很低（秩r远小于m,n），则它可以拆成一个m*r矩阵和一个r*n矩阵之积（类似于SVD分解）。后面这两个矩阵所占用的存储空间比原来的m*n矩阵小得多。

范数

Norm（范数）是向量和矩阵上的概念。标量可以作为向量的特例，即标量的绝对值。Lp Norm常写作p-Norm。

向量范数，对于向量x = [x_1,x_2,...x_m]：

||x||_p = (\sum_{i=1}^m |x_i|^p)^{\frac{1}{p}}

  • L0 Norm，向量非零元素的个数。0的0次幂为0，非零数的0次幂为1。
  • L1 Norm，向量元素绝对值之和。用于计算曼哈顿距离，绝对值误差等。表示点x到原点的曼哈顿距离。
  • L2 Norm，Euclid Norm（欧几里得范数），向量元素绝对值的平方和再开方。用于计算欧式距离，平方误差/均方误差（MSE）等。表示点x到原点的欧氏距离。
  • L\infty Norm，向量元素绝对值的最大值。当p趋向于正无穷时，其他元素会被绝对值最大的元素掩盖。
  • L-\infty Norm，向量元素绝对值的最小值。当p趋向于正无穷时，绝对值最小的元素的-\infty次幂最大，其他元素被掩盖。

矩阵范数，对于矩阵A \in R^{m \times n}：

  • L1 Norm，||A||_1 = \underset{j}{max} \sum_{i=1}^m |a_{i,j}| = \underset{j}{max} ||A_{:,j}||_1，列和范数，矩阵列向量元素绝对值之和（列向量的L1 Norm）的最大值。
  • L2 Norm，||A||_2 = \sqrt{\lambda_1}，谱范数，\lambda_1表示A^TA的最大特征值。
  • L\infty Norm，||A||_\infty = \underset{i}{max} \sum_{j=1}^n |a_{i,j}| = \underset{i}{max} ||A_{i,:}||_1，行和范数，矩阵行向量元素绝对值之和（行向量的L1 Norm）的最大值。
  • LF Norm，||A||_F =(\sum_{i=1}^m \sum_{j=1}^n |a_{i,j}|^2)^\frac{1}{2}，Frobenius Norm（斐波那契范数），矩阵元素绝对值的平方和再开方。
  • L2,1 Norm，||A||_{2,1} =\sum_{i=1}^m (\sum_{j=1}^n |a_{i,j}|^2)^\frac{1}{2} = ||A_{i,:}||_2，矩阵行向量的2-Norm之和，即矩阵先在行上2-Norm，然后在结果上1-Norm。当矩阵每行越多的元素为0时（行稀疏），L2,1 Norm约小。
  • L1,2 Norm，与L2,1类似，表示列稀疏。

相关代码：

对于复数标量，绝对值np.abs()和Frobenius模np.linalg.norm()结果一样。对于向量/矩阵，前者为[|z_1|, ..., |z_n|]，后者为\sqrt{|z_1|^2 + ... + |z_n|^2}。其中|z_n|^2 = z_n*z_n^*。
参考Norm and inner products in C^n

矩阵

线性代数和矩阵论概念。

方阵：行数和列数相同的矩阵，如n\times n矩阵A，又称n阶方阵。对角线是左上角到右下角的连线。A的行列式是其n个特征值之积。A的迹是n个特征值之和。

单位矩阵：主对角线全是1而其他元素全是0的方阵，如I_n矩阵。

可逆矩阵：非奇异方阵，当n\times n方阵A, \ B满足AB = BA = I_n时，A和B为可逆矩阵，B称作A的逆矩阵，记作A^{-1}。可逆矩阵行列式非零。

转置矩阵：矩阵A的转置是以对角线为轴，将左下方和右上方的元素兑换。

对称矩阵：Symmetric Matrices，指转置矩阵为自身的方阵。A = A^T。

斜对称矩阵：又称反对称矩阵，指对角线全是0、转置矩阵和自身符号相反（加法逆元）的方阵。A^T = -A, \ a_{ij} = -a_{ji}。任一矩阵A，A^T - A为斜对称矩阵。

埃尔米特矩阵：Hermitian matrix，又称厄米特矩阵，厄米矩阵，自伴随矩阵。指对角线为实数的共轭对称的方阵，即方阵A \in C^{n\times n}的共轭转置等于自身，A = A^H。

斜埃尔米特矩阵：指对角线全是虚数、共轭转置与自身符号相反（加法逆元）的方阵。A^H = -A。

正定矩阵：Positive-definite matrix，又称正定阵。对称矩阵M \in R^{n\times n}是正定的，当且仅当对所有非零向量z都有z^TMz > 0。对称矩阵M \in C^{n\times n}是正定的，当且仅当对所有非零向量z都有z^HMz > 0。等价于M的所有特征值均为正。对应的有负定矩阵。

半正定矩阵：Positive semi-definite matrix，上述条件换为\ge，等级于特征值非负，对应的有半负定矩阵。

三角矩阵：上三角矩阵对角线左下方元素全是0。下三角矩阵对角线右上方元素全是0。是特殊方阵。

对角矩阵：Diagonal matrix，除主对角线外全是0的方阵，对角线上元素不必非零。对角矩阵是对称矩阵、上三角矩阵、下三角矩阵。单位矩阵、零矩阵、一维矩阵为对角矩阵。如对角矩阵diag(a_1,...,a_n)的特征值为a_1,...,a_n，对应的特征向量为单位向量e_1,...,e_n。

数量矩阵：对角线上元素皆相等的对角矩阵。单位矩阵、零矩阵为数量矩阵。

可对角化矩阵：若一个方阵A相似于对角矩阵，即存在可逆矩阵P使得P^{-1}AP是对角矩阵，则A是可对角化的。

三对角矩阵：除对角线、对角线低一行、对角线高一行外全是0的方阵。是海森堡矩阵。

行阶梯行矩阵：Row Echelon Form，所有非零行（至少有一个非零元素的行）在全零行上方，非零行首项系数（leading coefficient，也称主元，左边首个非零元素）严格比上方行的首项系数更靠右。

简约行阶梯形矩阵：Reduced row echelon form，又称简化列阶梯型矩阵，行规范形矩阵（Row canonical form）。每行首项系数是1，且是其所在列唯一非零元素。

增广矩阵：线性方程组系数矩阵右侧加上方程组等号右边的常数列。

旋转矩阵：Rotation matrix，在乘以一个向量的时改变向量的方向但不改变大小并保持了手性的矩阵。是行列式为1的正交矩阵。可表示为斜对称矩阵A的指数。

下列关于方阵A的命题等价：

  • A可逆/逆矩阵存在。
  • det(A) \ne 0。
  • rank(A) = n。
  • A的任一特征值\lambda_i非零。
  • A^TA可逆。

酉矩阵

酉矩阵（又称幺正矩阵，unitary matrix），在线性代数中，指其共轭转置恰为其逆矩阵的复数方阵。

U^*U=UU^*=I_n, \ U^{-1}=U^*

其中，U^*为U的共轭转置，U^{-1}为U的逆矩阵，I_n为n\times n单位矩阵。

所有特征值（复数）模长为1：|\lambda_n| = 1。

行列式（复数）模长为1：|det(U)| = 1。

对于复向量x,y，酉矩阵U有：

  • 点积（内积的一种特殊形式，运算结果为标量）：(Ux) \cdot (Uy) = x \cdot y。
  • 希尔伯特内积：\langle Ux,Uy\rangle = \langle x,y\rangle。
  • 酉矩阵和酉矩阵的矩阵乘还是酉矩阵。
  • U的列向量是C^n上的一组正交基，行向量也是。

正交矩阵

orthogonal matrix，实数方阵Q，且行向量与列向量皆为正交的单位向量，转置矩阵为其逆矩阵。是实数化的酉矩阵。

Q^TQ=QQ^T=I, \ Q^{-1}=Q^T

其中，Q^T为Q的转置，Q^{-1}为Q的逆矩阵，I为单位矩阵。

行列式值为+1或-1。

正规矩阵

Normal matrix，指与自己共轭转置在乘法下满足交换律的方阵。若为实矩阵，共轭转置改为转置。

A^HA = AA^H

正规矩阵可做酉对角化（unitary diagonalisation）A = UDU^*，其中U是酉矩阵，D是对角矩阵。反之亦然。酉矩阵、埃尔米特矩阵、斜埃尔米特矩阵、对角矩阵是正规矩阵。

矩阵变换

矩阵转置

实矩阵转置写作A^T，有(AB)^T = B^TA^T。

\begin{array}{left} Y = A * X -> DY/DX = A^T \\ Y = X * A -> DY/DX = A^T \\ Y = A * X * B -> DY/DX = A^T * B^T \\ Y = A * X^T * B -> DY/DX = B * A \end{array}

复数矩阵共轭转置（Conjugate transpose），又称埃尔米特转置（Hermitian transpose），写作：A^H。

矩阵求逆

可逆矩阵A的逆矩阵（又称反矩阵）写作A^{-1}。若A可被特征分解且特征值中不含零（非奇异矩阵），则：

A^{-1} = Q\Lambda^{-1}Q^{-1}

其中，Q为特征向量（列）构成的正交矩阵，\Lambda为特征值构成的对角矩阵。[\Lambda^{-1}]_{i,i} = \frac1{\lambda_i} = \frac{1}{\Lambda_{i,i}}。

任一矩阵都有Moore-Penrose广义逆（伪逆）。对于任一矩阵A \in C^{m\times n}，若X满足：

  1. AXA = A
  2. XAX = X
  3. (AX)^H = AX
  4. (XA)^H = XA

则称X是A的Moore-Penrose广义逆，且唯一，记作A^\dagger。若X只满足其中某一或几条，则称为i-逆，记作A^{(i)}，如1-逆（A^{(1)}），1,2,4-逆（A^{(1,2,4)}）。

吉文斯旋转

Givens rotation，又称吉文斯变换，主要用于在矩阵中介入0，可用于QR分解，易并行计算。吉文斯旋转矩阵G(i,j,\theta)为n阶方阵（作用于n\times k矩阵A），除以下元素外全为0：
G_{k,k} = 1\ for\ k \ne i,j \\ G_{i,i} = G_{j,j} = cos(\theta) = c \\ G_{i,j} = sin(\theta) = s \\ G_{j,i} = -sin(\theta) = -s
吉文斯旋转矩阵G(i,j,\theta)左乘矩阵A时G(i,j)A，只会改变A的i,j行。是正交矩阵。

实际不必计算\theta，计算出c,s即可。如需将A_{j,k}变为0，可将c,s以及A_{i,k},A_{j,k}（记为a,b）提取出来：
\left[ \begin{matrix} c & s\\ -s & c \end{matrix} \right] \left[ \begin{matrix} a\\ b \end{matrix} \right] = \left[ \begin{matrix} r\\ 0 \end{matrix} \right]
然后，可得c,s的解（不唯一）。同时c,s会作用在A的i,j行的其他元素上，改变其值。

参考资源：

雅可比旋转

Jacobi旋转，又称Jacobi算法，用来将n阶实对称矩阵A^0非对角线元素置零，是特征值分解的核心运算，易并行计算。雅可比旋转矩阵J(i,j,\theta)定义同吉文斯旋转矩阵G(i,j,\theta)。

A^1=J(i,j)^TA^0 J(i,j)

若令[A^{1}]_{i,j} = [A^{1}]_{j,i} = 0，可以计算出c,s，进而计算出其他元素变换后的值。实际使用中，无需计算出c,s，可以利用中间值来计算其他元素变换后的值。

  • A^1仍为对称矩阵。
  • off(A^1) = off(A^0)-2[A^0_{i,j}]^2，其中off(A^0)表示A^0非对角线元素的平方和。

雅可比算法从A^0=A,\ U^0=I_n出发，反复作雅可比变换。

  • 在第k步中，已有A^{k-1}，求其非对角线元素绝对值最大者(i_k,j_k)，根据雅可比旋转算法求出A^{k}。
  • 如此重复，直到A^{k}非对角线元素绝对值最大值小于预设值。A^{k}收敛到一个对角阵，且对角线元素为A的特征值。

此法收敛较快，但是寻找非对角线元素绝对值最大者较耗时，所以有改进算法

高斯消元法

Gaussian Elimination，又称高斯消去法，可将矩阵转化为行阶梯形矩阵。用于线性方程组求解、矩阵求秩、矩阵求逆。做法是依次将第i+1行的前i个元素消除，具体的：

  1. 将其他任一行缩放后，加到第i+1行上，使得第0个元素为0，然后同样操作直到前i个元素都为0。最终得到一个行阶梯形矩阵。
  2. 对于线性方程组的增广矩阵，得到其行阶梯型形矩阵后，可以从下至上，依次求解出变量。

矩阵分解

EVD分解

特征值分解（Eigen Value Decomposition，EVD），也称作特征分解、相似对角化分解，只有对角化矩阵才可以特征值分解。

Aq_i = \lambda q_i

其中，A \in R^{n\times n}为可对角化矩阵，q_i为n维非零向量（不必标准化）。称\lambda_i为A的一个特征值，q_i该特征值对应的特征向量。几何意义是特征向量被施以矩阵变换A，只会在长度上缩放。

对于A的n个特征值\{\lambda_1, \lambda_2,...,\lambda_n \}和n个特征向量\{q_1, q_2,...,q_n \}，若n个特征向量线性无关，则A的特征值分解为

A = Q\Lambda Q^{-1}

其中，Q = [q_1, q_2,...,q_n], \ \Lambda = diag(\lambda_1, \lambda_2,...,\lambda_n)。

对于实对称矩阵SVD，可将n个特征向量标准化（q_i^Tq_i = 1），构成正交矩阵（Q^TQ = I, Q^T = Q^{-1}），则A = Q\Lambda Q^T。

对于复正规矩阵SVD，有一组正交特征向量，构成酉矩阵U，则A = U\Lambda U^H。

求解EVD，此处以实矩阵为例：
p(\lambda) = det(\lambda I - A) = 0
称为矩阵的特征多项式、特征方程，是未知数\lambda的n次多项式，每个特征值都有一个特征多项式。

直接求解特征多项式较难，一般通过迭代算法实现。

参考资源：

SVD分解

常见的矩阵分解有奇异值分解，Schur分解，特征值分解（针对可对角化矩阵），Jordan分解（针对不可对角化矩阵）等。奇异值分解(Singular Value Decomposition，SVD)可用于解线性方程组、线性最小二乘、Moore-Penrose广义逆，还可用于降维算法中的特征分解、推荐系统、NLP等领域。

任意矩阵A \in C^{m \times n} \ (m \ge n)，存在酉矩阵U \in C^{m \times m},\ V \in C^{n \times n},\ U^HU=UU^H=I_m,\ V^HV=VV^H=I_n，对角矩阵\Sigma \in R^{m\times n}，使得A = U\Sigma V^H。

其中，

\Sigma = \left[ \begin{matrix} \Sigma_n \\ 0 \end{matrix} \right] \\ \Sigma_n = diag(\sigma_1, \sigma_2, ...\sigma_n)

\sigma_1 \ge \sigma_2 ... \ge \sigma_n \ge 0=0...=0 \ (m-n个0)为A的奇异值。

U = [u_1, u_2, ..., u_m], \ V = [v_1, v_2, ..., v_n]中u_i, v_i（列向量）为奇异值\sigma_i对应的左奇异向量和右奇异向量，统称奇异向量。

A = U\Sigma V^H = \sigma_1 u_1 v_1^H + \sigma_2 u_2 v_2^H + ... + \sigma_m u_m v_m^H

若m \le n，则
\Sigma = [\Sigma_m \ 0]\in R^{m\times n} \\ \Sigma_m = diag(\sigma_1, \sigma_2, ...\sigma_m)
若A \in R^{m \times n}为实矩阵，则将共轭转置A换位转置，即A = U\Sigma V^T

奇异值与特征值的关系：

  • 只有方阵才有特征值和特征向量，但任一矩阵都有奇异值和奇异向量。
  • 矩阵的特征值可能是复数（即使实数矩阵），但奇异值必是非负实数（即使复数矩阵）。
  • A的奇异值\{\sigma_1, \sigma_2, ...\sigma_n\}为A^H A \in C^{n \times n}特征值的平方根。同时\{\sigma_1, \sigma_2, ...\sigma_n, 0,...,0\}为A A^H \in C^{m \times m}特征值的平方根（非零部分相同）。
  • 对于方阵来说，任一特征值\lambda和奇异值有\sigma_m \le |\lambda| \le \sigma_1。
  • 对于对称（或埃尔米特）半正定（或正定）矩阵，奇异值和奇异向量就是特征值和特征向量，即EVD是SVD的特殊情况。

SVD的几何意义是A在一系列旋转和平移下（U,V）转换成一个对角矩阵\Sigma。旋转和平移是正交变换，所以SVD分解在数值计算上是稳定的，而特征值分解不稳定。

秩：rank(A) = rank(\Sigma)，\{\sigma_1, \sigma_2, ...\sigma_m\}中非零奇异值的个数就是矩阵的秩。假设秩为r，则A = U_r \Sigma_r V_r^H称作经济型SVD分解。

低秩逼近/截断SVD（truncated，tSVD）：若min\{\sigma_k,1\} \gg \sigma_{k+1}，则认为奇异值耗散很快，可用A_k = U_k \Sigma_k V_k^H近似A，近似误差和\sigma_{k+1}在一个量级。

求解SVD，此处以实矩阵为例：

A=U\Sigma V^T \Rightarrow A^T=V\Sigma^T U^T \Rightarrow A^TA = V\Sigma^T U^TU\Sigma V^T = V\Sigma^2V^T

所以，A^T A的特征向量组成的矩阵即V。类似的AA^T的特征向量组成的矩阵即U。特征值的平方根即奇异值\sigma_i = \sqrt{\lambda_i}

极分解

A = PW = WQ

其中，W是酉矩阵，P,Q是Hermite半正定矩阵。

根据SVD分解，A = U\Sigma V^H = U\Sigma U^H(UV^H) = (UV^H)V\Sigma V^H，得W = UV^H, \ P = U\Sigma U^H, \ Q = V\Sigma V^H。

参考资源：

格拉姆-施密特正交化

基：在线性代数中，如果内积空间上的一组向量能够组成一个子空间，那么这一组向量就称为这个子空间的一组基。
Gram-Schmidt Othogonalization提供了一种方法，能通过子空间的一组基得出一组正交基，并可进一步求出对应的标准正交基。

向量a在向量b上的投影：\frac{\langle a,b\rangle}{\langle b,b\rangle}b

基本想法是利用投影原理在已有正交基的基础上构造一个新的正交基，即用基向量a_n减去a_n在b_1,...,b_{n-1}（a_1,...,a_{n-1}对应的正交基）上的投影，即得到一个和b_1,...,b_{n-1}均正交的基向量b_n。单位化可得标准正交基\frac{b_n}{|b|}。
\begin{aligned} & b_0 = a_0 \\ & b_n = \sum_{i=1}^{n} \frac{\langle a_n,b_i\rangle}{\langle b_i,b_i\rangle}b_i \end{aligned}

相关代码：

  • numpy.linalg.qr(A)：使用QR分解构造一组正交基，封装了LAPACK 功能。
  • scipy.linalg.orth(A)：使用SVD构造一组正交基，封装了LAPACK 功能，相对稳定，但稍慢。
  • numpy.linalg.svd：SVD，封装了LAPACK 功能。
  • scipy.linalg.svd：SVD，封装了LAPACK 功能。

参考资源：

QR分解

实数矩阵A的QR分解是把A分解为A=QR。其中，Q是正交矩阵（Q^TQ = I），R是上三角矩阵。类似的有义A的QL, RQ和LQ分解。

更一般的，分解复数m \times n矩阵（m>n）为m \times n幺正矩阵（酉矩阵，即共轭转置为其逆矩阵的方阵，在仅考虑Q^*Q=I时，不必为方阵）和n \times n上三角矩阵。分解复数m \times n矩阵（m<n）为m \times m方阵和m \times n矩阵。

QR分解方法有：Givens旋转、Householder变换，以及Gram-Schmidt正交化等。

如矩阵A=[a\space b\space c]（a,b,c为列向量），基于Gram-Schmidt正交化得出Q = [q_1\ q_2\ q_3]，则A=QR为：
[a\ b\ c] = [q_1\ q_2\ q_3] \left[ \begin{matrix} q_1^Ta & q_1^Tb & q_1^Tc\\ & q_2^Tb & q_2^Tc \\ & & q_3^Tc \end{matrix} \right] \tag{2}

导数和微分

导数（derivative）和微分（differential）不同，可导（derivable）和可微（differentiable）是等价的。假设函数y = f(x)，定义域都是可微函数，导数的值域是导函数f'(x)，微分的值域是1-formf'(x)。给定y = f(x)，导数的几种表示：
f'(x)=y’=dy/dx=df/dx=d/dx(f)=Df(x)=Dxf(x)

’ (prime) 、D、d/dx看成是一种对 f 的作用，称作“微分算子”。对 f 微分表示对函数f(x)取导数。

导数：y = f(x)在(x_0,y_0)处的增量为Δx, Δy=f(x_0 + Δx) - f(x_0)（差分），若当 Δx → 0 时Δy/Δx的极限存在，则函数在x_0点可导，这个极限为在点x_0处的导数，记为f'(x0)，也即f'(x0) = lim Δy / Δx = lim [ f(x_0 + Δx) - f(x_0) ] / Δx，Δx → 0，也记作y'|x=x_0。

微分：在\Delta x → 0的极限状态下，用切线段近似曲线段，有Δx, dy = f'(x)Δx，令dx = Δx, dy = f'(x)Δx（微分，是一个线性函数）。此时f'(x) = \frac{dy}{dx}。

几何意义：

  • 微分：微小的变化量，局部范围内，用线性函数近似非线性函数，用切线段近似曲线段，在数学上称为非线性函数的局部线性化。dx,dy不仅表示\Delta x, \Delta y，同时有点(x,y)的位置含义。
  • 导数：切线的斜率，表示在某点处的变化率。

因为实数空间中不存在无穷小，即不存在点(x+dx, f(x+dx))。所以f'(x) = dy/dx不是商或分数，但有类似商的性质，如链式法则f'(x) = \frac{dy}{dx} = \frac{dy}{du}\frac{du}{dx}，逆函数定理f'(y) = \frac{dx}{dy} = \frac1{\frac{dx}{dy}}。

偏微分/偏导数：多元函数有多个变量，如果函数沿着其中一个变量的方向变化，其他变量保持不变时，微分和导数就是偏微分和偏导数。

矩阵求导

参考矩阵求导术和速查手册“The Matrix Cookbook”。

狄拉克delta函数

狄拉克 delta 函数

泰勒级数

泰勒公式：泰勒展开式、泰勒多项式。
泰勒级数：Taylor Series，级数就是无限项之和。
泰勒公式通过把【任意函数表达式】转换为【多项式】形式，是一种函数近似工具。使用f(x)在x = a处的导数来估计f(x)的信息，通常取a=0。

\begin{align} f(x)_{Taylor} &= \sum_{n=0}^{\infty} \frac{f^{(n)}(a)}{n!} \times (x - a)^n \\ &= f(a) + \frac{f'(a)}{1!}(x-a) + \frac{f^{(2)}(a)}{2!}(x-a)^2+ \cdots + \frac{f^{(n)}(a)}{n!}(x-a)^n + R_n(x) \end{align}

把泰勒展开式，扩展到无限项之后，就会出现收敛（Converge）和发散（diverge）。
收敛，在泰勒展开式被推广到无限项之后，整体式子对函数拟合的非常好，代入任何x，泰勒展开式的值趋近于函数值，如e^x的泰勒展开式。
发散，在泰勒展开式被推广到无限项之后，整体式子对函数拟合的只在部分定义域内非常好，如ln(x)的泰勒展开式（a=1）在x \in [0,2]范围内才能拟合函数（收敛半径），超过收敛半径后，拟合变差。说明（a=1）处的导数信息无法估计整个函数的信息。

傅里叶级数

Fourier Series，针对连续周期性的信号，转换为离散的频谱的叠加（求和）。即，周期性函数g(y)可分解为一些列正（余）弦函数之和。

将时间轴、频率轴分别看做x、y轴，对应z轴分别表示信号强度、振幅。有：

时域图像：沿着时间轴x，每个时间点对应的信号值z。
频域图像：又称频谱或振幅谱，即沿着频率轴y，每个频率点对应的振幅z。
相位谱：沿着频率轴y，每个频率点对应的距频率轴（时间轴0点）最近的波峰的相位差(-pi, pi]x。

任一正弦函数：s_n(t) = A sin(2\pi f t + \phi) = A sin(\phi)cos(2\pi f t) + A cos(\phi)sin(2\pi f t) = a_n cos(2\pi f t) + b_n sin(2\pi f t)

其中，f为正弦函数频率（广义频率可正可负，正值表示顺时针，负值表示逆时针），\phi为初始相位，A为幅度（纵轴），t为时间（横轴）。

傅里叶级数为：

g(t) = \frac{a_0}{2} + \sum_{n=1}^{N}{a_n}cos(2\pi f n t) + \sum_{n=1}^{N}{b_n}sin(2\pi f n t)

也可以写作：

g(t) = \frac{a_0}{2} + \sum_{n=1}^{N}{a_n}sin(nwt+\phi_n) = \frac{a_0}{2} + \sum_{n=1}^{N}{a_n}cos(nwt) + \sum_{n=1}^{N}{b_n}sin(nwt)

其中，g(t)为连续周期函数，\frac{a_0}{2}为垂直分量（波形质心在垂直方向的偏移量，标准正/余弦的垂直分量为0），w为角速度（角频率），即频率f乘以2\pi，t为时间。1, cos(nwt), sin(nwt)构成了一组正交基。

提示：向量正交则内积为0，周期函数正交则函数乘积的积分为0。向量与自己的内积为常数，周期函数与自己乘积的积分为常数（一个周期内积分为1）。

因为傅里叶级数里各项之间都正交，为了计算a_n，公式两边同时乘以cos(2\pi f n t)，然后积分，右侧只保留了a_n部分。同样可求b_n。因此有：
a_n = 2f\int_{t0}^{t0+\frac1f} g(t) cos(2\pi f n t) dt \\ b_n = 2f\int_{t0}^{t0+\frac1f} g(t) sin(2\pi f n t) dt

复频域傅里叶级数。利用欧拉公式以及共轭复数和为实数的性质，将复频域级数转化为三角级数来求解。g(t)为连续周期函数（实数域）。

g(t) = \sum_{n=-N}^{N}c_n e^{i 2\pi f n t} = \sum_{n=-N}^{N}{c_n}cos(2\pi f n t) + \sum_{n=-N}^{N}{c_n}i sin(2\pi f n t)

具体的，[1,N]转换为[- N,N]，c_n = p + iq, (n>0); c_n = p - iq, (n<0)，系数共轭的两项相加，有：

(p-iq)(cos(2\pi f n t) + i sin(2\pi f n t)) + (p+iq){c_n}(cos(2\pi f n t) + i sin(2\pi f n t)) = 2pcos(2\pi f n t) -2qsin(2\pi f n t)

可得，p = \frac{a_n}2, q = -\frac{b_n}2，即：

c_n = \frac{1}2(a_n - i b_n), (n>0); c_n = \frac{a_0}2, (n=0); c_n = c_{|n|}^*, (n<0)

在复频域上e^{i 2\pi f n t}也具有正交性，于是有：

c_n = f \int_{t0}^{t0+\frac1f} g(x) e^{(-i 2\pi f n t)} dt

过冲：使用不同频率的正（余）弦函数拟合周期函数，在周期函数的不连续点会出现过冲，即使频域扩展到无穷，过冲也不会降为零的。

一般情况下，傅里叶级数里N取\infin。

傅里叶变换

Fourier Transform（FT），即连续傅里叶变换，时傅里叶级数的推广。针对连续非周期性的信号（可以理解为周期无限大），转换为连续的频谱的累加（积分）。用复平面上的相位、振幅和旋转频率来表示信号曲线，傅立叶变换公式的联想链条：

  • 一个逆时针旋转360°画成的圆：e^{i2\pi}
  • 表示运动，需要原函数的自变量，时间t：e^{i2\pi t}
  • 表示旋转速度，需要自变量，频率 f：e^{i 2\pi f t}
  • 规定变换的采样方向为顺时针，加负号：e^{-i 2\pi ft}
  • 乘以原函数，将信号曲线缠绕到单位圆：g(t) e^{-i 2\pi ft}
  • 旋转频率和信号频率一致时，质心向量模长最大，为了计算质心特征，积分：\int_{-\infty}^{+\infty} g(t)e^{-i 2\pi \color{red}f\color{black} t}dt
  • 自变量为频率f，时域转频域的表达式：\hat g(\color{red}{f} \color{black}) = \int_{-\infty}^{+\infty} g(t)e^{-i 2\pi \color{red}f\color{black}t}dt

傅里叶变换得到的频域函数/值为复数，可以从中提取强度和相位信息。

傅里叶变换的逆变换（inverse Fourier Transform，iFT）为g(t) = \int_{-\infty}^{+\infty} \hat g(f)e^{i 2\pi ft}df。

FT和iFT式前的系数（上述均为1，规范化因子）是主观选择的，两者乘积为1即可（此时称归一化系数）。若用w代替2\pi f，则乘积为\frac1{2\pi}。

一般称g(t)为原函数，\hat g(f)为像函数，两者构成傅里叶变换对（Transform pair）。有时也写作f(t)和F(w)。

分数傅里叶变换：Fractional Fourier Transform（FRFT），做傅里叶变换a次（a未必为整数），变换后信号在介于时域和频域之间的分数域（Fractional domain）。

当g(t)为偶函数时，傅里叶变换的正玄分量消失，称为余玄变换（Cosine Transform）。反之依然，称为正玄变换（Sine Transform）。

提示：偶函数是关于y轴对称的函数f(x) = f(-x)。奇函数是关于原点对称的函数f(-x) = -f(x)。

连续傅里叶变换

一般情况下指傅里叶变换。

离散时间傅里叶变换

Discrete Time Fourier Transform（DTFT），用于连续函数的均匀间隔采样（实际的信号都是间隔采样得到的）。在时域上离散，在频域上则是周期的。可被看作是傅里叶级数的逆变换。

对于非周期时域序列\{x_n\}_{x \in (-\infty, +\infty)}，其DTFT为：

\hat g(e^{iw}) = \Sigma_{n=-\infty}^{+\infty} e^{-iwn} x_n

其逆变换（iDTFT）为：

x_n = \frac1{2\pi} \int_0^{2\pi} \hat g(e^{iw}) e^{iwn} dw

其中，\hat g()常被写作X()，角频率w=2\pi f。\hat g(e^{iw}) = \hat g(e^{iw + 2k\pi})为周期性函数，

离散傅里叶变换

Discrete Fourier Transform（DFT），傅里叶变换在时域和频域上都呈离散的形式，是离散时间傅里叶变换的特例（近似）。变换两端（时域和频域上）的序列是有限长的，这两组序列都应当被认为是离散周期信号的主值序列。可以将DFT看作经过周期延拓成为周期信号再作变换。

对于N点时域序列\{x_n\}_{0\le n\lt N}，其DFT为：

\hat x_k = \Sigma_{n=0}^{N-1} e^{-i 2\pi \frac{nk}N} x_n

得到N点频域序列\{x_k\}_{0\le k\lt N}。离散傅里叶变换的逆变换（iDFT）为：

x_n = \frac1N \Sigma_{k=0}^{N-1} e^{i 2\pi \frac{nk}N} \hat x_k

其中，

  • k为频域点的索引，n为时域点的索引。k取值[0,N-1]对应[0,2\pi]，[0,N/2]是正频部分，[N/2,N-1]是负频部分（由于正余弦函数的周期性，用[\pi,2\pi]代替[-\pi,0]，便于计算）。

  • x_n, x_k都是复数，x_n的虚数部分为0，实数部分是原始信号。

  • 若将复指数写为正余弦形式e^{-i2\pi nk/N} = cos(2\pi nk/N) - jsin(2\pi nk/N)，则实域频谱呈偶对称性（余弦波频谱），虚域频谱呈奇对称性（正玄波频谱）。

  • DFT和IDFT变换式中和式前面的归一化系数是主观选择的，有时会将式前的系数都改为\frac1{\sqrt N}。

这种DFT/iDFT方法利用了信号的相关性（Correlation），即：

  1. DFT，某个频率（k/N）的时域函数与时域序列\{x_n\}内积，如果频率出现在信号中（波形相似），则相关性大，内积值大（复数\hat x_k强度大）。反之，相关性小，内积值小（若正交则为0）。
  2. iDFT，所有频率（k/N）的时域函数与自身强度（\hat x_k）相乘后累加，即可得到时域序列\{x_n\}。

原函数在时域的离散对应于像函数在频域的周期性，在频域的离散对应在时域的周期性。反之，在一域的连续对应于在另一域的非周期性。在实际应用中，只有DFT不涉及连续（无限多），适合使用计算机计算。信号通常是有限长的、离散的（计算机中），把信号通过复值的方式无限延申，可以得到离散周期性信号，进而可用DFT做变换。通常采用快速傅里叶变换以高效计算DFT。

变换 时域信号 频域图像
连续傅里叶变换 连续，非周期性 非周期性，连续
傅里叶级数 连续，周期性 非周期性，离散
离散时间傅里叶变换 离散，非周期性 周期性，连续
离散傅里叶变换 离散，周期性 周期性，离散

离散傅里叶变换矩阵

Discrete Fourier transform matrix，可将DFT以矩阵乘法来表示。N点DFT可表示为X = Wx，其中x是原始的输入信号，X是DFT输出的信号，W是一个N\times N的变换矩阵W = (w^{ij})_{i,j=0,...,N-1}（ij表示i乘j），通常还会乘以归一化（正规化）系数1/N或1/sqrt(N)。w为N次单位根e^{-i \frac{2\pi}N}，即W_{i,j} = w^{ij} = e^{-i \frac{2\pi}N ij}。

iDFT的变换矩阵与DFT的变换矩阵类似，但N次单位根指数正负号相反，归一化系数与DFT的乘积为1/N。变换矩阵是DFT定义的矩阵实现，效率不如FFT。

快速傅里叶变换

Fast Fourier Transform（FFT），一种快速计算DFT/iDFT的方法，通过把DFT矩阵分解为稀疏（大多为零）因子之积来计算，计算复杂度O(nlogn)。而DFT定义中的计算利用的是相关性，计算复杂度O(n^2)。其中n为元素个数。

库利-图基算法（Cooley-Tukey）是最常见的FFT算法。这一方法以分治法为策略递归地将长度为N的DFT分解为多个较短的DFT，以及与O(N)个旋转因子的复数乘法。适用于长度为2^n的序列（2-FFT），或者长度N可因数分解形式的序列（混合基FFT）。实现上一般将递归算法改为非递归形式。

N次单位根W_N = e^{-i \frac{2\pi}N}（N次幂为1的复数，Primitive Nth root of unity），其周期为N，以N/2呈奇对称性，若m为N的约数，W_N^m = e^{-i \frac{2\pi}N m} = e^{-i \frac{2\pi}{N/m}} = W_{\frac N m}。

对于N点时域序列\{x_n\}_{0\le n\lt N}，频率k对应的DFT：
\begin{aligned} y_k &= \Sigma_{n=0}^{N-1} W_N^{kn} x_n \\ &= \Sigma_{n=2t} W_N^{kn} x_n + \Sigma_{n=2t+1} W_N^{kn} x_n \\ &= \Sigma_{t} W_{N/2}^{kt} x_{2t} + W_N^k\Sigma_{t} W_{N/2}^{kt} x_{2t+1} \\ &= F_{even}(k) + W_N^kF_{odd}(k) \end{aligned}
F_{even}(k),F_{odd}(k)只能计算出k\in[0,N/2]的频率（因为周期为N/2）。结合单位根奇对称性，后N/2个频率有：

y_{k+N/2} = F_{even}(k) - W_N^kF_{odd}(k)

这样，一个长度为N的DFT就变为2个N/2的DFT的加法和减法。

参考资料：

参考文献

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 205,236评论 6赞 478
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 87,867评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 151,715评论 0赞 340
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,899评论 1赞 278
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,895评论 5赞 368
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,733评论 1赞 283
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,085评论 3赞 399
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,722评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 43,025评论 1赞 300
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,696评论 2赞 323
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,816评论 1赞 333
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,447评论 4赞 322
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,057评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,009评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,254评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,204评论 2赞 352
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,561评论 2赞 343

推荐阅读更多精彩内容