Date of Award

Spring 1-1-2011

Document Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Applied Mathematics

First Advisor

Francois G. Meyer

Second Advisor

James H. Curry

Third Advisor

Juan G. Restrepo

Abstract

In this thesis, we study the representation of local, or fine scale, snippets --- or patches --- that are extracted from a signal or image. We describe a method that characterizes the dimensionality that is observed in the set of patches when they are regarded as points in Euclidean space. Our approach is based on the assumption that the signal or image is composed of solutions to ordinary differential equations of a certain class. We also provide a theoretical interpretation --- via graph models --- that explains the success of analyzing signal and image patches using diffusion-based graph metrics. Our framework is built on the assumption that there exists a partition of the signal or image's patches. Specifically, we assume there are two subsets of patches. One set comprises patches that are connected through some type of coherence in the domain of the signal, such as temporal coherence in time series, or spatial coherence between patches in the image plane. The other set comprises patches whose edge connections are not so largely influenced by the aforementioned coherence. Instead, these connections are more sporadic, with little relationship between the locations in the signal or image domain from which the patches were extracted. Using the commute time metric --- a diffusion-based graph metric --- we prove that the average proximity between patches in the first set grows faster than the average proximity between patches in the second set, as the number of patches approaches infinity. Consequently, a parametrization of the patches based on commute times will relatively cluster the second set of patches, which is the first step toward solving a larger problem, such as classification or clustering of the patches, detection of anomalies, or segmentation of an image. In addition to our theoretical results, this thesis also evaluates numerical procedures designed to efficiently compute the spectral decomposition of large matrices. These procedures include the Nystrom extension, and a multilevel eigensolver. Finally, we benchmark a classifier that is trained on the commute time embedding of a dataset of seismic events, against a standard algorithm used to detect arrival-times.

Share

COinS