We introduce a novel variation on the well-known Matching Pursuit (MP) algorithm. In particular, the sparse approximation problem is solved in a greedy scheme using estimated higher-order statistics as similarity measures instead of the somehow limited second-order statistics that perform optimally only under Gaussian assumptions. This is conveyed via the generalized correntropy (GC) function instead of the cross-correlation approach usually utilized in stochastic random processes applications. Additionally, extra flexibility is achieved by the GC parameters that control the behavior of the induced metric. The result is the robust Generalized Correntropy Matching Pursuit (GCMP) algorithm. Furthermore, we present results on two different frameworks dealing with detection and sparse approximation and highlight the robustness of this method in the presence of high-tailed impulsive noise.