Deterministic tensor completion with hypergraph expanders
arXiv:1910.10692 · doi:10.1137/20M1379745
Abstract
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- tensor with at most entries per dimension is linear in , under the assumption that the rank and order of the tensor are . As steps in our proof, we find a new expander mixing lemma for a -partite, -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.
arXiv comment35 pages, 4 figures. To appear in SIAM Journal on Mathematics of Data Science
References in corpus (10)
- A Simpler Approach to Matrix Completion
- Multi-Task Feature Learning Via Efficient l2,1-Norm Minimization
- Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery
- Provable Tensor Factorization with Missing Data
- Noisy low-rank matrix completion with general sampling distribution
- Matrix Completion via Max-Norm Constrained Optimization
- Mixing in high-dimensional expanders
- Spectral gap in random bipartite biregular graphs and applications
- Matrix Completion from Samples in Linear Time
- Sparse random tensors: Concentration, regularization and applications