Compressed sensing and Bayesian experimental design

ABSTRACT

We relate compressed sensing (CS) with Bayesian experimental design and provide a novel efficient approximate method for the latter, based on expectation propagation. In a large comparative study about linearly measuring natural images, we show that the simple standard heuristic of measuring wavelet coefficients top-down systematically outperforms CS methods using random measurements; the sequential projection optimisation approach of (Ji & Carin, 2007) performs even worse. We also show that our own approximate Bayesian method is able to learn measurement filters on full images efficiently which outperform the wavelet heuristic. To our knowledge, ours is the first successful attempt at "learning compressed sensing" for images of realistic size. In contrast to common CS methods, our framework is not restricted to sparse signals, but can readily be applied to other notions of signal complexity or noise models. We give concrete ideas how our method can be scaled up to large signal representations.

REFERENCES

• 1: Candès, E., & Romberg, J. (2004). Practical signal recovery from random projections. Proceedings of SPIE.
• 2: Candès, E., Romberg, J., & Tao, T. (2006). Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theo., 52, 489--509.
• 3: Donoho, D. (2006). Compressed sensing. IEEE Trans. Inf. Theo., 52, 1289--1306.
• 4: Duarte, M., Davenport, M., Takhar, D., Laska, J., Sun, T., Kelly, K., & Baraniuk, R. (2008). Single pixel imaging via compressive sampling. To appear in IEEE Signal Processing Magazine.
• 5: Elad, M. (2007). Optimized projections for compressed sensing. IEEE Transactions on Signal Processing.
• 6: Gerwinn, S., Macke, J., Seeger, M., & Bethge, M. (2008). Bayesian inference for spiking neuron models with a sparsity prior. Advances in NIPS 20.
• 7: Shihao Ji , Lawrence Carin, Bayesian compressive sensing and projection optimization, Proceedings of the 24th international conference on Machine learning, p.377-384, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273544]
• 8: Thomas P. Minka, Expectation Propagation for approximate Bayesian inference, Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, p.362-369, August 02-05, 2001
• 9: Matthias W. Seeger, Bayesian Inference and Optimal Design for the Sparse Linear Model, The Journal of Machine Learning Research, 9, p.759-813, 6/1/2008
• 10: Seeger, M., Steinke, F., & Tsuda, K. (2007). Bayesian inference and optimal design in the sparse linear model. AI and Statistics 11.
• 11: Simoncelli, E. (1999). Modeling the joint statistics of images in the Wavelet domain. Proceedings 44th SPIE (pp. 188--195).
• 12: Michael E. Tipping, Sparse bayesian learning and the relevance vector machine, The Journal of Machine Learning Research, 1, p.211-244, 9/1/2001 [doi>10.1162/15324430152748236]
• 13: Weiss, Y., Chang, H., & Freeman, W. (2007). Learning compressed sensing. Snowbird Learning Workshop, Allerton, CA.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Wavelets and fractals

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory