Orthogonal Sparse Coding and Sensing

Thomas Martinetz

University of Luebeck
Wednesday, January 22, 2014 at 12:00pm
560 Evans Hall

Sparse Coding has been a very successful concept since many natural signals have the property of being sparse in some dictionary (basis). Some natural signals are even sparse in an orthogonal basis, most prominently natural images. They are sparse in a respective wavelet transform. An encoding in an orthogonal basis has a number of advantages,.e.g., finding the optimal coding coefficients is simply a projection instead of being NP-hard. Given some data, we want to find the orthogonal basis which provides the sparsest code. This problem can be seen as a generalization of Principal Component Analysis. We present an algorithm, Orthogonal Sparse Coding (OSC), which is able to find this basis very robustly. On natural images, it compresses on the level of JPEG, but can adapt to arbitrary and special data sets and achieve significant improvements. With the property of being sparse in some orthogonal basis, we show how signals can be sensed very efficiently in an hierarchical manner with at most k log D sensing actions. This hierarchical sensing might relate to the way we sense the world, with interesting applications in active vision.