We address the problem of fast and robust tracking of free-form templates. For this we use Linear Predictors, introduced by Jurie & Dhome in 'Hyperplane Approximation for Template Matching', 2002. This approach allows to track templates at high frame-rates (>1000Hz) very robustly. However, the involved learning requires a significant amount of time and is therefore not suitable for many tasks where the environment is not known a-priori. Within this project we introduced several methods addressing this problem, starting with an adaptive approach that starts with learning a small template and then iteratively grows it over time. This approach also allows to adapt the size and shape of the tracked template during tracking, making it possible to handle occlusions. To speed-up the direct learning of large templates, we introduced two different approaches, a reformulation of the learning equations and a dimensionality reduction step. Both resulting in speed-ups up to two orders of magnitude.