首次揭示分数阶p范数在高维中何时集中,打破以往误解。
When fractional quasi p-norms concentrate
- 提出分数阶p范数集中性的判断条件,适用于广泛分布类。
- 发现多数分布下范数具均匀且指数级集中,与p值无关。
- 揭示邻近分布可反向抗集中,适合设计特定数据编码方案。
高维距离集中性是构建稳定可靠数据分析算法的关键因素。本文首次系统解答了分数阶准p-范数(p∈(0,1))在高维下的集中性长期悬而未决的核心问题。该主题长期存在理论与实证争议。我们首次明确指出,在广义分布类下,分数阶准p-范数具有指数级且对p一致的集中界,从而否定了此前通过‘最优’选取p∈(0,1)缓解集中的建议。同时,我们给出仍可通过p调节控制集中速率的分布条件。更重要的是,我们证明:在一大类具均匀集中的分布任意邻域内,存在不可数多个呈现反集中的分布。这一现象为设计有利或抑制距离集中的数据编码/表征方案提供了可能。研究澄清了该领域长期存在的理论与实证矛盾。
原文摘要 · Abstract (English)
Concentration of distances in high dimension is an important factor for the development and design of stable and reliable data analysis algorithms. In this paper, we address the fundamental long-standing question about the concentration of distances in high dimension for fractional quasi $p$-norms, $p\in(0,1)$. The topic has been at the centre of various theoretical and empirical controversies. Here we, for the first time, identify conditions when fractional quasi $p$-norms concentrate and when they don't. We show that contrary to some earlier suggestions, for broad classes of distributions, fractional quasi $p$-norms admit exponential and uniform in $p$ concentration bounds. For these distributions, the results effectively rule out previously proposed approaches to alleviate concentration by "optimal" setting the values of $p$ in $(0,1)$. At the same time, we specify conditions and the corresponding families of distributions for which one can still control concentration rates by appropriate choices of $p$. We also show that in an arbitrarily small vicinity of a distribution from a large class of distributions for which uniform concentration occurs, there are uncountably many other distributions featuring anti-concentration properties. Importantly, this behavior enables devising relevant data encoding or representation schemes favouring or discouraging distance concentration. The results shed new light on this long-standing problem and resolve the tension around the topic in both theory and empirical evidence reported in the literature.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。