Convex Coding - Robotics Institute Carnegie Mellon University

Convex Coding

Conference Paper, Proceedings of 25th Conference on Uncertainty in Artificial Intelligence (UAI '09), pp. 83 - 90, June, 2009

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.

BibTeX

@conference{Bradley-2009-10240,
author = {David Bradley and J. Andrew (Drew) Bagnell},
title = {Convex Coding},
booktitle = {Proceedings of 25th Conference on Uncertainty in Artificial Intelligence (UAI '09)},
year = {2009},
month = {June},
editor = {Eric Xing},
pages = {83 - 90},
keywords = {Sparse Coding, Fenchel Duality, Boosting, Unsupervised Learning, Convex Optimization},
}