Fast randomized Kronecker tensor decomposition: Algorithms and error analysis

Salman Ahmadi‐Asl

doi:10.1016/j.jfranklin.2026.108924

Fast randomized Kronecker tensor decomposition: Algorithms and error analysis

2026-08-01

0

PRE

AI

André L. F. de Almeida

Y

Yipeng Liu

DOI：10.1016/j.jfranklin.2026.108924

原文链接

原文求助

摘要

En 中文

本文提出了一种快速随机算法，用于计算Kronecker张量分解（KTD），通过在TTr1SVD框架中用随机SVD替代确定性SVD序列，并引入过采样和幂迭代。所提出的算法能够将给定张量分解为KTD格式，其速度显著快于现有的确定性方法。我们的主要思想是利用随机化来降低计算复杂度，同时保持可控的精度。文中进行了详细的理论分析，包括递归误差界，该误差界考虑了通过TTr1SVD树结构的误差传播。我们证明了预期的Frobenius范数误差被一个尾能量之和所限制，其乘数因子随幂迭代次数呈指数衰减。在合成和真实数据集上的大量模拟实验表明，与确定性方法相比，该算法实现了数个数量级的加速，并应用于张量补全、视频/图像压缩、图像去噪和图像超分辨率等领域。

Keyword:

Kronecker tensor decomposition (KTD)

Randomized algorithms

TTr1SVD

Power iteration

Low-rank approximation

Fast randomized Kronecker tensor decomposition: Algorithms and error analysis

摘要

期刊

机构

引用论文