论文标题
线性复杂性黑框随机压缩的等级结构矩阵
Linear-Complexity Black-Box Randomized Compression of Rank-Structured Matrices
论文作者
论文摘要
出现了用于计算给定级别结构的矩阵$ a \ in \ mathbb {r}^{n \ times n} $的随机算法。该算法仅通过其对向量的操作与$ a $相互作用。具体而言，它从合适的分布中绘制两个高薄矩阵$ω，\，ψ\，in \ mathbb {r}^{n \ times s} $，然后从集合中包含的信息中重建$ a $，$ \ {aΩ，\ {aΩ，\，\，\，\，ω，对于“层次上可分开（HBS）”矩阵（又称层次上半分离矩阵）的特定情况，块等级$ k $，所需的样本$ s $的数量满足$ s = o（k）$，$ s \ s \ s \ s \ 3k $是代表性的。虽然以前已经发布了许多用于压缩级别结构矩阵的随机算法，但目前的算法似乎是第一种真正的线性复杂性（复杂性绑定中没有$ n \ log log（n）$因子），而无需矩阵输入评估，这是第一种算法。此外，所有样品都可以并行提取，从而使算法能够以“流”或“单视图”模式工作。
A randomized algorithm for computing a compressed representation of a given rank-structured matrix $A \in \mathbb{R}^{N\times N}$ is presented. The algorithm interacts with $A$ only through its action on vectors. Specifically, it draws two tall thin matrices $Ω,\,Ψ\in \mathbb{R}^{N\times s}$ from a suitable distribution, and then reconstructs $A$ from the information contained in the set $\{AΩ,\,Ω,\,A^{*}Ψ,\,Ψ\}$. For the specific case of a "Hierarchically Block Separable (HBS)" matrix (a.k.a. Hierarchically Semi-Separable matrix) of block rank $k$, the number of samples $s$ required satisfies $s = O(k)$, with $s \approx 3k$ being representative. While a number of randomized algorithms for compressing rank-structured matrices have previously been published, the current algorithm appears to be the first that is both of truly linear complexity (no $N\log(N)$ factors in the complexity bound) and fully "black box" in the sense that no matrix entry evaluation is required. Further, all samples can be extracted in parallel, enabling the algorithm to work in a "streaming" or "single view" mode.
