5
$\begingroup$

Let's say we have a weighted least squares problem under the same matrix $A$ such that,

$$\hat{x} := \arg \min_x ||A x - b||_{W_1}$$ where $|| \cdot ||_{W_1}$ is the Euclidean norm weighted by diagonal elements in $W_1$. We can solve this easily by performing a $QR$ decomposition of $W^{1/2}_1 A$ together with $W^{1/2}_1 b$ using standard software.

Given this, is there an approach to re-use the previous QR decomposition to solve a similar weighted least square problems under the same $A$, such that $$\hat{z} := \arg \min_z ||A z - c||_{W_2}$$ if we can bound $||c - b||$ and $||W_1 - W_2||_F$?

The motivation for this, is to see if there are faster means of iterative re-weighted least squares to solve generalized inverse problems, rather than re-computing a complete $QR$ decomposition at each step.

My gut tells me that there is no easy way to re-use a $QR$, no matter the bound, as this would make too many related problems easy to solve (and thus folks would already be talking about it). Nature is uncaring in that way.

$\endgroup$
2
  • $\begingroup$ How large is your $A$ matrix? Is it sparse? $\endgroup$ Commented Oct 3, 2023 at 4:22
  • $\begingroup$ Not necessarily large. $n \times p$ for $n \approx 1000$ and $p \approx 25$ (guestimates). Not sparse in general. $\endgroup$ Commented Oct 4, 2023 at 16:32

1 Answer 1

2
$\begingroup$

Perhaps only some values change, in which case you might be able to make use of the Woodbury matrix identity to make a cheap rank-k update, given that $$\hat{z} = \arg \min_z ||A z - c||_{W}$$ has the solution $$\hat{z} = (A^TWA)^{-1}A^TWc$$

$\endgroup$
1
  • 2
    $\begingroup$ Unfortunately in OP's problem, iteratively reweighted least squares, W is a diagonal matrix all of whose entries change at each step. They might change by very little when close to convergence, though. $\endgroup$ Commented Oct 8, 2023 at 7:43

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.