3
$\begingroup$

This is a continuation of the question asked here. I want to solve numerous least squares systems of the form $$ D_i A x \approx D_i b $$ where $D_i$ are $m \times m$ diagonal matrices with positive elements on the diagonal, $A$ is $m \times n$ with $m > n$, $x$ is $n \times 1$, and $b$ is $m \times 1$.

The answer given in the previous question recommended to factor $A$ with an $LQ$ decomposition, noting that $D_i L$ would be lower triangular so that it wouldn't be necessary to factor $D_i A$ for each $D_i$.

However, it turns out that $L$ in an $LQ$ factorization is only lower triangular when $m \le n$ (under-determined). When $m > n$ (over-determined), $L$ is in fact lower trapezoidal (zero above the $m=n$ diagonal, see the LAPACK routine DGELQF). So $L$ would look like $$ L = \pmatrix{ L_{11} \\ L_{21}} $$ where $L_{11}$ is $n \times n$ lower triangular, and $L_{21}$ is $(m-n) \times n$ dense.

Therefore, when using an $LQ$ factorization, we would need to solve $$ D_i L z \approx D_i b $$ where $z = Q x$. Now multiplying a diagonal matrix by a trapezoidal gives a trapezoidal matrix, so the problem becomes solving the trapezoidal least squares problem $$ (D_i L) z = y $$ My question is how can this trapezoidal system be solved efficiently? It seems to me I'm back to square 1 because I would need to factor $D_i L$ with $QR$ or $SVD$ in order to solve this least squares system. I don't see any LAPACK/BLAS routines which can efficiently solve trapezoidal systems.

$\endgroup$

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.