Deterministic tensor completion with hypergraph expanders
We provide a novel analysis of low-rank tensor completion based on hypergraph expanders. As a proxy for rank, we minimize the max-quasinorm of the tensor, which generalizes the max-norm for matrices. Our analysis is deterministic and shows that the number of samples required to approximately recover an order-$t$ tensor with at most $n$ entries per dimension is linear in $n$, under the assumption that the rank and order of the tensor are $O(1)$. As steps in our proof, we find a new expander mixing lemma for a $t$-partite, $t$-uniform regular hypergraph model, and prove several new properties about tensor max-quasinorm. To the best of our knowledge, this is the first deterministic analysis of tensor completion. We develop a practical algorithm that solves a relaxed version of the max-quasinorm minimization problem, and we demonstrate its efficacy with numerical experiments.
Code (2)
Tasks
LEMMASimilar Papers 제목 키워드 기반
EvRainDrop: HyperGraph-guided Completion for Effective Frame and Event Stream Aggregation
Event cameras produce asynchronous event streams that are spatially sparse yet temporally dense. Mainstream event representation learning algorithms typically use event frames, voxels, or tensors as input. Although these…
Representation LearningBeyond the Signs: Nonparametric Tensor Completion via Sign Series
We consider the problem of tensor estimation from noisy observations with possibly missing entries. A nonparametric approach to tensor completion is developed based on a new model which we coin as sign representable tens…
Spectral gap-based deterministic tensor completion
Tensor completion is a core machine learning algorithm used in recommender systems and other domains with missing data. While the matrix case is well-understood, theoretical results for tensor problems are limited, parti…
Recommendation SystemsGuaranteed Multidimensional Time Series Prediction via Deterministic Tensor Completion Theory
In recent years, the prediction of multidimensional time series data has become increasingly important due to its wide-ranging applications. Tensor-based prediction methods have gained attention for their ability to pres…
Computational EfficiencyPredictionTensor DecompositionTime Series+1Fundamental Conditions for Low-CP-Rank Tensor Completion
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 struct…
Matrix Completion