Local sparse coding on a Delaunay triangulation: structured sensing and stability analysis using distance geometry

Sparse coding is a technique of representing data as a sparse linear combination of a set of vectors. This representation facilitates computation and analysis of high-dimensional data that is prevalent in many applications. We study sparse coding in the setting where the set of vectors define a unique Delaunay triangulation. We propose a weighted l1 regularizer and show that it provably yields a sparse solution. Further, we show that the stability of sparse codes depends on local distances which can be suitably estimated using the Cayley-Menger determinant. We make connections to dictionary learning, manifold learning and computational geometry. We discuss an optimization algorithm to learn the sparse codes and optimal set of vectors given a set of data points. Finally, we show numerical experiments to illustrate that the resulting sparse representations yield competitive performance for the problem of clustering.