noiseless/nonnegative sparse recovery and feature retrieval via compressed sensing
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Type Name Latest commit message Commit time
Failed to load latest commit information.
LICENSE readme upd8 May 8, 2018


This module provides solvers and utility functions for several problems in sparse recovery/compressed sensing. The file, which depends only on NumPy/SciPy and can be used with Python 2 or 3, provides methods to compute the following:

  • Basis Pursuit (BP), including Nonnegative BP (BP+); the BP solver is ported from the l1-MAGIC MATLAB package [1]; the BP+ solver is based on the same primal-dual interior point method [2].
  • Orthogonal Matching Pursuit (OMP), including Nonnegative OMP (OMP+).
  • Supporting Hyperplane Property (SHP), a property that guarantees recovery of a signal x from linear measurements Ax via BP+ [3].

The feature retrieval files (, additionally require scikit-learn and text_embedding. These files are used by scripts in the directory scripts-AKSV2018 to recreate the results in [3].

If you find this code useful please cite the following:

  title={A Compressed Sensing View of Unsupervised Text Embeddings, Bag-of-n-Grams, and LSTMs},
  author={Arora, Sanjeev and Khodak, Mikhail and Saunshi, Nikunj and Vodrahalli, Kiran},
  booktitle={Proceedings of the 6th International Conference on Learning Representations (ICLR)},


[1] Candès & Romberg, "l1-MAGIC: Recovery of Sparse Signals via Convex Programming," Technical Report, 2005.

[2] Boyd & Vandenberghe, "Chapter 11: Interior-point Methods," Convex Optimization, 2004.

[3] Arora et al., "A Compressed Sensing View of Unsupervised Text Embedding, Bag-of-n-Grams, and LSTMS," ICLR, 2018.