Output details

K-Dimensional Coding Schemes in Hilbert Spaces

<24>Originality: Sparse coding methods have been studied by machine learning practitioners since the early 90's but deriving theoretical guarantees on their performance has been a long standing open problem. This paper establishes a comprehensive framework for low dimensional coding methods (including k-means clustering, principal component analysis, sparse coding, etc.), deriving a tight upper bound on their generalisation error. Significance: Our results have been followed up by researchers at Ecole Polytechnique, MIT, University of Chicago and Technion, among others. Rigour: Our bound is sharp and is based on novel techniques from statistical learning theory, some of which are of independent interest.