Mode-wise Tensor Decompositions: Multi-dimensional Generalizations of CUR Decompositions
This work addresses tensor decomposition for machine learning and data science, offering incremental improvements in efficiency and theoretical guarantees for specific tensor structures.
The paper tackles the problem of low rank tensor approximation by characterizing, analyzing, and providing efficient sampling strategies for two tensor CUR decompositions (Chidori and Fiber CUR), showing that uniform sampling works for incoherent tensors and achieving speed advantages over other methods in empirical evaluations.
Low rank tensor approximation is a fundamental tool in modern machine learning and data science. In this paper, we study the characterization, perturbation analysis, and an efficient sampling strategy for two primary tensor CUR approximations, namely Chidori and Fiber CUR. We characterize exact tensor CUR decompositions for low multilinear rank tensors. We also present theoretical error bounds of the tensor CUR approximations when (adversarial or Gaussian) noise appears. Moreover, we show that low cost uniform sampling is sufficient for tensor CUR approximations if the tensor has an incoherent structure. Empirical performance evaluations, with both synthetic and real-world datasets, establish the speed advantage of the tensor CUR approximations over other state-of-the-art low multilinear rank tensor approximations.