Exact and Heuristic Methods for Simultaneous Sparse Coding


The simultaneous sparse coding (SSC) problem consists in approximating several data points as linear combinations of the same few basis elements selected within a given dictionary. It is key in many applications of machine learning and signal processing. Solving SSC up to global optimality has never been explored in the literature, to the best of our knowledge. In this paper, we propose a reformulation of SSC into a mixed-integer quadratic program (MIQP) solvable globally by generic solvers. We also consider a variant of SSC with nonnegativity constraints. We show experimentally that the global resolution can be applied in practice to medium-scale problems. For larger-scale problems, we propose a hybrid method that first uses a heuristic as a pre-process to reduce the size of the original problem, and then solves the reduced problem exactly. Empirically, we show that our hybrid method outperforms existing heuristics on both synthetic data and in the unmixing of real-world hyperspectral images.