| The goal of sparse coding is to compute efficient representations of signals. The problem arises in diverse fields, ranging from theoretical neuroscience to signal processing. Current approaches cast sparse coding as an optimization problem to which standard methods are applied. These approaches ignore the geometric structure that underlies many classes of signals. In this dissertation we develop a geometric approach to sparse coding that exploits this structure.; Many classes of signal are observed to lie on low-dimensional manifolds in signal space. Capturing this structure is essential if sparse representations are to be computed. We show that if the dictionary, that is, the set of representational elements, is adapted to the signal manifold, and if minimum ℓ1 -norm signal representations are computed, then it is possible to almost always compute sparse, that is, minimum ℓ0-norm, signal representations and furthermore those representations will be as sparse as possible.; To compute minimum ℓ1-norm signal representations, we develop a new algorithm which we call Greedy Basis Pursuit (GBP). GBP is derived from a computational geometry and is equivalent to linear programming. We demonstrate that in some cases, GBP is capable of computing minimum ℓ 1-norm signal representations faster than standard linear programming methods.; Finally, to capture the geometric structure of the signal manifold we consider manifold learning approaches to dictionary learning. In particular, we experiment with clustering algorithms and show that the resulting dictionaries can be computed considerably faster than standard methods and that the results are often comparable. |
