Does White Noise Dream of Square Waves? A Matching Pursuit Conundrum

Matching pursuit is a greedy model selection algorithm used to extract a possible signal that underlies a time series of interest. The method represents the series as a linear combination of vectors from a large collection of vectors (a dictionary) by incrementally adding the vector that reduces the residual sum of squares in a linear model. In this article it is demonstrated that the probability of selecting vectors from the dictionary need not be uniform when there is no underlying structure in the series of interest and when the vectors in the dictionary are highly correlated. In particular, via simulation studies and analytic calculations, it is shown that matching pursuit can preferentially select square waves over sinusoids when analyzing Gaussian white noise, in some cases with a preference exceeding 95%. The ramification of this non-uniform selection is demonstrated for a climatological example, in which the scientific question is to explore underlying structures inherent in North Pacific indices.