Proximal Methods for Hierarchical Sparse Coding

By Rodolphe Jenatton, Julien Mairal, Guillaume Obozinski, Francis R. Bach. Journal of machine learning research, 2010

361 citations recorded by the source corpus.

Sparse coding consists in representing signals as sparse linear combinations of atoms selected from a dictionary. We consider an extension of this framework where the atoms are further assumed to be embedded in a tree. This is achieved using a recently introduced tree-structured sparse regularization norm, which has proven useful in several applications. This norm leads to regularized problems that are difficult to optimize, and in this paper, we propose efficient algorithms for solving them. More precisely, we show that the proximal operator associated with this norm is computable exactly via a dual approach that can be viewed as the composition of elementary proximal operators. Our procedure has a complexity linear, or close to linear, in the number of atoms, and allows the use of accelerated gradient techniques to solve the tree-structured sparse approximation problem at the same computational cost as traditional ones using the l1-norm. Our method is efficient and scales gracefully to millions of variables, which we illustrate in two types of applications: first, we consider fixed hierarchical dictionaries of wavelets to denoise natural images. Then, we apply our optimization tools in the context of dictionary learning, where learned dictionary elements naturally self-organize in a prespecified arborescent structure, leading to better performance in reconstruction of natural image patches. When applied to text documents, our method learns hierarchies of topics, thus providing a competitive alternative to probabilistic topic models.

Subfields: Biomedical Engineering, Computational Mechanics, Signal Processing

View Paper: https://www.semanticscholar.org/paper/617671a536e7bc598a5e1fbbc170181e91b3996d

How researchers see this paper

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

In Biomedical Engineering

In Computational Mechanics

In Signal Processing

Citations in the corpus

Sparse Overlapping Sets Lasso for Multitask Learning and its Application to fMRI Analysis (2013, methodology): “We then use proximal point methods [8] in conjunction with the MALSAR [22] package to solve the optimization problem.”
Sparse Modeling for Image and Vision Processing (2014, methodology): “This notion is called structured sparsity and has been introduced under a large number of different point of views [Zhao et al., 2009, Jacob et al., 2009, Jenatton et al., 2011a, Baraniuk et al., 2010, Huang et al., 2011].”
Group Lasso with Overlaps: the Latent Group Lasso approach (2011, background): “Jenatton et al. (2011) formalized this approach and proposed an `1/`2 norm construction for families of allowed supports stable by intersection.”
Proximal Algorithms (2013, background): “For instance, when G is tree-structured, meaning that either two groups g, g′ ∈ G are disjoint or one is a subset of the other, the proximal operator can still be evaluated in linear time, as discussed in [109, 4].”
A unified framework for high-dimensional analysis of $M$-estimators with decomposable regularizers (2009, methodology): “Some examples include different types of hierarchical regularizers and/or overlapping group regularizers [28, 29], as well as methods using combinations of decomposable regularizers, such as the fused Lasso [68].”
Sparse coding for multitask and transfer learning (2012, methodology): “(Jenatton et al., 2011; Lounici et al., 2011) or other families of regularizers.”
Sparse Representation Based Fisher Discrimination Dictionary Learning for Image Classification (2014, background): “Apart from the l 0 -or l 1 -norm sparsity penalty, nonnegative (Hoyer 2002), group (Bengio et al. 2009; Szabo et al. 2011), and structured (Jenatton et al. 2011) sparsity penalty on the representation coefficients have also been proposed in different applications.”
On Decomposing the Proximal Map (2013, background): “Note that the case k ∈ {1, |I|} was proved in [7] and Corollary 6 can be seen as an interpolation.”
Salient Object Detection via Structured Matrix Decomposition (2017, background): “The above problem can be solved by the hierarchical proximal operator [78], which computes a particular sequence of residuals obtained by projecting a matrix onto the unit ball of dual `p-norm.”
Tackling Over-pruning in Variational Autoencoders (2017, background): “Related is research in unsupervised sparse overcomplete representations, especially with group sparsity constraints c.f. (Gregor et al., 2011; Jenatton et al., 2011).”
Convex Optimization for Big Data: Scalable, randomized, and parallel algorithms for big data analytics (2014, background): “Tree sparsity [33, 18, 2, 69] f (x)-ball G = {{1, 2, 3}, {2}, {3}} valid selection of nodes Structure: We seek the sparsest signal with a rooted connected subtree support.”
Group Regularized Estimation Under Structural Hierarchy (2014, background): “Such a novel finding is owing to the careful treatment of the stochastic term, which is generally applicable to overlap group lasso (Jenatton et al. 2011).”
Reflection methods for user-friendly submodular optimization (2013, neutral): “This class of functions too admits to solve the proximal problem in O(n log n) time [22, 23, 26].”
Optimization with Sparsity-Inducing Penalties (2011, methodology): “This resulting penalty was first used in [157]; since then, this group structure has led to numerous applications, for instance, wavelet-based denoising [15, 62, 69, 157], hierarchical dictionary learning for both topic modeling and image restoration [68, 69], log-linear models for the selection of ”
Scalable hierarchical multitask learning algorithms for conversion optimization in display advertising (2014, methodology): “Whenever we have a fully hierarchical setting, Proposition 1 of [10] applies and we can simply perform prox steps bottom up in the process.”
Combinatorial Penalties: Structure preserved by convex relaxations (2017, methodology): “Sufficient support recovery and estimation consistency conditions for the (non-adaptive) estimator (5) have been established for homogeneous convex envelopes of submodular functions, for p =∞ in [1] and for general p in [29], in the high dimensional setting, and for latent group Lasso norm in [30], ”