Efficient Semidefinite Spectral Clustering via Lagrange Duality

2014-02-22 · Yan Yan, Chunhua Shen, Hanzi Wang

We propose an efficient approach to semidefinite spectral clustering (SSC), which addresses the Frobenius normalization with the positive semidefinite (p.s.d.) constraint for spectral clustering. Compared with the original Frobenius norm approximation based algorithm, the proposed algorithm can more accurately find the closest doubly stochastic approximation to the affinity matrix by considering the p.s.d. constraint. In this paper, SSC is formulated as a semidefinite programming (SDP) problem. In order to solve the high computational complexity of SDP, we present a dual algorithm based on the Lagrange dual formalization. Two versions of the proposed algorithm are proffered: one with less memory usage and the other with faster convergence rate. The proposed algorithm has much lower time complexity than that of the standard interior-point based SDP solvers. Experimental results on both UCI data sets and real-world image data sets demonstrate that 1) compared with the state-of-the-art spectral clustering methods, the proposed algorithm achieves better clustering performance; and 2) our algorithm is much more efficient and can solve larger-scale SSC problems than those standard interior-point SDP solvers.

📄 PDF Abstract BibTeX arXiv:1402.5497

Code (0)

등록된 구현이 없습니다.

Tasks

Clustering

Methods 이 논문이 사용한 방법론

Spectral Clustering Spectral clustering has attracted increasing attention due to the promising ability in dealing with nonlinearly separable datasets [15], [16]. In spectral clustering, the…

Spectral Clustering in Convex and Constrained Settings

2024-04-03 · Swarup Ranjan Behera, Vijaya V. Saradhi

Spectral clustering methods have gained widespread recognition for their effectiveness in clustering high-dimensional data. Among these techniques, constrained spectral clustering has emerged as a prominent approach, dem…

Clustering

On hyperparameter tuning in general clustering problemsm

2020-01-01 · ICML 2020 1 · Xinjie Fan, Yuguang Yue, Purnamrita Sarkar, Y. X. Rachel Wang

Tuning hyperparameters for unsupervised learning problems is difficult in general due to the lack of ground truth for validation. However, the success of most clustering methods depends heavily on the correct choice of t…

Clustering Community Detection Model Selection

Improved Linear Embeddings via Lagrange Duality

2017-11-30 · Kshiteej Sheth, Dinesh Garg, Anirban Dasgupta

Near isometric orthogonal embeddings to lower dimensions are a fundamental tool in data science and machine learning. In this paper, we present the construction of such embeddings that minimizes the maximum distortion fo…

Transitive Distance Clustering with K-Means Duality

2014-06-01 · CVPR 2014 6 · Zhiding Yu, Chunjing Xu, Deyu Meng, Zhuo Hui 외

We propose a very intuitive and simple approximation for the conventional spectral clustering methods. It effectively alleviates the computational burden of spectral clustering - reducing the time complexity from O(n^3) …

Clustering Image Segmentation Semantic Segmentation

Global Optimality for Point Set Registration Using Semidefinite Programming

2020-06-01 · CVPR 2020 6 · Jose Pedro Iglesias, Carl Olsson, Fredrik Kahl

In this paper we present a study of global optimality conditions for Point Set Registration (PSR) with missing data. PSR is the problem of aligning multiple point clouds with an unknown target point cloud. Since non-line…