### Abstract

Polytope Faces Pursuit (PFP) is a greedy algorithm that approximates the sparse solutions recovered by l(1) regularised least-squares (Lasso) [4,10] in a similar vein to (Orthogonal) Matching Pursuit (OMP) [16]. The algorithm is based on the geometry of the polar polytope where at each step a basis function is chosen by finding the maximal vertex using a. path-following method. The algorithmic complexity is of a similar order to OMP whilst being able to solve problems known to be hard for (O)MP. Matching Pursuit was extended to build kernel-based solutions to machine learning problems, resulting in the sparse regression algorithm, Kernel Matching, Pursuit (KMP) [17]. We develop a new algorithm to build sparse kernel-based solutions using PFP, which we call Kernel Polytope Faces Pursuit (KPFP). We show the usefulness of this algorithm by providing a generalisation error bound [7] that takes into account a natural regression loss and experimental results on several benchmark datasets.

Original language | English |
---|---|

Title of host publication | MACHINE LEARNING AND KNOWLEDGE DISCOVERY IN DATABASES, PT I |

Editors | W Buntine, M Grobelnik, D Mladenic, J ShaweTaylor |

Place of Publication | BERLIN |

Publisher | Springer Berlin Heidelberg |

Pages | 290-301 |

Number of pages | 12 |

ISBN (Print) | 978-3-642-04179-2 |

Publication status | Published - 2009 |

Event | Joint European Conference on Machine Learning (ECML)/European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD) - Bled, Slovenia Duration: 7 Sep 2009 → 11 Sep 2009 |

### Publication series

Name | Lecture Notes in Artificial Intelligence |
---|---|

Publisher | SPRINGER-VERLAG BERLIN |

Volume | 5781 |

ISSN (Print) | 0302-9743 |

### Conference

Conference | Joint European Conference on Machine Learning (ECML)/European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD) |
---|---|

Country | Slovenia |

Period | 7/09/09 → 11/09/09 |

### Keywords

- Polytope Faces Pursuit
- Orthogonal Matching Pursuit
- Pseudo-dimension
- Sample Compression Bounds
- Regression
- Kernel methods
- VAPNIK-CHERVONENKIS DIMENSION

## Cite this

*MACHINE LEARNING AND KNOWLEDGE DISCOVERY IN DATABASES, PT I*(pp. 290-301). (Lecture Notes in Artificial Intelligence; Vol. 5781). Springer Berlin Heidelberg.