Guaranteed Sampling Flexibility for Low-tubal-rank Tensor Completion
This work addresses a domain-specific bottleneck in tensor completion for applications requiring flexible sampling, but it is incremental as it builds on existing matrix and tensor sampling concepts.
The paper tackles the problem of limited sampling flexibility in low-tubal-rank tensor completion by introducing Tensor Cross-Concentrated Sampling (t-CCS), which bridges Bernoulli and t-CUR sampling, and develops an efficient algorithm (ITCURTC) validated on synthetic and real-world datasets.
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.