图 书 馆
p电阻族中的相变Phase transition in the family of p-resistances |
|
| 课程网址: | http://videolectures.net/nips2011_alamgir_resistances/ |
| 主讲教师: | Morteza Alamgir |
| 开课单位: | 马克斯普朗克研究所 |
| 开课时间: | 2012-09-06 |
| 课程语种: | 英语 |
| 中文简介: |  我们在图表上研究p≥1的p电阻族。该族概括了标准电阻距离。我们证明对于任何固定的图，对于p = 1，p电阻与最短路径距离重合，对于p = 2，它与标准电阻距离重合，对于p→∞，它收敛于最小st切口的倒数。在图中。其次，当图中顶点数n趋于无穷大时，我们考虑随机几何图的特殊情况（例如k个最近邻图）。我们证明发生了有趣的相变。存在两个临界阈值p ^ *和p ^。因此，如果p p ^，则仅取决于琐碎的局部量，而不取决于传达任何有用的信息。我们可以显式计算临界值：p ^ * = 1 1 /（d 1）和p ^ = 1 1 /（d 2）其中d是基础空间的维数（我们相信存在一个很小的事实p ^ *和p ^之间的差距是我们的证明。我们还将发现与拉普拉斯正则化相关，并建议使用q个拉普拉斯正则化器，其中q满足1 / p ^ * 1 / q = 1。 |
| 课程简介: | We study the family of p-resistances on graphs for p ≥ 1. This family generalizes the standard resistance distance. We prove that for any fixed graph, for p=1, the p-resistance coincides with the shortest path distance, for p=2 it coincides with the standard resistance distance, and for p → ∞ it converges to the inverse of the minimal s-t-cut in the graph. Secondly, we consider the special case of random geometric graphs (such as k-nearest neighbor graphs) when the number n of vertices in the graph tends to infinity. We prove that an interesting phase-transition takes place. There exist two critical thresholds p^* and p^ such that if p < p^*, then the p-resistance depends on meaningful global properties of the graph, whereas if p > p^, it only depends on trivial local quantities and does not convey any useful information. We can explicitly compute the critical values: p^* = 1 + 1/(d-1) and p^ = 1 + 1/(d-2) where d is the dimension of the underlying space (we believe that the fact that there is a small gap between p^* and p^ is an artifact of our proofs. We also relate our findings to Laplacian regularization and suggest to use q-Laplacians as regularizers, where q satisfies 1/p^* + 1/q = 1. |
| 关 键 词: | 临界阈值; 拉普拉斯定则 |
| 课程来源: | 视频讲座网 |
| 数据采集: | 2020-10-14：zyk |
| 最后编审: | 2021-01-08：yumf |
| 阅读次数: | 45 |