最小二乘求解前是否需先做QR分解以提升运算速度？

问题1：QR分解是否真的比常规最小二乘方法速度慢？ #

你的理解存在一个核心偏差：Strang提到的「基于正交基求解最小二乘很快」，指的是已经完成QR分解、拿到正交矩阵Q之后的求解步骤，只需要计算x̂ = Qᵀb再回代求解上三角矩阵R的线性方程，这个步骤确实非常高效，他并没有把QR分解本身的计算开销纳入这个结论的范围。
关于时间复杂度的对比可以参考这几个事实：

• 对于m行n列的设计矩阵A（绝大多数最小二乘场景下m>>n），两种方法的渐近时间复杂度属于同一量级，均为O(mn²)：常规方法计算AᵀA开销为O(mn²)，实际工业界根本不会直接求逆，而是对AᵀA做Cholesky分解，开销为O(n³)，总开销和Householder QR分解的O(mn²)基本持平，当n较大时QR的常数项表现反而更好。
• 你看到的「QR开销更高」的结论，一般只适用于n极小的极端场景，或者是错误地把「直接求逆」当成了常规实现方式，实际工程中几乎不会有人用直接求逆的方式计算最小二乘。
• 如果是固定A、多次求解不同b的场景，QR分解只需要做一次，后续每次求解仅需O(n²)开销，和基于AᵀA Cholesky分解的效率相当，但数值稳定性优势明显。

问题2：QR分解在最小二乘场景下只有提升数值稳定性的作用吗？ #

不是。除了核心的数值稳定性优势（避免AᵀA把病态矩阵的条件数平方放大，大幅降低解的误差）之外，还有几个不可替代的作用：

• 处理列秩亏场景：带列主元的QR分解可以直接检测矩阵的秩，同时自动给出最小范数的最小二乘解，而常规的AᵀA方法在秩亏时直接不可逆，需要额外计算伪逆，复杂度和稳定性都更差。
• 残差计算更便捷：拿到Q之后，最小二乘的残差可以直接用b - QQᵀb计算，不需要再代入原始矩阵A运算，精度更高。
• 支持增量更新：如果有新增的观测数据（即给A新增行），可以直接对已有的QR分解做增量更新，不需要从头重新计算，比基于AᵀA的方法高效得多。
• 方便做特征选择：带列主元的QR分解的交换矩阵可以直接用来做列子集选择，快速筛选出对拟合贡献最大的特征。

内容的提问来源于stack exchange，提问作者mathgeek