Efficient Compressed Sensing with L0 Projections

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.