Fast and Robust Sparsity-Aware Block Diagonal Representation
- URL: http://arxiv.org/abs/2312.01137v1
- Date: Sat, 2 Dec 2023 13:44:27 GMT
- Title: Fast and Robust Sparsity-Aware Block Diagonal Representation
- Authors: Aylin Tastan, Michael Muma and Abdelhak M.Zoubir
- Abstract summary: The block diagonal structure of an affinity matrix represents clusters of feature vectors by non-zero coefficients that are concentrated in blocks.
We propose a Fast and Robust Sparsity-Aware Block Diagonal Representation (FRS-BDR) method, which jointly estimates cluster memberships and the number of blocks.
Experiments on a variety of real-world applications demonstrate the robustness of FRS-BDR in terms of clustering accuracy, against corrupted features, time and cluster enumeration performance.
- Score: 13.167450470598045
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The block diagonal structure of an affinity matrix is a commonly desired
property in cluster analysis because it represents clusters of feature vectors
by non-zero coefficients that are concentrated in blocks. However, recovering a
block diagonal affinity matrix is challenging in real-world applications, in
which the data may be subject to outliers and heavy-tailed noise that obscure
the hidden cluster structure. To address this issue, we first analyze the
effect of different fundamental outlier types in graph-based cluster analysis.
A key idea that simplifies the analysis is to introduce a vector that
represents a block diagonal matrix as a piece-wise linear function of the
similarity coefficients that form the affinity matrix. We reformulate the
problem as a robust piece-wise linear fitting problem and propose a Fast and
Robust Sparsity-Aware Block Diagonal Representation (FRS-BDR) method, which
jointly estimates cluster memberships and the number of blocks. Comprehensive
experiments on a variety of real-world applications demonstrate the
effectiveness of FRS-BDR in terms of clustering accuracy, robustness against
corrupted features, computation time and cluster enumeration performance.
Related papers
- Interpretable Multi-View Clustering Based on Anchor Graph Tensor Factorization [64.00146569922028]
Multi-view clustering methods based on anchor graph factorization lack adequate cluster interpretability for the decomposed matrix.
We address this limitation by using non-negative tensor factorization to decompose an anchor graph tensor that combines anchor graphs from multiple views.
arXiv Detail & Related papers (2024-04-01T03:23:55Z) - Block-Diagonal Guided DBSCAN Clustering [1.6550162152849242]
Cluster analysis plays a crucial role in database mining.
One of the most widely used algorithms in this field is DBSCAN.
This paper introduces an improved version of DBSCAN to guide the clustering procedure of DBSCAN.
arXiv Detail & Related papers (2024-03-31T05:04:38Z) - Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
We devise an efficient algorithm that recovers clusters using the observed labels.
We present Instance-Adaptive Clustering (IAC), the first algorithm whose performance matches these lower bounds both in expectation and with high probability.
arXiv Detail & Related papers (2023-06-18T08:46:06Z) - High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
We introduce a new inference scheme that avoids explicit construction of the covariance matrix.
Our approach couples a little-known diagonal estimation result from numerical linear algebra with the conjugate gradient algorithm.
On several simulations, our method scales better than existing approaches in computation time and memory.
arXiv Detail & Related papers (2022-02-25T16:35:26Z) - Robust Regularized Locality Preserving Indexing for Fiedler Vector
Estimation [32.26669925809068]
In real-world applications, the data may be subject to heavy-tailed noise and outliers which results in deteriorations in the structure of the Fiedler vector estimate.
We design a Robust Regularized Locality Preserving Indexing (RRLPI) method for Fiedler vector estimation that aims to approximate the nonlinear manifold structure of the Laplace Beltrami operator.
arXiv Detail & Related papers (2021-07-26T09:49:23Z) - Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature
Selection [138.97647716793333]
We propose a simple and efficient unsupervised feature selection method, by combining reconstruction error with $l_2,p$-norm regularization.
We present an efficient optimization algorithm to solve the proposed unsupervised model, and analyse the convergence and computational complexity of the algorithm theoretically.
arXiv Detail & Related papers (2020-12-29T04:08:38Z) - Convex Subspace Clustering by Adaptive Block Diagonal Representation [30.709797128259236]
Subspace clustering is a class of extensively studied clustering methods.
Its key first step is to desire learning a representation coefficient matrix with block diagonal structure.
We propose Adaptive Block Diagonal Representation (ABDR) which explicitly pursues block diagonalty without sacrificing the convexity of the indirect one.
arXiv Detail & Related papers (2020-09-20T08:31:43Z) - Multi-View Spectral Clustering with High-Order Optimal Neighborhood
Laplacian Matrix [57.11971786407279]
Multi-view spectral clustering can effectively reveal the intrinsic cluster structure among data.
This paper proposes a multi-view spectral clustering algorithm that learns a high-order optimal neighborhood Laplacian matrix.
Our proposed algorithm generates the optimal Laplacian matrix by searching the neighborhood of the linear combination of both the first-order and high-order base.
arXiv Detail & Related papers (2020-08-31T12:28:40Z) - On spectral algorithms for community detection in stochastic blockmodel
graphs with vertex covariates [6.029067308095145]
We present a comparative analysis of two model-based algorithms for clustering vertices in blockmodel graphs.
We show that the second algorithm has the advantages of revealing underlying block structure.
Our findings emphasize the importance of distinguishing between observed and unobserved factors that can affect block structure in graphs.
arXiv Detail & Related papers (2020-07-04T18:22:22Z) - Selective Inference for Latent Block Models [50.83356836818667]
This study provides a selective inference method for latent block models.
We construct a statistical test on a set of row and column cluster memberships of a latent block model.
The proposed exact and approximated tests work effectively, compared to the naive test that did not take the selective bias into account.
arXiv Detail & Related papers (2020-05-27T10:44:19Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.