We introduce the diffusion @math -means clustering method on Riemannian submanifolds, which maximizes the within-cluster connectedness based on the diffusion distance. The diffusion @math -means constructs a random walk on the similarity graph with vertices as data points randomly sampled on the manifolds and edges as similarities given by a kernel that captures the local geometry of manifolds. Thus the diffusion @math -means is a multi-scale clustering tool that is suitable for data with non-linear and non-Euclidean geometric features in mixed dimensions. Given the number of clusters, we propose a polynomial-time convex relaxation algorithm via the semidefinite programming (SDP) to solve the diffusion @math -means. In addition, we also propose a nuclear norm (i.e., trace norm) regularized SDP that is adaptive to the number of clusters. In both cases, we show that exact recovery of the SDPs for diffusion @math -means can be achieved under suitable between-cluster separability and within-cluster connectedness of the submanifolds, which together quantify the hardness of the manifold clustering problem. We further propose the localized diffusion @math -means by using the local adaptive bandwidth estimated from the nearest neighbors. We show that exact recovery of the localized diffusion @math -means is fully adaptive to the local probability density and geometric structures of the underlying submanifolds.
On the contrary, literature on theoretical guarantees for manifold clustering is rather scarce, with the exception @cite_6 . Near-optimal exact recovery of some emblematic clustering methods based on pairwise distances of data is derived under a condition that the minimal signal separation strength over all pairs of submanifolds is larger than a threshold. Compared with our diffusion @math -means with local scaling, results established in @cite_6 are non-adaptive to the local density and (geometric) structures of the submanifolds (cf. Theorem and ahead).
@cite_6
2104094124
We study exact recovery conditions for convex relaxations of point cloud clustering problems, focusing on two of the most common optimization problems for unsupervised clustering: @math -means and @math -median clustering. Motivations for focusing on convex relaxations are: (a) they come with a certificate of optimality, and (b) they are generic tools which are relatively parameter-free, not tailored to specific assumptions over the input. More precisely, we consider the distributional setting where there are @math clusters in @math and data from each cluster consists of @math points sampled from a symmetric distribution within a ball of unit radius. We ask: what is the minimal separation distance between cluster centers needed for convex relaxations to exactly recover these @math clusters as the optimal integral solution? For the @math -median linear programming relaxation we show a tight bound: exact recovery is obtained given arbitrarily small pairwise separation @math between the balls. In other words, the pairwise center separation is @math . Under the same distributional model, the @math -means LP relaxation fails to recover such clusters at separation as large as @math . Yet, if we enforce PSD constraints on the @math -means LP, we get exact cluster recovery at center separation @math . In contrast, common heuristics such as Lloyd's algorithm (a.k.a. the @math -means algorithm) can fail to recover clusters in this setting; even with arbitrarily large cluster separation, k-means++ with overseeding by any constant factor fails with high probability at exact cluster recovery. To complement the theoretical analysis, we provide an experimental study of the recovery guarantees for the