随着学习的深入，愈发感受到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分解的方式拥有更好的数值稳定性。
