Search papers, labs, and topics across Lattice.
This paper critiques the widely accepted belief that the Subspace Constrained Mean Shift (SCMS) algorithm converges to a static density ridge, revealing that this assumption overlooks the dynamics of the eigenspace during the algorithm's flow. The authors introduce the "stable ridge," a new geometric structure that accurately represents the true target of SCMS, and establish a generalized SCMS framework that achieves uniform R-linear convergence and topological surjectivity. Additionally, they address the computational inefficiencies of the original SCMS, demonstrating that their approach offers a statistically consistent and more efficient alternative.
The assumption that SCMS converges to a static ridge is fundamentally flawed, revealing a need for a new understanding of density ridge extraction.
The Subspace Constrained Mean Shift (SCMS) algorithm is a popular nonparametric method for extracting density ridges, which serve as a low-dimensional representation of high-dimensional data. It is a widely held belief in the literature that SCMS trajectories converge to the classical density ridge, which we call the "static ridge", defined via the density gradient and the eigenvalues and eigenvectors of the density's Hessian. In this paper, we demonstrate that this assumption does not hold in general, as the static definition fails to account for the rotation of the trailing eigenspace along the continuous flow of the algorithm's underlying vector field. To resolve this, we propose a paradigm shift by introducing the "stable ridge", a novel geometric structure defined through the lens of dynamical systems and the Jacobian of the projected density gradient. We prove that this stable ridge is the true theoretical target of the SCMS algorithm. Building upon this foundation, we develop a generalized SCMS framework utilizing a constant step size, establishing its uniform R-linear convergence and topological surjectivity onto the stable ridge. We further derive the rates of convergence for estimating the stable ridge in terms of the Hausdorff distance. Finally, we expose that the original SCMS algorithm suffers from polynomial-time computational complexity, which is caused by implicitly coupling the step size to the smoothing bandwidth via the Mean Shift operator, and demonstrate how our generalized framework provides a statistically consistent and more efficient solution.
