Clustering from Sparse Pairwise Measurements
We consider the problem of grouping items into clusters based on few random pairwise comparisons between the items. We introduce three closely related algorithms for this task: a belief propagation algorithm approximating the Bayes optimal solution, and two spectral algorithms based on the non-backtracking and Bethe Hessian operators. For the case of two symmetric clusters, we conjecture that these algorithms are asymptotically optimal in that they detect the clusters as soon as it is information theoretically possible to do so. We substantiate this claim for one of the spectral approaches we introduce.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringSimilar Papers 제목 키워드 기반
Spatial Sparse subspace clustering for Compressive Spectral imaging
This paper aims at developing a clustering approach with spectral images directly from CASSI compressive measurements. The proposed clustering method first assumes that compressed measurements lie in the union of multipl…
ClusteringImage ClusteringStatistical Properties of the Single Linkage Hierarchical Clustering Estimator
Distance-based hierarchical clustering (HC) methods are widely used in unsupervised data analysis but few authors take account of uncertainty in the distance data. We incorporate a statistical model of the uncertainty th…
ClusteringConvex Sparse Spectral Clustering: Single-view to Multi-view
Spectral Clustering (SC) is one of the most widely used methods for data clustering. It first finds a low-dimensonal embedding $U$ of data by computing the eigenvectors of the normalized Laplacian matrix, and then perfor…
ClusteringFast Randomized Semi-Supervised Clustering
We consider the problem of clustering partially labeled data from a minimal number of randomly chosen pairwise comparisons between the items. We introduce an efficient local algorithm based on a power iteration of the no…
ClusteringGeneral ClassificationStable Camera Motion Estimation Using Convex Programming
We study the inverse problem of estimating n locations $t_1, ..., t_n$ (up to global scale, translation and negation) in $R^d$ from noisy measurements of a subset of the (unsigned) pairwise lines that connect them, that …
ClusteringMotion EstimationNegation