38.6.3 Large Dense Linear Systems Solution Steps

The typical steps required to solve large regularized linear least squares problems are as follows:

1. Choose the regularization matrix L.
2. Construct a block of rows of the least squares matrix, right hand side vector, and weight vector (X_i, y_i, w_i).
3. Transform the block to standard form (\tilde{X_i},\tilde{y_i}). This step can be skipped if L = I and W = I.
4. Accumulate the standard form block (\tilde{X_i},\tilde{y_i}) into the system.
5. Repeat steps 2-4 until the entire matrix and right hand side vector have been accumulated.
6. Determine an appropriate regularization parameter \lambda (using for example L-curve analysis).
7. Solve the standard form system using the chosen \lambda.
8. Backtransform the standard form solution \tilde{c} to recover the original solution vector c.