文章基本信息

标题：Sparse random tensors: Concentration, regularization and applications
本地全文：下载
作者：Zhixin Zhou ; Yizhe Zhu
期刊名称：Electronic Journal of Statistics
印刷版ISSN：1935-7524
出版年度：2021
卷号：15
期号：1
页码：2483-2516
DOI：10.1214/21-EJS1838
语种：English
出版社：Institute of Mathematical Statistics
摘要：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 pmax≥clogn n, we show that ‖T−ET‖=O(np maxlogk−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 pmax≥clogn nm with 1≤m≤k−1 and obtain concentration inequalities for different sparsity regimes. We also provide a simple way to regularize T such that O(nmpmax) concentration still holds down to sparsity pmax≥c nm with k∕2≤m≤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.
关键词：15B52; 60C05; hypergraph expander; Sparse random tensor; spectral norm; tensor sparsification