论文标题
在神经科学限制下对约翰逊·林顿斯转变的简单分析
Simple Analysis of Johnson-Lindenstrauss Transform under Neuroscience Constraints
论文作者
论文摘要
该论文重新分析了著名的Johnson-Lindenstrauss Lemma的版本，其中矩阵受到了自然而然地从神经科学应用中出现的约束：a）稀疏性和b）签名稳定性。这种特殊的变体首先是由艾伦·祖（Allen-Zhu），盖拉什维利（Gelashvili），米卡利（Micali），莎维特（Shavit）以及贾加德森（Jagadeesan）（随机'19）研究的。 这项工作的贡献是一个新颖的证明，与以前的工作相比，a）使用现代概率工具包，尤其是次高斯和伽玛估算的基础知识b）是独立的，没有对微妙的第三方结果c）提供显式常数。 我们证明的核心是Hanson-Wright引理的一种新型变体（关于二次形式的浓度）。独立感兴趣的也是高斯下随机变量的辅助事实。
The paper re-analyzes a version of the celebrated Johnson-Lindenstrauss Lemma, in which matrices are subjected to constraints that naturally emerge from neuroscience applications: a) sparsity and b) sign-consistency. This particular variant was studied first by Allen-Zhu, Gelashvili, Micali, Shavit and more recently by Jagadeesan (RANDOM'19). The contribution of this work is a novel proof, which in contrast to previous works a) uses the modern probability toolkit, particularly basics of sub-gaussian and sub-gamma estimates b) is self-contained, with no dependencies on subtle third-party results c) offers explicit constants. At the heart of our proof is a novel variant of Hanson-Wright Lemma (on concentration of quadratic forms). Of independent interest are also auxiliary facts on sub-gaussian random variables.
