Algorithms that analyze patches extracted from time series or images have led to state-of-the art techniques for classification, denoising, and the study of nonlinear dynamics.
In the first part of the talk we describe two examples of such algorithms: a novel method to estimate the arrival-times of seismic waves from a seismogram, and a new patch-based method to denoise images. Both approaches combines the following two ingredients: the signals (times series or images) are first lifted into a high-dimensional space using time/space-delay embedding; the resulting phase space is then parametrized using a nonlinear method based on the eigenvectors of the graph Laplacian. Both algorithms outperform existing gold standards.
In the second part of the talk we provide a theoretical explanation for the success of algorithms that organize patches according to graph-based metrics. Our approach relies on a detailed analysis of the commute time on prototypical graph models that epitomize the geometry observed in general patch-graphs.