# Mode-wise Tensor Decompositions: Multi-dimensional Generalizations of CUR Decompositions

arXiv: https://arxiv.org/abs/2103.11037 · HTML: https://mlsanity.com/paper/2103.11037/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 73 references that are in the map.
- First posted on arXiv 19 Mar 2021.

## Builds on (most cited first, 13 of 13)

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Tensor Decomposition for Signal Processing and Machine Learning](https://mlsanity.com/paper/1607.01668/) (2016)
- [Revisiting the Nystrom Method for Improved Large-Scale Machine Learning](https://mlsanity.com/paper/1303.1849/) (2013)
- [Relative Error Tensor Low Rank Approximation](https://mlsanity.com/paper/1704.08246/) (2017)
- [Optimal CUR Matrix Decompositions](https://mlsanity.com/paper/1405.7910/) (2014)
- [Accelerated Alternating Projections for Robust Principal Component Analysis](https://mlsanity.com/paper/1711.05519/) (2017)
- [Statistically Optimal and Computationally Efficient Low Rank Tensor Completion from Noisy Entries](https://mlsanity.com/paper/1711.04934/) (2017)
- [Improving CUR Matrix Decomposition and the Nystr"om Approximation via Adaptive Sampling](https://mlsanity.com/paper/1303.4207/) (2013)
- [Robust CUR Decomposition: Theory and Imaging Applications](https://mlsanity.com/paper/2101.05231/) (2021)
- [Rapid Robust Principal Component Analysis: CUR Accelerated Inexact Low Rank Estimation](https://mlsanity.com/paper/2010.07422/) (2020)
- [Extension of PCA to Higher Order Data Structures: An Introduction to Tensors, Tensor Decompositions, and Tensor PCA](https://mlsanity.com/paper/1803.00704/) (2018)
- [Matrix Coherence and the Nystrom Method](https://mlsanity.com/paper/1408.2044/) (2014)
- [CUR Decompositions, Similarity Matrices, and Subspace Clustering](https://mlsanity.com/paper/1711.04178/) (2017)

## Built on by (most cited first, 13 of 13)

- [Matrix Completion with Cross-Concentrated Sampling: Bridging Uniform Sampling and CUR Sampling](https://mlsanity.com/paper/2208.09723/) (2022)
- [Robust Tensor CUR Decompositions: Rapid Low-Tucker-Rank Tensor Recovery with Sparse Corruption](https://mlsanity.com/paper/2305.04080/) (2023)
- [Fast Robust Tensor Principal Component Analysis via Fiber CUR Decomposition](https://mlsanity.com/paper/2108.10448/) (2021)
- [CURSOR: Scalable Mixed-Order Hypergraph Matching with CUR Decomposition](https://mlsanity.com/paper/2402.16594/) (2024)
- [Guaranteed Sampling Flexibility for Low-tubal-rank Tensor Completion](https://mlsanity.com/paper/2406.11092/) (2024)
- [S3Attention: Improving Long Sequence Attention with Smoothed Skeleton Sketching](https://mlsanity.com/paper/2408.08567/) (2024)
- [Error Analysis of Tensor-Train Cross Approximation](https://mlsanity.com/paper/2207.04327/) (2022)
- [Non-convex approaches for low-rank tensor completion under tubal sampling](https://mlsanity.com/paper/2303.12721/) (2023)
- [Maximal Volume Matrix Cross Approximation for Image Compression and Least Squares Solution](https://mlsanity.com/paper/2309.17403/) (2023)
- [Hyperspectral Band Selection based on Generalized 3DTV and Tensor CUR Decomposition](https://mlsanity.com/paper/2405.00951/) (2024)
- [Robust Anomaly Detection via Tensor Pseudoskeleton Decomposition](https://mlsanity.com/paper/2502.09926/) (2025)
- [Property Inheritance for Subtensors in Tensor Train Decompositions](https://mlsanity.com/paper/2504.11396/) (2025)
- [Robust Low-Tubal-Rank Tensor Completion under Cross-Concentrated Sampling](https://mlsanity.com/paper/2608.03928/) (2026)

## Abstract (arXiv)

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.