2024/12/03 by Salman Ahmadi-Asl, Salman Ahmadi‐Asl, Ahmadi-Asl, Salman +7
Mathematics · #Mathematical Approximation and Integration #Tensor decomposition and applications #cs.NA #math.NA
paper · pdf · doi:10.48550/arxiv.2412.02597
openalex publication_date 2024/12/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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-the-art 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.