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 <n$, 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?

  • $\begingroup$ 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? $\endgroup$ – tch May 27 at 16:50
  • $\begingroup$ Corrected the matrix dimensions. $\endgroup$ – JaW. May 28 at 7:07
  • $\begingroup$ What about the usual refinement approach, compute the residual $r=b-Ax$ and solve $A\Delta x=r$ using the same factorization? $\endgroup$ – LutzL May 29 at 6:32
  • $\begingroup$ Thought about it, but does it keep the sparsity of the basic solution? $\endgroup$ – JaW. May 29 at 10:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.