关于QR分解
随着学习的深入，愈发感受到QR分解的重要性，必须重写一篇博客来记录之。 QR分解的具体定义如下：
对于任意方阵
A
A
A， 有：
A
=
Q
R
A = QR
A=QR
其中，
Q
Q
Q是一个正交矩阵，
R
R
R是一个上三角矩阵。 此外，若
A
\mathbf{A}
A为长方形矩阵，即行数大于列数，则有：
A
=
Q
R
=
Q
[
R
1
0
]
=
[
Q
1
Q
2
]
[
R
1
0
]
=
Q
1
R
1
A=Q R=Q\left[\begin{array}{c} R_{1} \\ 0 \end{array}\right]=\left[\begin{array}{ll} Q_{1} & Q_{2} \end{array}\right]\left[\begin{array}{c} R_{1} \\ 0 \end{array}\right]=Q_{1} R_{1}
A=QR=Q[R10]=[Q1Q2][R10]=Q1R1
其中
R
1
R_1
R1是一个上三角矩阵。
我们首先通过QR分解的常见实现，施密特正交化 （Gram–Schmidt process）来深入理解为什么对于任意矩阵都存在这样的分解。 首先从
A
A
A的第一列
a
1
a_1
a1出发，将其归一化得到第一个“基” 作为
Q
Q
Q的第一列，即:
q
1
=
a
1
∥
a
1
∥
q_1 = \frac{a_1}{\|a_1\|}
q1=∥a1∥a1，
那么对于第二列
a
2
a_2
a2，其可以被分为平行于
q
1
q_1
q1和正交于
q
1
q_1
q1 的两部分，我们可以将正交的这一部分作为第二个“基”成为
Q
Q
Q的第二列，它可以通过从
a
2
a_2
a2中减去平行于
q
1
q_1
q1的部分归一化得到，也即：
t
=
a
2
−
(
q
1
T
a
2
)
q
1
,
q
2
=
t
∥
t
∥
t = a_2 - (q_1^Ta_2)q_1 ,\quad q_2 = \frac{t}{\|t\|}
t=a2−(q1Ta2)q1,q2=∥t∥t
容易验证，
q
1
T
t
=
q
1
T
a
2
−
q
1
T
q
1
(
q
1
T
q
2
)
=
0
(
q
1
T
q
1
=
1
)
q_1^Tt=q_1^Ta_2 - q_1^Tq_1(q_1^Tq_2)=0 (q_1^Tq_1=1)
q1Tt=q1Ta2−q1Tq1(q1Tq2)=0(q1Tq1=1)，也即
q
2
q_2
q2与
q
1
q_1
q1正交。因此，若
A
A
A就是个
2
×
2
2\times 2
2×2的矩阵，我们有：
A
=
[
q
1
q
2
]
[
∥
a
1
∥
q
1
T
a
2
0
∥
t
∥
]
A = [q_1\; q_2]\left[\begin{array}{cc} \|a_1\| & q_1^Ta_2 \\ 0 & \|t\| \end{array}\right]
A=[q1q2][∥a1∥0q1Ta2∥t∥]
其中，
∥
a
1
∥
\|a_1\|
∥a1∥可视为
a
1
a_1
a1投影到
q
1
q_1
q1上的分量，
q
1
T
a
2
q_1^Ta_2
q1Ta2和
∥
t
∥
\|t\|
∥t∥可视为
a
2
a_2
a2分别投影到
q
1
q_1
q1和
q
2
q_2
q2上的分量。 显然，第一个矩阵是一个正交矩阵，而第二个矩阵是一个上三角矩阵。 上述结论很容易拓展到更大维度的矩阵的QR分解中。 具体而言，
Q
Q
Q的第三列即
a
3
a_3
a3将投影到
q
1
q_1
q1和
q
2
q_2
q2的分量减掉后的结果，以此来满足
q
1
q_1
q1，
q
2
q_2
q2和
q
3
q_3
q3间均严格正交的约束。 从中我们也可以看到， 如果
A
A
A的每一列线性独立，那么QR分解得到的
Q
Q
Q矩阵就是
A
A
A的列空间的一组正交基。
值得注意的是， m × n m\times n m×n矩阵的QR分解，复杂度为 2 m n 2 2mn^2 2mn2，低于奇异值分解。
QR分解与最小二乘求解
考虑如下的典型最小二乘问题：
min
β
∥
y
−
X
β
∥
2
\min_\beta \|\mathbf{y}-X \beta\|^{2}
βmin∥y−Xβ∥2
其中
X
X
X是一个长方形矩阵。
不妨假设结果为
β
^
\hat{\beta}
β^, 那么残差可以表示为：
r
=
y
−
X
β
^
\mathbf{r}=\mathbf{y}-X \hat{\boldsymbol{\beta}}
r=y−Xβ^
此时，对
X
X
X进行QR分解，可以得到：
X
=
Q
(
R
0
)
X=Q\left(\begin{array}{c} R \\ 0 \end{array}\right)
X=Q(R0)
对
r
\mathbf{r}
r两边都左乘
Q
T
Q^T
QT，得到:
Q
T
r
=
Q
T
y
−
(
Q
T
Q
)
(
R
0
)
β
^
=
[
(
Q
T
y
)
n
−
R
β
^
(
Q
T
y
)
m
−
n
]
=
[
u
v
]
Q^{\mathrm{T}} \mathbf{r}=Q^{\mathrm{T}} \mathbf{y}-\left(Q^{\mathrm{T}} Q\right)\left(\begin{array}{c} R \\ 0 \end{array}\right) \hat{\boldsymbol{\beta}}=\left[\begin{array}{c} \left(Q^{\mathrm{T}} \mathbf{y}\right)_{n}-R \hat{\boldsymbol{\beta}} \\ \left(Q^{\mathrm{T}} \mathbf{y}\right)_{m-n} \end{array}\right]=\left[\begin{array}{l} \mathbf{u} \\ \mathbf{v} \end{array}\right]
QTr=QTy−(QTQ)(R0)β^=[(QTy)n−Rβ^(QTy)m−n]=[uv]
注意到，最小二乘目标函数可以表示为：
∥
r
∥
2
=
r
T
Q
Q
T
r
=
u
T
u
+
v
T
v
\|\mathbf{r}\|^2 = \mathbf{r}^T\mathbf{Q}\mathbf{Q}^T\mathbf{r}=\mathbf{u}^{\mathrm{T}} \mathbf{u}+\mathbf{v}^{\mathrm{T}} \mathbf{v}
∥r∥2=rTQQTr=uTu+vTv
注意到
v
\mathbf{v}
v与
β
^
\hat{\beta}
β^无关，因此，最小化
∥
r
∥
2
\|\mathbf{r}\|^2
∥r∥2即令
u
=
0
\mathbf{u}=0
u=0，也即：
R
β
^
=
(
Q
T
y
)
n
R \hat{\boldsymbol{\beta}}=\left(Q^{\mathrm{T}} \mathbf{y}\right)_{n}
Rβ^=(QTy)n
这是一个简单的线性方程组，且注意到
R
R
R是上三角矩阵，因此
β
^
\hat{\boldsymbol{\beta}}
β^可以非常容易地得到，几乎不需要任何的计算复杂度。因此，该方法的计算复杂度主要来自于QR分解。
我们再对比一下传统的最小二乘最优解，可以通过求导令结果为0获得，即：
β
^
=
(
X
T
X
)
−
1
X
T
y
=
X
+
y
\hat{\boldsymbol{\beta}}=\left(\mathbf{X}^{\mathrm{T}} \mathbf{X}\right)^{-1} \mathbf{X}^{\mathrm{T}} \mathbf{y}=\mathbf{X}^{+} \mathbf{y}
β^=(XTX)−1XTy=X+y
相较之下，两者的复杂度是类似的。 QR分解的复杂度为
2
m
n
2
2mn^2
2mn2，而计算
(
X
T
X
)
−
1
\left(\mathbf{X}^{\mathrm{T}} \mathbf{X}\right)^{-1}
(XTX)−1也需要差不多这个级别的复杂度。但是QR分解的方式拥有更好的数值稳定性。
