PaperlayerView exact revision on arXiv

Source-linked AI summary

On Unifying Multi-View Self-Representations for Clustering by Tensor Multi-Rank Minimization

Yuan Xie, Dacheng Tao, Wensheng Zhang, Lei Zhang, Yan Liu, Yanyun Qu

arXiv:1610.07126v3cs.CV

TL;DR

Multi-view subspace clustering must combine heterogeneous, potentially noisy views without groundtruth guidance while exploiting both shared and complementary information. t-SVD-MSC rotates a tensor formed from view-specific subspace representations and minimizes a t-SVD-based tensor nuclear norm; experiments report clear or significant advances over contemporary multi-view clustering methods, with an efficient convergent optimization procedure.

  • Problem

    Multi-view clustering lacks groundtruth guidance, while individual views may be limited or noisy, motivating models that capture relationships among views.

  • Method

    t-SVD-MSC stacks view-specific subspace representations into a tensor, rotates it, and applies t-SVD-based tensor multi-rank minimization while iteratively updating the representations.

  • Results

    Clear advance over contemporary multi-view clustering approaches is reported across face, scene, and generic object image-clustering datasets.

  • Takeaways & Limitations

    The t-SVD-based tensor constraint is used to capture complementary information and high-order correlations among multiple views in a unified clustering model.

  • Takeaways & Limitations

    The proposed tensor low-rank constraint requires rotating self-represented coefficients to accommodate the intrinsic circulant algebra underlying the t-TNN.

Abstract

from arXiv · show

In this paper, we address the multi-view subspace clustering problem. Our method utilizes the circulant algebra for tensor, which is constructed by stacking the subspace representation matrices of different views and then rotating, to capture the low rank tensor subspace so that the refinement of the view-specific subspaces can be achieved, as well as the high order correlations underlying multi-view data can be explored.} By introducing a recently proposed tensor factorization, namely tensor-Singular Value Decomposition (t-SVD) \cite{kilmer13}, we can impose a new type of low-rank tensor constraint on the rotated tensor to capture the complementary information from multiple views. Different from traditional unfolding based tensor norm, this low-rank tensor constraint has optimality properties similar to that of matrix rank derived from SVD, so the complementary information among views can be explored more efficiently and thoroughly. The established model, called t-SVD based Multi-view Subspace Clustering (t-SVD-MSC), falls into the applicable scope of augmented Lagrangian method, and its minimization problem can be efficiently solved with theoretical convergence guarantee and relatively low computational complexity. Extensive experimental testing on eight challenging image dataset shows that the proposed method has achieved highly competent objective performance compared to several state-of-the-art multi-view clustering methods.

1 Introduction

The paper targets multi-view subspace clustering by refining view-specific representations while capturing consensus and complementary information through a rotated tensor and t-SVD-based low-rank constraint.

  • Motivation: Multi-view clustering combines heterogeneous representations, but lacks groundtruth guidance and must handle noisy, limited information from individual views.The goal is to capture relationships among views to improve clustering from the available representations.
  • Method: The t-SVD-based constraint provides a tensor-space alternative to unfolding-based norms, supporting consensus and more thorough exploration of complementary information across views.The paper motivates this constraint through t-SVD and its derived tensor nuclear norm.
  • Method: t-SVD-MSC stacks view-specific subspace representations into a third-order tensor, rotates it, and updates the rotated tensor through t-SVD-based tensor nuclear norm minimization.The view-specific representations are subsequently updated under self-reconstruction constraints until convergence.
  • Optimization: The optimization problem is solved with an efficient algorithm that has a theoretical convergence guarantee and relatively low computational complexity.The contribution is framed as an augmented-Lagrangian-solvable minimization problem.
  • Evaluation: Experiments on challenging image datasets report significant improvement over state-of-the-art multi-view subspace clustering approaches.With CNN features included as a view, the method is reported to perform competitively with recent CNN-based clustering on some large-scale datasets.

2 Related Work

Related work spans graph fusion, co-training or co-regularization, subspace learning, and self-representation methods for integrating multi-view information.

  • Graph-based approaches: Graph-based approaches exploit relationships among views through graph fusion, including bipartite graphs, latent graph transitions, tensor product graphs, and multiple-kernel combinations.These methods construct or combine view-specific graphs before clustering.
  • Co-training and co-regularization: Co-training and co-regularized methods use separate learners or embeddings from distinct views to constrain one another and reduce disagreement.Examples exchange partition information, constrain adjacency matrices, or regularize clustering hypotheses across views.
  • Subspace learning: Subspace learning methods seek a shared latent subspace, using CCA, kernel CCA, deep models, autoencoders, or tensor CCA for multiple views.Tensor CCA extends CCA to an arbitrary number of views by analyzing a covariance tensor.
  • Self-representation: Self-representation approaches extend SSC or LRR to multi-view data by learning relationships among samples and imposing tensor constraints on view-specific coefficients.A closely related method uses the rank-sum of different tensor unfoldings, but this constraint lacks a clear physical meaning for general tensors.

3 Notations and Preliminaries

The preliminaries define tensor operations, t-SVD, tensor multi-rank, and the t-SVD-based tensor nuclear norm used to formulate low-rank tensor constraints.

  • Tensor notation: A 3-way tensor is organized into horizontal, lateral, and frontal slices, mode fibers, and a third-mode Fourier transform.These structures support the block and Fourier-domain operations used by t-SVD.
  • Tensor operations: The t-product multiplies tensors by replacing scalar multiplication between mode-3 fibers with circular convolution.In the Fourier domain, the t-product corresponds to matrix multiplication of frontal slices.
  • Tensor singular value decomposition: t-SVD decomposes a tensor into orthogonal tensors and an f-diagonal tensor under the t-product, and it can be computed efficiently in the Fourier domain.The decomposition is illustrated for an n1 × n2 × n3 tensor.
  • Tensor multi-rank: Tensor multi-rank is a vector whose entries are the ranks of the frontal slices of the tensor after the third-mode Fourier transform.The definition connects tensor rank structure to matrix ranks in the Fourier domain.
  • Tensor nuclear norm: The t-SVD-based tensor nuclear norm is a valid norm and the tightest convex relaxation of the ℓ1 norm of tensor multi-rank.Its block-circulant interpretation compares structure across rows and columns of frontal slices over the third dimension.

4 The Proposed Approach

The proposed approach extends self-representation subspace clustering to multiple views by learning view-specific coefficients and combining them into a tensor-based clustering formulation.

  • Subspace clustering: Single-view LRR learns a coefficient matrix that reconstructs data and uses its absolute symmetrization as an affinity matrix for spectral clustering.The coefficients represent samples in terms of one another.
  • Multi-view extension: The naive multi-view extension learns a separate subspace representation Z(v) for each view under the self-reconstruction constraint X(v) = X(v)Z(v) + E(v).The learned representations are then combined to construct the final affinity matrix.
  • Tensor formulation: The proposed tensor formulation merges the view-specific coefficient matrices into a third-order tensor and uses their joint structure to support multi-view clustering.This provides a unified representation for the view-specific subspace coefficients.

4.1 Motivation

The paper models multi-view self-representations jointly in a tensor space, using t-TNN to capture relationships and high-order correlations across views. Tensor rotation preserves Fourier-domain coefficients and gives the resulting constraint favorable approximation and computational properties.

  • Multi-view subspace clustering must preserve low rank within each representation while enforcing consensus across views.
  • Unlike unfolding-based g-TNN, t-TNN has clearer physical meaning and avoids uniformly penalizing ranks across all tensor modes.
  • t-SVD-based tensor nuclear norm captures high-order correlations among different views in a unified tensor space.
  • A truncated t-SVD provides an optimal Frobenius-norm approximation under a tubal-rank constraint, analogous to truncated matrix SVD.
  • Rotating the coefficient tensor preserves self-representation coefficients in the Fourier domain and enables comparisons across samples and views.
  • The rotation operation also reduces computational complexity while accommodating the circulant algebra underlying t-TNN.

4.2 Problem Formulation

The formulation learns view-specific self-representations and errors while coupling them through a rotated tensor and a tensor nuclear-norm objective. The mapping Φ merges the representations, rotates the tensor, and supports recovery of each view’s representation.

  • Each view is modeled by the self-representation constraint X^(v) = X^(v)Z^(v) + E^(v).
  • The function Φ merges the view-specific representations into a 3-mode tensor and rotates it to dimensions N × V × N.
  • The inverse mapping Φ^-1 extracts the v-th frontal slice as the representation Z^(v).
  • Vertically concatenating error matrices encourages jointly consistent column magnitudes across views.
  • The objective seeks self-representations that capture the informational and structural complexity of multi-view features.
  • An auxiliary tensor G converts the constrained problem into an unconstrained form suitable for alternating minimization with augmented Lagrange multipliers.

4.3 Optimization Procedure

The optimization alternates updates of view-specific representations, errors, and an auxiliary tensor. The tensor subproblem is solved using t-SVD-based multi-rank minimization and tensor tubal shrinkage.

  • The alternating minimization scheme updates Z^(v), E^(v), and G in three steps.
  • The Z^(v) subproblem has a closed-form solution obtained by setting the derivative of its augmented objective to zero.
  • The matrix D is formed by vertically concatenating view-specific residual terms and multiplier corrections for updating Z^(v).
  • With the representations fixed, the G-subproblem performs tensor multi-rank minimization under the t-TNN constraint.
  • Algorithm 2 summarizes tensor multi-rank minimization, while Algorithm 3 gives the complete multi-view subspace-clustering procedure.
  • The globally optimal G update is given by a tensor tubal-shrinkage operator applied through the t-SVD factorization.

4.4 Convergence Properties and Computational Complexity

The algorithm’s convergence analysis uses sufficient conditions involving feature-matrix rank and decreasing optimality gaps. Its complexity is dominated by spectral clustering and tensor Fourier/SVD operations, with iteration counts commonly between 30 and 50.

  • Convergence Properties: Convergence is difficult to establish directly because the algorithm has multiple variable blocks and a nonsmooth objective.
  • Convergence Properties: Two sufficient convergence conditions are full column rank for each feature matrix and monotonically decreasing optimality gaps.
  • Convergence Properties: Full-column-rank conditions can be met by factorizing each Z^(v) using an orthogonalized feature matrix.
  • Computational Complexity: The computational bottleneck is solving the E and G subproblems, especially 3D FFTs, inverse FFTs, and Fourier-domain SVDs.
  • Computational Complexity: The stated complexity is O(N^3) + O(K(2N^2V log(N))).
  • Computational Complexity: With η fixed at 2, the iteration count K commonly falls between 30 and 50.

4.5 Discussion

The paper analyzes how view-specific discriminative power affects self-representation structure and clustering quality. Less discriminative features generate cross-subspace responses, whereas stronger features encourage block-diagonal representations.

  • Block-diagonal structure in the representation is associated with better clustering results.The paper relates clustering quality to the structure of the learned self-representation matrices.
  • Low-rank representation can produce block-diagonal structure without requiring samples to be ordered by subspace membership.The stated reason is that the low-rank representation solution is globally optimal and independent of sample arrangement.
  • Less discriminative features produce more non-zero representation coefficients between samples from different subspaces.Such cross-subspace responses indicate weaker separation in the learned representation.
  • Strongly discriminative features drive representation coefficients between different subspaces toward zero.This behavior supports clearer separation among subspaces.

5 Experimental Results and Analysis

Experiments evaluate t-SVD-MSC across face, scene, and generic object clustering using multiple handcrafted and CNN-based views and standard clustering criteria. Across the reported datasets, the method generally outperforms competing approaches, while complementary and degenerate views affect performance differently.

  • Evaluation Methodology: The evaluation covers eight challenging image datasets using simple face features, sophisticated scene features, and CNN features for MITIndoor-67 and Caltech-101.The feature sets include intensity, LBP, Gabor, PHOW, CENTRIST, and ImageNet-trained CNN features.
  • Evaluation Measures: Clustering quality is assessed with external and internal criteria, including accuracy computed after Hungarian permutation matching.Accuracy increases with the number of correctly predicted sample labels.
  • Face Clustering: On Yale, t-SVD-MSC exceeds LTMSC with NMI 0.953 vs. 0.765 and ACC 0.963 vs. 0.741.LTMSC is reported as the second-best method on this dataset.
  • Scene Clustering: On MITIndoor-67, t-SVD-MSC improves over GSNMF-CNN by 7.7% in NMI, 16.7% in ACC, and 29.1% in AR.The reported gains are 19.0% in F-score, 17.6% in Precision, and 20.1% in Recall.
  • Generic Clustering: Degenerate views can reduce competing methods’ performance, whereas t-SVD-MSC is reported as robust to their presence and benefits from CNN–handcrafted feature complementarity.The paper also reports that optimized view performances improve simultaneously on ORL and MITIndoor-67.

6 Conclusions

The paper proposes a t-SVD-based tensor low-rank subspace model for multi-view clustering. It constrains a rotated subspace-coefficient tensor through tensor multi-rank and formulates an efficient unified optimization framework.

  • The method captures complementary information across views by constraining the rotated subspace coefficient tensor through tensor multi-rank.
  • t-SVD-MSC formulates multi-view clustering in a unified optimization framework and provides an efficient algorithm for finding a solution.

7 Appendix

The appendix reformulates the optimization in the Fourier domain and separates it into independent matrix subproblems. It also describes soft-thresholding and tensor singular-value thresholding, alongside parameter-tuning and convergence figures.

  • In the Fourier domain, the optimization problem separates into n3 independent subproblems.
  • Each Fourier-domain subproblem is an F-norm-based nuclear-norm low-rank matrix approximation problem solvable by soft-thresholding.
  • Figure 11 presents parameter λ tuning using ACC and NMI on the Yale and Scene-15 datasets.
  • Figure 12 presents convergence curves on the Scene-15 dataset.
  • The appendix states that convolution-based tubal shrinkage in the original domain is equivalent to tensor singular-value thresholding in the Fourier domain.
Loading 1610.07126v3…