标题： 黎曼流形上基于图拉普拉斯近似张量扩展器的切尔诺夫界 显示英文标题

标题： Chernoff Bounds for Tensor Expanders on Riemannian Manifolds Using Graph Laplacian Approximation

摘要： 本文研究了概率尾部界分析的进步，这是评估随机变量偏离其期望值的概率的统计工具中的关键部分。传统的尾部界，如马尔可夫界、切比雪夫界和切尔诺夫界，在众多科学和工程领域已被证明具有价值。然而，随着数据复杂性的增加，迫切需要将尾部界估计从标量变量扩展到高维随机对象。现有的研究通常依赖于高维随机对象之间独立性的假设，而这一假设并不总是成立。基于Garg等人以及Chang的研究工作，他们利用随机游走来模拟高维集合，本研究通过探索流形上的随机游走引入了一种更通用的方法。为了解决为流形构建适当底层图的挑战，我们提出了一种新颖的方法，以增强近似流形的图上的随机游走。此方法确保原始流形与近似图之间的光谱相似性，包括匹配特征值、特征向量和特征函数。利用Burago等人提出的流形图近似技术，我们推导出张量切尔诺夫界，并根据流形的光谱特性建立其在黎曼流形上随机游走的范围。 显示英文摘要

摘要： This paper addresses the advancement of probability tail bound analysis, a crucial statistical tool for assessing the probability of large deviations of random variables from their expected values. Traditional tail bounds, such as Markov's, Chebyshev's, and Chernoff bounds, have proven valuable across numerous scientific and engineering fields. However, as data complexity grows, there is a pressing need to extend tail bound estimation from scalar variables to high-dimensional random objects. Existing studies often rely on the assumption of independence among high-dimensional random objects, an assumption that may not always be valid. Building on the work of researchers like Garg et al. and Chang, who employed random walks to model high-dimensional ensembles, this study introduces a more generalized approach by exploring random walks over manifolds. To address the challenges of constructing an appropriate underlying graph for a manifold, we propose a novel method that enhances random walks on graphs approximating the manifold. This approach ensures spectral similarity between the original manifold and the approximated graph, including matching eigenvalues, eigenvectors, and eigenfunctions. Leveraging graph approximation technique proposed by Burago et al. for manifolds, we derive the tensor Chernoff bound and establish its range for random walks on a Riemannian manifold according to the underlying manifold's spectral characteristics.