是否应该在最小二乘法之前计算 QR 分解以加快该过程？

Question

我正在阅读 Gilbert Strang 的书“线性代数导论”。该部分称为“Orthonormal Bases and Gram-Schmidt”。作者多次强调，使用标准正交基计算最小二乘解非常容易且快速，因为 Qᵀ*Q = I，其中 Q 是设计矩阵正交基。所以你的等式变成 x̂ = Qᵀb.

我的印象是每次在应用最小二乘法之前计算 QR 分解是个好主意。但后来我想出了 QR 分解的结果是计算 QR 分解然后应用最小二乘法比常规 x̂ = inv(AᵀA)Aᵀb.

更昂贵

使用 QR 分解来加速最小二乘是没有意义的吗？还是我搞错了？
所以关于最小二乘的QR分解的唯一目的是数值稳定性？

Answer 1

有很多方法可以做最小二乘；通常这些在适用性、准确性和速度方面有所不同。

也许劳斯莱斯的方法就是使用SVD。这可用于求解欠定（obs 少于状态）和奇异系统（其中 A'*A 不可逆）并且非常准确。也是最慢的。

QR 只能用于求解非奇异系统（即我们必须有 A'*A 可逆，即 A 必须是满秩的），虽然可能不如 SVD 准确也是一个很好的交易更快。

正规方程即

compute P = A'*A
solve P*x = A'*b

是最快的（如果 P 可以有效计算，例如如果 A 是稀疏的，则可能有很大的余量）但也是最不准确的。这也只能用于解决非奇异系统。

不应轻视不准确之处，也不应将其视为学术幻想。如果你碰巧知道 ypu 将要解决的问题表现得很好，那么使用不准确的方法可能会很好。但否则不准确的例程很可能会失败（即说没有解决方案，或者更糟的是提出一个完全虚假的答案）。

我很困惑，您似乎建议在执行 QR 分解后形成和求解正规方程。在最小二乘法中使用 QR 的通常方法是，如果 A 是 nObs x nStates：

    decompose A as A = Q*(R ) 
                         (0 )
    transform b into b~ = Q'*b
    (here R is upper triangular)
    solve R * x =  b# for x, 
    (here b# is the first nStates entries of b~)

是否应该在最小二乘法之前计算 QR 分解以加快该过程？

Should one calculate QR decomposition before Least Squares to speed up the process?

performance

big-o

linear-algebra

least-squares

numerical-computing