5
$\begingroup$

Hi, everyone!

I have a sparse $n \times n$ matrix $A$ with $nnz(A)$ denoting the number of non-zero entries in $A$. Now I use QR factorization to decompose $A$ into an orthogonal matrix $Q$ and triangular matrix $R$. My problem is that : can we use some methods to control the sparsity of $Q$ satisfying $nnz(Q) \le nnz(A)$.

$\endgroup$
1
  • $\begingroup$ What about the sparsity of $R$ wrt that of $A$ ? $\endgroup$
    – Mike
    Apr 17, 2012 at 11:26

2 Answers 2

9
$\begingroup$

Unfortunately you can't. With any orthogonal factorization (e.g. QR, LQ, or SVD) you have the problem that because some of the columns of the orthogonal matrix have to span a particular subspace, and because the remaining columns have to form an orthogonal basis for the complement to this subspace, and because these spaces can be completely arbitrary, the orthogonal matrix won't be sparse unless you happen to be very lucky.

There are "sparse QR" methods that effectively represent Q as a product of Givens rotations rather than storing Q explicitly. The Givens rotations are transformations that are extremely sparse/structured matrices.

$\endgroup$
2
  • $\begingroup$ The typical case in which sparse QR factorization is used is where $A$ is of size $m$ by $n$, $m \gg n$, and $A$ has full column rank. In this situation, $Q$ would be $m$ by $m$ and typically dense with nonzeros, but the effect of multiplication by $Q$ can be achieved by using sequences of Givens rotations. So $Q$ isn't stored explicitly. It is also possible to order the columns of $A$ to reduce the nonzero fill-in in the $R$ matrix. $\endgroup$ Apr 17, 2012 at 13:32
  • $\begingroup$ If you want to use this sparse QR "factorization" to solve $\min \| Ax-b \|$, the procedure is to first apply the Givens rotations to reduce $A$ to $R$, possibly reordering the columns of $A$ to minimize fill-in in the $R$ matrix. As you do these Givens rotations you also apply them to $b$ to obtain $Q^{T}b$. Then you solve the triangular system $Rx=Q^{T}b$ to obtain the least squares solution. There is lots of available software for performing these computations. $\endgroup$ Apr 17, 2012 at 13:36
1
$\begingroup$

Also, if $A$ is invertible and $R$ is required to have positive diagonal, the $QR$ decomposition is unique, so you can't really control it. If you are looking for approximate decompositions, though, it's a whole different game.

$\endgroup$
1
  • $\begingroup$ Could you please elaborate? $\endgroup$ Nov 15, 2022 at 22:48

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.