AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

Learning approximately block sparse vectors using a small number of linear measurements is a standard task in the sparse recovery/compressed sensing literature. Schemes achieving a constant factor approximation are long known, e.g. using model-based RIP. We give an asymptotically measurement-optimal scheme achieving (1+eps)-approximation, which runs in near-linear time in the length of the vector. As an intriguing side result, we obtain the simplest known measurement-optimal l_2/l_2 sparse recovery scheme recorded in the literature. The main component of our algorithm is a subtle variant of the classic CountSketch data structure where the random signs are substituted by Gaussians and the number of repetitions (rows) is tuned to smaller than usual. We also provide experimental evaluation in synthetic and real datasets.

--------
Join Zoom Meeting
Meeting ID: 527 278 8807

Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.

Sándor Kisfaludi-Bak

--email hidden

Join Zoom Meeting
Meeting ID: 527 278 8807

Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.