Deterministic and Probabilistic Conditions for Finite Completability of Low-Tucker-Rank Tensor
arXiv:1612.01597
Abstract
We investigate the fundamental conditions on the sampling pattern, i.e., locations of the sampled entries, for finite completability of a low-rank tensor given some components of its Tucker rank. In order to find the deterministic necessary and sufficient conditions, we propose an algebraic geometric analysis on the Tucker manifold, which allows us to incorporate multiple rank components in the proposed analysis in contrast with the conventional geometric approaches on the Grassmannian manifold. This analysis characterizes the algebraic independence of a set of polynomials defined based on the sampling pattern, which is closely related to finite completion. Probabilistic conditions are then studied and a lower bound on the sampling probability is given, which guarantees that the proposed deterministic conditions on the sampling patterns for finite completability hold with high probability. Furthermore, using the proposed geometric approach for finite completability, we propose a sufficient condition on the sampling pattern that ensures there exists exactly one completion for the sampled tensor.
References in corpus (10)
- A Simpler Approach to Matrix Completion
- Robust Low-rank Tensor Recovery: Models and Algorithms
- Estimation of low-rank tensors via convex optimization
- A New Convex Relaxation for Tensor Completion
- Multiarray Signal Processing: Tensor decomposition meets compressed sensing
- Adaptive Sampling of RF Fingerprints for Fine-grained Indoor Localization
- A Characterization of Deterministic Sampling Patterns for Low-Rank Matrix Completion
- Low-tubal-rank Tensor Completion using Alternating Minimization
- High-Rank Matrix Completion and Subspace Clustering with Missing Data
- Tensor Completion by Alternating Minimization under the Tensor Train (TT) Model