论文标题
无限核的切割标准和抽样引理
The cut norm and Sampling Lemmas for unbounded kernels
论文作者
论文摘要
概括了Borgs，Chayes，Lovász，Sós和Vesztergombi（2008）的有界内核结果，我们证明了在剪切规范方面无限制内核的两个采样引理。一方面，我们证明了一个（对称的）内核$ u \ in l^p（[0,1]^2）$对于一些$ 3 <p <p <\ infty $，$ u $的随机$ k $ - 样本的缩短规范在$ o（k^{ - \ frac14+\ frac+frac \ frac} $ a $} $ a $} $ a $} $ a $ a $ a $ a $ a $ a $ a $ a $ a的可能性很高。样品的切割规范对比原始的偏差有很大的偏见，从而使我们实际上获得了更强的高概率限制$ o（k^{ - \ frac 12+ \ frac1p+\ varepsilon}）$，它可以较小，而它可以较小（对于任何$ p> 2 $）。然后将这些结果部分扩展到矢量有价值核的情况。另一方面，我们表明，$ k $ -samples在切割度量中也接近$ u $，尽管较弱的订单$ o（（\ ln k）^{ - \ frac12+\ frac1+\ frac1 {2pp}}}}）$（对于任何适当的$ p> 2 $）。作为推论，我们每当以$ p> 4 $中的$ u \ in l^p $中的$ u \ u \ $ k $ -samples肯定会肯定地汇聚为$ k \ $ k \ to \ infty $时。
Generalizing the bounded kernel results of Borgs, Chayes, Lovász, Sós and Vesztergombi (2008), we prove two Sampling Lemmas for unbounded kernels with respect to the cut norm. On the one hand, we show that given a (symmetric) kernel $U\in L^p([0,1]^2)$ for some $3<p<\infty$, the cut norm of a random $k$-sample of $U$ is with high probability within $O(k^{-\frac14+\frac{1}{4p}})$ of the cut norm of $U$. The cut norm of the sample has a strong bias to being larger than the original, allowing us to actually obtain a stronger high probability bound of order $O(k^{-\frac 12+\frac1p+\varepsilon})$ for how much smaller it can be (for any $p>2$ here). These results are then partially extended to the case of vector valued kernels. On the other hand, we show that with high probability, the $k$-samples are also close to $U$ in the cut metric, albeit with a weaker bound of order $O((\ln k)^{-\frac12+\frac1{2p}})$ (for any appropriate $p>2$). As a corollary, we obtain that whenever $U\in L^p$ with $p>4$, the $k$-samples converge almost surely to $U$ in the cut metric as $k\to\infty$.
