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.

$\endgroup$
  • $\begingroup$ I assume the $D_{i}$ are strictly positive definite? $\endgroup$ – Geoff Oxberry Dec 13 '13 at 19:47
  • $\begingroup$ Is $A$ rectangular with more rows than columns? $\endgroup$ – Wolfgang Bangerth Dec 13 '13 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 Dec 14 '13 at 20:27
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.

$\endgroup$

Your Answer

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

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