Linear Algebra(8):正交性

线性代数

正交性

正交基和标准正交基

描述空间的一个重要方式除了维度以外就是基，基是一组向量，这组向量的个数就是这个空间的维度. 而一个n维空间任何一组线性无关的向量都是这个n维空间的一组基.正因如此一个n维空间是有无数组基的.但实际为了研究方便，一般更倾向于正交基(下右)

首先两个向量互相垂直，称两个向量正交. 而一组向量，如果两两正交，则称为正交向量组. 正交非零向量组一定线性无关.

P ro f . 正交非零向量组一定线性无关 假设 v_{1}, v_{2}, v_{3}, .. v_{n} 是一组正交向量组 需证明 : k_{1} v_{1} + k_{2} v_{2} + k_{3} v_{3} + ... + k_{n} v_{n} = 0 只有零解 (k_{1} v_{1} + k_{2} v_{2} + k_{3} v_{3} + ... + k_{n} v_{n}) . v_{1} = 0. v_{i} k_{1} v_{1} . v_{i} + k_{2} v_{2} . v_{i} + + ... + k_{i} v_{i} . v_{i} + k_{n} v_{n} . v_{i} = 0 k_{i} v_{i} . v_{i} = 0 k_{i} ∣∣ v_{i} ∣ ∣^{2} = 0 ∣∣ v_{i} ∣ ∣^{2} > 0, k_{i} = 0 得证

因此，n个非零正交向量一定是n维空间的基.

如果一个空间的一组基两两正交，则称这组基为一组正交基.

如果一个空间的一组正交基，模均为1，则称这组基为一组标准正交基. 而一个空间的标准正交基依然有无数组：

一维投影

通常对于一个空间来说我们只能得到随便的一组基，前面讲了如何求四大子空间的维度和一组基，但是得到的那组基绝对不能保证他们是正交的，我们得到的这组基是什么样子是和给定的矩阵是密切相关的.

因此如果给定一个空间的一组基，我们希望进一步找到这个空间的一组正交基，进一步如何找到标准正交基？

以2维空间为例，如果给出任意一组基，如何得到一组正交基？需要借助投影：

这样就解决了2维空间如何找到一组标准正交基的问题，那么到3维空间以及n维空间呢？

高维投影和Gram-Schmidt过程

看看三维空间如何求正交基：

如上图左是一组三维空间的基 $u, v, w$ ,首先使用上面讲的一维投影处理其中的两个向量 $u, v$ 变成 $p_{1}, p_{2}$ , 此时 $p_{1}, p_{2}$ 相互正交，接着只需要将 $w$ 和 $p_{1}, p_{2}$ 垂直. 在 $w$ 向量末端引一条垂线垂直于 $p_{1}, p_{2}$ 组成的平面得到投影 $p$ ，此时和 $p_{1}, p_{2}$ 都垂直的向量就是绿色的 $w - p$ .

很容易发现 $a$ 是 $w$ 在 $p_{1}$ 的投影，而 $b$ 是 $w$ 在 $p_{2}$ 的投影.

a = \frac{w . p _{1}}{∣∣ p _{1} ∣ ∣ ^{2}} p_{1} b = \frac{w . p _{2}}{∣∣ p _{2} ∣ ∣ ^{2}} p_{2} w - p = w - \frac{w . p _{1}}{∣∣ p _{1} ∣ ∣ ^{2}} p_{1} - \frac{w . p _{2}}{∣∣ p _{2} ∣ ∣ ^{2}} p_{2}

因此最终结果：

p_{1} = u p_{2} = v - p_{v} = v - \frac{p _{1} . v}{∣∣ p _{1} ∣ ∣ ^{2}} p_{1} p_{3} = w - p_{w} = w - \frac{w . p _{1}}{∣∣ p _{1} ∣ ∣ ^{2}} p_{1} - \frac{w . p _{2}}{∣∣ p _{2} ∣ ∣ ^{2}} p_{2}

如果已知一组基： $v_{1}, v_{2}, v_{3}, \dots v_{n}$ , 求一组正交基：

p_{1} = v_{1} p_{2} = v_{2} - \frac{p _{1} . v _{2}}{∣∣ p _{1} ∣ ∣ ^{2}} p_{1} p_{3} = v_{3} - \frac{v _{3} . p _{1}}{∣∣ p _{1} ∣ ∣ ^{2}} p_{1} - \frac{v _{3} . p _{2}}{∣∣ p _{2} ∣ ∣ ^{2}} p_{2} p_{4} = v_{4} - \frac{v _{4} . p _{1}}{∣∣ p _{1} ∣ ∣ ^{2}} p_{1} - \frac{v _{4} . p _{2}}{∣∣ p _{2} ∣ ∣ ^{2}} p_{2} - - \frac{v _{4} . p _{3}}{∣∣ p _{3} ∣ ∣ ^{2}} p_{3} ... p_{n} = v_{n} - ...

这个过程就叫做格拉姆-施密特过程，即Gram-Schmidt过程. 注意算法的输入是一组基，即线性无关的.

Gram-Schmidt过程就是给出一组基，求出另外一组基的过程.

有了正交基得到标准正交基就很简单：

\overset{u}{^} = \frac{1}{∣∣ u ∣∣} . u = (\frac{u _{1}}{∣∣ u ∣∣}, \frac{u _{2}}{∣∣ u ∣∣}, ..., \frac{u _{n}}{∣∣ u ∣∣})

代码实现Gram-Schmidt:

from .Vector import Vector
from .Matrix import Matrix
from .LinearSystem import rank

def gram_schmidt_process(basis):

    matrix = Matrix(basis)
    assert rank(matrix) == len(basis)

    res = [basis[0]]
    for i in range(1, len(basis)):
        p = basis[i]
        for r in res:
            p = p - basis[i].dot(r) / r.dot(r) * r
        res.append(p)
    
    return res

简单测试代码：

from LA.Vector import Vector
from LA.GramSchmidtProcess import gram_schmidt_process


if __name__ == "__main__":
    basis = [Vector([2,1]),Vector([1,1])]

    res1 = gram_schmidt_process(basis)
    for row in res1:
        print(row)

可见这组基是正交基.

标准正交基的性质

一组n维标准正交基 $v_{1}, v_{2}, v_{3}, \dots, v_{n}$ , 按照列的方式排成一个n阶方阵Q，称Q为标准正交矩阵. 之所以是方阵是因为标准正交矩阵的核心性质和幂有关，而只有方阵有矩阵的幂.

标准正交矩阵的重要性质：

Q^{T} . Q = I

证明：

P ro f . Q^{T} . Q = I Q = (v_{1} v_{2} ... v_{n}) Q^{T} . Q = v_{1} v_{2} ... v_{n} (v_{1} v_{2} ... v_{n}) = v_{1} . v_{1} v_{2} . v_{1} ... v_{n} . v_{1} v_{1} . v_{2} v_{2} . v_{2} ... v_{n} . v_{2} ... ... ... ... v_{1} . v_{n} v_{2} . v_{n} v_{n} . v_{n} = 10 ... 0 01 ... 0 ... ... ... ... 001 = I

Q的各列是线性无关的，可以得到Q是可逆的，而 $Q^{T}$ 是Q的左逆， $Q^{T}$ 就是Q的右逆， $Q^{T}$ 就是Q的逆.

因此对于标准正交矩阵来说：

Q^{- 1} = Q^{T}

机器学习算法的PCA降维将一个高维空间降为一个低维空间，反过来低维空间在转成高维空间就需要利用这条性质. 因为描述低维空间的方式就是一个标准正交矩阵，反过去的过程就需要看这个标准正交矩阵的逆.

矩阵的QR分解

上面标准正交矩阵的这个性质 $Q^{- 1} = Q^{T}$ 的一个应用就是矩阵的QR分解：

A = QR

其中Q就是标准正交矩阵，R是一个上三角矩阵.

为什么把矩阵分成Q,R和这样的形式？很多真实世界的问题本质就是 $A x = b$ 这样的线性系统，如果此时A可以分解为Q和R两部分：

(QR) x = b Q^{- 1} QR x = Q^{- 1} b R x = Q^{T} b

两边同时乘以 $Q^{- 1}$ ,此时方程就可以非常快的求解出来.

假设 $A = (a_{1} a_{2} \dots a_{n})$ ,对A的各个列向量执行Gram-Schmidt过程，得到 $p_{1}, p_{2}, p_{3}, \dots, p_{n}$ , 然后在进行规范化得到 $q_{1}, q_{2}, q_{3}, \dots, q_{n}$ .

而每个p的求法就是前面提到的Gram-Schmidt过程：

p_{1} = a_{1} p_{2} = a_{2} - \frac{a _{2} . p _{1}}{∣∣ p _{1} ∣ ∣ ^{2}} p_{1} p_{3} = a_{3} - \frac{a _{3} . p _{1}}{∣∣ p _{1} ∣ ∣ ^{2}} p_{1} - \frac{a _{3} . p _{2}}{∣∣ p _{2} ∣ ∣ ^{2}} p_{2} p_{4} = a_{4} - \frac{a _{4} . p _{1}}{∣∣ p _{1} ∣ ∣ ^{2}} p_{1} - \frac{a _{4} . p _{2}}{∣∣ p _{2} ∣ ∣ ^{2}} p_{2} - - \frac{a _{4} . p _{3}}{∣∣ p _{3} ∣ ∣ ^{2}} p_{3} ...

观察一下a,p,q的关系：

p_{1} = a_{1} = ∣∣ p_{1} ∣∣ q_{1} = r_{11} q_{1} p_{2} = a_{2} - \frac{a _{2} . p _{1}}{∣∣ p _{1} ∣ ∣ ^{2}} p_{1} = ∣∣ p_{2} ∣∣ q_{2} a_{2} = \frac{a _{2} . p _{1}}{∣∣ p _{1} ∣ ∣ ^{2}} p_{1} + ∣∣ p_{2} ∣∣ q_{2} = r_{21} q_{1} + r_{22} q_{2} p_{3} = a_{3} - \frac{a _{3} . p _{1}}{∣∣ p _{1} ∣ ∣ ^{2}} p_{1} - \frac{a _{3} . p _{2}}{∣∣ p _{2} ∣ ∣ ^{2}} p_{2} a_{3} = \frac{a _{3} . p _{1}}{∣∣ p _{1} ∣ ∣ ^{2}} p_{1} + \frac{a _{3} . p _{2}}{∣∣ p _{2} ∣ ∣ ^{2}} p_{2} + ∣∣ p_{3} ∣∣ q_{3} = r_{31} q_{1} + r_{32} q_{2} + r_{33} q_{3}

根据Gram-Schmidt过程把A化成一组正交基，然后化为标准正交基，那么反推回来A的各个列向量都可以写成这组标准正交基各个列向量的线性组合:

a_{1} = r_{11} q_{1} a_{2} = r_{21} q_{1} + r_{22} q_{2} a_{3} = r_{31} q_{1} + r_{32} q_{2} + r_{33} q_{3} a_{4} = r_{41} q_{1} + r_{42} q_{2} + r_{43} q_{3} + r_{44} q_{4} a_{n} = r_{n 1} q_{1} + r_{n 2} q_{2} + r_{n 3} q_{3} + ... + r_{nn} q_{n}

因此A可以写成n个矩阵相加的形式：

A = (a_{1} a_{2} ... a_{n}) = (r_{11} q_{1} r_{21} q_{1} + r_{22} q_{2} ... r_{n 1} q_{1} + r_{n 2} q_{2} + ... + r_{nn} q_{n}) = (r_{11} q_{1} r_{21} q_{1} .. r_{n 1} q_{1}) + (0 r_{22} q_{2} ... r_{n 2} q_{2}) + ... + (00 ... r_{nn} q_{n}) = (q_{1} q_{2} ... q_{n}) . r_{11} 0 ... 0 r_{21} r_{22} ... 0 ... ... ... ... r_{n 1} r_{n 2} ... r_{nn} = Q . R

前面的标准正交矩阵就是Q,后面的上三角矩阵是R,这样就实现了矩阵的QR分解.

相当于证明了方阵A的各个列向量线性无关的话能够进行矩阵的QR分解，进而通过Gram-Schmidt求出Q,然后通过正交矩阵性质求出R.

对于R,我们可以通过下面式子求得：

R = Q^{- 1} . A

代码实现QR分解：

def qr(A):
    assert A.row_num() == A.col_num(),"A must be square"

    basis=[A.col_vector(i) for i in range(A.col_num())]
    P = gram_schmidt_process(basis)
    Q = Matrix([v/v.norm() for v in P]).T()
    R = Q.T().dot(A)

    return Q, R

测试代码：

from LA.Matrix import Matrix
from LA.GramSchmidtProcess import qr


if __name__ == "__main__":
    A = Matrix([[1,1,2],[1,1,0],[1,0,0]])

    Q1,R1 = qr(A)
    print(Q1)
    print(R1)
    print(Q1.dot(R1))

上面打印结果正确.