2019/10/23 by Kameron Decker Harris, Yizhe Zhu · 1 voice · 1 citation
Computer Science · Mathematics · #cs.LG #math.OC #math.ST #stat.ML #stat.TH
paper · pdf · doi:10.1137/20m1379745
published as SIAM Journal on Mathematics of Data Science, 3(4), 1117-1140, 2021 · 35 pages, 4 figures. To appear in SIAM Journal on Mathematics of Data Science
arxiv published 2019/10/23 · arxiv created 2021/07/29 · arxiv updated 2021/10/11
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.