SHO-FA: Robust compressive sensing with order-optimal complexity, measurements, and bits

Mayank Bakshi, Sidharth Jaggi, Sheng Cai +1

Suppose x is any exactly k-sparse vector in R^n. We present a class of sparse matrices A, and a corresponding algorithm that we call SHO-FA (for Short and Fast) that, with high pro…