Concentration of bounded sparse chaoses and sparse Khatri-Rao embeddings
Abstract
We prove moment and mixed-tail inequalities for decoupled homogeneous chaoses of arbitrary fixed order generated by independent, centered, bounded random variables with coordinate-dependent second-moment bounds. The estimates hold for arbitrary real rectangular coefficient tensors and are expressed through weighted slice and partition norms. A Bennett-type logarithmic correction sharpens the contribution of the largest coefficient to these bounds. The proof combines a comparison with sums of sparse exponential variables with an elementary replication argument. We also extend the results to diagonal-free non-decoupled chaoses and sparse sub-exponential inputs. As an application, we establish conditions under which sparse Khatri--Rao random projections approximately preserve norms and inner products for finite collections of tensors. For a sparse random relation containing a planted dense block, we prove matching upper and lower bounds on the required projection dimension, demonstrating the sharpness of the logarithmic correction.
Related
- New tools for sparse graph embeddings: Hybrid expanders and application to nested cycles
- A General Kernel Framework for Non-CND Distance Measures Using |D|-Dimensional Sparse Landmark Embeddings
- Two-point concentration for graph classes admitting sparse vertex deletion
- Sharp spectral norm concentration and regularization of sparse random tensors
- Concentration of Regularized Sparse Random Matrices: Spectral Edge Bounds via Nonbacktracking Operators
BibTeX
@misc{dai2026concentration,
title = {{Concentration of bounded sparse chaoses and sparse Khatri-Rao embeddings}},
author = {Guozheng Dai and Yiyun He and Ke Wang and Yizhe Zhu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.28875},
eprint = {2609.28875},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.28875},
}
RIS
TY - UNPB
TI - Concentration of bounded sparse chaoses and sparse Khatri-Rao embeddings
AU - Guozheng Dai
AU - Yiyun He
AU - Ke Wang
AU - Yizhe Zhu
PY - 2026
DA - 2026/09/24
PB - arXiv
DO - 10.48550/arxiv.2609.28875
UR - https://arxiv.org/abs/2609.28875
AB - We prove moment and mixed-tail inequalities for decoupled homogeneous chaoses of arbitrary fixed order generated by independent, centered, bounded random variables with coordinate-dependent second-moment bounds. The estimates hold for arbitrary real rectangular coefficient tensors and are expressed through weighted slice and partition norms. A Bennett-type logarithmic correction sharpens the contribution of the largest coefficient to these bounds. The proof combines a comparison with sums of sparse exponential variables with an elementary replication argument. We also extend the results to diagonal-free non-decoupled chaoses and sparse sub-exponential inputs. As an application, we establish conditions under which sparse Khatri--Rao random projections approximately preserve norms and inner products for finite collections of tensors. For a sparse random relation containing a planted dense block, we prove matching upper and lower bounds on the required projection dimension, demonstrating the sharpness of the logarithmic correction.
ER -