The weekly SILO Seminar Series is made possible through the generous support of the 3M Company and its Advanced Technology Group


with additional support from the Analytics Group of the Northwestern Mutual Life Insurance Company

Northwestern Mutual

Efficient Compressed Sensing with L0 Projections

Ping Li, Assistant Professor, Statistics, Cornell

Date and Time: Apr 30, 2013 (12:30 PM)
Location: 2nd floor Research Link of WID. Please see the front desk for access to the building if someone is not at the door.


Many applications concern sparse signals, for example, detecting anomalies from the differences between consecutive images taken by surveillance cameras. In general, anomaly events are sparse. This talk focuses on the problem of recovering a K-sparse signal in N dimensions (coordinates). Classical theories in compressed sensing say the required number of measurement is M = O(K log N). In our most recent work on L0 projections, we show that an idealized algorithm needs about M = 5K measurements, regardless of N. In particular, 3 measurements suffice when K = 2 nonzeros. Practically, our method is very fast, accurate, and very robust against measurement noises. Even when there are no sufficient measurements, the algorithm can still accurately reconstruct a significant portion of the nonzero coordinates, without catastrophic failures (unlike popular methods such as linear programming). This is joint work with Cun-Hui Zhang at Rutgers University.