Abstract:
A substantial amount of research in the elds of statistics, machine learning and signal processing during the last three decades considers the problem of variable selection for high-dimensional (HD) data. Typically, these results were derived by assuming that the total number of potential explanatory variables (pn) is larger than the sample size (n), but that most of them are unimportant (sparse model). It has been shown that the greedy algorithms e ciently generate models in the HD case as well as in the big data (BD) case (n pn). We discuss the use of the following greedy algorithms: Matching Pursuit Algorithm (MPA), Orthogonal Matching Pursuit (OMP), Relaxed Matching Pursuit (RMP), Frank-Wolfe Algorithm (FWA) and Constrained Matching Pursuit (CMP). We show how twelve information theoretic (IT) criteria can be used jointly with the greedy algorithms. As part of this e ort, we derive new theoretical results that allow us to modify the IT criteria so as to be compatible with MPA and RMP. We provide a simulation study for MPA, and compare the prediction capabilities of all greedy algorithms in experiments with two real-life data sets.