most recent 30 from http://mathoverflow.net 2013-05-21T21:55:44Z http://mathoverflow.net/feeds/question/94198 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/94198/sparsity-of-qr-decomposition Mike 2012-04-16T10:40:40Z 2012-04-17T07:18:26Z

<p>Hi, everyone!</p> <p>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)$. </p>

http://mathoverflow.net/questions/94198/sparsity-of-qr-decomposition/94212#94212 Brian Borchers 2012-04-16T13:33:12Z 2012-04-17T03:16:11Z

<p>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. </p> <p>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. </p>

http://mathoverflow.net/questions/94198/sparsity-of-qr-decomposition/94277#94277 Felix Goldberg 2012-04-17T07:18:26Z 2012-04-17T07:18:26Z

<p>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.</p>