Properties of Mean Shift

Abstract

We study properties of the mean shift (MS)-type algorithms for estimating modes of probability density functions (PDFs), via regarding these algorithms as gradient ascent on estimated PDFs with adaptive step sizes. We rigorously prove convergence of mode estimate sequences generated by the MS-type algorithms, under the assumption that an analytic kernel function is used. Moreover, our analysis on the MS function finds several new properties of mode estimate sequences and corresponding density estimate sequences, including the result that in the MS-type algorithm using a Gaussian kernel the density estimate monotonically increases between two consecutive mode estimates. This implies that, in the one-dimensional case, the mode estimate sequence monotonically converges to the stationary point nearest to an initial point without jumping over any stationary point.