Characterization of Deterministic and Probabilistic Sampling Patterns
  for Finite Completability of Low Tensor-Train Rank Tensor
  In this paper, we analyze the fundamental conditions for low-rank tensor
completion given the separation or tensor-train (TT) rank, i.e., ranks of
unfoldings. We exploit the algebraic structure of the TT decomposition to
obtain the deterministic necessary and sufficient conditions on the locations
of the samples to ensure finite completability. Specifically, we propose an
algebraic geometric analysis on the TT manifold that can incorporate the whole
rank vector simultaneously in contrast to the existing approach based on the
Grassmannian manifold that can only incorporate one rank component. Our
proposed technique characterizes the algebraic independence of a set of
polynomials defined based on the sampling pattern and the TT decomposition,
which is instrumental to obtaining the deterministic condition on the sampling
pattern for finite completability. In addition, based on the proposed analysis,
assuming that the entries of the tensor are sampled independently with
probability $p$, we derive a lower bound on the sampling probability $p$, or
equivalently, the number of sampled entries that ensures finite completability
with high probability. Moreover, we also provide the deterministic and
probabilistic conditions for unique completability.
