Learning with structured sparsity

By Junzhou Huang, Tong Zhang, Dimitris N. Metaxas. 2009

571 citations recorded by the source corpus.

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.

Subfields: Computational Mechanics, Computer Networks and Communications, Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Networks and Communications

In Computer Vision and Pattern Recognition

Citations in the corpus

Optimization with Sparsity-Inducing Penalties (2011, methodology): “Reducing parsimony to finding the model of lowest cardinality turns out to be limiting, and structured parsimony [15, 62, 64, 66] has emerged as a natural extension, with applications to computer vision [32, 62, 70], text processing [68], bioinformatics [64, 73] or audio processing [80].”
Bayesian group factor analysis with structured sparsity (2016, methodology): “…structure of Λ in GFA models belongs to a general class of structured sparsity methods that has drawn attention recently (Zou and Hastie, 2005; Yuan and Lin, 2006; Jenatton et al., 2011, 2010; Kowalski, 2009; Kowalski and Torrésani, 2009; Zhao et al., 2009; Huang et al., 2011; Jia et al., 2010).”
Learning with Submodular Functions: A Convex Optimization Perspective (2011, background): “, A ⊂ B ⇒ F (A) 6 F (B)) – Explicit prior knowledge on supports (Haupt and Nowak, 2006; Baraniuk et al., 2008; Huang et al., 2009) • Define Θ(w) = F (Supp(w)): How to get its convex envelope? 1.”
Multi-Label Prediction via Compressed Sensing (2009, methodology): “cture, namely output sparsity, which is not addressed in previous work. Moreover, our method is general enough to take advantage of structured notions of sparsity (e.g. group sparsity) when available [10]. Recently, heuristics have been proposed for discovering structure in large output spaces that ”
Gradient boosted feature selection (2014, methodology): “Prior work on handling structured sparsity include group lasso [10, 20] and generalized lasso [19].”
Data-Driven Intelligent Transportation Systems: A Survey (2011, unknown): “idea [112].”
Feature Selection for Classification: A Review (2014, background): “, spatial or temporal smoothness [65, 79], disjoint/overlapping groups [29], trees [33], and graphs [25].”
Combinatorial Penalties: Structure preserved by convex relaxations (2017, unknown): “Non-convex approaches were also proposed in [4, 18].”
Structured Sparse Principal Component Analysis (2009, background): “Recent research on structured sparsity [6, 7, 1] has highlighted the beneﬁt of exploiting such structure for variable selection and prediction in the context of regression and classiﬁcation.”
Super-Resolution With Sparse Mixing Estimators (2010, methodology): “Structured approximation algorithms use such prior information to restrict the set of possible approximation spaces [28], [31].”
Network Flow Algorithms for Structured Sparsity (2010, unknown): “Following [9, 10], we consider a background subtraction task.”
Learning Nonlinear Functions Using Regularized Greedy Forest (2011, background): “This leads to the second idea in our approach, which is to impose explicit regularization via the concept of structured sparsity that has drawn much attention in recent years [1]–[3], [20]–[22].”
Decomposition into Low-rank plus Additive Matrices for Background/Foreground Separation: A Review for a Comparative Evaluation with a Large-Scale Dataset (2015, unknown): “Furthermore, structured sparsity [161][162][159][50] can be”
Sparse Recovery With Orthogonal Matching Pursuit Under RIP (2010, background): “for suggestions to improve the presentation. APPENDIX We need a number of technical lemmas. Lemma A.3 and Lemma A.4, key to the proof, are based on earlier work of the author with collaborators [13], [7]. The ﬁrst three lemmas u se the following notations. Let F,F¯ be two subsets of {1,...,d}. Let s”