UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

Design and Generalization Analysis of Orthogonal Matching Pursuit Algorithms

Hussain, Z; Shawe-Taylor, J; Hardoon, DR; Dhanjal, C; (2011) Design and Generalization Analysis of Orthogonal Matching Pursuit Algorithms. IEEE T INFORM THEORY , 57 (8) 5326 - 5341. 10.1109/TIT.2011.2158880.

Full text not available from this repository.


We derive generalization error (loss) bounds for orthogonal matching pursuit algorithms, starting with kernel matching pursuit and sparse kernel principal components analysis. We propose (to the best of our knowledge) the first loss bound for kernel matching pursuit using a novel application of sample compression and Vapnik-Chervonenkis bounds. For sparse kernel principal components analysis, we find that it can be bounded using a standard sample compression analysis, as the subspace it constructs is a compression scheme. We demonstrate empirically that this bound is tighter than previous state-of-the-art bounds for principal components analysis, which use global and local Rademacher complexities. From this analysis we propose a novel sparse variant of kernel canonical correlation analysis and bound its generalization performance using the results developed in this paper. We conclude with a general technique for designing matching pursuit algorithms for other learning domains.

Title:Design and Generalization Analysis of Orthogonal Matching Pursuit Algorithms
Keywords:Kernel methods, matching pursuit, Nystrom approximation, principle components analysis, sample compression bounds, sparse kernel canonical correlation analysis, sparsity, LOCAL RADEMACHER COMPLEXITIES, COMPONENT ANALYSIS, NOISE, CLASSIFICATION, DICTIONARIES, MINIMIZATION, RECOVERY
UCL classification:UCL > School of BEAMS > Faculty of Engineering Science > Computer Science

Archive Staff Only: edit this record