Expand description

This library provides routines to compute low-rank approximations of matrices.


Let $A\in\mathbb{C}^{m\times n}$ be a given matrix. A low-rank approximation is a representation of the form $$ A\approx UV^H $$ with $U\in\mathbb{C}^{m\times k}$ and $V\in\mathbb{C}^{n\times k}$, where $k$ is sufficiently small for the required application. A frequently used representation is also $$ A\approx \tilde{U}X\tilde{V}^H $$ with a $k\times k$ matrix $X$.

The basis of the library is a pivoted QR decomposition of $A$ of the form $$ AP = QR $$ with $P$ a permutation matrix, $Q\in\mathbb{C}^{m\times \ell}$ a matrix with orthogonal columns of unit norm, $R\in\mathbb{C}^{\ell\times n}$ upper triangular, and $\ell=\min\{m, n\}$.

In a pivoted QR decomposition the diagonal elements of $R$ are sorted in non-increasing order, that is $|r_{11}|\geq |r_{22}|\geq \dots$. We can therefore compress $A$ by choosing an index $k$ and only keeping the first $k$ columns of $Q$ and the first $k$ rows of $R$. The library allows to choose the parameter $k$ directly or by a given tolerance $\tau$ such that $\langle|\frac{r_{kk}}{r_{11}}\rangle|< \tau$.

Alternatively, one can also low-rank compress by first computing the Singular Value Decomposition. This is more accurate but also more costly.

From the compressed QR decomposition we can compute a column pivoted interpolative decomposition of the form $$ A \approx CZ $$ The matrix $C$ is defined as $$ C = A[:, [i_1, i_2, \dots]], $$ that is a selection of columns of $A$ with indices $i_1, i_2, \dots$.

The column pivoted interpolative decomposition has the advantage that we are using columns of $A$ as low-rank basis, which in applications often have physical meaning as opposed to the columns of $Q$.

From the column pivoted interpolative decomposition we can also compute a two-sided decomposition of the form $$ A\approx C X R $$ Here, $X$ is a $k\times k$ matrix, which is the submatrix of $A$ formed of the column indices $i_1, i_2, \dots$ and row indices $j_1, j_2, \dots$.

Similarly to a column interpolative decomposition, a corresponding row interpolative decomposition is available that selects rows of $A$ for the low rank approximation.


pub use qr::QR;
pub use qr::LQ;
pub use qr::QRTraits;
pub use qr::LQTraits;
pub use col_interp_decomp::ColumnID;
pub use col_interp_decomp::ColumnIDTraits;
pub use row_interp_decomp::RowID;
pub use row_interp_decomp::RowIDTraits;
pub use two_sided_interp_decomp::TwoSidedID;
pub use two_sided_interp_decomp::TwoSidedIDTraits;
pub use svd::SVD;
pub use svd::SVDTraits;
pub use random_matrix::RandomMatrix;
pub use permutation::*;
pub use types::RelDiff;
pub use random_sampling::*;
pub use types::Result;


Data structures for Column Interpolative Decomposition.

A simple trait to wrap SVD Computation.

Library examples

Traits and functions for permutation vectors.

Data Structures and traits for QR Decompositions

Generation of random matrices for various types

Random sampling of matrices

Data structure for Row Interpolative Decomposition

Define an SVD container and conversion tools.

Implementation of the two sided interpolative decomposition

This module collects the various traits definitions



Type Definitions