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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.