Abstract

Geometrical considerations can often give us insights or new approaches to tricky problems. One of these is the “sparse representation” problem. Here we would like to represent a given vector or signal as a linear combination of basis vectors (or signals), using as few “active” vectors as possible in our representation. For example, we might wish to represent the spectrum of a frame of polyphonic music using a small number of “active” note spectra.

In practice, we often approxmate this difficult problem by trying to approximate our vector y with y=Ax, where A is a basis matrix of column vectors, and x has minimum 1-norm. This problem is now a linear program (LP), and this type of solution is known as the “Basis Pursuit” (BP) or “Lasso” method. There are also other methods that build up an approximate sparse representation one basis vector at a time, including matching pursuit (MP), or orthogonal matching pursuit (OMP), although these do not guarantee to find the 1-norm (BP) solution. It is possible to find conditions where MP, OMP and BP methods give the same solution as the “minimum number of vectors” (minimum zero-norm) solution.

In this talk, I will give an overview of some of these methods, and investigate the operation of these from a geometrical perspective. In particular, we will see that the idea of convex polytopes, the generalization of polygons to high dimensions, will be useful. This will lead us to an algorithm to find sparse representations, called “Polytope Faces Pursuit”, that builds up a sparse solution like MP, but will also find the 1-norm solution eventually.