浅谈一下Gram-Schmidt正交化

欢迎大家来到IT世界,在知识的湖畔探索吧!

线性代数作为一门被广泛应用在计算机领域的学科, 重要性不言而喻. 但很多人学完线代还是停留在解题的范畴内, 并未能将其应用到实际中. 本文讲解了线代中的Schmidt正交化及其简化正规方程的方法. 通过了解正交矩阵的概念及其应用来进一步理解线性代数的应用.

本篇目录

1. 什么是标准正交矩阵
2. 标准正交矩阵有什么用
3. 如何利用Gram-Schmidt法则得到一个正交矩阵

在正式开始前我想先补充一点基本知识, 以便于接下来的展开.

什么是正交?

正交其实就是垂直这一概念的拓展, 可以直接将其认为是垂直. 举个例子, 在二维空间中, 两个向量a,b正交就代表这两个向量之间的夹角为90, 也就是互相垂直. 在线性代数中, 若两向量点乘为0, 则这两个向量正交 (这个可以通过毕达哥拉斯定理证明).

为什么向量点积为0, 向量相互垂直?

欢迎大家来到IT世界,在知识的湖畔探索吧!

构建一个向量直角三角形, 三边关系为|A|^2 + |B|^2 = |C|^2 , C = A + B

利用模的平方等于向量与自己的点积这一特性, 带入发现唯有A^TB = 0 时直角三角形才成立, 由此可得向量点积为0时, 两向量垂直

什么是标准正交矩阵

如果一个矩阵的基(basis)由标准正交向量(orthonormal vector)构成, 我们则称该矩阵为标准正交矩阵.

q表示标准正交向量, Q表示标准正交矩阵. 矩阵中每一列与其他列的点积为0, 与自己的点积为1(向量与自己转置的点积是该向量模的平方)

根据上面的性质, 我们可以得知正交矩阵的转置和正交矩阵相乘会得到单位矩阵(注: 正交矩阵不一定是方阵)

正交矩阵的这个性质可以简化某些公式, 这也是为什么正交矩阵很重要的原因

标准正交矩阵有什么用

最常见的矩阵应用莫过于机器学习算法了. 比如线性回归算法, 以微积分为理论发展而出的梯度下降算法可以找到一组数据的最优解. 但是梯度下降算法有两个明显的缺点 1) 需要经历多轮迭代 2) 需要选择一个合适的学习率α. 而在线性代数中, 我们可以通过正规方程来一步到位的找到最优解.

正规方程:

θ是参数向量, X是设计矩阵, 由数据集构成. y则是结果集向量

其原理是将目标值y投影到设计矩阵X上, 得到最接近y的参数向量θ. 尽管正规方程在参数数量n较小的时候极为高效, 当n大于大约10^4数量级的时候, 正规方程的效率就不尽人意了. 原因是计算(X^TX)^-1的时间复杂度高达O(n^3), 当参数数量增大时, 时间成本呈三次递增. 而标准正交矩阵恰好解决了正规方程耗时的缺点, 简化了正规方程.

简化后的正规方程 :

有的人就会问这玩意怎么得出来的. 别急, 听我娓娓道来

首先, 原来的正规方程式是找到一个合适的θ将目标值y投影到数据集X上使得损失函数最小, 也就是最小二乘. 那如果我们将y投影到正交矩阵上会发生什么?

将X(数据集构成的矩阵)替换成Q(数据集对应的正交矩阵). 记得我在上面提到的正交矩阵的性质吗, 正交矩阵的转置和正交矩阵的乘积是单位矩阵 Q^TQ = I. 所以方程的左半边就剩下一个θ, 右半边不变.

这就是标准正交矩阵在正规方程中的用途啦. 它将时间复杂度为O(n^3)的矩阵运算直接简化掉了, 大大提升了使用正规方程的效率, 也让正规方程在参数数量庞大的情况下依旧有效.

有些人可能会问, 那什么样的正交矩阵才能替换原来由数据集构成的矩阵呢, 总不能任何一个正交矩阵都能替换吧. 没错, 这个正交矩阵必须在矩阵X的列空间内, 也就是说, 这个正交矩阵Q是通过矩阵X的基衍生出来的. 在同一向量空间内, 向量之间的线性组合仍旧处在该空间内, 所以我们将矩阵X中的向量正交化得出来的正交矩阵, 仍旧处于原来那个向量空间. 这也是为什么简化后正规方程得出来的参数θ可以被带回到原来的式子里. 因为正交化后的向量和原向量处在同一向量空间.

如何正交化

Gram-Schmidt正交化的具体过程如下:

来自百度

如图所示, 假设我们现在有两个线性无关且不正交的向量a和向量b, 我们需要得到新的正交向量A和B. p是b在a向量上的投影, 而e则是b和a之间的残差(实际值和观测值的差). 有A = p, B = e.

根据向量运算和子空间投影,

再在正交向量AB的基础上令它们除以自身的模长来获得最终的正交基A’和B’

正交矩阵Q就是由这两个正交基构成的矩阵.

同理, 如果引入第三个向量c, 则正交向量C等于c减去c在a上和b上的投影, 留下的部分与向量ab正交.