Performance Gaps in Multi-view Clustering under the Nested Matrix-Tensor Model

• URL: http://arxiv.org/abs/2402.10677v1
• Date: Fri, 16 Feb 2024 13:31:43 GMT
• Title: Performance Gaps in Multi-view Clustering under the Nested Matrix-Tensor Model
• Authors: Hugo Lebeau, Mohamed El Amine Seddik, Jos\'e Henrique de Morais Goulart
• Abstract summary: We study the estimation of a planted signal hidden in a recently introduced nested matrix-tensor model. We quantify here the performance gap between a tensor-based approach and a tractable alternative approach.
• Score: 7.4968526280735945
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the estimation of a planted signal hidden in a recently introduced nested matrix-tensor model, which is an extension of the classical spiked rank-one tensor model, motivated by multi-view clustering. Prior work has theoretically examined the performance of a tensor-based approach, which relies on finding a best rank-one approximation, a problem known to be computationally hard. A tractable alternative approach consists in computing instead the best rank-one (matrix) approximation of an unfolding of the observed tensor data, but its performance was hitherto unknown. We quantify here the performance gap between these two approaches, in particular by deriving the precise algorithmic threshold of the unfolding approach and demonstrating that it exhibits a BBP-type transition behavior. This work is therefore in line with recent contributions which deepen our understanding of why tensor-based methods surpass matrix-based methods in handling structured tensor data.

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)
• Interaction Screening and Pseudolikelihood Approaches for Tensor Learning in Ising Models [7.298865011539767]
  We study two well known methods of Ising structure learning, namely the pseudolikelihood approach and the interaction screening approach. We show that both approaches retrieve the underlying hypernetwork structure using a sample size logarithmic in the number of network nodes.
  arXiv  Detail & Related papers  (2023-10-20T02:42:32Z)
• A Nested Matrix-Tensor Model for Noisy Multi-view Clustering [5.132856740094742]
  We propose a nested matrix-tensor model which extends the spiked rank-one tensor model of order three. We show that our theoretical results allow us to anticipate the exact accuracy of the proposed clustering approach. Our analysis unveils unexpected and non-trivial phase transition phenomena depending on the model parameters.
  arXiv  Detail & Related papers  (2023-05-31T16:13:46Z)
• Multi-View Clustering via Semi-non-negative Tensor Factorization [120.87318230985653]
  We develop a novel multi-view clustering based on semi-non-negative tensor factorization (Semi-NTF) Our model directly considers the between-view relationship and exploits the between-view complementary information. In addition, we provide an optimization algorithm for the proposed method and prove mathematically that the algorithm always converges to the stationary KKT point.
  arXiv  Detail & Related papers  (2023-03-29T14:54:19Z)
• Rethinking Clustering-Based Pseudo-Labeling for Unsupervised Meta-Learning [146.11600461034746]
  Method for unsupervised meta-learning, CACTUs, is a clustering-based approach with pseudo-labeling. This approach is model-agnostic and can be combined with supervised algorithms to learn from unlabeled data. We prove that the core reason for this is lack of a clustering-friendly property in the embedding space.
  arXiv  Detail & Related papers  (2022-09-27T19:04:36Z)
• Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
  We propose a novel semi-supervised subspace clustering method, which is able to simultaneously augment the initial supervisory information and construct a discriminative affinity matrix. Comprehensive experimental results on six commonly-used benchmark datasets demonstrate the superiority of our method over state-of-the-art methods.
  arXiv  Detail & Related papers  (2022-05-21T01:47:17Z)
• Robust M-estimation-based Tensor Ring Completion: a Half-quadratic Minimization Approach [14.048989759890475]
  We develop a robust approach to tensor ring completion that uses an M-estimator as its error statistic. We present two HQ-based algorithms based on truncated singular value decomposition and matrix factorization.
  arXiv  Detail & Related papers  (2021-06-19T04:37:50Z)
• Clustering Ensemble Meets Low-rank Tensor Approximation [50.21581880045667]
  This paper explores the problem of clustering ensemble, which aims to combine multiple base clusterings to produce better performance than that of the individual one. We propose a novel low-rank tensor approximation-based method to solve the problem from a global perspective. Experimental results over 7 benchmark data sets show that the proposed model achieves a breakthrough in clustering performance, compared with 12 state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-12-16T13:01:37Z)
• Doubly Stochastic Subspace Clustering [9.815735805354905]
  Many state-of-the-art subspace clustering methods follow a two-step process by first constructing an affinity matrix between data points and then applying spectral clustering to this affinity. In this work, we learn both a self-expressive representation of the data and an affinity matrix that is well-normalized for spectral clustering. Experiments show that our method achieves state-of-the-art subspace clustering performance on many common datasets in computer vision.
  arXiv  Detail & Related papers  (2020-11-30T14:56:54Z)
• Multi-View Spectral Clustering Tailored Tensor Low-Rank Representation [105.33409035876691]
  This paper explores the problem of multi-view spectral clustering (MVSC) based on tensor low-rank modeling. We design a novel structured tensor low-rank norm tailored to MVSC. We show that the proposed method outperforms state-of-the-art methods to a significant extent.
  arXiv  Detail & Related papers  (2020-04-30T11:52:12Z)
• Tensor denoising and completion based on ordinal observations [11.193504036335503]
  We consider the problem of low-rank tensor estimation from possibly incomplete, ordinal-valued observations. We propose a multi-linear cumulative link model, develop a rank-constrained M-estimator, and obtain theoretical accuracy guarantees. We show that the proposed estimator is minimax optimal under the class of low-rank models.
  arXiv  Detail & Related papers  (2020-02-16T07:09:56Z)

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.