Output details
11 - Computer Science and Informatics
University College London
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.