Guaranteed Sampling Flexibility for Low-tubal-rank Tensor Completion
<|reference_start|>Guaranteed Sampling Flexibility for Low-tubal-rank Tensor Completion: 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.<|reference_end|>
@article{su2024guaranteed,
    title={Guaranteed Sampling Flexibility for Low-tubal-rank Tensor Completion},
    author={Bowen Su, Juntao You, HanQin Cai, and Longxiu Huang},
    journal={arXiv preprint arXiv:2406.11092},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.11092},
    primaryClass={cs.LG cs.NA math.NA stat.ML}
}