Tuesday, January 20, 2009

CS: GPSR 6.0, ILRS Minimization for Sparse Recovery Code and On Sparse Solutions of Underdetermined Linear Systems, Data Streams

The GPSR page was updated showing that now GPSR is at version 6.0: Download it at GPSR_6.0. Thank you Mário Figueiredo, Robert D. Nowak, Stephen J. Wright!

I featured the paper before, but Massimo Fornasier just released the attendant poster and the code featured in Iteratively Re-weighted Least Squares Minimization for Sparse Recovery by Ingrid Daubechies, Ronald DeVore, Massimo Fornasier, and C. Sinan Güntürk. The codes are here:

They are also in the reconstruction section of the big picture in compressive sensing.

Here is also a survey article on l_p areconstruction techniques in On Sparse Solutions of Underdetermined Linear Systems by Ming-Jun Lai. The abstract reads:
We first explain the research problem of finding the sparse solution of underdetermined linear systems with some applications. Then we explain three different approaches how to solve the sparse solution: the ℓ1 approach, the orthogonal greedy approach, and the ℓq approach with 0 less q less 1. We mainly survey recent results and present some new or simplified proofs. In particular, we give a good reason why the orthogonal greedy algorithm converges and why it can be used to find the sparse solution. About the restricted isometry property (RIP) of matrices, we provide an elementary proof to a known result that the probability that the random matrix with iid Gaussian variables possesses the PIP is strictly positive.


The 2009 Annual Workshop on Computational Complexity in Barbados will feature S. Muthu Muthukrishnan who will be the main speaker. The course is titled Data Streams:
Proposed outline

In order to deal with massive data that arrives rapidly and has to be processed instantly, the theoretical computer science community has developed the sublinear space, polylog time-per item, one-pass "data stream" model. In this course, we will study the theory of algorithms in the data stream model. Lectures will include (from here):

* Data stream models and applications
* Forward distributions and Sketches
* Inverse distributions and Samples.
* Advanced Topic: Lower bounds in Data Stream model.
* Advanced Topic: Algorithms for graph, geometric, matrix streams.
* Advanced Topic: Second generation models including multipass, MapReduce and Probablistic streams.
* Applications beyond data streams: compressed sensing, machine learning.

We start with the basic material from the book "Data Streams and Applications", but the advanced material is from the ongoing Stream 2.0 survey with Andrew McGregor.

Background material is a document entitled: Data Streams: Algorithms and Applications.

No comments:

Printfriendly