PaperlayerView exact revision on arXiv

Source-linked AI summary

Essential Tensor Learning for Multi-view Spectral Clustering

Jianlong Wu, Zhouchen Lin, Hongbin Zha

arXiv:1807.03602v2cs.CV

TL;DR

The paper addresses the high computational cost and limited correlation modeling of self-representation-based multi-view clustering. It proposes Markov-chain spectral clustering with rotated transition-probability tensors and t-SVD-based essential tensor learning, achieving superior reported performance across datasets and applications.

  • Problem

    Recent multi-view clustering methods mainly use self-representation-based subspace learning, which has high computation complexity and does not comprehensively model shared and view-specific information.

  • Method

    The method constructs a third-order tensor from multi-view transition probability matrices, rotates it, and learns a low-rank essential tensor using t-SVD-based tensor nuclear norm minimization.

  • Results

    The proposed ETLMSC achieves the best performance across six evaluation metrics on six listed datasets and reports superior performance across seven datasets overall.

  • Takeaways & Limitations

    Tensor modeling preserves principal information while incorporating view-specific information, providing an effective representation for Markov-chain-based multi-view spectral clustering.

Abstract

from arXiv · show

Multi-view clustering attracts much attention recently, which aims to take advantage of multi-view information to improve the performance of clustering. However, most recent work mainly focus on self-representation based subspace clustering, which is of high computation complexity. In this paper, we focus on the Markov chain based spectral clustering method and propose a novel essential tensor learning method to explore the high order correlations for multi-view representation. We first construct a tensor based on multi-view transition probability matrices of the Markov chain. By incorporating the idea from robust principle component analysis, tensor singular value decomposition (t-SVD) based tensor nuclear norm is imposed to preserve the low-rank property of the essential tensor, which can well capture the principle information from multiple views. We also employ the tensor rotation operator for this task to better investigate the relationship among views as well as reduce the computation complexity. The proposed method can be efficiently optimized by the alternating direction method of multipliers~(ADMM). Extensive experiments on six real world datasets corresponding to five different applications show that our method achieves superior performance over other state-of-the-art methods.

I. INTRODUCTION

Multi-view clustering seeks to exploit complementary information across feature spaces, but many recent self-representation methods have high computational complexity. This paper instead develops Markov-chain spectral clustering with tensor modeling to capture shared and view-specific high-order information.

  • Motivation: Multi-view clustering combines representations from different domains or feature spaces to improve clustering when labels are difficult to acquire.Examples include text, images, and videos describing the same object.
  • Limitations of existing methods: Self-representation-based multi-view methods achieve promising performance but mainly use pairwise matrices and have high computation complexity.The paper motivates tensor representations as a more comprehensive way to model multi-view correlations.
  • Research gap: RMSC uses Markov-chain spectral clustering to learn shared information, whereas this work also targets view-specific information and high-order correlations.The goal is to identify principal information across multi-view representations.
  • Proposed approach: The method constructs a tensor from multi-view transition probability matrices, rotates it, and learns an essential tensor using t-SVD-based tensor nuclear norm minimization.The learned low-rank tensor is then used by standard Markov-chain spectral clustering.
  • Contributions: The proposed method combines tensor rotation, t-SVD-based low-rank modeling, and an ADMM optimization algorithm for multi-view spectral clustering.The paper reports superior performance and the lowest computation complexity across different datasets and applications.

III. NOTATIONS AND PRELIMINARIES

The paper establishes notation for third-order tensors and introduces the t-product framework underlying t-SVD. It defines tensor transposition, Fourier operations, block representations, and the t-SVD-based tensor nuclear norm.

  • Notations: The paper primarily considers third-order tensors A ∈ R^{n1×n2×n3}, whose mode-i fibers and mode-i matricizations are defined explicitly.The tensor transpose is formed by transposing frontal slices and reversing transposed frontal slices 2 through n3.
  • Notations: Block vectorization, folding, block diagonalization, and block circulant representations convert third-order tensors into structured matrix forms.These constructions support the algebra used for tensor products and decompositions.
  • Tensor algebra: The t-product multiplies compatible third-order tensors, while identity, orthogonal, and f-diagonal tensors define the corresponding tensor algebra.An f-diagonal tensor has diagonal frontal slices, and the identity tensor has an identity first frontal slice with zeros elsewhere.
  • t-SVD: t-SVD factorizes a tensor into orthogonal tensors U and V and an f-diagonal tensor S.The decomposition is the tensor analogue used to define tensor singular values.
  • Tensor nuclear norm: The t-SVD-based tensor nuclear norm is defined as the sum of singular values across the frontal slices of the tensor’s third-mode Fourier transform.The Fourier transform and its inverse are applied along the third dimension.

IV. ESSENTIAL TENSOR LEARNING FOR MULTI-VIEW SPECTRAL CLUSTERING

Markov-chain spectral clustering constructs a graph transition matrix, derives a normalized Laplacian, extracts cluster-indicator eigenvectors, and applies k-means. The method uses this framework to cluster data from transition probabilities.

  • Input and similarity construction: For data vectors X = [x1, · · · , xN] ∈ R^{d×N}, the pipeline begins with the input samples and computes their pairwise similarities.A Gaussian kernel using the ℓ2 distance is a standard similarity choice described by the algorithm.
  • Markov-chain spectral clustering: The Markov-chain pipeline computes a similarity matrix, constructs a weighted graph, and defines transition probabilities as P = D^-1S.With a unique stationary distribution π, the random walk supports the subsequent spectral formulation.
  • Markov-chain spectral clustering: The algorithm clusters the rows of the eigenvector matrix U with k-means and assigns each data point to a class.U contains C eigenvectors associated with the C largest eigenvalues of the normalized Laplacian.
  • Markov-chain spectral clustering: The stationary distribution π defines the Markov-chain Laplacian L = Π − (ΠP + P^TΠ)/2.Π is diagonal with Π_ii = π(i).
  • Markov-chain spectral clustering: Cluster indicators are obtained from eigenvectors of a generalized eigenvalue problem, equivalently from the largest eigenvalues of a normalized Laplacian.The number of selected eigenvectors equals the number of clusters C.

B. The Proposed Method

The method learns an essential multi-view transition representation by decomposing transition matrices into low-rank shared structure and view- or sample-specific errors. Tensor construction, t-SVD regularization, tensor rotation, and ℓ2,1-norm sparsity support this representation.

  • Multi-view transition representation: Each view produces a similarity matrix, weighted graph, and Markov-chain transition probability matrix for clustering.
  • Motivation: RMSC separates each transition matrix into shared information and view-specific error, whereas this method models high-order correlations with a tensor.
  • Essential tensor learning: The method collects per-view components into a third-order tensor and imposes a t-SVD-based tensor nuclear norm to learn low-rank essential information.
  • Tensor rotation: Tensor rotation changes P from R^(N×N×M) to a rotated tensor in R^(N×M×N), allowing FFT and SVD operations to capture multi-view relationships.
  • Algorithm: The optimization is summarized in Algorithm 2, which takes multi-view data and iteratively updates Z, E, and Y until convergence.
  • Error modeling: The ℓ2,1-norm models sample-related noise and outliers because affected transition-probability vectors are not sparse entrywise.

C. Optimization

The optimization uses ADMM to alternate updates of the low-rank tensor, sparse error tensor, and Lagrange multipliers. The learned tensor is then aggregated into an essential transition matrix for final spectral clustering.

  • ADMM framework: ADMM solves the tensor objective by alternating updates of variables under an augmented Lagrangian formulation.
  • Low-rank update: The Z update is a t-SVD tensor nuclear norm minimization with a closed-form tensor tubal-shrinkage solution.
  • Error update: The E update uses matricization along the third mode to optimize the tensor ℓ2,1-norm in matrix form.
  • Final clustering: After optimization, lateral slices of the essential transition tensor are summed to form Z*, which replaces P in Markov-chain spectral clustering.

D. Convergence and Complexity

The ADMM procedure converges to an optimal solution under the stated two-block setting, while tensor rotation reduces the essential-tensor learning cost. The overall pipeline still includes the final spectral-clustering cost.

  • Convergence: ADMM convergence for the two-block variable setting has been established, so the algorithm converges to an optimal solution.
  • Tensor-learning complexity: O(M^2N^2 + MN^2 log(N)) computes the rotated Z update, compared with O(MN^3 + MN^2 log(M)) without rotation.
  • Tensor-learning complexity: Under M ≪ N and M ≤ log(N), tensor rotation largely reduces optimization complexity.
  • Tensor-learning complexity: O(KMN^2(M + log(N))) is the complexity for learning the essential tensor over K iterations.
  • Overall complexity: The complete pipeline has overall complexity O(N^3 + KMN^2(M + log(N))) after adding Markov-chain spectral clustering.

A. Experimental Settings

The experiments use real-world datasets spanning multiple clustering applications, with results reported in tables and parameters specified per dataset pair.

  • Datasets: BBC-Sport contains 737 sports-news documents in five topical areas and provides two views.The topical areas are athletics, cricket, football, rugby, and tennis.
  • Datasets: UCI-Digits contains 2,000 digit images from 10 classes represented by Fourier, pixel-average, and morphological features.These are three distinct feature views for the digit images.
  • Datasets: COIL-20 contains 1,440 normalized 32×32 images from 20 object categories, represented using intensity, LBP, and Gabor features.Each category contains 72 images.
  • Evaluation setup: Tables III and IV report experimental results for BBC-Sport/UCI-Digits and COIL-20/Notting-Hill, with ETLMSC λ values set separately for each dataset.The reported λ settings are 0.03 and 0.007 for Table III, and 0.003 and 0.0008 for Table IV, respectively.
  • Datasets: Notting-Hill is a video-based face dataset with 4,660 faces from five main casts across 76 tracks, using intensity, LBP, and Gabor features.The face images have size 50 × 40.

2) Compared Methods:

The evaluation compares ETLMSC with single-view, spectral-clustering, subspace-learning, and tensor-based methods across multiple datasets and metrics. ETLMSC generally delivers the strongest results, with tensor methods outperforming other approaches in most cases.

  • Compared Methods:: The comparison includes ETLMSC, UR-ETLMSC, two single-view baselines, and six multi-view state-of-the-art methods spanning spectral, subspace, and tensor-based approaches.UR-ETLMSC is ETLMSC without tensor rotation.
  • Compared Methods:: The experiments evaluate clustering using NMI, ACC, AR, F-score, precision, and recall, with higher values indicating better performance.Results are averaged over 20 runs and parameters are selected by grid search.
  • Compared Methods:: ETLMSC achieves the best performance on BBC-Sport, UCI-Digits, COIL-20, Scene-15, MITIndoor-67, and Caltech-101 under all six metrics.Its improvements over t-SVD-MSC are more than 10% on BBC-Sport and MITIndoor-67, and 2%, 2%, 6%, and 3% on UCI-Digits, COIL-20, Scene-15, and Caltech-101, respectively.
  • Compared Methods:: Tensor-based methods, including ETLMSC and t-SVD-MSC, significantly outperform other state-of-the-art methods in most cases.On Scene-15, ETLMSC and t-SVD-MSC perform better than LTMSC across almost all classes, while ETLMSC improves slightly over t-SVD-MSC in many categories.
  • Compared Methods:: ETLMSC gains significant improvement over RMSC by incorporating view-specific information while preserving principal components through t-SVD-based tensor nuclear-norm regularization.RMSC captures only shared information among views.
  • Compared Methods:: ETLMSC outperforms UR-ETLMSC on all datasets, indicating that tensor rotation improves performance while reducing complexity.Rotation enables complementary information to be investigated after Fourier transformation; without it, similarity-coefficient arrangement may be disrupted.

2) Parameter Sensitivity Analysis:

The sensitivity analysis examines the balance parameter λ and Gaussian-kernel standard deviation σ, alongside ADMM convergence. ETLMSC is relatively insensitive to σ over a broad range and converges within 20 iterations.

  • Parameter Sensitivity Analysis:: ETLMSC tunes λ by grid search and sets each view's σ_i to its average Euclidean distance, following RMSC.The main parameters are λ and σ.
  • Parameter Sensitivity Analysis:: ETLMSC is not sensitive to σ when it varies across a certain large range.The reported tables use σ_i/AED_i = 1.
  • Parameter Sensitivity Analysis:: When σ is too small or too large, similarities approach 0 or 1, making differences difficult to distinguish and worsening results.With a proper σ_i/AED_i ratio, performance improves especially on BBCSport, UCI-Digit, COIL-20, Scene-15, and MITIndoor-67.
  • Parameter Sensitivity Analysis:: The ADMM parameters μ and ρ are fixed at 10^-5 and 1.9, respectively, and mainly affect the number of iterations required for convergence.These values follow the suggestion in.
  • Parameter Sensitivity Analysis:: The algorithm's total error decreases as iterations increase and convergence occurs within 20 iterations on COIL-20, Notting-Hill, and Caltech-101.The total error is the maximum of update changes and reconstruction error; each iteration has a closed-form solution with relatively low complexity.

4) Complexity Comparison:

ETLMSC achieves the lowest computational complexity and shortest processing time among the compared methods across datasets. Its tensor formulation also produces transition matrices with more concentrated diagonal-block structure than RMSC.

  • Complexity comparison: ETLMSC has the lowest complexity and shortest processing time among related approaches on all datasets.The comparison concerns learning the affinity matrix; post-processing complexity is shared across methods.
  • Complexity comparison: Running time depends on iteration count K and parameter selection, so timings vary across datasets.For example, ETLMSC runs shorter on UCI-Digit than COIL-20 despite the same method.
  • Transition-matrix visualization: ETLMSC produces transition matrices whose large values concentrate more strongly in diagonal blocks than RMSC.For ETLMSC, the matrix is computed by averaging lateral slices of the optimal essential tensor Z.
  • Transition-matrix visualization: The comparison attributes ETLMSC’s richer representation to high-order multi-view correlations, whereas RMSC captures only shared information.Both methods are Markov chain based spectral clustering approaches, but ETLMSC uses a tensor formulation.
  • Future work: Further scalability improvements remain a stated future direction through sampling or recovery from a smaller seed tensor.These approaches are intended to further reduce computation complexity for large-scale applications.
Loading 1807.03602v2…