Geometry of Sparse Representations

Add to your list(s) Download to your calendar using vCal

• Mark Plumbley, Center for Digital Music, Queen Mary University of London
• Tuesday 12 December 2006, 13:00-14:00
• LR5, Engineering, Department of.

If you have a question about this talk, please contact Taylan Cemgil.

Room changed

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.

This talk is part of the Signal Processing and Communications Lab Seminars series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge University Engineering Department Talks
• Cambridge talks
• Centre for Smart Infrastructure & Construction
• Chris Davis' list
• Computational Continuum Mechanics Group Seminars
• Featured lists
• Information Engineering Division seminar list
• Interested Talks
• LR5, Engineering, Department of
• School of Technology
• Signal Processing and Communications Lab Seminars
• Trust & Technology Initiative - interesting events
• bld31
• ndk22's list
• ob366-ai4er
• rp587

Note that ex-directory lists are not shown.