我必须解决以下最小二乘问题： 其中\mathbf{L} \in \mathbb{R}^{n\times n}是O(n)稀疏下三角矩阵，\mathbf{I} \in \mathbb{R}^{n \times n}是身份和\mathbf{b} = \left[ \begin{smallmatrix} \mathbf{b}_1 \\ \mathbf{b}_2 \end{smallmatrix} \right] \in \mathbb{R}^{2n}。

$$\begin{equation} \| \left[ \begin{smallmatrix} \mathbf{L} \\ \mathbf{I} \end{smallmatrix} \right]\mathbf{x} - \mathbf{b} \|_2^2 \end{equation}$$ $\mathbf{L} \in \mathbb{R}^{n\times n}$$O(n)$$\mathbf{I} \in \mathbb{R}^{n \times n}$$\mathbf{b} = \left[ \begin{smallmatrix} \mathbf{b}_1 \\ \mathbf{b}_2 \end{smallmatrix} \right] \in \mathbb{R}^{2n}$

因此，通过前向替换算法求解单个系统$\mathbf{Lx} = \mathbf{b}_1$的复杂度为$O(n)$，但最小二乘拟合的成本很高。

我愿意接受任何建议，包括快速近似随机求解器等。当然，如果有人知道利用这种结构的直接方法，那将是完美的。