Explicit constructions for compressed sensing of sparse signals

ABSTRACT

Over the recent years, a new approach for obtaining a succinct approximate representation of n-dimensional vectors (or signals) has been discovered. For any signal x, the succinct representation of x is equal to Ax, where A is a carefully chosen R x n real matrix, R ≪ n. Often, A is chosen at random from some distribution over R x n matrices. The vector Ax is often refered to as the measurement vector or a sketch of x. Although the dimension of Ax is much shorter than of x, it contains plenty of useful information about x.

REFERENCES

• 1: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.20-29, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237823]
• 2: {CCFC02} M. Charikar, K. Chen, and M. Farach-Colton. Finding frequent items in data streams. ICALP, 2002.
• 3: Graham Cormode , S. Muthukrishnan, What's hot and what's not: tracking most frequent items dynamically, ACM Transactions on Database Systems (TODS), v.30 n.1, p.249-278, March 2005 [doi>10.1145/1061318.1061325]
• 4: {CM04} G. Cormode and S. Muthukrishnan. Improved data stream summaries: The count-min sketch and its applications. FSTTCS, 2004.
• 5: {CM06} G. Cormode and S. Muthukrishnan. Combinatorial algorithms for compressed sensing. SIROCCO, 2006.
• 6: {CRT06} E. Candes, J. Romberg, and T. Tao. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on Information Theory, 52:489--509, 2006.
• 7: {CRTV05} E. Candes, M. Rudelson, T. Tao, and R. Vershynin. Error correction via linear programming. FOCS, 2005.
• 8: {CT06} E. Candes and T. Tao. Near optimal signal recovery from random projections: Universal encoding strategies. IEEE Transactions on Information Theory, 2006.
• 9: {DeV06} R. DeVore. Optimal computation. Proceedings of the International Congress of Mathematicians, 2006.
• 10: Ronald A. DeVore, Deterministic constructions of compressed sensing matrices, Journal of Complexity, v.23 n.4-6, p.918-925, August, 2007 [doi>10.1016/j.jco.2007.04.002]
• 11: {Don06} D. Donoho. Compressed sensing. IEEE Transactions on Information Theory, 52(4):1289--1306, 2006.
• 12: Cristian Estan , George Varghese, New directions in traffic measurement and accounting: Focusing on the elephants, ignoring the mice, ACM Transactions on Computer Systems (TOCS), v.21 n.3, p.270-313, August 2003 [doi>10.1145/859716.859719]
• 13: Anna C. Gilbert , Sudipto Guha , Piotr Indyk , Yannis Kotidis , S. Muthukrishnan , Martin J. Strauss, Fast, small-space algorithms for approximate histogram maintenance, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509966]
• 14: A. C. Gilbert , S. Guha , P. Indyk , S. Muthukrishnan , M. Strauss, Near-optimal sparse fourier representations via sampling, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509933]
• 15: Minos Garofalakis , Johannes Gehrke , Rajeev Rastogi, Querying and mining data streams: you only get one look a tutorial, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564794]
• 16: Anna C. Gilbert , Yannis Kotidis , S. Muthukrishnan , Martin Strauss, Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries, Proceedings of the 27th International Conference on Very Large Data Bases, p.79-88, September 11-14, 2001
• 17: {GKMS01b} A. Gilbert, Y. Kotidis, S. Muthukrishnan, and M. Strauss. Quicksand: Quick summary and analysis of network data. DIMACS Technical Report 2001--43, 2001.
• 18: {GMS05} A. Gilbert, M. Muthukrishnan, and M. Strauss. Improved time bounds for near-optimal space fourier representations. SPIE Conference, Wavelets, 2005.
• 19: {Gro06} Rice DSP Group. Compressed sensing resources. Available at http://www.dsp.ece.rice.edu/cs/, 2006.
• 20: {GSTV06} A. Gilbert, M. Strauss, J. Tropp, and R. Vershynin. Algorithmic linear dimension reduction in the l1 norm for sparse vectors. Allerton, 2006.
• 21: A. C. Gilbert , M. J. Strauss , J. A. Tropp , R. Vershynin, One sketch for all: fast algorithms for compressed sensing, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250824]
• 22: Piotr Indyk, Uncertainty principles, extractors, and explicit embeddings of l2 into l1, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250881]
• 23: {JL84} W. B. Johnson and J. Lindenstrauss. Extensions of lipshitz mapping into hilbert space. Contemporary Mathematics, 26:189--206, 1984.
• 24: Yishay Mansour, Randomized Interpolation and Approximationof Sparse Polynomials, SIAM Journal on Computing, v.24 n.2, p.357-368, April 1995 [doi>10.1137/S0097539792239291]
• 25: {Mut06} S. Muthukrishnan. Compressed sensing algorithms for functions. Allerton, 2006.
• 26: {Sha04} R. Shaltiel. Recent developments in extractors. In Current trends in theoretical computer science. The Challenge of the New Century. Vol 1: Algorithms and Complexity, 2004.
• 27: {Tao07} T. Tao. Open question: deterministic uup matrices. Weblog at http://terrytao.wordpress.com, 2007.
• 28: Nitin Thaper , Sudipto Guha , Piotr Indyk , Nick Koudas, Dynamic multidimensional histograms, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564741]
• 29: {Vad07} S. Vadhan. Pseudorandomness (cs225). available at http://www.eecs.harvard.edu/ salil/, Spring 2007.
• 30: {WLD⁺06} Michael Wakin, Jason Laska, Marco Duarte, Dror Baron, Shriram Sarvotham, Dharmpal Takhar, Kevin Kelly, and Richard Baraniuk. An architecture for compressive imaging. Proc. Int. Conf. on Image Processing (ICIP), 2006.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.0 General

General Terms:
Algorithms, Design, Theory