Abstract
高次元における距離の集中（concentration）は、安定で信頼性の高いデータ解析アルゴリズムの開発および設計において重要な要因である。本論文では、分数型準 p-ノルム（fractional quasi p-norms, p\in(0,1)）に関する、高次元における距離の集中に関する基礎的で長年の問題に取り組む。この話題は、さまざまな理論的・経験的な論争の中心にあった。ここで我々は初めて、「分数型準 p-ノルムが集中する場合」と「集中しない場合」の条件を明確にする。我々は、これまでのいくつかの提案とは対照的に、広いクラスの分布に対して、分数型準 p-ノルムが指数関数的かつ p に一様な（uniform in p）集中境界を満たすことを示す。これらの分布に対する結果は、(0,1) の範囲で p の値を「最適に」設定することで、距離の集中を緩和するために提案されてきた従来のアプローチを事実上排除する。同時に、適切な p の選択によって集中率（concentration rates）をなお制御できる条件と、そのときの分布の族（families）を特定する。さらに、大きな分布のクラスのうち一様な集中が起こる分布から、任意に小さな近傍（vicinity）の中には、反集中（anti-concentration）特性を特徴とする他の無数に多い分布が存在することも示す。重要な点として、この挙動は、距離の集中を助長する／抑制するような、関連するデータの符号化（encoding）または表現（representation）の方式を考案できることを可能にする。本結果は、この長年の問題に新たな光を当て、文献中に報告された理論と経験的証拠の双方における当該分野の緊張関係を解消する。
