Linearithmic time sparse and convex maximum margin clustering.

Area of Science:

• Machine Learning
• Data Mining
• Optimization

Background:

• Maximum Margin Clustering (MMC) was previously formulated as a difficult nonconvex integer problem.
• Existing methods either sacrifice convexity for efficiency or are inefficient.
• A need exists for convex and efficient MMC algorithms.

Purpose of the Study:

• To propose a novel, efficient, and convex algorithm for Maximum Margin Clustering (MMC).
• To extend the proposed method to Multiple-Kernel Clustering (MKC) and Multiclass MMC (M3C).

Main Methods:

• Introduced Support-Vector-Regression-based MMC (SVR-MMC), utilizing Support-Vector Regression (SVR) as its core.
• Relaxed the problem into a convex optimization problem solved iteratively by a cutting-plane algorithm.
• Decomposed subproblems using a Global Extended-Level Method (GELM) and solved them with a Sparse-Kernel SVR (SKSVR) algorithm for linear time complexity.
• Extended SVR-MMC to SVR-MKC and SVR-M3C.

Main Results:

• The SVR-MMC algorithm achieves linearithmic time complexity, maintaining convexity and efficiency.
• The SVR-MKC demonstrated strong performance in unsupervised Voice Activity Detection (VAD), comparable to supervised methods and meeting real-time demands.
• The novel SKSVR algorithm provides a linear time interface for nonlinear kernel scenarios, ensuring overall linearithmic complexity.

Conclusions:

• SVR-MMC and its extensions (SVR-MKC, SVR-M3C) offer an effective and efficient solution for clustering problems.
• The unsupervised application of SVR-MKC to VAD highlights its practical utility without requiring labeled data.
• The proposed algorithms successfully address the limitations of previous MMC approaches by combining convexity and efficiency.