Combinatorial Algorithms for Compressed Sensing

  • Graham Cormode
  • S. Muthukrishnan
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 4056)


In sparse approximation theory, the fundamental problem is to reconstruct a signal A ∈ ℝ n from linear measurements 〈A ψ i 〉 with respect to a dictionary of ψ i ’s. Recently, there is focus on the novel direction of Compressed Sensing [9] where the reconstruction can be done with very few—O(k logn)—linear measurements over a modified dictionary if the signal is compressible, that is, its information is concentrated in k coefficients with the original dictionary. In particular, these results [9, 4, 23] prove that there exists a single O(k logn) ×n measurement matrix such that any such signal can be reconstructed from these measurements, with error at most O(1) times the worst case error for the class of such signals. Compressed sensing has generated tremendous excitement both because of the sophisticated underlying Mathematics and because of its potential applications.

In this paper, we address outstanding open problems in Compressed Sensing. Our main result is an explicit construction of a non-adaptive measurement matrix and the corresponding reconstruction algorithm so that with a number of measurements polynomial in k, logn, 1/ε, we can reconstruct compressible signals. This is the first known polynomial time explicit construction of any such measurement matrix. In addition, our result improves the error guarantee from O(1) to 1 + ε and improves the reconstruction time from poly(n) to poly(k logn).

Our second result is a randomized construction of O(kpolylog (n)) measurements that work for each signal with high probability and gives per-instance approximation guarantees rather than over the class of all signals. Previous work on Compressed Sensing does not provide such per-instance approximation guarantees; our result improves the best known number of measurements known from prior work in other areas including Learning Theory [20, 21], Streaming algorithms [11, 12, 6] and Complexity Theory [1] for this case.

Our approach is combinatorial. In particular, we use two parallel sets of group tests, one to filter and the other to certify and estimate; the resulting algorithms are quite simple to implement.


Compress Sensing Unpublished Manuscript Explicit Construction Measurement Matrix Combinatorial Algorithm 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Akavia, A., Goldwasser, S., Safra, S.: Proving hard-core predicates by list decoding. In: FOCS, pp. 146–157 (2003)Google Scholar
  2. 2.
    Candès, E., Romberg, J., Tao, T.: Stable signals recovery from incomplete and inaccurate measurements (unpublished manuscript, 2005)Google Scholar
  3. 3.
    Candès, E., Rudelson, M., Tao, T., Vershynin, R.: Error correction via linear programming. In: FOCS (2005)Google Scholar
  4. 4.
    Candès, E., Tao, T.: Near optimal signal recovery from random projections and universal encoding strategies (2004),
  5. 5.
    Clementi, A., Monti, A., Silvestri, R.: Selective families, superimposed codes, and broadcasting on unknown radio networks. In: SODA (2001)Google Scholar
  6. 6.
    Cormode, G., Muthukrishnan, S.: What’s hot and what’s not: Tracking most frequent items dynamically. In: ACM PODS (2003)Google Scholar
  7. 7.
    Cormode, G., Muthukrishnan, S.: Towards an algorithmic theory of compressed sensing. DIMACS Tech Report 2005-25 (2005)Google Scholar
  8. 8.
    Devore, R., Lorentz, G.G.: Constructive Approximation, vol. 303. Springer, Grundlehren (1993)zbMATHGoogle Scholar
  9. 9.
    Donoho, D.: Compressed sensing (unpublished manuscript, 2004)Google Scholar
  10. 10.
    Du, D.-Z., Hwang, F.K.: Combinatorial Group Testing and Its Applications. Series on Applied Mathematics, vol. 3. World Scientific, Singapore (1993)zbMATHCrossRefGoogle Scholar
  11. 11.
    Gilbert, A., Guha, S., Indyk, P., Kotidis, Y., Muthukrishnan, S., Strauss, M.: Fast, small-space algorithms for approximate histogram maintenance. In: STOC (2002)Google Scholar
  12. 12.
    Gilbert, A., Guha, S., Indyk, P., Muthukrishnan, S., Strauss, M.: Near-optimal sparse Fourier representation via sampling. In: STOC (2002)Google Scholar
  13. 13.
    Gilbert, A., Muthukrishnan, S., Strauss, M.: Improved time bounds for near-optimal sparse Fourier representations. In: SPIE Conference on Wavelets (2005)Google Scholar
  14. 14.
    Haupt, J., Nowak, R.: Signal reconstruction from noisy random projections, (unpublished manuscript, 2005)Google Scholar
  15. 15.
    IEEE International Conference on Acoustics, Speech, and Signal Processing (2005)Google Scholar
  16. 16.
    Indyk, P.: Explicit constructions of selectors and related combinatorial structures, with applications. In: SODA (2002)Google Scholar
  17. 17.
    Indyk, P.: Personal communication (2005)Google Scholar
  18. 18.
    Integration of Sensing and Processing, Workshop at IMA (2005)Google Scholar
  19. 19.
    Kautz, W.H., Singleton, R.R.: Nonrandom binary superimposed codes. IEEE Transactions on on Information Theory 10, 363–377 (1964)zbMATHCrossRefGoogle Scholar
  20. 20.
    Kushilevitz, E., Mansour, Y.: Learning decision trees using the fourier spectrum. SIAM Journal on Computing 22(6), 1331–1348 (1993)zbMATHCrossRefMathSciNetGoogle Scholar
  21. 21.
    Mansour, Y.: Randomized interpoloation and approximation of sparse polynomials. SIAM Journal of Computing 24(2) (1995)Google Scholar
  22. 22.
    Compressed sensing website,
  23. 23.
    Rudelson, M., Vershynin, R.: Geometric approach to error correcting codes and reconstruction of signals (unpublished manuscript, 2005)Google Scholar
  24. 24.
    Tropp, J., Gilbert, A.: Signal recovery from partial information via orthogonal matching pursuit (unpublished manuscript, 2005)Google Scholar
  25. 25.
    Tsaig, Y., Donoho, D.: Extensions of compressed sensing (unpublished manuscript, 2004)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Graham Cormode
    • 1
  • S. Muthukrishnan
    • 2
  1. 1.Bell LabsLucent Technologies 
  2. 2.Rutgers University 

Personalised recommendations