We prove a non-asymptotic concentration inequality for the spectral norm of sparse inhomogeneous random tensors with Bernoulli entries. For an order-$k$ inhomogeneous random tensor $T$ with sparsity $p_{max}geq frac{clog n}{n }$, we show that $|T-mathbb E T|=O(sqrt{n p_{max}}log^{k-2}(n))$ with high probability. The optimality of this bound up to polylog factors is provided by an information theoretic lower bound. By tensor unfolding, we extend the range of sparsity to $p_{max}geq frac{clog n}{n^{m}}$ with $1leq mleq k-1$ and obtain concentration inequalities for different sparsity regimes. We also provide a simple way to regularize $T$ such that $O(sqrt{n^{m}p_{max}})$ concentration still holds down to sparsity $p_{max}geq frac{c}{n^{m}}$ with $k/2leq mleq k-1$. We present our concentration and regularization results with two applications: (i) a randomized construction of hypergraphs of bounded degrees with good expander mixing properties, (ii) concentration of sparsified tensors under uniform sampling.
Download