Sub-linear time algorithms for sparse signal estimation and learning via coding theoretic tools

Kannan Ramchandran, Kangwook Lee, Ramtin Pedarsani, Orhan Ocal, Dong Yin, Reinhard Heckel and Xiao Li

National Science Foundation CCF-EAGER-1439725 and Air Force Office of Scientific Research MURI Chase 556016

Our era of data deluge is seriously challenging our ability to scale in diverse fields in engineering and the sciences (both physical and data-oriented). Sparsity in data structure offers promise in addressing this challenge, as evidenced by the success of fields like compressed sensing. However, existing popular methods are typically based on convex relaxation techniques, which scale polynomially with the problem dimension, and are getting increasingly hard to scale. In this project, we view the problem of sparse estimation and learning in high-dimensional problems through a novel sparse-graph coding lens. Using a simple divide-and-conquer philosophy and fast peeling-based decoding, we show how to achieve sub-linear time costs for both acquisition, queries and computation. This helps us break the complexity barrier while providing strict performance guarantees, and has the potential to enable "real-time" processing of massive data-sets featuring sparsity. This framework can be used for a host of problems from sparse discrete transform computations to compressed sensing and phase-retrieval, with applications to imaging, optics, quantum information systems, and machine learning.

Figure 1
Figure 1: Sub-linear time algorithms for sparse signal estimation and learning via coding theoretic tools

Li, Xiao, and Kannan Ramchandran. "An Active Learning Framework using Sparse-Graph Codes for Sparse Polynomials and Graph Sketching." Advances in Neural Information Processing Systems. 2015.
XiaoLi, S. Pawar and K. Ramchandran, Sub-linear Time Support Recovery for Compressed Sensing Using Sparse-Graph Codes, arXiv preprint arXiv:1412.7646 (2014).