# Least Squares: basic solution / iterative refinement

Calculating the basic solution to the least squres problem (Algorithm 5.7.1 from Matrix Computations - Golub/VanLoan)

$$min_x |\mathbf{Ax}-\mathbf{b}|$$

with $$A \in \mathbb{R}^{m \times n }$$ and $$m , using a pivoted QR decomposition,

$$\mathbf{Q}^T \mathbf{A} \mathbf{P}= \left[\mathbf{R_1}\, \mathbf{R_2}\right]$$,

end in a solution for the coefficients:

$$\mathbf{x}_b = \mathbf{P} (\mathbf{R_{1}\backslash c \,\,0})$$

with $$\mathbf{c} = \mathbf{Q}^T \mathbf{b}$$.

Is there an iterative refinement procedure for this basic solution, keeping the sparity of $$\mathbf{x_b}$$, while enhancing the accuracy of the solution?

• Do you mean $A^Tx-b$? Because I'm not sure your $Q^T$ and $b$ are compatible the way you have written things. Also, why do you expect $x_b$ to be sparse? – tch May 27 at 16:50
• Corrected the matrix dimensions. – JaW. May 28 at 7:07
• What about the usual refinement approach, compute the residual $r=b-Ax$ and solve $A\Delta x=r$ using the same factorization? – LutzL May 29 at 6:32
• Thought about it, but does it keep the sparsity of the basic solution? – JaW. May 29 at 10:13