Learning with structured sparsity

ABSTRACT

This paper investigates a new learning formulation called structured sparsity, which is a natural extension of the standard sparsity concept in statistical learning and compressive sensing. By allowing arbitrary structures on the feature set, this concept generalizes the group sparsity idea. A general theory is developed for learning with structured sparsity, based on the notion of coding complexity associated with the structure. Moreover, a structured greedy algorithm is proposed to efficiently solve the structured sparsity problem. Experiments demonstrate the advantage of structured sparsity over standard sparsity.

REFERENCES

• 1: Francis R. Bach, Consistency of the Group Lasso and Multiple Kernel Learning, The Journal of Machine Learning Research, 9, p.1179-1225, 6/1/2008
• 2: Baraniuk, R., Cevher, V., Duarte, M., & Hegde, C. (2008). Model based compressive sensing. preprint.
• 3: Bradley Efron, Trevor Hastie, I. J., & Tibshirani, R. (2004). Least angle regression. Annals of Statistics, 32, 407--499.
• 4: Candes, E. J., & Tao, T. (2005). Decoding by linear programming. IEEE Trans. on Information Theory, 51, 4203--4215.
• 5: Daudet, L. (2004). Sparse and structured decomposition of audio signals in overcomplete spaces. International Conference on Digital Audio Effects (pp. 1--5).
• 6: Donoho, D. (2006). Compressed sensing. IEEE Transactions on Information Theory, 52, 1289--1306.
• 7: Grimm, D., Netzer, T., & Schweighofer, M. (2007). A note on the representation of positive polynomials with structured sparsity. Arch. Math., 89, 399--403.
• 8: Huang, J., & Zhang, T. (2009). The benefit of group sparsity (Technical Report). Rutgers University.
• 9: Huang, J., Zhang, T., & Metaxas, D. (2009). Learning with structured sparsity (Technical Report). Rutgers University. available from http://arxiv.org/abs/0903.3002.
• 10: Stphane Mallat, A Wavelet Tour of Signal Processing, Third Edition: The Sparse Way, Academic Press, 2008
• 11: Needell, D., & Tropp, J. (2008). Cosamp: Iterative signal recovery from incomplete and inaccurate samples. Applied and Computational Harmonic Analysis. Accepted.
• 12: Stojnic, M., Parvaresh, F., & Hassibi, B. (2008). On the reconstruction of block-sparse signals with an optimal number of measurements. Preprint.
• 13: Tibshirani, R. (1996). Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society, 58, 267--288.
• 14: Tropp, J., & Gilbert, A. (2007). Signal recovery from random measurements via orthogonal matching pursuit. IEEE Transactions on Information Theory, 53, 4655--4666.
• 15: Yuan, M., & Lin, Y. (2006). Model selection and estimation in regression with grouped variables. Journal of The Royal Statistical Society Series B, 68, 49--67.
• 16: Zhang, T. (2008). Adaptive forward-backward greedy algorithm for learning sparse representations. Proceedings of Neural Information Processing Systems (pp. 1--8).
• 17: Zhao, P., Rocha, G., & Yu, B. Grouped and hierarchical model selection through composite absolute penalties. The Annals of Statistics. to appear.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical computing; Experimental design

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Structural
      I.5.2 Design Methodology
          Subjects: Feature evaluation and selection
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Experimentation, Performance