Crate rusty_compression

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

• Overview
• Random sampling of operators
• Examples

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

CompressionType

Traits

Scalar

Type Aliases

c32

Alias for a Complex<f32>

c64

Alias for a Complex<f64>