Fundamental Conditions for Low-CP-Rank Tensor Completion
Authors: Morteza Ashraphijuo, Xiaodong Wang
JMLR 2017 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. [...] In order to show the advantage of our proposed CP approach over the unfolding approach, we compare the lower bound on the total number of samples that is required for finite completability using an example. [...] Figure 1 plots the bounds given in (14) (unfolding approach) and in (29) (CP approach) for the corresponding rank value, where ϵ = 0.001. |
| Researcher Affiliation | Academia | Morteza Ashraphijuo EMAIL Columbia University New York, NY 10027, USA Xiaodong Wang EMAIL Columbia University New York, NY 10027, USA |
| Pseudocode | No | The paper describes theoretical conditions and mathematical derivations using lemmas and theorems. It does not include any explicitly labeled pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any explicit statements about releasing source code, nor does it include links to a code repository or mention code in supplementary materials. |
| Open Datasets | No | The paper is theoretical, focusing on tensor completion conditions. It does not use specific real-world or benchmark datasets, and therefore no information about open dataset access is provided. |
| Dataset Splits | No | The paper is theoretical and does not involve experiments with actual datasets, thus no dataset split information (training, validation, test) is provided. |
| Hardware Specification | No | The paper's 'Numerical Comparisons' section plots theoretical bounds rather than presenting results from computational experiments. Therefore, no specific hardware specifications are mentioned. |
| Software Dependencies | No | The paper describes theoretical concepts and mathematical derivations. It does not mention any specific software, libraries, or solvers with version numbers that would be required to reproduce any computational aspects. |
| Experiment Setup | No | The paper is primarily theoretical, establishing deterministic and probabilistic conditions for tensor completion. It does not conduct empirical experiments with models or data that would require a detailed experimental setup, hyperparameter values, or training configurations. |