Projection Gram-Schmidt and QR Factorization

Projection Gram-Schmidt and QR Factorization

从最小二乘法开始聊起。

我们都知道所谓最小二乘法,就是线性回归。

输入: \((\mathbf {x}_i, y_i), (i=1, 2, \ldots, m)\) 找到一条直线 \(\hat y = \mathbf {x}^T \mathbf {k}\) , 使得平方误差最小 (square root),这里 \(\mathbf {k}, \mathbf {x} \in \mathbb {R}^n\) ,即 \(n\) 维列向量,\(y_i\) 是标量

说简单点,找到直线系数 \(\mathbf {k}\) ,使得该直线的误差平方和最小 \[
\min_{\mathbf {k}} E = \sum_{i=1}^{m} (\mathbf {k}^T \mathbf {x}_i – y_i)^2
\]
显然,只有当方程的个数 \(m\) 大于未知数的个数 \(n\) 时,我们才需要使用最小二乘法进行直线拟合,不然我们可以直接求解出这条直线。

如果从矩阵的角度考虑,等价于寻找矩阵乘法的解: \[
A \mathbf {x} = \mathbf { b}
\]
为什么这么说 ?

因为这里 \(A\) 的每一行相当于上面的 \(\mathbf {x}_i^T\) \[
A =
\begin {bmatrix}
— & \mathbf {x}_1^T & — \\
— & \mathbf {x}_2^T & — \\
& \vdots & \\
— & \mathbf {x}_m^T & — \\
\end {bmatrix}
\]
我们这里要求解的 \(\mathbf {x}\) 相当于上面的直线系数 \(\mathbf {k}\)

那如何表示误差平方和呢 ? (利用向量内积, 因为 \(\mathbf {b}\) 的每一个元素都表示一个输出) \[
\min_{\mathbf {\hat x}} E = || \mathbf {b} – \mathbf { \hat b} ||^2 = ||\mathbf {b} – A \mathbf {\hat x}|| ^2
\]
这就引出了我们要介绍的问题:

投影施密特正交化QR 分解

1. 投影

根据前面学过的知识,我们知道 \(A\mathbf {x}\) 一定在 \(C(A)\) 子空间内。

原问题可以变为:

\(\mathbb {R}^n\) 中寻找一个列向量 \(\mathbf {\hat x}\) ,使得向量 \((\mathbf {b} – A \mathbf {\hat x})\) 的长度最小。或者说,在何种情况下,下图中的向量 \(\mathbf {e}\) 长度最小 ?

用优化理论表述为:
\[
\min_{\mathbf {\hat x} \in \mathbb {R}^n} \vert \vert \mathbf {b} – A \mathbf {\hat x} \vert \vert
\]

类似于点到直线的距离是垂线的长度,点到平面的距离是法向量的长度。我们可以得到,\(\mathbf {b}\) 到 列空间 \(C(A)\) 的最短距离是 \(\mathbf {b}\) 在 左零空间 \(N(A^T)\) 的投影长度,也就是说,满足要求的 \(\mathbf {\hat x}\) 为:

\[
A^T (\mathbf {b} – A \mathbf {\hat x}) = \mathbf {0}
\]
证明: 根据直和的定义有 \(\mathbb {R}^m = C(A) + N(A^T)\) , 因此 \(\mathbf {b} = \mathbf {u} + \mathbf {z}\) ,其中 \(\mathbf {u} \in C(A)\), \(\mathbf {z} \in N(A^T)\) , 于是 \[
\vert \vert \mathbf {b} – A \mathbf {\hat x} \vert \vert =
\vert \vert (\mathbf {u} – A \mathbf {\hat x}) + \mathbf {z} \vert \vert = \vert \vert \mathbf {u} – A \mathbf {\hat x} \vert \vert + \vert \vert \mathbf {z} \vert \vert \quad 因为 (\mathbf {u} – A \mathbf {\hat x}) \perp \mathbf {z}
\]

如果想要 \(\vert \vert \mathbf {b} – A \mathbf {\hat x} \vert \vert\) 最小,显然必须找到 \(\mathbf {\hat x}\) 满足 \(\mathbf {u} = A \mathbf {\hat x}\) ,

于是 \(\mathbf {b} – A \mathbf {\hat x} = \mathbf {z} \in N(A^T)\) , 即 \[
A^T (\mathbf {b} – A \mathbf {\hat x}) = \mathbf {0}
\]
将上面等式变形,得到: \[
A^TA \mathbf {\hat x} = A^T \mathbf {b}
\]
取逆,得到: \[
\mathbf {\hat x} = (A^T A)^{-1} A^T b
\]
那么什么时候可以说矩阵 \((A^TA)\) 是可逆的呢 ?

回答: 当矩阵 \(A\) 列满秩的时候,即 \(\mathrm {rank} (A) = n\) ,或者说 \(A\) 的列向量线性独立。

注: 如果仔细挖掘, \(A\) 存在两个列向量不是线性独立的,这种情况在线性回归中也称 “共线性”

此时,向量 \(\mathbf {b}\)\(C(A)\) 的投影向量 \(\mathbf {p} = A \mathbf {\hat x} = A(A^TA)^{-1} A^T b\)

我们得到了投影矩阵 (Projection Matrix) 的表达式: \[
P = A \mathbf {\hat x} = A(A^TA)^{-1} A^T
\]
它有如下两个性质:

  • It equals its square: \(P^2 = P\)
  • It equals its transpose: \(P^T = P\)

注: 如果感兴趣,还可以利用 矩阵偏导 找到误差平方和 \(E\) 取最小值对应的 \(\mathbf {\hat x}\),结论是相同的。

2. Gram-Schmidt orthogonalization

2.1 正交矩阵 (orthogonal matrix)

当矩阵 \(Q\) 满足 \(Q^TQ = I\) 时,矩阵 \(Q\) 称为正交矩阵 (orthogonal matrix)。

请注意: \(Q\) 不一定是方阵,它可以是普通矩阵

它的列向量满足如下关系: \[
\mathbf{q}_i^T \mathbf{q}_j = \begin{cases}
0, &\text{whenever } i \neq j ,\quad \text {giving the orthogonality}\\
1, &\text{whenever } i = j, \quad \text {giving the normalization}
\end{cases}
\]
关于正交矩阵的可以看看 特殊矩阵 的博客

这里多加一条性质: \(||Q \mathbf{x}|| = ||\mathbf{x} ||\) for any vector \(\mathbf{x}\) ,证明很简单。

结合上一小节的投影矩阵 \(P = A \mathbf {\hat x} = A(A^TA)^{-1} A^T\) ,我们当时非常想知道 \((A^TA)\) 是否可逆,而且 这个式子求解起来非常麻烦。

但现在,如果 \(A\) 是正交矩阵 \(Q\) ,那么 \(Q^TQ = I\) ,于是

投影矩阵: \(P = Q(Q^TQ)^{-1}Q^T = QI^{-1}Q^T = QQ^T\)

注意: \(Q^TQ\) is the \(n\) by \(n\) identity matrix, whereas \(QQ^T\) is an \(m\) by \(m\) projection \(P\) . It is the identity matrix on the columns of \(Q\), but \(QQ^T\) is the zero matrix on the orthogonal complement.

上面说出了 \(QQ^T\) 矩阵的两个性质:

  1. \(QQ^T\)\(Q\) 列空间的向量,效果和 \(I\) 是相同的
    \((QQ^T) (Q \mathbf{x}) = Q(Q^TQ)\mathbf{x} = Q\mathbf{x}\)
    这里 \((QQ^T)\) 效果和 矩阵 \(I\) 相同

  2. \(QQ^T\)\(Q\) 左零空间的向量, 效果和左零空间的正交空间的向量是相同的
    因为如果 \(Q^T \mathbf{b} = \mathbf {0}\) ,则 \((QQ^T) \mathbf{b} = Q (Q^T \mathbf{b}) = \mathbf {0}\)
    也就是说,对于左零空间的任何向量 \(\mathbf{b}\) , 都有 \(QQ^T\mathbf{b} = \mathbf{0}\)
    其实很好理解,\(QQ^T\) 的列空间 是 \(Q\) 的列空间的子集,

    • 它是投影矩阵,自然 \(QQ^T\) 会把任何向量投影到 \(Q\) 的列空间
    • \(QQ^T\) 的列向量是 \(Q\) 的列向量的线性组合

既然正交矩阵如此有效,如何从一个普通矩阵 \(A\) 得到 正交矩阵 \(Q\) 呢 ?

2.2 向量在正交系上的分解

对于线性方程组: \(Q\mathbf{x} = \mathbf{b}\) ,我们想要得到 \(\mathbf{x}\) ,其实对应着:

计算 系数 \(\mathbf{x}= [x_1, \ldots, x_n]^T\) 使得: \[
\mathbf{b} = x_1 \mathbf{q}_1 + x_2 \mathbf{q}_2 + \cdots + x_n \mathbf{q}_n
\]
其中 \(\mathbf{q}_i, i=1, \ldots, n\)\(Q\) 的列向量

根据前面的正交向量的定义,对上面的等式两边乘以 \(\mathbf{q}_i^T\) 可以得到: \(x_i = \mathbf{q}_i^T \mathbf{b}\) ,因为 \(\mathbf{q}_i^T \mathbf{q}_i = 1, \mathbf{q}_i^T \mathbf{q}_j = 0 (i \neq j)\)

不知道你看到这里有没有联想到什么 ?

有没有想到傅里叶变换的推导,如何利用正交函数系获得每个函数前的系数 其实用的也是相似的技巧。 \[
\mathbf{x} = Q^T \mathbf{b} = \begin {bmatrix} \mathbf{q}_1^T \mathbf{b} \\ \mathbf{q}_2^T \mathbf{b} \\ \vdots \\ \mathbf{q}_n^T \mathbf{b} \end {bmatrix}
\]
当然我们也可以直接利用 \(\mathbf{x} = Q^{-1} \mathbf{b} = Q^T \mathbf{b}\) 也得到相同的结论

这里我们将 \(Q\) 的列空间的任一个向量 \(\mathbf{b}\) 分解为它在正交向量系上的投影向量叠加。

2.3 施密特正交化

施密特正交化就利用了前面的知识

  1. 向量空间的任何向量都可以分解为两个正交子空间的向量之和
    \(\mathcal {X} = \mathcal {S} \oplus \mathcal {S}^{\perp}\), 则 \(\forall \mathbf {x} \in \mathcal {X}\), 可以找到 \(\mathbf {u} \in \mathcal {S}, \mathbf {v} \in \mathcal {S}^{\perp}\) ,使得 \(\mathbf {x} = \mathbf {u} + \mathbf {v}\)

  2. 任何一个子空间都可以找到一组正交基, 使得该空间的任何向量都可以分解为基的线性组合,并且利用内积运算可以很容易获得线性组合的系数

假设向量空间 \(A\) 有一组基 \([\mathbf{a}_1, \mathbf{a}_2, \ldots, \mathbf{a}_n]\) ,这里 \(\mathbf{a}_i \in \mathbb {R}^m\)

基于上面的结论,我们先取出 \(\mathbf{a}_1\), 对其归一化得到 \(\mathbf{q}_1\), 并且它在子空间 \(\text {span}(\mathbf{q}_1)\) 中,于是我们可以找到 \(\mathbf{v}\) 使得 \(\mathbf{a}_2 = \alpha_1 \mathbf{q}_1 + \mathbf{v}\), 其中 \(\mathbf{v} \in \text {span}(\mathbf{q}_1)^{\perp}\), 即 \(\mathbf{v} \perp \mathbf{q}_1\), 等式两边同乘 \(\mathbf{q}_1^T\) 得到 \(\alpha_1 = \mathbf{q}_1^T \mathbf{a}_2\), 于是 \(\mathbf{v} = \mathbf{a}_2 – (\mathbf{q}_1^2 \mathbf{a}_2) \mathbf{q}_1\), 对其归一化得到 \(\mathbf{q}_2\) , 由此得到子空间 \(\text {span}(\mathbf{q}_1, \mathbf{q}_2)\) , 依此类推下去,就可以得到一组正交基向量

那么: \[
A_j = \mathbf{a}_j – (\mathbf{q}_1^T \mathbf{a}_j) \mathbf{q}_1 – (\mathbf{q}_2^T \mathbf{a}_j) \mathbf{q}_2 – \cdots – (\mathbf{q}_{j-1}^T \mathbf{a}_j) \mathbf{q}_{j-1}
\]
其中 \(\mathbf{q}_j = A_j / ||A_j||\)

施密特正交化的问题在于 它不是数值稳定的。

3. QR Factorization

利用 高斯消去法,我们得到了 LU 分解。

利用施密特正交化,我们也可以得到 QR 分解。 \[
A_j = \mathbf{a}_j – (\mathbf{q}_1^T \mathbf{a}_j) \mathbf{q}_1 – (\mathbf{q}_2^T \mathbf{a}_j) \mathbf{q}_2 – \cdots – (\mathbf{q}_{j-1}^T \mathbf{a}_j) \mathbf{q}_{j-1}
\]
推出: \[
\mathbf{a}_j = (\mathbf{q}_1^T \mathbf{a}_j) \mathbf{q}_1 + (\mathbf{q}_2^T \mathbf{a}_j) \mathbf{q}_2 + \cdots + (\mathbf{q}_{j}^T \mathbf{a}_j) \mathbf{q}_{j}
\]
于是: \[
A = [\mathbf{a}_1, \mathbf{a}_2, \ldots, \mathbf{a}_n] = [\mathbf{q}_1, \mathbf{q}_2, \ldots, \mathbf{q}_n]
\begin {bmatrix}
\mathbf{q}_1^T \mathbf{a}_1 & \mathbf{q}_2^T \mathbf{a}_1 & \cdots & \mathbf{q}_n^T \mathbf{a}_1 \\
& \mathbf{q}_2^T \mathbf{a}_2 & \cdots & \mathbf{q}_n^T \mathbf{a}_2 \\
& & \ddots & \vdots \\
& & & \mathbf{q}_n^T \mathbf{a}_n
\end {bmatrix}
\]
\(A = QR\)

Every \(m\) by \(n\) matrix with independent columns can be factored into \(A=QR\). The columns of \(Q\) are orthonormal, and \(R\) is upper triangular and invertible. When \(m=n\) and all matrices are square, \(Q\) becomes an orthogonal matrix.

此时,\(A^TA = R^TQ^T QR = R^T R\)

我们计算之前的最小平方和误差的条件: \[
A^T (\mathbf {b} – A \mathbf {\hat x}) = \mathbf {0}
\]
等价于: \[
R^T Q^T \mathbf {b} = R^T R \mathbf {\hat x}
\]
即: \[
Q^T \mathbf {b} = R \mathbf {\hat x}
\]
因为 \(R\) 是 上三角矩阵,一定可逆

One thought on “Projection Gram-Schmidt and QR Factorization

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d 博主赞过: