Deterministic tensor completion with hypergraph expanders
This work addresses tensor completion, a problem in machine learning and data analysis, by providing the first deterministic analysis, which is incremental as it builds on existing methods with new theoretical insights.
The paper tackles the problem of low-rank tensor completion by using hypergraph expanders and minimizing the max-quasinorm, showing that the number of samples needed for approximate recovery is linear in n under constant rank and order assumptions. It includes a practical algorithm and numerical experiments to demonstrate efficacy.
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.