Expand description
This library provides routines to compute low-rank approximations of matrices.
§Overview
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.
Re-exports§
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 types::RelDiff;pub use types::Result;pub use permutation::*;pub use random_sampling::*;
Modules§
- col_
interp_ decomp - Data structures for Column Interpolative Decomposition.
- compute_
svd - A simple trait to wrap SVD Computation.
- examples
- Library examples
- permutation
- Traits and functions for permutation vectors.
- qr
- Data Structures and traits for QR Decompositions
- random_
matrix - Generation of random matrices for various types
- random_
sampling - Random sampling of matrices
- row_
interp_ decomp - Data structure for Row Interpolative Decomposition
- svd
- Define an SVD container and conversion tools.
- two_
sided_ interp_ decomp - Implementation of the two sided interpolative decomposition
- types
- This module collects the various traits definitions
Enums§
Traits§
Type Aliases§
- c32
- Alias for a
Complex<f32> - c64
- Alias for a
Complex<f64>