Remembering the matrix dimensions of QR and SVD decompositions, reduced and full versions.
24 Mar 2022Given a \(m \times n\) matrix \(\mathbf{A}\), \(m \geq n\), what are the dimensions / sizes of the QR decomposition (full and reduced), and the SVD (full and reduced)?
I’m tired of forgetting and then re-deriving, so here are the dimensions. My reference is Trefethen and Bau 1997, Numerical Linear Algebra.
The reduced version is referred to as thin in Eigen. I’ll get to that at the end of the post.
Full QR dimensions
The decomposition of \(A\) is
\(A = QR\),
in the ‘full’ version of the decomposition,
- \(Q\) is \({m \times m}\),
- \(R\) is \(m \times n\).
Note that \(R\)’s last \(m-n\) rows are zero.
Reduced QR dimensions
\(A = \hat{Q}\hat{R}\),
- \(\hat{Q}\) is \({m \times n}\),
- \(\hat{R}\) is \({n \times n}\).
Full SVD dimensions
\(A = U \Sigma V^*\),
- \(U\) is \({m \times m}\),
- \(\Sigma\) is \({m \times n}\),
- \(V\) is \({n \times n}\).
Reduced SVD dimensions
\(A = \hat{U} \hat{\Sigma} V^*\),
- \(\hat{U}\) is \({m \times n}\),
- \(\hat{\Sigma}\) is \({n \times n}\),
- \(V\) is \({n \times n}\).
Requesting Full or Reduced versions in Eigen
For the SVD, computing the full or reduced versions in Eigen is done by way of flags, ComputeThinU, ComputeFullU, etc. flags. While the reduced version from the above is analogous to thin in Eigen, it is not the same as that of Trefethen and Bau. Eigen, JacobiSVD docs:
This JacobiSVD decomposition computes only the singular values by default. If you want U or V, you need to ask for them explicitly.
You can ask for only thin U or V to be computed, meaning the following. In case of a rectangular n-by-p matrix, letting m be the smaller value among n and p, there are only m singular vectors; the remaining columns of U and V do not correspond to actual singular vectors. Asking for thin U or V means asking for only their m first columns to be formed. So U is then a n-by-m matrix, and V is then a p-by-m matrix. Notice that thin U and V are all you need for (least squares) solving.
Using the dimensions from above, that \(\mathbf{A}\) is \(m \times n\), the dimensions of the thin representations are the following:
- \(\hat{U}\) is \({m \times n}\),
- \(\hat{\Sigma}\) is \({n} \times 1\) (a vector of singular values),
- \(V\) is \({n \times n}\).
I have not been able to find comparable options for QR decompositions in Eigen.
References
- Eigen documentation for JacobiSVD.
- Lloyd N. Trefethen; David Bau III. 1997. Numerical Linear Algebra. ISBN 9780898713619.