# Fast and Robust Sparsity-Aware Block Diagonal Representation

arXiv: https://arxiv.org/abs/2312.01137 · HTML: https://mlsanity.com/paper/2312.01137/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 81 references that are in the map.
- First posted on arXiv 2 Dec 2023.

## Builds on (most cited first, 10 of 10)

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Subspace Clustering by Block Diagonal Representation](https://mlsanity.com/paper/1805.09243/) (2018)
- [A General Optimization Technique for High Quality Community Detection in Complex Networks](https://mlsanity.com/paper/1308.3508/) (2013)
- [Fast Robust PCA on Graphs](https://mlsanity.com/paper/1507.08173/) (2015)
- [Color Image and Multispectral Image Denoising Using Block Diagonal Representation](https://mlsanity.com/paper/1902.03954/) (2019)
- [Toward Unobtrusive In-home Gait Analysis Based on Radar Micro-Doppler Signatures](https://mlsanity.com/paper/1809.06653/) (2018)
- [Postprocessing of Compressed Images via Sequential Denoising](https://mlsanity.com/paper/1510.09041/) (2015)
- [The eigenvalues of stochastic blockmodel graphs](https://mlsanity.com/paper/1803.11551/) (2018)
- [Discriminative Block-Diagonal Representation Learning for Image Recognition](https://mlsanity.com/paper/1707.03548/) (2017)
- [Robust Regularized Locality Preserving Indexing for Fiedler Vector Estimation](https://mlsanity.com/paper/2107.12070/) (2021)

## Built on by (most cited first, 1 of 1)

- [Block-Diagonal Guided DBSCAN Clustering](https://mlsanity.com/paper/2404.01341/) (2024)

## Abstract (arXiv)

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.