# sparsity of QR decomposition

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)$.

-
What about the sparsity of $R$ wrt that of $A$ ? – Mike Apr 17 '12 at 11:26

## 2 Answers

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.

-
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. – Brian Borchers Apr 17 '12 at 13:32
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. – Brian Borchers Apr 17 '12 at 13:36

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.

-