Theory of matching pursuit
Zakria Hussain and John Shawe-Taylor University College London, UK

M33

Can we upper b ound the loss of matching pursuit algorithms?
Bound plots for sparse kernel PCA 1.8 PCA bound sample compression bound test residual 1.6

Matching pursuit for kernel PCA (SKPCA) Prove SKPCA is a compression scheme
Sample compression bound for SKPCA Tighter than state-of-the art PCA bounds

1.4

1.2

1 Residual 0.8 0.6 0.4 0.2 0 0

10

20

30

40

50

60

70 80 Level of sparsity

90

100

110

120

130

140

150

KMP error on Boston housing data set 0.9 bound KMP test error 0.8

0.7

Kernel matching pursuit (KMP) Novel generalisation bound for KMP
Uses VC and sample compression theory Unaffected by dimensionality of the feature space

0.6

0.5 Loss 0.4 0.3 0.2 0.1 0 0

5

10

15

20

25 30 Level of sparsity

35

40

45

50

Generic matching pursuit algorithm Theory justifies matching pursuit as a general meta-algorithm The definition of the space as the span of a small subset of the training set enables sparse bounds to be combined with appropriate bounds for the analysis task, e.g., sparse KCCA, sparse LDA, etc