4
$\begingroup$

I am solving a problem using an iteratively-reweighted least squares method: http://en.wikipedia.org/wiki/Iteratively_reweighted_least_squares

Essentially this requires solving a number of least-squares problems of the form $$D_i A\vec x\approx D_i\vec b,$$ where each $D_i$ is a different diagonal weighting matrix.

Is there any way to pre-factor $A$ or do other calculations to speed up iterations of this algorithm? Right now, I'm resolving the least-squares problem from scratch during each iteration.

Improve this question
$\endgroup$
3
  • $\begingroup$ I assume the $D_{i}$ are strictly positive definite? $\endgroup$
    – Geoff Oxberry
    Commented Dec 13, 2013 at 19:47
  • $\begingroup$ Is $A$ rectangular with more rows than columns? $\endgroup$
    – Wolfgang Bangerth
    Commented Dec 13, 2013 at 23:12
  • $\begingroup$ Yes, the diagonal matrices are square and have positive numbers (not sure if this matters for least-squares). And we can assume $A$ is rectangular with more rows than columns (and that its columns are linearly independent). $\endgroup$
    – Justin Solomon
    Commented Dec 14, 2013 at 20:27

1 Answer 1

Reset to default
1
$\begingroup$

Perhaps you can use an LQ factorization instead of the usual QR approach to solve the least squares problem. Say you already have $A = LQ$ where $L$ is lower-triangular and $Q$ is orthogonal. For some diagonal matrix $D$, we'll have that $DA = DLQ$, and the matrix $DL$ is still lower triangular; we didn't need to re-compute the factorization of $DA$.

I can edit my answer to elaborate if you need more detail.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.