I have to solve the following least squares problem:\begin{equation}\| \left[ \begin{smallmatrix} \mathbf{L} \\ \mathbf{I} \end{smallmatrix} \right]\mathbf{x} - \mathbf{b} \|_2^2\end{equation}where $\mathbf{L} \in \mathbb{R}^{n\times n}$ is $O(n)$ sparse lower triangular matrix, $\mathbf{I} \in \mathbb{R}^{n \times n}$ is the identity and $\mathbf{b} = \left[ \begin{smallmatrix} \mathbf{b}_1 \\ \mathbf{b}_2 \end{smallmatrix} \right] \in \mathbb{R}^{2n}$.Hence, solving individual system $\mathbf{Lx} = \mathbf{b}_1$ is of $O(n)$ complexity, by the forward substitution algorithm, but the least squares fit is expensive. I am open to any suggestion, including fast approximate stochastic solvers etc. Of course, it would be perfect if one is aware of a direct method that exploits this kind of structure.
Large scale triangular least squares
linear solver;sparse;least squares