Convex Coding

Abstract

Inspired by recent work on convex formulations of clustering we investigate a new formulation of the Sparse Coding Problem. In sparse coding we attempt to simultaneously represent a sequence of data-vectors sparsely (i.e. sparse approximation) in terms of a "code" defined by a set of basis elements, while also finding a code that enables such an approximation. As existing alternating optimization procedures for sparse coding are theoretically prone to severe local minima problems, we propose a convex relaxation of the sparse coding problem and derive a boosting-style algorithm, that serves as a convex ``master problem'' which calls a (potentially non-convex) sub-problem to identify the next code element to add. Finally, we demonstrate the properties of our boosted coding algorithm on an image denoising task.