.png){kind=icon}
Return
Fast randomized Kronecker tensor decomposition: Algorithms and error analysis
.png){kind=icon}
PRE
AI
DOI：10.1016/j.jfranklin.2026.108924.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This paper proposes fast randomized algorithms for computing the Kronecker Tensor Decomposition (KTD) by replacing the sequence of deterministic SVDs in the TTr1SVD framework with randomized SVDs incorporating oversampling and power iterations . The proposed algorithms can decompose a given tensor into the KTD format significantly faster than existing state-of-theart deterministic methods. Our principal idea is to use randomization to reduce computational complexity while maintaining controlled accuracy. A detailed theoretical analysis is presented, including a recursive error bound that accounts for error propagation through the TTr1SVD tree structure. We prove that the expected Frobenius norm error is bounded by a sum of tail energies multiplied by factors that decay exponentially with the number of power iterations. Extensive simulations on synthetic and real-world datasets demonstrate several orders of magnitude acceleration compared to the deterministic approach, with applications to tensor completion, video/image compression, image denoising, and image super-resolution.
Keywords:
Kronecker tensor decomposition (KTD)
Randomized algorithms
TTr1SVD
Power iteration
Low-rank approximation
Journal
J
IF:
4.2
Papers:
925
Citations:
0
Organization
View more organizations
Cited Papers
No cited papers available