# Guaranteed Sampling Flexibility for Low-tubal-rank Tensor Completion

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 69 references that are in the map.
- First posted on arXiv 16 Jun 2024.

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

- [Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements](https://mlsanity.com/paper/2104.14526/) (2021)
- [Improving CUR Matrix Decomposition and the Nystr"om Approximation via Adaptive Sampling](https://mlsanity.com/paper/1303.4207/) (2013)
- [Mode-wise Tensor Decompositions: Multi-dimensional Generalizations of CUR Decompositions](https://mlsanity.com/paper/2103.11037/) (2021)

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

- [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)
- [Strict-Saddle Landscapes and Multi-Rank Geometry in Low-Tubal-Rank Tensor Sensing](https://mlsanity.com/paper/2609.37865/) (2026)

## Abstract (arXiv)

While Bernoulli sampling is extensively studied in tensor completion, t-CUR sampling approximates low-tubal-rank tensors via lateral and horizontal subtensors. However, both methods lack sufficient flexibility for diverse practical applications. To address this, we introduce Tensor Cross-Concentrated Sampling (t-CCS), a novel and straightforward sampling model that advances the matrix cross-concentrated sampling concept within a tensor framework. t-CCS effectively bridges the gap between Bernoulli and t-CUR sampling, offering additional flexibility that can lead to computational savings in various contexts. A key aspect of our work is the comprehensive theoretical analysis provided. We establish a sufficient condition for the successful recovery of a low-rank tensor from its t-CCS samples. In support of this, we also develop a theoretical framework validating the feasibility of t-CUR via uniform random sampling and conduct a detailed theoretical sampling complexity analysis for tensor completion problems utilizing the general Bernoulli sampling model. Moreover, we introduce an efficient non-convex algorithm, the Iterative t-CUR Tensor Completion (ITCURTC) algorithm, specifically designed to tackle the t-CCS-based tensor completion. We have intensively tested and validated the effectiveness of the t-CCS model and the ITCURTC algorithm across both synthetic and real-world datasets.