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 that has become popular in recent years. A general theory is developed for learning with structured sparsity, based on the notion of coding complexity associated with the structure. It is shown that if the coding complexity of the target signal is small, then one can achieve improved performance by using coding complexity regularization methods, which generalize the standard sparse regularization. Moreover, a structured greedy algorithm is proposed to efficiently solve the structured sparsity problem. It is shown that the greedy algorithm approximately solves the coding complexity optimization problem under appropriate conditions. Experiments are included to demonstrate the advantage of structured sparsity over standard sparsity on some real applications.

References in corpus (13)

• Discussion of "Least angle regression" by Efron et al
• Rejoinder to "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
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Consistency of the group Lasso and multiple kernel learning
• The composite absolute penalties family for grouped and hierarchical variable selection
• Taking Advantage of Sparsity in Multi-Task Learning

Cited by in corpus (49)

• Neural Granger Causality
• Sub-Nyquist Radar Systems: Temporal, Spectral and Spatial Compression
• Convex Relaxation for Combinatorial Penalties
• Supervised Feature Selection in Graphs with Path Coding Penalties and Network Flows
• Radar and Communication Co-existence: an Overview
• Making Neural Networks Interpretable with Attribution: Application to Implicit Signals Prediction
• SpaRCe: Improved Learning of Reservoir Computing Systems through Sparse Representations
• Forest Sparsity for Multi-channel Compressive Sensing
• Variance State Propagation for Structured Sparse Bayesian Learning
• Learning the Structure for Structured Sparsity
• Structured Sparse Regression via Greedy Hard-Thresholding
• Fast Iteratively Reweighted Least Squares Algorithms for Analysis-Based Sparsity Reconstruction
• Approximate Message Passing with Nearest Neighbor Sparsity Pattern Learning
• Structure Regularization for Structured Prediction: Theories and Experiments
• A totally unimodular view of structured sparsity
• Solving OSCAR regularization problems by proximal splitting algorithms
• Complex Structure Leads to Overfitting: A Structure Regularization Decoding Method for Natural Language Processing
• Performance of time delay estimation in a cognitive radar
• Network-Guided Biomarker Discovery
• Knowledge-Based Distant Regularization in Learning Probabilistic Models
• Exploiting Structure Sparsity for Covariance-based Visual Representation
• Technical Report: Graph-Structured Sparse Optimization for Connected Subgraph Detection
• Clustering Noisy Signals with Structured Sparsity Using Time-Frequency Representation
• Group-sparse SVD Models and Their Applications in Biological Data
• Blind Community Detection from Low-rank Excitations of a Graph Filter
• Bayesian Structured Sparsity Priors for EEG Source Localization Technical Report
• Half-Space Proximal Stochastic Gradient Method for Group-Sparsity Regularized Problem
• Modelling Heterogeneity Using Bayesian Structured Sparsity
• Learning sparsity in reservoir computing through a novel bio-inspired algorithm
• Technical Report: A Generalized Matching Pursuit Approach for Graph-Structured Sparsity
• A Fast Algorithm for Separated Sparsity via Perturbed Lagrangians
• Graph-Sparse Logistic Regression
• Sparse and redundant signal representations for x-ray computed tomography
• Compressive Measurement Designs for Estimating Structured Signals in Structured Clutter: A Bayesian Experimental Design Approach
• Exclusive Group Lasso for Structured Variable Selection
• Attribute Guided Sparse Tensor-Based Model for Person Re-Identification
• Convex Latent Effect Logit Model via Sparse and Low-rank Decomposition
• Best-Choice Edge Grafting for Efficient Structure Learning of Markov Random Fields
• Approximation Guarantees of Local Search Algorithms via Localizability of Set Functions
• Error Analysis on Graph Laplacian Regularized Estimator
• Pathways-driven Sparse Regression Identifies Pathways and Genes Associated with High-density Lipoprotein Cholesterol in Two Asian Cohorts
• Robust Online Matrix Factorization for Dynamic Background Subtraction
• Parametric Maxflows for Structured Sparse Learning with Convex Relaxations of Submodular Functions
• Color Face Recognition using High-Dimension Quaternion-based Adaptive Representation
• Hyperspectral Imaging and Analysis for Sparse Reconstruction and Recognition
• Multi-dimensional signal approximation with sparse structured priors using split Bregman iterations
• Multi-dimensional sparse structured signal approximation using split Bregman iterations
• Improved Algorithms For Structured Sparse Recovery
• From biological vision to unsupervised hierarchical sparse coding