Keaton Hamm

The Subspace Clustering Problem is an unsupervised Machine Learning problem in which data in a high-dimensional Euclidean space is assumed to actually come from the union of low-dimensional affine subspaces, and the goal is to find a partition of the data for which each partition (cluster) corresponds to the data from a given subspace. Subsequently, one can find a basis for the subspace. There are many applications in which data naturally fits this framework including motion segmentation, particle picking in cryo-electon microscopy, and object recognition under different illumination patterns.

With Akram Aldroubi (Math, Vanderbilt University), Ali Sekmen (Computer Science, Tennessee State University), and Bugra Koku (Mechanical Engineering, Middle East Technical University), I proved that CUR decompositions lead to a solution of the Subspace Clustering problem, and we gave an algorithm which is robust to noise and achieved the best performance to date on the Hopkins155 motion segmentation dataset.

CUR decompositions are relatively little-known matrix factorizations obtained by choosing column and row submatrices from a given matrix. Longxiu Huang (Math, UCLA) and I have characterized CUR decompositions and done a thorough perturbation analysis for variants of this factorization. Additionally, we give sampling guarantees which show when randomly sampling column and row submatrices yield a CUR decomposition of a low-rank matrix with high probability.

Graph sketches are subgraphs of a large graph which approximately maintain some property of the initial graph, such as pairwise distances between vertices. In this case, the sketch is called a graph spanner. With Stephen Kobourov’s group at University of Arizona along with Greg Bodwin, I have written a survey of graph spanners.

We have also introduced the subject of multi-level graph spanners, and considered several algorithmic solutions to the problem. All Manifold Learning algorithms include a graph sparsification step to approximate geodesic distances; we hope to apply spanner techniques in this arena in the near future.

Sampling theory asks the question: given a class of functions, if we have access to a set of discrete measurements for a given function f , is it possible to reconstruct f from these measurements? If so, how can this reconstruction be done in a computationally efficient manner?

Modern sampling theory has attempted to go as far beyond Paley–Wiener (or bandlimited) signals as possible, and my research has been on interpolation of smooth functions (Sobolev or Triebel–Lizorkin classes) by approximants in quasi shift-invariant spaces, which are relatively unstructured generalizations of bandlimited signals.