Sunday, December 24, 2006

Compressed Sensing in Media, Contd.

Barry Cipra and SIAM News join the line, discussing Compressed Sensing. Unlike the Economist and the Guardian, this article in the November issue is somewhat technical and discusses the idea of going from l_2 and l_0 in sparse approximations to l_1 where linear programming applies. Alas, perhaps because the focus is on l_1, the article leaves out much of the work in theoretical CS that uses direct combinatorial ie., l_0 techniques to solve these problems. Work in TCS that predates Compressed Sensing include sampling for fourier reconstruction in learning theory (Mansour), complexity theory (Akavia, Goldwasser, Safra) and streaming (Gilbert, Guha, Indyk, M, Strauss). The articles has a great quote from Bob Dylan.


Blogger igor said...

Are those l_0 techniques competitive with the l_1 breakthrough ?


2:21 PM  

Post a Comment

<< Home