Proximal Methods for Hierarchical Sparse Coding
arXiv:1009.2139
Abstract
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 we propose in this paper 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 organize in a prespecified arborescent structure, leading to a 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.
References in corpus (20)
- Discussion of "Least angle regression" by Efron et al
- Rejoinder to "Least angle regression" by Efron et al
- Discussion of "Least angle regression" by Efron et al
- Discussion of "Least angle regression" by Efron et al
- Least Angle Regression
- Discussion of "Least angle regression" by Efron et al
- Discussion of "Least angle regression" by Efron et al
- Discussion of "Least angle regression" by Efron et al
- Discussion of "Least angle regression" by Efron et al
- Discussion of "Least angle regression" by Efron et al
- Simultaneous analysis of Lasso and Dantzig selector
- Supervised Topic Models
- Supervised Dictionary Learning
- The composite absolute penalties family for grouped and hierarchical variable selection
- A note on the group lasso and a sparse group lasso
- Structured Variable Selection with Sparsity-Inducing Norms
- Structured Sparse Principal Component Analysis
- Exploring Large Feature Spaces with Hierarchical Multiple Kernel Learning
- Network Flow Algorithms for Structured Sparsity
- Structured sparsity-inducing norms through submodular functions
Cited by in corpus (65)
- Structured Variable Selection with Sparsity-Inducing Norms
- Generalized Forward-Backward Splitting
- A Unified Framework for High-Dimensional Analysis of M-Estimators with Decomposable Regularizers
- Neural Granger Causality
- Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization
- C-HiLasso: A Collaborative Hierarchical Sparse Modeling Framework
- A Flexible and Efficient Algorithmic Framework for Constrained Matrix and Tensor Factorization
- Group Lasso with Overlaps: the Latent Group Lasso approach
- Fixed Point Strategies in Data Science
- Convex and Network Flow Optimization for Structured Sparsity
- Forward - Backward Greedy Algorithms for Atomic Norm Regularization
- Reflection methods for user-friendly submodular optimization
- Sparse coding for multitask and transfer learning
- Hierarchical Sparse Modeling: A Choice of Two Group Lasso Formulations
- Tackling Over-pruning in Variational Autoencoders
- Convex Relaxation for Combinatorial Penalties
- High Dimensional Forecasting via Interpretable Vector Autoregression
- Machine Learning Methods in the Computational Biology of Cancer
- Sparse Overlapping Sets Lasso for Multitask Learning and its Application to fMRI Analysis
- GAP Safe Screening Rules for Sparse-Group-Lasso
- Local stability and robustness of sparse dictionary learning in the presence of noise
- Image classification by visual bag-of-words refinement and reduction
- Latent Semantic Learning with Structured Sparse Representation for Human Action Recognition
- Learning the Structure for Structured Sparsity
- Tight Measurement Bounds for Exact Recovery of Structured Sparse Signals
- Convex Approaches to Model Wavelet Sparsity Patterns
- Learning Efficient Structured Sparse Models
- Learning efficient sparse and low rank models
- On the Convergence Rate of Decomposable Submodular Function Minimization
- Generalized Conditional Gradient for Sparse Estimation
- Bayesian Structured Sparsity from Gaussian Fields
- Gap Safe screening rules for sparsity enforcing penalties
- Optimal Computational Trade-Off of Inexact Proximal Methods
- Model-based Sketching and Recovery with Expanders
- Fast Iteratively Reweighted Least Squares Algorithms for Analysis-Based Sparsity Reconstruction
- Classification with Sparse Overlapping Groups
- An Efficient Privacy-Preserving Algorithm based on Randomized Response in IoT-based Smart Grid
- Matrix Cofactorization for Joint Representation Learning and Supervised Classification -- Application to Hyperspectral Image Analysis
- A totally unimodular view of structured sparsity
- Parameter Choices for Sparse Regularization with the Norm
- Collaborative Filtering via Group-Structured Dictionary Learning
- Sample Complexity of Dictionary Learning and other Matrix Factorizations
- Efficient Learning with a Family of Nonconvex Regularizers by Redistributing Nonconvexity
- Sparse and spurious: dictionary learning with noise and outliers
- Modelling Interactions in High-dimensional Data with Backtracking
- Alternating Estimation for Structured High-Dimensional Multi-Response Models
- Group Regularized Estimation under Structural Hierarchy
- Convergence rate analysis of primal-dual splitting schemes
- Learning Hierarchical Interactions at Scale: A Convex Optimization Approach
- Multi-scale Mining of fMRI data with Hierarchical Structured Sparsity
- A first-order optimization algorithm for statistical learning with hierarchical sparsity structure
- Supervised Quantile Normalization for Low-rank Matrix Approximation
- Error Bounds for Compressed Sensing Algorithms With Group Sparsity: A Unified Approach
- Sparse hierarchical interaction learning with epigraphical projection
- Short-Term Prediction of Signal Cycle in Actuated-Controlled Corridor Using Sparse Time Series Models
- Learning sparse representations on the sphere
- Fitting ARMA Time Series Models without Identification: A Proximal Approach
- Sparse and redundant signal representations for x-ray computed tomography
- Convex Latent Effect Logit Model via Sparse and Low-rank Decomposition
- Towards Ultrahigh Dimensional Feature Selection for Big Data
- Efficient Algorithm for Extremely Large Multi-task Regression with Massive Structured Sparsity
- On The Projection Operator to A Three-view Cardinality Constrained Set
- Parametric Maxflows for Structured Sparse Learning with Convex Relaxations of Submodular Functions
- Learning with Optimal Interpolation Norms
- Exclusive Group Lasso for Structured Variable Selection