Linear Convergence of the Subspace Constrained Mean Shift Algorithm: From Euclidean to Directional Data

Abstract

This paper studies the linear convergence of the subspace constrained mean shift (SCMS) algorithm, a well-known algorithm for identifying a density ridge defined by a kernel density estimator. By arguing that the SCMS algorithm is a special variant of a subspace constrained gradient ascent (SCGA) algorithm with an adaptive step size, we derive the linear convergence of such SCGA algorithm. While the existing research focuses mainly on density ridges in the Euclidean space, we generalize density ridges and the SCMS algorithm to directional data. In particular, we establish the stability theorem of density ridges with directional data and prove the linear convergence of our proposed directional SCMS algorithm.

arXiv commentSubstantial revision. The updated version has 93 pages, 12 figures, and 1 table

References in corpus (13)

• Stochastic gradient descent on Riemannian manifolds
• Uniform in bandwidth consistency of kernel-type function estimators
• Kernel density estimation for directional-linear data
• Nonparametric ridge estimation
• Cosmic Web Reconstruction through Density Ridges: Method and Algorithm
• Exact risk improvement of bandwidth selectors for kernel density estimation with directional data
• Cosmic Web Reconstruction through Density Ridges: Catalogue
• Asymptotic theory for density ridges
• Asymptotic behaviour of self-contracted planar curves and gradient orbits of convex functions
• Path Length Bounds for Gradient Descent and Flow
• Kernel Smoothing, Mean Shift, and Their Learning Theory with Directional Data
• Algorithms for ridge estimation with convergence guarantees
• The EM Perspective of Directional Mean Shift Algorithm

Cited by in corpus (2)

• SCONCE: A cosmic web finder for spherical and conic geometries
• Mode and Ridge Estimation in Euclidean and Directional Product Spaces: A Mean Shift Approach