Mode-wise Tensor Decompositions: Multi-dimensional Generalizations of CUR Decompositions
arXiv:2103.11037
Abstract
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.
References in corpus (7)
- Sparsity and Incoherence in Compressive Sampling
- Tensor Decomposition for Signal Processing and Machine Learning
- Improving CUR Matrix Decomposition and the Nyström Approximation via Adaptive Sampling
- CANDECOMP/PARAFAC Decomposition of High-order Tensors Through Tensor Reshaping
- Rapid Robust Principal Component Analysis: CUR Accelerated Inexact Low Rank Estimation
- Rectangular maximum-volume submatrices and their applications
- Accelerated Alternating Projections for Robust Principal Component Analysis