Consistent spectral clustering in sparse tensor block models

• URL: http://arxiv.org/abs/2501.13820v1
• Date: Thu, 23 Jan 2025 16:41:19 GMT
• Title: Consistent spectral clustering in sparse tensor block models
• Authors: Ian Välimaa, Lasse Leskelä,
• Abstract summary: High-order clustering aims to classify objects in multiway datasets that are prevalent in various fields. This paper introduces a tensor block model specifically designed for sparse integer-valued data tensors. We propose a simple spectral clustering algorithm augmented with a trimming step to mitigate noise fluctuations.
• Score: 0.0
• License:
• Abstract: High-order clustering aims to classify objects in multiway datasets that are prevalent in various fields such as bioinformatics, social network analysis, and recommendation systems. These tasks often involve data that is sparse and high-dimensional, presenting significant statistical and computational challenges. This paper introduces a tensor block model specifically designed for sparse integer-valued data tensors. We propose a simple spectral clustering algorithm augmented with a trimming step to mitigate noise fluctuations, and identify a density threshold that ensures the algorithm's consistency. Our approach models sparsity using a sub-Poisson noise concentration framework, accommodating heavier than sub-Gaussian tails. Remarkably, this natural class of tensor block models is closed under aggregation across arbitrary modes. Consequently, we obtain a comprehensive framework for evaluating the tradeoff between signal loss and noise reduction during data aggregation. The analysis is based on a novel concentration bound for sparse random Gram matrices. The theoretical findings are illustrated through simulation experiments.

Related papers

• High-Dimensional Tensor Discriminant Analysis with Incomplete Tensors [5.745276598549783]
  We introduce a novel approach to tensor classification with incomplete data, framed within high-dimensional linear discriminant analysis. Our method demonstrates excellent performance in simulations and real data analysis, even with significant proportions of missing data.
  arXiv  Detail & Related papers  (2024-10-18T18:00:16Z)
• Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
  We show that PCA becomes computationally hard at a critical value of the signal's magnitude. We define a new set of objects, which provide an explicit, near-orthogonal basis for invariants of a given degree. It also lets us analyze a new problem of distinguishing between different ensembles.
  arXiv  Detail & Related papers  (2024-04-29T14:33:24Z)
• Datacube segmentation via Deep Spectral Clustering [76.48544221010424]
  Extended Vision techniques often pose a challenge in their interpretation. The huge dimensionality of data cube spectra poses a complex task in its statistical interpretation. In this paper, we explore the possibility of applying unsupervised clustering methods in encoded space. A statistical dimensional reduction is performed by an ad hoc trained (Variational) AutoEncoder, while the clustering process is performed by a (learnable) iterative K-Means clustering algorithm.
  arXiv  Detail & Related papers  (2024-01-31T09:31:28Z)
• Heteroskedastic Tensor Clustering [20.979358557219953]
  We propose a two-stage method, named $mathsfHightext-orderHeteroClustering$ ($mathsfHHC$) It starts by performing tensor subspace estimation via a novel spectral algorithm called $mathsfThresholdedDeflatedtext-HeteroPCA$, followed by approximate $k$-means to obtain cluster nodes. Our algorithm provably achieves exact clustering as long as the SNR exceeds the computational limit.
  arXiv  Detail & Related papers  (2023-11-04T02:50:40Z)
• A Robust and Flexible EM Algorithm for Mixtures of Elliptical Distributions with Missing Data [71.9573352891936]
  This paper tackles the problem of missing data imputation for noisy and non-Gaussian data. A new EM algorithm is investigated for mixtures of elliptical distributions with the property of handling potential missing data. Experimental results on synthetic data demonstrate that the proposed algorithm is robust to outliers and can be used with non-Gaussian data.
  arXiv  Detail & Related papers  (2022-01-28T10:01:37Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  Clustering is a fundamental primitive in unsupervised learning. Recent work has established lower bounds against the class of low-degree methods. We show that, perhaps surprisingly, this particular clustering model textitdoes not exhibit a statistical-to-computational gap.
  arXiv  Detail & Related papers  (2021-12-07T18:50:17Z)
• Information-Theoretic Generalization Bounds for Iterative Semi-Supervised Learning [81.1071978288003]
  In particular, we seek to understand the behaviour of the em generalization error of iterative SSL algorithms using information-theoretic principles. Our theoretical results suggest that when the class conditional variances are not too large, the upper bound on the generalization error decreases monotonically with the number of iterations, but quickly saturates.
  arXiv  Detail & Related papers  (2021-10-03T05:38:49Z)
• Correlation Clustering Reconstruction in Semi-Adversarial Models [70.11015369368272]
  Correlation Clustering is an important clustering problem with many applications. We study the reconstruction version of this problem in which one is seeking to reconstruct a latent clustering corrupted by random noise and adversarial modifications.
  arXiv  Detail & Related papers  (2021-08-10T14:46:17Z)
• Exact Clustering in Tensor Block Model: Statistical Optimality and Computational Limit [10.8145995157397]
  High-order clustering aims to identify heterogeneous substructure in multiway dataset. Non- computation and nature of the problem poses significant challenges in both statistics and statistics.
  arXiv  Detail & Related papers  (2020-12-18T00:48:27Z)
• Robust spectral clustering using LASSO regularization [0.0]
  This paper presents a variant of spectral clustering, called 1-spectral clustering, performed on a new random model closely related to block model. Its goal is to promote a sparse eigenbasis solution of a 1 minimization problem revealing the natural structure of the graph.
  arXiv  Detail & Related papers  (2020-04-08T07:12:56Z)
• Randomized Spectral Clustering in Large-Scale Stochastic Block Models [13.366036495177923]
  We study the spectral clustering using randomized sketching algorithms from a statistical perspective. Under mild conditions, the randomized spectral clustering algorithms lead to the same theoretical bounds as those of the original spectral clustering algorithm. A new R package called Rclust is developed and made available to the public.
  arXiv  Detail & Related papers  (2020-01-20T04:15:25Z)

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.