On the number of iterations for the matching pursuit algorithm

Abstract

We address the problem of selecting, from a given dictionary, a subset of predictors whose linear combination provides the best description for the vector of measurements. To this end, we apply the well-known matching pursuit algorithm (MPA). Even if there are theoretical results on the performance of MPA, there is no widely accepted rule for stopping the algorithm. In this work, we focus on stopping rules based on information theoretic criteria (ITC). The key point is to evaluate the degrees of freedom (df) for the model produced at each iteration. This is traditionally done by computing the trace of the hat matrix which maps the data vector to its estimate. We prove some theoretical results concerning the hat matrix. One of them provides an upper bound on the increase of df from the m-th to the (m + 1)-th iteration. Based on the properties of the hat matrix, we propose novel ITC for selecting the number of iterations. All of them are obtained by modifying criteria designed for variable selection in the classical linear model. For assessing the performance of the novel criteria, we conduct a simulation study.