Research map / Learning theory and algorithms / Matrix and tensor methods
Performance Gaps in Multi-view Clustering under the Nested Matrix-Tensor Model
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives the precise algorithmic threshold of the unfolding (matrix SVD) approach for the nested matrix-tensor multi-view clustering model, showing it has a BBP-type transition requiring beta_T = Theta(n_T^{1/4}), versus Theta(1) for best rank-one tensor approximation.
Problem
Estimating a planted cluster signal in the nested matrix-tensor model for multi-view clustering: the tensor best rank-one approach is near-optimal but NP-hard, while the tractable unfolding-plus-SVD approach had unknown performance.
Approach
Uses random matrix theory (resolvent deterministic equivalents, Stein's lemma, spiked-model analysis) to derive the limiting spectral distribution of tensor unfoldings and the spike eigenvalue/alignment, thereby quantifying the performance gap between unfolding SVD and best rank-one tensor approximation.
Key results
- The unfolding approach has an algorithmic phase transition requiring beta_T = Theta(n_T^{1/4}), whereas the best rank-one tensor approach works at Theta(1) SNR.
- Simulations with (p,n,m)=(150,300,60) show the unfolding approach has a later phase transition and lower clustering accuracy than the tensor approach, which nearly matches the optimal upper bound at ||h||=1.5.
- Theoretical clustering accuracy of the unfolding SVD converges to Phi(sqrt(zeta/(1-zeta))).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use a best rank-one tensor approximation instead of an unfolding-based estimator | Multi-view spectral clustering · Nested matrix-tensor model | clustering accuracy | Helped |
| increase the view-signal norm | Tensor approach relative to the unfolding approach · Multi-view spectral clustering | clustering accuracy gap | Helped |
| increase the view-signal norm to 1.5 | Tensor approach · Multi-view spectral clustering | clustering accuracy relative to the optimistic upper bound | Helped |
Surprising findings
- For the unfolding approach, the signal can be undetectable at any SNR when beta_M^4 <= c1c2/(1-c3), i.e., the matrix-level threshold cannot be beaten by the tensor unfolding.
Limitations
- Analysis restricted to Gaussian noise and linear view functions f_k(M)=h_k M.
- Tensor approach is NP-hard with no known efficient algorithm reaching Theta(1) SNR.
Experimental setup
Metrics: alignment |y^T yhat|^2 clustering accuracy
Baselines: best rank-one tensor approximation optimal weighted-mean estimator
Builds on: spiked rank-one tensor model BBP transition spiked Wigner model
Closest papers by meaning
- Large-scale Multi-view Tensor Clustering with Implicit Linear Kernels (CVPR 2025 · similarity 0.90)
- S2MVTC: a Simple yet Efficient Scalable Multi-View Tensor Clustering (CVPR 2024 · similarity 0.90)
- From Dictionary to Tensor: A Scalable Multi-View Subspace Clustering Framework with Triple Information Enhancement (NeurIPS 2024 · similarity 0.90)
- SLR-MVTC: Smooth Low-Rank Multi-View Tensor Clustering (AAAI 2025 · similarity 0.89)
- EDISON: Enhanced Dictionary-Induced Tensorized Incomplete Multi-View Clustering with Gaussian Error Rank Minimization (ICML 2024 · similarity 0.89)
- Low-Rank Kernel Tensor Learning for Incomplete Multi-View Clustering (AAAI 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.