rusty-compression

Rust 中的低秩压缩库。

此库提供各种用于线性算子低秩压缩的程序。算法主要来自 Gunar Martinsson 的书籍《椭圆偏微分方程的快速直接求解器》。

有关示例，请参阅目录中的两个示例程序 examples。在使用库时，需要链接 ndarray-linalg 依赖项，针对 Openblas 或其他 Lapack 库。有关详细信息，请参阅ndarray-linalg 的相应文档。

lib.rs:

此库提供计算矩阵低秩近似的程序。

• 概述
• 算子的随机采样
• 示例

概述

设 $A\in\mathbb{C}^{m\times n}$ 为一个给定的矩阵。低秩近似是形如 $$ A\approx UV^H $$ 的表示，其中 $U\in\mathbb{C}^{m\times k}$ 和 $V\in\mathbb{C}^{n\times k}$，其中 $k$ 对于所需应用足够小。也常用的一种表示形式是 $$ A\approx \tilde{U}X\tilde{V}^H $$，其中 $X$ 是一个 $k\times k$ 的矩阵。

库的基础是 $A$ 的带置换的 QR 分解，形式为 $$ AP = QR $$，其中 $P$ 是置换矩阵，$Q\in\mathbb{C}^{m\times \ell}$ 是具有单位范数正交列的矩阵，$R\in\mathbb{C}^{\ell\times n}$ 是上三角矩阵，且 $\ell=\min\{m, n\}$。

在带置换的 QR 分解中，$R$ 的对角元素按非递减顺序排列，即 $|r_{11}|\geq |r_{22}|\geq \dots$。因此，我们可以通过选择索引 $k$ 并仅保留 $Q$ 的前 $k$ 列和 $R$ 的前 $k$ 行来压缩 $A$。库允许直接选择参数 $k$ 或通过给定的容差 $\tau$ 来选择，使得 $\langle|\frac{r_{kk}}{r_{11}}\rangle|< \tau$。

或者，也可以先计算奇异值分解来低秩压缩。这更准确，但成本也更高。

从压缩的 QR 分解中，我们可以计算列置换插值分解的形式 $$ A \approx CZ $$。矩阵 $C$ 定义为 $$ C = A[:, [i_1, i_2, \dots]], $$ 即选择 $A$ 的列，其索引为 $i_1, i_2, \dots$。

列置换插值分解的优点在于我们使用 $A$ 的列作为低秩基，在应用中，这些列通常具有物理意义，而与 $Q$ 的列相对。

从列转置插值分解中，我们还可以计算形如 $$ A\approx C X R $$ 的双边分解。在这里，$X$ 是一个 $k\times k$ 矩阵，它是 $A$ 的子矩阵，由列索引 $i_1, i_2, \dots$ 和行索引 $j_1, j_2, \dots$ 组成。

与列插值分解类似，还有一个相应的行插值分解可用于选择 $A$ 的行进行低秩近似。