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
165483176
This paper advocates a novel framework for segmenting a dataset in a Riemannian manifold @math into clusters lying around low-dimensional submanifolds of @math . Important examples of @math , for which the proposed clustering algorithm is computationally efficient, are the sphere, the set of positive definite matrices, and the Grassmannian. The clustering problem with these examples of @math is already useful for numerous application domains such as action identification in video sequences, dynamic texture clustering, brain fiber segmentation in medical imaging, and clustering of deformed images. The proposed clustering algorithm constructs a data-affinity matrix by thoroughly exploiting the intrinsic geometry and then applies spectral clustering. The intrinsic local geometry is encoded by local sparse coding and more importantly by directional information of local tangent spaces and geodesics. Theoretical guarantees are established for a simplified variant of the algorithm even when the clusters intersect. To avoid complication, these guarantees assume that the underlying submanifolds are geodesic. Extensive validation on synthetic and real data demonstrates the resiliency of the proposed method against deviations from the theoretical model as well as its superior performance over state-of-the-art techniques.