Design and Generalization Analysis of Orthogonal Matching Pursuit Algorithms.
IEEE T INFORM THEORY
5326 - 5341.
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