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

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

2 Answers 2

Reset to default
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.

Improve this answer
$\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$
    – Brian Borchers
    Commented 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$
    – Brian Borchers
    Commented 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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Could you please elaborate? $\endgroup$
    – Philipp Trunschke
    Commented Nov 15, 2022 at 22:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .