标题： 图像块上的随机游走 显示英文标题

标题： A random walk on image patches

摘要： 本文研究了根据基于图的度量组织补丁算法成功的原理问题。分析从图像或时间序列中提取的补丁的算法已经带来了最先进的分类、去噪和非线性动力学研究技术。 本工作的主要贡献在于为上述实验观察提供了一个理论解释。 我们的方法依赖于对原型图模型中通勤时间度量的详细分析，这些图模型概括了一般补丁图中观察到的几何形状。 我们证明了基于通勤时间的图参数化会缩小信号中对应局部快速变化的补丁之间的互距离，而对应局部缓慢变化的补丁之间的距离则会扩大。 因此，我们的结果解释了为何基于拉普拉斯算子特征函数的补丁集参数化可以集中那些对应局部快速变化的补丁，否则这些补丁会在补丁空间中分散。 虽然我们的结果基于大样本分析，但对合成数据和真实数据的数值实验表明，对于实践中非常小的数据集，结果仍然成立。 显示英文摘要

摘要： In this paper we address the problem of understanding the success of algorithms that organize patches according to graph-based metrics. Algorithms that analyze patches extracted from images or time series have led to state-of-the art techniques for classification, denoising, and the study of nonlinear dynamics. The main contribution of this work is to provide a theoretical explanation for the above experimental observations. Our approach relies on a detailed analysis of the commute time metric on prototypical graph models that epitomize the geometry observed in general patch graphs. We prove that a parametrization of the graph based on commute times shrinks the mutual distances between patches that correspond to rapid local changes in the signal, while the distances between patches that correspond to slow local changes expand. In effect, our results explain why the parametrization of the set of patches based on the eigenfunctions of the Laplacian can concentrate patches that correspond to rapid local changes, which would otherwise be shattered in the space of patches. While our results are based on a large sample analysis, numerical experimentations on synthetic and real data indicate that the results hold for datasets that are very small in practice.