Convex Coding

David Bradley, J. Andrew Bagnell
Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, PMLR R7:75-82, 2009.

Abstract

Inspired by recent work on convex formulations of clustering (Lashkari & Golland, 2008; Nowozin & Bakir, 2008) we investigate a new formulation of the Sparse Coding Problem (Olshausen & Field, 1997). In sparse coding we attempt to simultaneously represent a sequence of data-vectors sparsely (i.e. sparse approximation (Tropp et al., 2006)) in terms of a 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 and derive a boosting-style algorithm, that (Nowozin & Bakir, 2008) 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR7-bradley09a, title = {Convex Coding}, author = {Bradley, David and Bagnell, J. Andrew}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {75--82}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/bradley09a/bradley09a.pdf}, url = {https://proceedings.mlr.press/r7/bradley09a.html}, abstract = {Inspired by recent work on convex formulations of clustering (Lashkari & Golland, 2008; Nowozin & Bakir, 2008) we investigate a new formulation of the Sparse Coding Problem (Olshausen & Field, 1997). In sparse coding we attempt to simultaneously represent a sequence of data-vectors sparsely (i.e. sparse approximation (Tropp et al., 2006)) in terms of a 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 and derive a boosting-style algorithm, that (Nowozin & Bakir, 2008) 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.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Convex Coding %A David Bradley %A J. Andrew Bagnell %B Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2009 %E Jeff Bilmes %E Andrew Y. Ng %F pmlr-vR7-bradley09a %I PMLR %P 75--82 %U https://proceedings.mlr.press/r7/bradley09a.html %V R7 %X Inspired by recent work on convex formulations of clustering (Lashkari & Golland, 2008; Nowozin & Bakir, 2008) we investigate a new formulation of the Sparse Coding Problem (Olshausen & Field, 1997). In sparse coding we attempt to simultaneously represent a sequence of data-vectors sparsely (i.e. sparse approximation (Tropp et al., 2006)) in terms of a 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 and derive a boosting-style algorithm, that (Nowozin & Bakir, 2008) 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. %Z Reissued by PMLR on 04 October 2026.
APA
Bradley, D. & Bagnell, J.A.. (2009). Convex Coding. Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R7:75-82 Available from https://proceedings.mlr.press/r7/bradley09a.html. Reissued by PMLR on 04 October 2026.

Related Material