Module rusty_compression::qr
source · [−]Expand description
Data Structures and traits for QR Decompositions
The pivoted QR Decomposition of a matrix $A\in\mathbb{C}^{m\times n}$ is
defined as $AP = QR$, where $P$ is a permutation matrix, $Q\in\mathbb{C}^{m\times k}$
is a matrix with orthogonal columns, satisfying $Q^HQ = I$, and $R\in\mathbb{C}^{k\times n}$
is an upper triangular matrix with diagonal elements $r_{ii}$ satisfying $|r_{11}|\geq |r_{22}|\geq \dots$.
Here $k=\min{m, n}$. The matrix $P$ is defined by an index vector ind in such a way that if ind[j] = k then
the jth column of $P$ is 1 at the position P[k, j] and 0 otherwise. In other words the matrix $P$ permutes the
$k$th column of $A$ to the $j$th column.
This module also defines the LQ Decomposition defined as $PA = LQ$ with $L$ a lower triangular matrix. If $A^H\tilde{P}=\tilde{Q}R$ is the QR decomposition as defined above, then $P = \tilde{P}^T$, $L=R^H$, $Q=\tilde{Q}^H$.
Both, the QR and the LQ Decomposition of a matrix can be compressed further, either by specifying a rank or by specifying a relative tolerance. Let $AP=QR$. We can compress the QR Decomposition by only keeping the first $\ell$ columns ($\ell \leq k$) of $Q$ and correspondingly only keeping the first $\ell$ rows of $R$. We can alternatively determine the $\ell$ by a tolerance tol such that only the first $\ell$ rows of $R$ are kept that satisfy $|r_{\ell, \ell}| / |r_{1, 1}| \geq tol$.