  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.
