Fundamental conditions for low-CP-rank tensor completion

MaRDI QIDQ5361335zbMATH OpenFDO

Authors Morteza Ashraphijuo, Xiaodong Wang

Publication date 27 September 2017

Full work available at URL https://arxiv.org/abs/1703.10740, http://jmlr.csail.mit.edu/papers/v18/17-189.html

zbMATH Keywords

algebraic geometryBernstein's theoremcanonical polyadic decompositionfinite completabilitylow-rank tensor completionunique completability

Mathematics Subject Classification ID

Multilinear algebra, tensor calculus (15A69) Vector and tensor algebra, theory of invariants (15A72) Exterior algebra, Grassmann algebras (15A75) Matrix completion problems (15A83)

Abstract: We consider the problem of low canonical polyadic (CP) rank tensor completion. A completion is a tensor whose entries agree with the observed entries and its rank matches the given CP rank. We analyze the manifold structure corresponding to the tensors with the given rank and define a set of polynomials based on the sampling pattern and CP decomposition. Then, we show that finite completability of the sampled tensor is equivalent to having a certain number of algebraically independent polynomials among the defined polynomials. Our proposed approach results in characterizing the maximum number of algebraically independent polynomials in terms of a simple geometric structure of the sampling pattern, and therefore we obtain the deterministic necessary and sufficient condition on the sampling pattern for finite completability of the sampled tensor. Moreover, assuming that the entries of the tensor are sampled independently with probability $p$ and using the mentioned deterministic analysis, we propose a combinatorial method to derive a lower bound on the sampling probability $p$, or equivalently, the number of sampled entries that guarantees finite completability with high probability. We also show that the existing result for the matrix completion problem can be used to obtain a loose lower bound on the sampling probability $p$. In addition, we obtain deterministic and probabilistic conditions for unique completability. It is seen that the number of samples required for finite or unique completability obtained by the proposed analysis on the CP manifold is orders-of-magnitude lower than that is obtained by the existing analysis on the Grassmannian manifold.

Recommendations

• Characterization of sampling patterns for low-tt-rank tensor retrieval
• Rank determination for low-rank data completion
• Fiber sampling approach to canonical polyadic decomposition and application to tensor completion
• Union of low-rank tensor spaces: clustering and completion
• Deterministic tensor completion with hypergraph expanders

Cited in

(14)

• Riemannian conjugate gradient descent method for fixed multi rank third-order tensor completion
• Low-CP-rank tensor completion via practical regularization
• Characterization of sampling patterns for low-tt-rank tensor retrieval
• Fundamental conditions on the sampling pattern for union of low-rank subspaces retrieval
• An approximation method of CP rank for third-order tensor completion
• Rank determination for low-rank data completion
• Union of low-rank tensor spaces: clustering and completion
• Nonconvex Low-Rank Tensor Completion from Noisy Data
• Deterministic tensor completion with hypergraph expanders
• Deterministic and Probabilistic Conditions for Finite Completability of Low-Tucker-Rank Tensor
• Fiber sampling approach to canonical polyadic decomposition and application to tensor completion
• The geometry of rank-one tensor completion
• Nonlocal robust tensor recovery with nonconvex regularization
• A novel tensor completion algorithm with regularization and its application to image processing and hyperspectral data analysis

This page was built for publication: Fundamental conditions for low-CP-rank tensor completion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5361335)