Can you use a QR decomposition of an unweighted matrix to speed up the factorization of the weighted matrix?

58 Views Asked by At

In active set solvers for quadratic programs we often run into the following issue: we have a Q-less QR factorization of a matrix $Q, R = qr(A)$, a diagonal (positive) weight matrix $W$, and we need to compute the QR factorization of the weighted matrix $P, U = qr(W A)$ so we can initialize the solver on a weighted version of the solver using $U$.

This is a fairly common issue which comes up in iteratively solving weighted least squares problem, but there it is not essential to solve for $P, U$ respectively. But in active set solvers which use an iteratively updated QR factorization we often need to solve for $U$ specifically to maintain performance, because solving the upper triangular system is fast. That is why this StackExchange post is not helpful.

My question is whether there is any way to leverage the fact we have $Q, R$ to solve for $P, U$, and specifically for $U$. Obviously we can compute a matrix $\tilde U = Q^T W A$ such that $\tilde U^T \tilde U = U^T U$, but this matrix will not be upper triangular because $W Q$ is not orthonormal. Maybe $\tilde U$ could somehow be efficiently projected onto the space of orthogonal matrices, solving for $P$ and then we can take $U = P^T A$? But it's not obvious how to compute this projection or whether it would be faster than simply recomputing the QR factorization of $W A$.

It may not be possible to speed up this computation, but if that is the case it would be nice to have an explanation for why. It seems intuitively like it should be possible since $W$ is such a polite form: diagonal and positive. The lack of an explanation of how to compute an update like this online points to impossibility, but it'd be nice to have it confirmed.