Bayesian compressive sensing and projection optimization

ABSTRACT

This paper introduces a new problem for which machine-learning tools may make an impact. The problem considered is termed "compressive sensing", in which a real signal of dimension N is measured accurately based on K << N real measurements. This is achieved under the assumption that the underlying signal has a sparse representation in some basis (e.g., wavelets). In this paper we demonstrate how techniques developed in machine learning, specifically sparse Bayesian regression and active learning, may be leveraged to this new problem. We also point out future research directions in compressive sensing of interest to the machine-learning community.

REFERENCES

• 1: Christopher M. Bishop , Michael E. Tipping, Variational Relevance Vector Machines, Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence, p.46-53, June 30-July 03, 2000
• 2: Candès, E., Romberg, J., & Tao, T. (2006). Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Information Theory, 52, 489--509.
• 3: Rich Caruana, Multitask Learning, Machine Learning, v.28 n.1, p.41-75, July 1997 [doi>10.1023/A:1007379606734]
• 4: Scott Shaobing Chen , David L. Donoho , Michael A. Saunders, Atomic Decomposition by Basis Pursuit, SIAM Journal on Scientific Computing, v.20 n.1, p.33-61, Aug. 1998 [doi>10.1137/S1064827596304010]
• 5: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 6: Donoho, D. L. (2006). Compressed sensing. IEEE Trans. Information Theory, 52, 1289--1306.
• 7: Donoho, D. L., Tsaig, Y., Drori, I., & Starck, J.-C. (2006). Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit. Preprint.
• 8: Efron, B., Hastie, T., Johnstone, I., & Tibshirani, R. (2004). Least angle regression. The Annals of Statistics, 32, 407--499.
• 9: Faul, A. C., & Tipping, M. E. (2002). Analysis of sparse Bayesian learning. NIPS 14.
• 10: Fedorov, V. V. (1972). Theory of optimal experiments. Academic Press.
• 11: Figueiredo, M. (2002). Adaptive sparseness using Jeffreys prior. NIPS 14).
• 12: Gilks, W. R., Richardson, S., & Spiegelhalter, D. J. (1996). Markov Chain Monte Carlo in Practice. Chapman & Hall.
• 13: Haupt, J., & Nowak, R. (2006). Signal reconstruction from noisy random projections. IEEE Trans. Information Theory, 52, 4036--4048.
• 14: David J. C. MacKay, Information-based objective functions for active data selection, Neural Computation, v.4 n.4, p.590-604, July 1992 [doi>10.1162/neco.1992.4.4.590]
• 15: Mallat, S. (1998). A wavelet tour of signal processing. Academic Press. 2nd edition.
• 16: Papoulis, A., & Pillai, S. U. (2002). Probability, random variables and stochastic processes. McGraw-Hill. 4th edition.
• 17: Pearlman, W. A., Islam, A., Nagaraj, N., & Said, A. (2004). Efficient, low-complexity image coding with a set-partitioning embedded block coder. IEEE Trans. Circuits Systems Video Technology, 14, 1219--1235.
• 18: Tibshirani, R. (1996). Regression shrinkage and selection via the lasso. J. Royal. Statist. Soc B., 58, 267--288.
• 19: Michael E. Tipping, Sparse bayesian learning and the relevance vector machine, The Journal of Machine Learning Research, 1, p.211-244, 9/1/2001
• 20: Tipping, M. E., & Faul, A. C. (2003). Fast marginal likelihood maximisation for sparse Bayesian models. Proc. of the 9th International Workshop on AIStats.
• 21: Tropp, J. A., & Gilbert, A. C. (2005). Signal recovery from partial information via orthogonal matching pursuit. Preprint.
• 22: Yaakov Tsaig , David L. Donoho, Extensions of compressed sensing, Signal Processing, v.86 n.3, p.549-571, March 2006 [doi>10.1016/j.sigpro.2005.05.029]
• 23: Wipf, D., Palmer, J., & Rao, B. (2004). Perspectives on sparse Bayesian learning. NIPS 16.