Physics – Data Analysis – Statistics and Probability
Scientific paper
2011-07-02
Physics
Data Analysis, Statistics and Probability
Scientific paper
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.
Meyer Francois G.
Taylor Kye M.
No associations
LandOfFree
A random walk on image patches does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A random walk on image patches, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A random walk on image patches will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-706990