Structured Matrix Approximations via Tensor Decompositions
Structured Matrix Approximations via Tensor Decompositions
复制标题
DOI：
10.1137/21m1418290
复制
发表时间：
2021-05
期刊：
影响因子：
--
通讯作者：
M. Kilmer;A. Saibaba
中科院分区：
文献类型：
--
作者：
M. Kilmer;A. Saibaba
我们提供了一个计算框架，用于近似一类结构化矩阵;在这里，术语结构是非常一般的，并且可以指规则的稀疏模式（例如，块状带状），或者更高度结构化（例如，对称块Toeplitz）。我们的目标是发现{\it额外的潜在结构}，这反过来又会导致计算效率的算法时，新的结构化矩阵近似采用在原来的运营商的地方。我们的方法有三个步骤：将结构化矩阵映射到张量，使用张量压缩算法，并将压缩后的张量映射回来，以获得两种不同的矩阵表示-Kronecker乘积和块低秩格式。张量分解的使用使我们能够发现问题中的潜在结构，并导致原始矩阵的压缩表示，可以在应用中有效地使用。由此产生的矩阵逼近具有内存效率，易于计算，并且保留了由于弗罗贝纽斯范数中的张量压缩而产生的误差。我们的框架是非常通用的。我们说明了我们的方法的能力，发现块低秩格式的结构矩阵从两个应用程序：系统识别，空时协方差矩阵。此外，我们证明了我们的方法可以发现SuiteSparse集合中的几个矩阵上的结构化Kronecker产品结构的总和。最后，我们表明，我们的框架是足够广泛的，包括和改善其他相关的结果，从文献中，我们说明了一个三维模糊算子的近似。
We provide a computational framework for approximating a class of structured matrices; here, the term structure is very general, and may refer to a regular sparsity pattern (e.g., block-banded), or be more highly structured (e.g., symmetric block Toeplitz). The goal is to uncover {\it additional latent structure} that will in turn lead to computationally efficient algorithms when the new structured matrix approximations are employed in the place of the original operator. Our approach has three steps: map the structured matrix to tensors, use tensor compression algorithms, and map the compressed tensors back to obtain two different matrix representations -- sum of Kronecker products and block low-rank format. The use of tensor decompositions enables us to uncover latent structure in the problem and leads to compressed representations of the original matrix that can be used efficiently in applications. The resulting matrix approximations are memory efficient, easy to compute with, and preserve the error that is due to the tensor compression in the Frobenius norm. Our framework is quite general. We illustrate the ability of our method to uncover block-low-rank format on structured matrices from two applications: system identification, space-time covariance matrices. In addition, we demonstrate that our approach can uncover sum of structured Kronecker products structure on several matrices from the SuiteSparse collection. Finally, we show that our framework is broad enough to encompass and improve on other related results from the literature, as we illustrate with the approximation of a three-dimensional blurring operator.