BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Sharpness\, Restart and Compressed Sensing Performance - Alex d'As
 premont (CNRS - Ecole Normale Superieure Paris)
DTSTART:20180117T090000Z
DTEND:20180117T094500Z
UID:TALK97717@talks.cam.ac.uk
CONTACT:INI IT
DESCRIPTION:Joint work with Vincent Roulet (University of Washington) and 
 Nicolas Boumal (Princeton University).  We show that several classical qua
 ntities controlling compressed sensing performance directly match paramete
 rs controlling algorithmic complexity. We first describe linearly converge
 nt restart schemes on first-order methods using a sharpness assumption. Th
 e Lojasievicz inequality shows that sharpness bounds on the minimum of con
 vex optimization problems hold almost generically. Here\, we show that sha
 rpness directly controls the performance of restart schemes. For sparse re
 covery problems\, sharpness at the optimum can be written as a condition n
 umber\, given by the ratio between true signal sparsity and the largest si
 gnal size that can be recovered by the observation matrix. Overall\, this 
 means that in compressed sensing problems\, a single parameter directly co
 ntrols both computational complexity and recovery performance.
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR