Performance Gaps in Multi-view Clustering under the Nested Matrix-Tensor Model
Authors: Hugo Lebeau
Mohamed El Amine Seddik
José Henrique De Morais Goulart
Venue: ICLR 2024 poster (2024)
Keywords: random tensors
multi-view clustering
random matrix theory
tensor unfolding
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
TL;DR: In a multi-view clustering context, the performance gap between a tensor unfolding approach and and a purely tensor-based method are quantified, relying on a nested matrix-tensor model and tools from random matrix theory.

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.

Published as a conference paper at ICLR 2024
PERFORMANCE GAPS IN MULTI-VIEW CLUSTERING UNDER THE NESTED MATRIX-TENT
MODEL
Hugo Lebeau'* Mohamed El Amine Seddik? José Henrique de Morais Goulart
l Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG TTechnooogy Innovation Institute Univ. Toulouse, INP-ENSEEIHT, IRIT, CNRS "uugo. wwwaeuanniiieee................. w fr
ABSTRACT
We study the estimation of a planted signal hidden in 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 censor-based approach, which relies on finding best rank- one approximation, a problem known to be computationally hard. A tractable alternative approach consists in computing instead the best rank-one (matrix) ap- proximation of an unfolding of the observed tensor data, but its performance was hitherto unknown. We quantify here the performance gap between these ap- proaches, in particular by deriving the precise algorithmic threshold of the un- folding approach and demonstrating that exhibits a BBP-type transition behav- ior (Baik et al., 2005). This work is therefore in line with recent contributions which deepen our understanding of why bensor-based methods surpass matrix- based methods in handling structured tensor data.
INTRODUCTION
In the age of artificial intelligence, handling vast amounts of data has become a fundamental aspect of machine learning tasks. Datasets are often high-dimensions and composed of multiple modes, such as various modalities, sensors, sources, types, or domains, naturally lending themselves to be represented as tensors. Tensors offer a richer structure compared to traditional one- mne-iimesioonl vectors and two-dimensional matrices, making them increasingly relevant in various applications, including statistical learning and data analysis (Landsberg. 2012 Sun et al. 2014).
Yet, in the existing literature, there is a notable scarcity of theoretical studies that specifically ad- dress the performance gaps between tensor-based methods and traditional (matrix) spectral methods in the context of high-dimensional data analysis. While tensor methods have shown promise in var- ious applications, including multi-view clustering, co-clustering, community detection, and latent variable modeling (Wu et al.] 2019; Anandkumar et al.) 2014:) Papalexakis et al.) 2012; Wang et al. 2023), little attention has been devoted to rigorously quantifying the advantages and drawbacks of leveraging the hidden low-rank tensor structure. Filling this gap by conducting a thorough theoreti- cal analysis is crucial for gaining deeper understanding of the practical implications and potential performance gains associated with tensor-based techniques.
In the specific case of multi-view clustering, Seddik et al. (2023a) recently proposed spectral tensor method and carried out precise analysis of its performance in the large-dimensional limit. Their method consists in computing best rank-one (tensor) approximation of nested matrix-tensor model, which, in particular, generalizes the classical rank-one spiked tensor model of Montanari & Richard (2014), and can described as follows. Assume that we observe m transformations of p x n matrix M- = pyy + Z representing n. points in dimension p split into two clusters centered around +u,, with y E 1-1,1]" and Gaussian matrix encoding the "inherent" dispersion of individuals (that is, regardless of measurement errors) around the center of their respective cluster. Mathematically, each view is thus expressed as
X fx + Z) + Wey k= m. where f& models the transformation applied to M on the k-th view and W. is an additive observa- tion noise with i. entries drawn from (00 1). The mastid-matrix tensor model then arises when
(1)

---

Published as a conference paper at ICLR 2024
take (M) h2 M, meaning the function fs simply rescales the matrix M by an unknown
coefficient h4 E R. With = (hl hm) E RT and @ denoting the outer product, this gives
x (uy T + Z) h W R
(Nested Matrix-Tensor Model)
By seeking a best rank-one approximation of X to estimate its latent clustering structure. Seddik eet al. (2023a) showed empirically that it outperforms an unfolding approach based on applying an SVD to unfolding of X (Ben Arous et al. 2021 Lebeau et al.) 2024), which is matrix obtained by rearranging the entries of a tensor (see Section 2.2 However, the tensor-based approach hinges upon solving problem which is worst-case NP-hard, unlike the unfolding approach. A natural question is thus: what is the exact performance gap that exists between these two approaches, as function of some measure of difficulty of the problem (typically, a measure of signal-to- -o-nose ratio)?
Here, in order to answer this guestion, we rigorously study the unfolding method by deploying tools from random matrix theory. Specifically, our main contributions are
within the framework of the general nested matrix-tenso model, we derive the limiting spectral distribution of the unfoldings of the tensor (Theorems [and3) and precisely quan- tify how well the hidden low-rank (tensor) structure can be recovered from them in the high-dimensional regime annd
we perform similar random matrix analysis of the model when the vector spanning the third mode is known (Theorems and 4p, providing an optimal upper bound on the recovery performance;
in the context of multi-view clustering. we compare the performance of the tensor and unfolding approaches to the optimal one and specify the gap between them thanks to our theoretical findings (Theorem 5), supported by empirical results]]
Although the above described model arises from a rather particular choice of view transformations ft. it is amenable to a precise estimation performance analysis, either by means of a tensor spectral estimator as recently done by (Seddik et al. (2023a), or via matrix spectral estimator as we consider in the present paper. Moreover, from a broader perspective (that is, beyond the multi-view clustering problem considered here), this model can be viewed as a more flexible version of the rank-one spiked model, incorporating nested structure that allows for versatile data modeling, deviating from pure rank-one assumption. A common low-rank structure encoding the underlying latent clustering pattern is shared by all slices Xx, which represent distinct views of the data. In partieular, when the variances of the elements in Z approach zero, the rank-one spiked model is retrieved. Hence, we believe that the nested tensor-matrix model (and extensions) be a useful tool in other contexts in the broader area of statistical learning.
Related work. In the machine learning literature, the notion of "view" is fairly general and models data whose form may differ but all represent the same object seen from different (and complemen- tary) angles (for instance, multiple descriptors of an image, translations of text or features of a webpage such as its hyperlinks, text and images). Various approaches have been considered to address multi-view clustering problems. For instance, NNe et al. (2016) 2017b 7b/a) consider graph- based model and construct similarity matrix by integrating all views with weighted sum before applying spectral clustering. Other approaches, relying upon a space-learning-basee model (Wang et al. 2017 Zhang et al. 2017 Wang et al.] 2019 Peng al. (009), reconstruct the data in an ideal space where clustering is easy. Zhang et al. (2019) suggest a method which is more suitable for large datasets by mixing binary coding and clustering. Tensor methods have also been considered: Wu et al. (2019) propose an essential tensor learning approach for Markov chain-based multi-view spectral clustering. Furthermore, [iu et al. 2202 2023) design simple yet effective methods for multi-view clustering relying on multiple kernel k-means. Our work differs from these previous contributions in that it is focused on tensor model having the specific form of equation Nested Matrix Model Even though this model corresponds to rather particular case of the general setting given in equation our results represent a first step towards precisely understanding how tensor methods can contribute to addressing the latter.
Note that these numerical results are only meant to illustrate our theoretical findings, showing their implica- tions in practice. However, our work does not purport to explain the performance gap between any tensor-hased and any matrix-hased multi-view clustering methods.
2

---

Published as a conference paper at ICLR 2024
Regarding the analysis of performance gaps between tensor- and mention the recent work by Seddik et al. (2023b), where the authors proposed a data model that consists of a Gaussian mixture assuming low-rank tensor structure the population means and further characterized the theoretical performance gap between a simple tensor-based method and a Hattening-basse method that neglects the low-rank structure. Their study has demonstrated that the tensor approach yields provably better performance compared to treating the data as mere vectors.
methods, we can
Proofs and simulations. All proofs deferred to the appendix. Python codes to reproduce simulations are available in the following GitHub repository htttp:///ithub: com HommHHu eau/nested mmt__maariiii tensorr
2
TENSORS AND RANDOM MATRIX THEORY
2.1 GENERAL NOTATIONS
The symbols a, a and A respectively denote a scalar, a vector and a matrix. Their random coun- terparts are a, and A, respectively. Tensors (be they random not) are denoted A. The set of integers {1.... . n is denoted [n]. The unit sphere in R" is S = {x E R" x = 1}. The set of cigenvalues of matrix A is called its spectrum and denoted sp(A), The support of a mcasure yu is denoted supp μ. As usual, & is the Dirac measure at point x. Given two sequences of scalars fn and In. the notation fn (ga) means that there exist constants C, C" 0 and no such that [g The convergence in distribution of sequence of random
> 140
Clggl < [xll & C"
variables (xn)nzo denoted Xn +00
D
where C is the limiting distribution.
2.2 TENSORS AND RELATED OPERATIONS
For our purposes, we can think of tensors as multidimensional arrays. In this work, we will only
consider tensors order 3, i.e., elements of IR Xm2xna, For such a tensor T and (i.j, k) E [m]] x
[ma] x [na). Ti.j.A denotes its ji keeerry. T can be unfolded along one of its three modes to construct "matricized version" of the tensor: the unfolding of T along mode 1 is the matrix (1)
1 and likewise for T(2) and T(3) the unfoldings of T along modes 2 and The inner product between two tensors T,
R XRang such that Tı.j. (T(3)
R21xnn Xns is (T, (T,
LijAk=1 R3
Tr Th. and the Frobenius norm of is defined simply as |T]| (T,T).
The outer product @ allows to construct an order-3 tensor from a matrix A E R X and a vec- tor E Rha, [A & w]igj A,, from three vectors (u, v, w) R"1 x R= x R", [u 0 w)i ueUyWn. In the latter case, the tensor is said be rank-one.
Unfoldings of tensors defined with outer products often expressed using Kronecker products В. Given two matrices (or vectors the second dimension is set to 1) A E TR B E RPI xpi, their Kronecker product A X B is the n1P1 X R2p2 matrix such that [A X B (i.((())))r.p..--31
Ai.j Br... Among the numerous properties of the Kronecker product, we highlight the fact that is bilinear, associative, (A B) = A
X and (A X B) (CDD) = AC BD.
Example. With a A
Am E R
[ X w (1) A (In, w))
u 2 e m (1) u (v X
[ C w (2) A
[In, X w)
1 2 v (2) = v (u
LA w
(3)
wa
(u
2.3 RANDOM MATRIX TOOLS
The results presented below are derived using tools from the theory of large random matrices (Bai & Silverstein 2010; Pastur & Shcherbina 2011 Couillet Liao 2022), the main tools of which are recalled here.
3

---

Published as a conference paper at ICLR 2024
Given random symmetric matrix S E R=x" interested in the behavior of its (real) eigen- values and eigenvectors as n + + A first kind of result is the weak convergence of its empirical spectral distribution (ESD) Exesp(s) 5x towards limiting spectral distribution (LSD) μa. The
((de) C sp SE t-s from which can be recovered using the inverse formula p(dt) = lim,-=u 1 m (t + in)]. A second kind of result the almost sure convergence of the alignment between vector I and an eigenvector x of S, i.e., the quantity x T x
latter is often characterized by its Stieltjes transform my
towards a fixed value in [0, 1].
A central tool to derive such results is the resolvent Qs(s) (S s(,) defined for all s ssp Indeed, Tr Qs(s) is the Stieltjes transform evaluated at s of the ESD S. so studying its asymptotic behavior shall give insight into my- The alignments
well be studied through the resolvent thanks to the property | T x| = žाr f, x Qs(s) x ds where ry is positively-oriente complex contour circling around the eigenvalue associated to & (assuming it has multiplicity one) and leaving all other eigenvalues outside.
Because of the random nature of Qs, we will first seek deterministicn equivalent, i.e., deterministic matrix Q, such that both quantities 1 II A (Qs Qs) and (Qs Qs) b vanish almost surely as + +oo for any (sequences of) deterministic matrices A and vectors a, b of bounded norms (respectively, operator and Euclidean). This is denoted Qs <> Qs- The following lemma will be extensively used to derive such equivalents.
n
Lemma Stein (981)) Letz NN 1) and f ; + IR be continuously differentiial functiooo When the following expectations exist, E [zf(z)) = E [f)(..
3
MAIN RESULTS
Before presenting its practical applications in Section 4 we recall the definition of the nested matrix- tensor model in a general framework. Consider the following statistical model.
T= B. M
W RaIXXnana VLT
M Baixy"
Z R
(2)
VnM
where nM n1 + n2 and nr n1 + 12 n3, x. y and z are of unit norm and the entries of W and Z are independent Gaussian random variables W.j.k NO 1), Zi,j iid. (N, 1). M is rank-1 1 signal BAreyT corrupted by noise Z, modelling the data matrix, whereas T models its multi- view observation 37 @ corrupted by noise W. The positive parameters Bys and Br control the signal-to-noise ratio (SNR). Our interest is the statistical recovery of æ. y in the regime where n1, /2, f2 + +00 with 0 < c = lim ny //rr < for all E [3]. This models the fact that, in practice, deal with large tensors whose dimensions have comparable sizes.
Seddik et al. (2023a) have studied the spectral estimator of σ, y and z based on computing the best rank-one approximation of T, that is, by solving
(x, 2,
TT, X w)) (u.0,))ES"L -
arg max
Concretely, they used random matrix tools to assess its performance in the recovery of x, and z, by deploying a recent approach developed by Goulart et al. (2022); (eddik et al. (2022). this work, we study instead the performance of spectral approach based on computing the dominant singular vectors of the (matrix) unfoldings of T, aiming to precisely quantify the performance gap between these different approaches.
Because M has the structure standard spiked matrix model (Benaych-Georger & Nadakuditi 2011 Couillet & Liao. 2022) with rank-one perturbation Buay of random matrix PPm Z,
shall assume BM = (1) since we know that is in this "non-trivial regime" that the recovery of ac
2Strietly speaking, consider sequence of matrices S,, but the dependence on dropped the assumption n + +00 models the fact that, in practice, n is large.
"The "interpolation trick" of Lytova & Pastur [2009) Corollary 3.1) allows to extend these results to non- Gaussian noise up control the moments of the distribution.
4

---

Published as a conference paper at ICLR 2024
or y given M is neither too easy (too high SNR) nor too hard (too small SNR) and phase- transition phenomenon (Baik et al. 2005) between impossible and possible recovery can be observed. How- ever, we shall see that the algorithmic phase transition related to the unfolding approach takes place when 3T ( in lieu of ST = (1). This is different from the tensor spectral approach for which both Ba and BT are (1) in the non-trivial regime, supposing better performance of the latter method, although, practically, no known algorithm is able to compute it below 3T = O(1 ) (Montanari & Richard 2014).
3.1 UNFOLDINGS ALONG THE FIRST TWo MODES
We start by studying the recovery of y (resp. æ) from the unfolding T(2) (resp. T(1). In multi- view clustering perspective - which motivates our work and which will be developed in Section | are especially interested in the recovery of since it carries the class labels. Therefore, we present our results for T()) only. As a and y play a symmetric role, it is easy to deduce the results for (1) from those presented below. The recovery of x from T is dealt with in Appendix A
Following the model presented in equation 2 the unfolding along the second mode of T develops as
BT Br_z" Z (Ini x2) VnM
T By (x 8 x)
W VNT
Hence, a natural estimator y of is the dominant left singular vector of (2) or, equivalently, the dominant eigenvector of (2)) The latter being symmetric, it is better suited to the tools presented in Section 2.3 Our first step is to characterize the limiting spectral distribution of this random matrix. However, do not have sizes of the same order, causing the spectrum of ((2) to diverge as 11, 722, ng + +00. In fact, its eigenvalues gather in "bulk" centered around @(nr) value and spread interval of size ((/r)) phenomenon which was first characterized by Ben Arous et al. 2001))
must be careful with the fact that the dimensions of (2) R
For this reason, in Theorem | we do not specify the LSD of T per se but of properly centered-and-se
version of it, whose spectrum no longer diverges. Moreover, it expected that the rank-one signal B1 BMy (x: X x)) causes the presence an isolated eigenvalue in the spectrum of (2)) with corresponding eigenvector positively correlated with y when is detectable, i.c., when 8r is large enough.
Our second step is thus to precisely specify what meant by "large enough" and characterize the asymptotic position of this spike eigenvalue and the alignment with y of its corresponding eigenvec- tor. It turns out that the signal vanishes if 35 does not scale with ny. Precisely, / /ningng must converge to a fixed positive quantity"] denoted pr, to reach the "non-trivial regime" that is, one where the signal and the noise in the model have comparable strengths. However, because the noise in Z is also weighted by ãr, this affects the shape of the bulk. Hence, the value of influences the limiting spectral distribution of ( and shall appear in its defining equatior Having said all this, we now ready introduce the following theorem.
Theorem (Limiting Spectral Distribution), As n1, n22 nyy +00, the centered and-scaled matrix ny (2)) na In has a limiting spectral distribution ò whose Stieltjes transform Voinans
VaiR2ng
m() is solution to
Pr
m + (1+3 PTC2
PT (02 - -c1) m m²( 3+
m(3) +1= O.
$ E ssupp i
1-c3
1 1- C3
where pT = lim ur
Vninans"
Proof. See Appendix B
'In fact, Barr/ Vningnt only needs stay bounded between two strictly positive quantities, i.e., stay @(1). It however easier for the present analysis consider that converges (as it allows express the LSD) and this assumption has no practical implications.
TThis may be at first surprising because pr relates the strength of the signal while the LSD stems from the noise. We see that plays ambivalent role of both signal and noise term.
5

---

Published as a conference paper at ICLR 2024
Figenvalue
Densily
ESD
LSD
Spike
100
110
120
130
140
190
200
210
220
Figure 1: Empirical Spectral Distribution (ESD) and Limiting Spectral Distribution (LSD) of (2)T (left) and (3)T (right) with n1 600, n22 400 and ny = 200. Both spectra show an isolated eigenvalue close to its predicted asymptotic position, represented by the green LSD & and spike location are defined in [ Right: @ 4, 3M 3. The LSD is hhifted-and-rescalee semi-circle distribution and the normalized spike location is + ! as precised in Theorems and
dashed line. Left: pr 2. Bar = 1.5. The centered-and-scalle
As mentioned in Section 2.3 the LSD i is characterized by its Stieltjes transform, uniquely defined as the solution of polynomial equation The influence of on the LSD of (22) is made explicit in this equation and it interesting to remark that, pT = 0 (i.e., the absence of signal), this equality reduces to ni r (8) + O, which is a well-known characterization of the Stieltjes transform of the semi-circle distribution (Pastur & Shcherbina 2011 Corollary 2.2.8). Note
also that the condition Pr (11) amounts to saying that 3r- = ( *), which coincides with the conjectured "computational threshold" under which no known algorithm able to detect a signal without prior information (Montanari & Richard 2014, Ben Arous et al., 202T).
The ESD and LSD of (2)) with parameters (PT, Bar) (2, 1.5) are represented in the left panel of Figure T We observe good agreement between the actual and predicted shape of the bulk. As expected, we see an isolated eigenvalue on the right which only appears for sufficiently high values of pr and 3y. The following theorem specifies this behavior and quantifies the alignment between the signal y and the spike eigenvector y.
Theorem (Spike Behavior).
Let
=
PT
C1
+
B/r
(
C2
+
+
PM
+
8
C3
C3
PT
1-c3
and
1=1-
1
AM
B
32
1-c3
$2
PT
C2 I-c3
+
32 M
C3
C3
Inz has an isolated eigenvalue asymptotically located in almost surely. Furthermore, in this case, the alignment be- tween the corresponding eigenvector and the true signal y converges to Ç almost surely, i.e.,
If > 0, then the centered-ane ana-sc matrix
T VmingRs
T (2))
y v/² R1.
S
almost surely.
Proof. See Appendix C
Naturally, we must assume Pr, 3a > 0 for and Ç to be well defined. The location of the iso- lated cigenvalue the spectrum (2)) predicted from the expression of & is represented as the green dashed line in the left panel of Figure [ In fact, Theorem 2 reveals a phase transition phenomenon between impossible and possible recovery of the signal with the estimator ý. This is
lthoughh this is not the only solution to this equation, is the only one that has the properties of Stieltjes transform, such (()) for all e (sce, e.g., Tao (201)) for other properties).

---

Published as a conference paper at ICLR 2024
1.0
Impossible recovery
C (phase transition)
PM ( 11c8 )1/4
0.8
0.6
PT
Possible recovery
0.4
0.2
0.0
2
3
4
5
BM
Figure 2: Asymptotic alignment Ç+ = max(Ç, 0) between the signal and the dominant eigen- vector of (()), as defined in Theorem 2 with c = 2. C2 = 3 and C3 6. The curve Ç = is the position of the phase transition between the impossible detectability of the signal (below) and the presence of an isolated eigenvalue in the spectrum of (2) with corresponding eigenvector correlated with the signal (above). It has an asymptote BM ( (1- 1/4 represented by the red dashed line, as pr +00.
precisely quantified by the value of Ç+ max(Ç, (1 0): the closer is the better the estimation of The precise dependence of ( PT and BM is hard to interpret directly from its expression. Figure 2 displays < as a function pr and 3M. The expression of the curve Ç = 0 marking the position of the transition from impossible to possible recovery is given by the following proposition.
B3
Proposition 1 (Phase Transition).
6162 then Ç T-03'
Pr (
+ P1.
0102
We see that, if By & c102, it is impossible find pT such that O. This is due to the fact that 21 Cr corresponds the position the phase transition in the estimation of y from M. If the signal not detectable from M, there obviously no chance to recover from T. Moreover, as pr grows, the value of BM such that Ç = coineides with (1-gg )1/4 but it goes to
I-cs
+oo as pr approaches 0. This shows the importance having 3r = (n, (/1) (in which case is more convenient to work with the rescaled version pT of (T): if BT is an order below (pT - 0) then we are stuck the "Impossible recovery" zone while if 3T is an order above (pr + +00) then 1/4 that this
estimating from T is just like estimating from M. It is precisely in the regime 3r ( phase-transition phenomenon can be observed, thereby justifying its designation as "non-trivial", Remark. should be noted that the aforementioned impossibility of (partially) recovering the sought signal in given regime refers only the case where such recovery is carried out by the unfolding method. In other words, our discussion concerns algorithmic thresholds pertaining to such method, and not statistical ones.
3.2 ESTIMATION WITH WEIGITED MEAN
Before diving into the application of the previous results to multi-view clustering (where we will be interested in the estimation of the class labels contained in y). propose analysis of a related matrix model corresponding to the optimal estimation of y when is perfectly known. These results will give optimistic upper bound the performance of the estimation of from T.
In case z is known, y can be estimated with the following weighted mean of along mode 3,
2k T k= BI
N
(4)
TM

---

Published as a conference paper at ICLR 2024
where No iid (o 1) and = S + "Mc well known that the dominant right singular
vector of T is optimal estimator of under this model (Onatski et al. 2013 Löffler et al. 2020). Hence, we study the spectrum of / T T, which is sample covariance matrix a standard model in random matrix theory (Pastur & Shcherbina 2011: Bai & Silverstein 2010). Its eigenvalue dis-
tribution converges to the Marchenko-Pastiee distribution (Marčenko & Pastur 1967). as expressed
in the following theorem.
Theorem (Limiting Spectral Distribution), Let E+
(V
As n1, n2 - +00,
1-c3
the matrix 1 T has a limiting spectral distribution Ps explicitly given by
pmp(dx)= =
1 Ci
8g (dx)
+
1 2x 2
|0 E- [E+ - x)) dr. -x]
1-cs
Similarly to the previous spiked models, the rank-one information 3ramayy induces the pres- ence of an isolated eigenvalue in the spectrum of ş T behavior and that of its corresponding eigenvector.
T. The following theorem characterize its
Theorem (Spike Behavior). If
ci (1-ea)
then the spectrum of + T exhibits an iso-
8 e²
lated eigenvalue asymptotically located in Moreover, this case, the corresponding eigenvector i is aligned with the signal y.
+ T-)) almost surely.
T-rs
52
2
C2
T-rs
almost surely.
11,02,
M
T-os
For more details standard spiked matrix models, see Couillet & Liao 2022 $2.5).
4 PERFORMANCE GAPS IN MULTI-VIRS CLUSTERING
We shall now illustrate our results in the context of multi-view clustering. As explained in the introduction, we consider the observation of tensor X E [xxxxm following the nested matrix- tensor model,
Zij Lid. N (0,
1 p+m
x = xuw T + +2) & h W
with
(5)
W.jik N 00 p+n-m
iid.
The two cluster centers are +u and D: = v depending on the class of the i-th individual. The third vector h encodes the variances along the different views of μÿJ Z. The clustering is performed by estimating the class labels with the dominant left singular vector of (2). is thus a direct application of the results of Section 3.1 where (I] [hll)) plays the role of (Bas 3r). ). In fact, the behavior of the alignment |y y/ given by Theorem 2 can be further precised with the following theorem.
Theorem 5 (Performance of Multi-Vice Spectral Clustering). Let (Cpr Cus Cm))
(p.0..)
ptnttm
|
pentm and pann
2
||aa|
On
Cp
(=1- ||m||2
+ 1 Cm
+
[1aa)(2)
[|aa)(2)
1 - Cm
I-cm
カ+ナx N(0, for all j E (I, i.e., Y, approximately follows N (Vii, Therefore, the clustering accuracy of the estimator ý converges almost surely to
Then,
12 I-c (g (iū))
where 4 : + 22n f e- 2 dt the standard Gaussian cumulative distribution
T-c
function.
8

---

Published as a conference paper at ICLR 2024
1.0
0.9
Accuracy
0.8
|h|]
0.3
1.5
0.7
T (tbb)
0.6
T (sim)
(th)
(sim)
0.5
2
4
5
Class separability || (++ easier task)
Figure 3: Empirical versus theoretical multi-view clustering performance with parameters (p, n. m) = (150, 300, 60), varying || and two values of hh] 0.5 in blue and 1.5 in orange. The solid curve (O) an optimistic upper bound given by Theorem
it can be reached when the variances along each view are perfectly known. The dash dotted curve (T) is the performance achieved with rank-one approximation of X (Seddik al., (2023a). The dashed curve (U) is the performance predicted by Theorem 5 with the unfolding approach.
Proof. See Appendix D for sketch.
Figure B the performances the unfolding approach predicted by T that of the "tensor approach" (Seddik al. 2023a) which performs clustering with rank-one approxima- tion of X. Moreover, an optimistic upper bound on the best achievable performance, given by the solid curve, can be derived from Theorem Empirical accuracies are computed for both approaches and show good match between theory and simulation results. It appears that the unfolding approach has later phase transition and lower performance than the tensor approach. This was expected
since they do not have the same non-trivial regime (O 1/4, against (1))). As ||//]] increases, the performance gap between both approaches reduces. The performance the tensor approach rapidly comes very close to the upper bound: the two curves almost coincide for hh| = 1.5.
These results show the superiority of the tensor approach in of accuracy of the multi-view spectral clustering. In particular, by contrast with the unfolding-based estimator, the tensor approach has near-optimal performance, quantified by Theorem 4 Nevertheless, when considering "not too hard" problems (i.e., for which ||ll|| and hhl are not too close to the phase transition threshold), the performances of both methods are close and the unfolding approach may be more interesting given its ease of implementation and lower computational cost.
CONCLUSION AND PERSPECTIVES
Under the nested matrix-tenson model, we have precisely quantified the multi-view clustering per- formance achievable by the unfolding method and compared with a previously studied tensor approach (Seddik et al. 2023a). This analysis has showed the theoretical superiority of the latter in terms of clustering accuracy. In particular, the tensor approach can, in principle, recover the signal at (1) signal-to-noise ratio, while the matrix approach needs this ratio to diverge as n1/4 However, the tensor approach based on an NP-hard formulation, and no efficient algorithm capable of suc- ceeding ((1) signal-to-noise ratio is currently known. In practice, for sufficiently large ratio, one may combine these approaches by initializing a tensor rank-one approximation algorithm (such power iteration) with the estimate given by the unfolding method. Overall, this work advances our understanding of tensor data processing through rigorous theoretical results. Finally, a natural question for future work is how to extend results to general view functions fk.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
H. de M. Goulart was supported by the ANR LabEx CIMI (ANR-11-LABX-0040) within the French program "Investissements d' Avenir.".
REFERENCES
Animashree Anandkumar, Rong Ge, Daniel Hsu, Sham M Kakade, and Matus Telgarsky. Tensor decompositions for learning latent variable models. Journal of Machine Learning Research, 15: 2773-2832, 2014.
Zhidong Bai and Jack W. Silverstein. Spectral analysis of large dimensional random matrices, volume 20. Springer, 2010.
Jinho Baik, Gérard Ben Arous, and Sandrine Péché. Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices. The Annals of Probability, 143-11776,1 doi: 10. 10.1114000117790000000333
September 2005. ISSN 0091-1798, 2168-894X.
URL
Publisher:
Institute of Mathematical Statistics.
Gérard Ben Arous, Daniel Zhengyu Huang, and Jiaoyang Huang. Long Random Matrices and
Tensor Unfolding. 10Xiv:2110.10210 (cs, math, stat], October 2021. URth:htt://axxx
g 1/abs/21100 10210 arXiv: 2110.10210.
Florent Beorges-Georges and Raj Rao Nadakuditi. The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices. Advances in Mathematics, 227(1):494-522 May 2011. ISSN 0001-8708.
doi: 10.10066j....... www..a..............0. URL httpt::: wwww sciencedir f.ct.com.. sci ence wawncc//rriclle.
/000000001111 8708177881111 000100000000111000000000
Patrick Billingsley. Probability and Measure, Wiley Series in Probability and Statistics. John Wiley & Sons, Inc., 2012.
Louis Chen. An inequality for the multivariate normal distribution. Journal Multivariate
Analysis, 1262):30--11,, June 1982. ISSN 0047-259X. doi: 10.00166/0444-299XX229900222
URL https: wwwp www.wscceeeee wwtp::/wswinnneeeecc........ com/ htt.:///cee.ctceeeeeeee///ee/aaa
906227
Romain Couillet and Zhenyu Liao. Random Matrix Methods for Machine Learning. Cambridge
University Press, Cambridge, 2022. ISBN 978-1-00-9122220 doi: 10.1017797810091228.8
http::::/www..cc.prrr.rerrrrrrrr or machire htt.a//ee....eaaeeeeeoeaanaaaann
matrix methods
Persi Diaconis and David Freedman. A dozen de Finetti-style results in search of a theory. Annales
de I'I.H.P. Probabilités statistiques, 23(S)):397 423, 1987. ISSN 1778-7017. URL http:
www. nundam. org/item/AAHHPB 1987
23 S2_S2______2
10__22_330 397_09
José Henrique de M. Goulart, Romain Couillet, and Pierre Comon. A Random Matrix Perspective on Random Tensors. Journal of Machine Learning Research, 23(264): 2022. ISSN 1533-7928.
html
Christopher Hillar and Lek-Heng Lim. Most tensor problems are NP-hard, June 2013. URL L //arxiv.org//bs//333 1393 arXiv:0911.1399 [cs, math].
Joseph M Landsberg. Tensors: Geometry and applications. Representation Theory, 381(40)):3 2012.
Hugo Lebeau, Florent Chatelain. and Romain Couillet. A Random Matrix Approach to Low- Multilinear Rank Tensor Approximation, February 2024. URL http::/aaxiv..rr s/ 8/2402.00 63169 4rXiv:2402.03166 [cs, math, stat].
10

---

Published as a conference paper at ICLR 2024
Michel Ledoux. The Concentration of Measure Phenomenon. Number 89 in Mathematical Surveys and Monographs. American Mathematical Society, 2001.
Xinwang Liu, Miaomiao Li, Chang Tang, Jingyuan Xia, Jian Xiong. Li Liu, Marius Kloft, and En Zhu. Efficient and Effective Regularized Incomplete Multi-View Clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence, 43(8):2634-2466, August 2021. ISSN 1939-3539. doi: 10.1109/TPAMI 2tt.2020..224822.. URL https: /etess//eeeeeeprreeeeeeeee / http:/ddcument//01112 and Machine Intelligence.
Conference Name: IEEE Transactions on Pattern Analysis
Xinwang Liu, En Zhu, Jiyuan Liu, Timothy Hospedales, Yang Wang. and Meng Wang. Sim- pleMKKM: Simple Multiple Kernel K-Means. IEEE Transactions Pattern Analysis and Machine Intelligence, 45(4):5174-5186, April 2023. ISSN 1939-3539. doi: 10. 10.1109/TPAM
1.2022.3 198633. URL https: ieee eeeeepploee www.reeee....o ieee org wttp///cuee/////////ee/eeeeee/ee /985766 Conference Name: IEEE Transactions on Pattern Analysis and Machine Intelligence.
Anna Lytova and Leonid Pastur. Central limit theorem for linear eigenvalue statistics of random
matrices with independent entries. The Annals of Probability, 1778):177--1840, 2009. Publisher: Institute of Mathematical Statistics.
Matthias Löffler, Anderson Y. Zhang, and Harrison H. Zhou. Optimality of Spectral Clustering in the Gaussian Mixture Model. arXiv:191 1tt::1911.0055. 1.00538 [cs, math, stat), August 2020. URL http:
arXiv: 1911.00538.
Vladimir A. Marčenko and Leonid A. Pastur. Distribution of eigenvalues for some sets of random matrices. Mathematics of the OSSR-Sbornik, 144):557, 1967. Publisher: IOP Publishing.
Andrea Montanari and Emile Richard. A statistical model for tensor PCA, November 2014. URL http://arxix: org/ abs 11///111111 1076 arXiv:1411.1076 [cs, math, stat].
Feiping Nie, Jing Li, and Xuelong Li. Parameter-Be free auto-weighted multiple graph learning: framework for multiview clustering and semi-supervised classification. In Proceedings of the Twenty-Fifth International Joint Conference Artificial Intelligence, IJCAI' 16, pp. 1881-1887, New York, New York, USA, July 2016. AAAI Press. ISBN 978-1 1-57735-770-4.
Feiping Nie, Guohao Cai, and Xuelong Li. Multi- View Clustering and Semi-Supervised Classifica- tion with Adaptive Neighbours. Proceedings of the AAAI Conference on Artificial Intelligence, 31(1), February 2017a ISSN 2374-3468,
doi: 10. 10.1609/aaii w.l......ll............ 10909, URL https:
7/ojs.aaat org htt///ndxxx...//// http://////aat..eeee/e/eeaa///ae
Number: 1.
Feiping Nie, Jing Li, and Xuelong Li. Self-weighted multiview clustering with multiple graphs. In Proceedings of the 26th International Joint Conference on Artificial Intelligence. IJCAI'17 pp- 2564-2570, Melbourne, Australia, August 2017b. AAAI Press. ISBN 978-0-9992441--033.
Alexei Onatski, Marcelo J. Moreira, and Marc Hallin. Asymptotic power sphericity tests for
high-dimensional data. The Annals of Statistics, 41(3): June 2013. ISSN 0090-5364, 2168-8966. doi: 10. http://eeeeeooooooooooooooo//a/a
URL http:////oo/t/t///poo//oaaaaaaa.
Publisher: Institute Mathematical Statisties.
Evangelos E. Papalexakis, Nicholas D. Sidiropoulos, and Rasmus Bro. From k-means to higher-way co-clustering: Multilinear decomposition with sparse latent factors. IEEE Transactions on Signal Processing, (1(2):9935506, 2012.
Leonid Andreevich Pastur and Mariya Shcherbina. Eigenvalue Distribution of Large Random Matrices. Number 171 in Mathematical Surveys and Monographs. American Mathematical Soci- cty, 2011.
Xi Peng, Zhenyu Huang, Jiancheng Lv, Hongyuan Zhu, and Joey Tianyi Zhou. COMIC: Multi-view Clustering Without Parameter Selection. In Proceedings of the 36th International Conference Machine Learning, pp. 5092-5101. PMLR, May 2019. http://ppps//pppceedngnggse .ml. ISSN: 2640-3498.
press/v97/peng1 9a html

---

Published as a conference paper at ICLR 2024
Mohamed EI Amine Seddik, Maxime Guillaud, and Romain Couillet. When Random Tensors meet Random Matrices. 2XXi:2112.125444 [math, stat]. January 2022. URLattp://axxiv.oo
abs/ 2ttp/2112.c 12348
arXiv: 2112.12348.
Mohamed El Amine Seddik, Mastane Achab, Henrique Goulart, and Merouane Debbah. A Nested M Model for Noisy Multi-view Clustering, May 2023a. httpp::///arx
g abs 2305. 19992 arXiv:2305. 199922 [cs, stat].
Mohamed Amine Seddik, Malik Tiomoko, Alexis Decurninge, Maxim Panov, and Maxime Gauil- laud. Learning from low rank tensor data: A random tensor theory perspective. In Robin J. Evans and Ilya Shpitser (eds.), Proceedings of the Thirty-Ninth Conference on Uncertainty Artificial Intelligence, volume 216 of Proceedings of Machine Learning Research, pp. 1858-1867. PMLR, 31 Jul-04 Aug 2023b. URL hhml
mlr wwwpsprsssssi. wetp////////dddd222e
Charles M. Stein. Estimation of the Mean of a Multivariate Normal Distribution. The Annals of Statistics, 96)):13351151,, November 1981. ISSN 0090-5364, 2168-8966. doi: 10.1214/aos/11
statssssttsts http://wweeeeeeeeee/tttttttttttn
76345632, URL URL htg3:////../.teee////rr//e////or
ormal Mathematical Statistics.
full
Publisher: Institute of
Will Wei Sun, Botao Hao, and Lexin Li. Tensors in modern statistical learning. Wiley StatsRef:
Statistics Reference Online, pp. 1-25, 2014.
Terence Tao. Topics in random matrix theory, volume 132. American Mathematical Soc., 2012.
Jinxin Wang, Yuen-Man Pun, Xiaolu Wang, Peng Wang, and Anthony Man-Cho So. Projected tensor power method for hypergraph community recovery. Proceedings of the 40th annual International Conference on Machine Learning, pp. 129-136, 2023.
Xiaobo Wang. Xiaojie Guo, Zhen Lei, Changqing Zhang, and Stan Li. Cicluivity-CConiiteeee Regularized Multi-Vien Subspace Clustering. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 923-931, 2017. URL / thecvf com/ content evpr 2017 hhtml /Wang Exclusivity- cy Reqularized Multi-Vies CVPR 2017 paper.htm.
Xiaobo Wang. Zhen Lei, Xiaojie Guo, Changqing Zhang, Hailin Shi, and Stan Z. Li. Multi-view subspace clustering with intactness-aware similarity. Pattern Recognition, 88:50-63, April 2019.
ISSN 0031-3203. doi: 10.1016/j patcoo 2018.09.188000 00.9...99900.................... URL https:tt//// www. sciencedirrd
Jianlong Wu, Zhouchen Lin, and Hongbin Zha. Essential Tensor Learning for Multi-View View Spectral Clustering. IEEE Transactions on Image Processing, 28(12):5910-55 10-5922, December 2019, ISSN 1941-0042. doi: 10. 10.11099/1P.2019.229111 Processing.
Conference Name: IEEE Transactions on Image
Changqing Zhang, Qinghua Hu, Huazhu Fu, Pengfei Zhu, and Xiaochun Cao. Latent Multi- View Subspace Clustering. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 4279-4287, 2017. URL t httppr/..r/ttmm//aaa_aatateeeee
com/conten thecvf www.eeewww.oo.ooooooooooeeoeeooo
er. hr.m
Zheng Zhang, Li Liu, Fumin Shen, Heng Tao Shen, and Ling Shao. Binary Multi- View Clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence, 41(7):1774-1788 July 2019. ISSN 1939-3539. doi: 10. I 1109/TAAM.2011S 2817.33335.. Conference Name: IEBE Transactions on Pattern Analysis and Machine Intelligence.
12

---

Published as a conference paper at ICLR 2024
A UNFOLDING ALONG THE THIRD MODE
For the sake of completeness, we study in this section the recovery of x from the third unfolding of T. Following the model in equation 2
the expression of T(3) is
(3) Brzm.
+
W
(6)
VnT
where 1
M E 17
This unfolding has the peculiarity that the rank-one perturbation 3ymm' mixes signal (the vector 2) and noise (contained in M). Still, as for the previous unfoldings, the dominant left singular vector of
(3) remains a natural estimator of z and we study the asymptotic spectral properties of T33). Because of the long shape of ( (one dimension grows faster than the other), the spectrum of (3)T diverges in the same way that of T(2), Therefore, we must proceed to a similar rescaling. The following theorem states that, after proper rescaling, the distribution of eigenvalues of T3) approaches the semi-circle distribution.
Theorem 6 (Limiting Spectral Distribution). As n1. 122, fg - +00, the limiting spectral distribu- tion of the semi-circle distribution on 2
matrix Vauigggg
( (33) 1ytan Ing converges weakly to Vningng
usc(dr) V 11 x²
Proof. See Appendix
The ESD and LSD of (3)T are plotted the right panel of Figure The result of Theorem is not surprising: the "non-trivial" shape of the LSD of ((2) Theeremm 1 is due to the presence of a "signal-noise" By ZT (In, X 2) in the expression of (2) but, when 3r is set to Vaa
0, we have observed that the LSD of ((2) is simply a semi-circle. This is coherent with the case that interest us here: in T3), the "signal-noise" is restrained to the rank-one perturbation and therefore does not impact the LSD of (3)) which then semi-circle.
Because of the rank-one perturbation 3r2mm the spectrum of (3)) exhibits isolated cigenvalue which can be observed in the right panel of Figure [ Our next step is to character- ize the behavior of this spike eigenvalue and the correlation with z of its corresponding eigenvector. let us have a close look at the expression of (3)) to understand, with hand-waving arguments, what should be the non-trivial regime in this case.
Before introducing the formal result in Theorem 7
BT
T 5% [MM] TzT
2m (W)) + W(0)z
W(3)
VTT
RT
Starting from the right, the term ny (3) is already understood thanks to Theorem 6 and yields a semi-circle as limiting spectral distribution. The crossed-terms in the middle have zero mean and are expected to vanish. On the left, remains the rank-one term 2z weighted by &2 [M]; [ which is a random quantity because of the noise in M. However, the quantity || is expected rapidly concentrate around its mean 21122 + + Hence, guessing from the results on the previous Rar
Wer value denoted p. Indeed, this is precisely what found when this analysis rigorously carried out (see Appendix E meaning that B7 Onn,1/4 1/44 In other words, if 3T is a constant (3T @(1)), we are above the non-trivial regime and therefore should expect (asymptotically) exact recovery. This is because the strength of the signal "boosted" by [[M][ = ((r)).
unfoldings, we would need the quantity B3 ming + B3,) Vninang to converge to fixed positive
Remark. is defined as the limit of 187 (nin2 + +32 Vningng which is the same that of 87 n1ng yningng since BM (1)). However, we keep the 83, term in the definition of pr as it yields better predictions in simulations.
nx
13

---

Published as a conference paper at ICLR 2024
Theorem 7 (Spike Behavior), f = lim
Sror
+ +Bh) then the centered aadd-caledd
V Fight
matrix
WT T natmin 12 Ing has an isolated eigenvalue asymptotically located in e Vennans
Vainans
almost surely. Furthermore, in this case, the alignment between the corresponding eigenvector 2 and the Irue signal z converges to z² almost surely, i.e.,
almost surely.
12, +0000
@
Proof. See Appendix
Once the quantity @ is defined, we recognize in Theorem the same results as that of the spiked Wigner model Sernaych-Georger & Nadakuditi 2011).
Remark. In practice, work with large but finite tensors. Hence, it makes sense to say that 87 = (n or BT ((nn In fact, the characterization the "non-trivial" regime is only important here reveal the relevant quantities, i.e., pr and p. which will use in practice without worrying whether By is in the right regime or not.
B PROOF OF THEOREM 1
Denote Q(s) = (T - -sln)) the resolvent of (2)) defined for all E C sp (2)T.
B.1 COMPUTATIONS WITH STEIN'S LEMMA
Before delving into the analysis of Q, we will derive few useful results thanks to Stein's 's lemma (Lemma I]. They are gathered in the following Proposition 2
Proposition 2.
E W (())T
7133 E
Q
1
E + +1)
VIT
VTT
M (Iny
X x) (2)T
(Q+
1
(QT:Q+Q*) Q?)
Br M
MQ
n1
E
z MQ]
1
(nl
n2 1)Q
s
11ns
(Q Q9)
VnM
nT
[4Q3 + 2Q
Tr Q QT + +Q
nT NT TM
E [ - Q)Q (n. +
RT AM
E yxx
ZQ
Br
E (x T(2)T Q?)]
(10)
VnM
Br E ya MQ]
= E y (x
(
Q
(Q (QTQ -9)
(11)
nr
In order to prove these results, will need the following expressions for the derivatives of Q. Proposition 3.
aQ b
1
Qa,c
(2)) Q
Qc.b
T(2)TQ] Q
(12)
(2) c.d
VeT
db
d,a)
iQabb
Br
Qand (QT(2) (Ins ]z] bcc
+ QaD (QT(2) (In, x2) a.
(13)
87.ed
Vnm
14

---

Published as a conference paper at ICLR 2024
Proof. Since aQ
Q0 (T
Q.
aQu.b
n2
n2
jTa Tima + Tse jTyhh.a
Qa,e
Qno
aW.j.
oW..j
@W...R
1=1
Qai Thin +
Σ
Qa Qjib
V
A=1
c=l
aQab
Qaii
T Q
+0,s
[T(2) ②)
@W....
/1T
[1.b1,.
Likewise,
0Qob
112
125
772
(TTfaa Ty
Tyea 5
Qa,e
Qno
Uhedd h=1
Whedd
BT
Qo To,n. Qn,b +
Qu To
VnM
1==1
cml gm
0Qobb
BT
Qu,d
(T((2)
(In, R2)
Qub (QT(2) (In, Al) 0.c
Hhedd
VnM
b,c
Combining Stein's 's lemma (Lemma I and Proposition 3
prove each expression of Proposi-
tion 2
Proof of equation 7
ming na Σ
w
(2)
E
W (2) (2) i.k 1.
Qr,j
(2
(2)
+ (2) aQu
Σ
E
(2)
(2)
i.6
aw (2)
1=1
Bing ni
11733
E
[Q),
E
Qt,
(3)) q kj
+Qu
(2)) Q
/nT
VIT
E
[Q),,
1
E 2
Q + QT (
VIT
VIT
111
1
[Q]
E
(nn
+
VTT
/nT
where the last equality comes from (2) Q In, + sQ.
15

---

Published as a conference paper at ICLR 2024
Proof of equation g
E M (In, =) T T
= B M MMMQ 2. +
M (I [z)
w Qui
VuT
i,k
aQu.j
= B [
M (In, =2)
i.k
aw(2) 1,k
Br M
E
M (Imz Ø2)
Q (
Ring m2
M (In, xx
Q
1.k
M SLTMQQ
E
M (In, M z) (2) (Q (Q Q Q7)
nT
Proof of equation 9
E Z
MQ
E Mr.
7h
iQis
n1
E
+
MR.1
VTM
Arm
111
[
VTM
Br
a1
Ma.1 Q1 QT((2) (Ing 0 xz) juk
+ +is (T((2) (In. 8 =)] 1.
VBM
k=
71
BT
QMT (In, 8x) (2) Q + QTr MM (In, xx) T T(2) Q) in
E
TM
and, since MT (In, &2) (2))
W(2,,
with the relation ( Q = =Q + Inn we
var
have,
E
Z
MQ]
ni
E
E[Q.. i.j
E [
+Q+
+Q + n2
Vu
M
E
QW
Q+QT+ (2(2)
ig
a1
[[Q
E
(n12 + +1)
(Q Tr Q + Q²)]
Vnas
VTM
na nina
n2
aQ i.
(2(
8Q m.j
MMTT
E
(w())
((2)
Que.
(w
w.
Q
T(2)
OW
(2)
0.0
u,
u,v
12 ΣΣΣ
12g Mils
aQ T
(2
aQ ar.a
E
Q w,
Q
Q
(2)
(2 u2
(2)
(W(
(2)
16

---

Published as a conference paper at ICLR 2024
where we have used Stein's 's lemma (Lemma] 1 again. Hence,
E I MQ.
E [[])
E [(n2 +
+ (Q Tr T +
+9)
R113
E [ + Q
Tr
VnM
VnM
nT VnM
E
T2T
+
u
T
T Fe
1T V T
10
122
Qi
T(2) wiF
Owa
T(2) Q
+ +uw
T
1/T TM
122 7ITS
T Q
+ +ou
T(21TQQ
T Qwa
TIT AM
1.7
Rips
E
Qi Q
T(2)
Qu,,
T(2)T
Q
+ +u,,
T(2)
TUT TM
1,00
w=l
which bunches up into
E I MQ
n1 VnM
E
(12 + Q)Q+ + 88 nin
(Q + (QT:Q+Q9)
VnM
nr
1
E
Q (elllaale
QTQQ
11 TTV
E
11 V
T
"r
E Tr (QT Q) QTQQQ (T( Q)
WT n
and, using again the relation (2) Q = =Q + Igg we get,
E IZ MQ]
n1
E [[
E
(n2 + Q+
(s 11113
(QT+Q+Q*)
VnM
nr
E
Q s TrQ
nT / TM
1
E
3
Q
+ + + 0:0
nT TMas
17
E
[Q
E
(nz +1)Q+
n1n3
(QTQQ+Q3)
VnM
V
11
E
is (4Q + +2Q 2 + Q + QT
RTVRM
1
E [n2 + 4) Q + (mg + 2) QTQQ]
nT TM
17

---

Published as a conference paper at ICLR 2024
Proof of equation 10
yæ
zQ)
IE
[y Ta. Zz. Quo
3.
k=1
1=1
31
n2
aQu.
E8
y
i.
O
1=
BT
n2
Ji,
Q1.1 QT((2) (Ins 8z)] 1,k
+ Qus (QT(2) (Ins x) ((n)
n
BT
(xx
T(2)T
(QQQQ= Q3]
VBM
Proof of equation
Br yar
MQ]
1r y (xx (x) (In, X x) MQ]
E
(x: (x)
T(2)
W(2)
Q
v
and,
11 m2 Σ
y (x: 8 2) W
(x
y
w
Qu.
1.8
k=1
Bing n2
aQ
E
y (x X 2)
1,k
1,k
y (x x2)
Q1.1 TT))TT]
+ +Qis
T(2) Q kd 1
nT
k.j
(x T (QT:
VnT
B.2 DETERMINISTIC EQUIVALENT
Since Q Q-QQ= = Ings we have T sQ Inz- Hence, using equation 3 and taking the expectation.
E M (In, E 22) T( +
( Q] sE sE( Ing
n
and, injecting equation 7 this yields
Br
M
(Ing
R 2)
(2) q]
1 E (n2 + Q + ( sIE [Q] Ing.
E
[Q]
11
nr
Here, we must be careful that, due to the no ning rectangular shape of (2), the spectrum of (2)T diverges in the limit n1, 72,
+oo. In order to bypass this obstacle, we shall
perform change of variable (s, Q) a (5, Q) which will become clearer after rearranging the terms:
Tr QQQq +
11/
E
112 n17g
E [[]] + In
nr
n22
nr
= 3r M (In, M x²) (1)) q] 1 E [Q + sQ
18

---

Published as a conference paper at ICLR 2024
Let nTS (n2 n1733)
11 (
(n2 n1n3)
Lnz
and Q(3) =
5l
With
n2223
VRingn3
this rescaling, note that we have Q(s)
(5).. and the previous equation becomes
NT
3
WT
+
nT
n2
Tr Q Q
+ 8 8+
2nz
Q +
Ina
Th 12213
103
Y12
1//
Th 12212
BTAT
M
M z)
(2))
Q
3
12
12
Q²
/2222
and we no longer have any diverging terms. Keeping only the dominant terms, we can now proceed matrix-equivalent formula
Tr Q Q +Q+++ Lo2 712
BTUT M (In, x2) T ( Q Vni22nn
Remark. This previous step is justified by the use of standard concentration arguments such as Poincaré-Nash inequality (Chen) 1982, Ledoux 200T) and Borel-Cantelli lemma (Billingsley 2012), following, e.g., the lines Couillet & Liao 2022, $2.2.2). This reasoning is applied in what follows whenever we move from an equality with expectations to an equality with matrix equiva- lents.
Applying the same rescaling to equation 8
yields
STUT M (In, x) (2)T Q /1122
BITT M T MQQ.
112222
Remark. We see, here, that we must chose Br = Onn (14 order to place ourselves in the non-
trivial regime where both the noise and the signal are @(1). This is different from the estimation of y with rank-one approximation of T, where 3r could be kept ((1) (Seddik et al. 2023a (but at the cost of an NP-hard computation (Hillar & Lim 2013)).
Mingnng and m lim Tr Q the Stieltjes transform of the (2))
With this in mind, let denote pr lim
na
limiting spectral distribution of the centered-and-scalee matrix Vaingng We have,
Vagngng n2*
m
sQ + In, - P
In order to handle the term M MQ. observe that
E
M
MQ
PM y JM
E Z
TQQ
v n
and, after rescaling, the only non-vanishing terms in equation Dlyield
z
Th
122
122
Tr
Q
122
Tr Q
Q
VTM
71
122
TM
11g
Moreover, from equation 10
have
By BrBuTTT
Tr Q
Buya MỘ
BLyyT Q
(o 8 T) (22)
Q
n. /ningng
n2
but, from equation
we also know that
yæ MÔ
(x B
(2) Q
We say that two (sequences of) matrices A, B E gaxa are equivalent, and we write A + B, if, for all M E _ X and u, _8_ of unit norms (respectively, operator and Euclidean).
Tr (AM(A-BI)
2s. 0. u1 (A-B) B)
u.s. O, AP B
a.s. 0.
19

---

Published as a conference paper at ICLR 2024
Hence,
1
BM + P1Barrn TrQ
(x
T Q Rryy" Q
BT
TM Mingng ne
and
33 TrQ
Buy "M + Byg
TM SMyynugng n2
yy Q.
3M BrBuuTTA T+Q Vhingng 92
Therefore, we have the following matrix equivalent for M MQ,
M T
MQ
yy
Q
Tr
Q
+
71
122
1+
Tr Q
+
Tr Q
Q
TM
Ultimately, define Q the deterministic equivalent of Q such that,
@ + SQ Inz
Pr
yy T
C1
(1 + 5m + mm(
Lnz
m
03
C3
or, equivalently,
pT (3)
+
1 + 3
PTC2
m())
PT (c2 c1)
Q In2
PT
yy
Q
I 1-c3 C3
1-c3)
C3
1
Cr
(
1-03
(14)
B.3 LIMITING SPECTRAL. DISTRIBUTION
According to the previous deterministic equivalent, the Stieltjes transform of the limiting spectral distribution ar (2))
ma In, is solution to Vn1n2n
Vingan
Cr
m
(3) + 1 3 1 03
m m3(+) + 8 Pr (c2 (1) Pr )
m(8) +1 0
C3
1- C3
pro mm()) + (m² + 3)m(3) + 1) Pr m(3) 0.
(15)
1-c3
C PROOF OF THEOREM 2
C. ISOLATED EIGENVALUE
The asymptotic position & of the isolated eigenvalue (when it exists) is a singular point of Q. From equation 14 it is therefore solution to
pTC2 TE) + 1 - C3
PTT2
PTC2 1- C3
mm(E)
+ PT (C2 -c1)
Pr
1-C3 C3 1 1 1-cy m((E)
11 pTC2 ml{))
pTL2
(m) ( +1) -m(E) { PTCI
1-c3
Pp
C3
C3
20

---

Published as a conference paper at ICLR 2024
Yet, ms)) + (37 + sm + +1) f-cg mm3) (from equation 15 Thus,
mm(E) - PICI
+ pr m({) (m(E) + +5) -T
1- 03
1- C3
PTc2 m(E)
(m(()) +5)
= -Pr.3tM prcl
+
1
1
pme
from equation 13 agaain
%
mit)
m(E)
pr I-c3
+ 53
Injecting this relation into equation 15 yields
PT
C1
Bi
02
(16)
C3
C3
PT
c T-rs
+ 8311
C.2 EIGENVECTOR ALIGNMENT
The eigendecomposition of (() is given by Ei= u.u. eigenvector pairs of T(2) (ma+ni Ma) have
where (Ae, us) are the eigenvalue-
Hence, thanks to Cauchy's 's integral formula, we
2i / y (Q(())) dā
1
y
where 7 is a positively-oriented complex contour circling around the isolated eigenvalue only. The asymptotic value of |y y12 can then be computed with the deterministic equivalent defined in equation 14
$ (5)y d3.
5 (= s= 2im J
Using residue calculus, we shall compute,
3
Ç = lim R proz (8) + 1-cy
proz 1-c3
m(s) + pr(e2-01)
Pr 14 1- (i())
1-o3
The limit can be expressed using L ''ópital's rule,
prca (3) + (1+ f m(() + 3 pr(ez-11)
pr 32
I-c3
P7 m)(3) T-r3
PT PTC2 e0
Pr m{{) + 1 +
PrC2
vi + Prcz m(()) +
2
+
C3
[ + proz m({))
C3
We already know that m({)
Let us then differentiate equation 15
+pr 1-cq
3 PrC2 m8( + 2 1
PTC2
m(() Pr (02 - 61)
m m'())
1
1-
PTC2 (²) + mm(3) = 0.
+ 1 -
Since
prozm m² (8) + (1 5fr0 mi(3)
proz
+3
(c2- 1-08
(3) + 1 = 0, we have,
PT m² m8()) + 1 1 PTC2
1
m m(()) + PT m m mm
m(3)
C3
C3
(()
1 1-c3 C3
2
pT
m(3)
PTC2
1
m 1- C3
PTC2
m 0.
1 C3
C3
m (3)
21

---

Published as a conference paper at ICLR 2024
From this last equality, that
PT 3/
prcz T-r
PT (E) m m'(E))
==
m ml(())
m2(()
(1 m
Moreover,
+
PrCz mE{)
ml (
1-cy
2 p mm({)) +
1-ra (E)
pr
20 tpr
1-cg
2 UT 1-
1-
+1+ 0
prez + prr
+pr
1-cs
pr B3
3
cr
Pr.
Pr
Prr + 1-
+ prr
1-08
PrB3s
(G)
+ +( prcz + B/g1 3
proz
pré
+ pr.
( (inc + PT PTB3r))
Hence,
Pr B/r
1
prez
pret 1-n3
+ ph. )
1-08 + prr 2 +
pree
prez 1-08
+ pr.
pr
1-08
prcz 1-c3
+ pT
pr
PTC2
1-ey
+ PT
pr 1-c3
+ prr
3
pr
82
C3
pT
1-03
+ 1
33
)
Ç -
+
C2
Ci
+
Bhg
(17)
83,
B&s
1 C3
1 C3
I-c3
PT
1-c3
D SKETCH OF PROOF OF THEOREM 5
can be decomposed as og + where ÿ. is unit norm vector orthogonal to ÿ and a + = 1. From Theorem we know that a² + < (and thus 32 + 1 () almost surely as n1, 122, 7hg + +o0.
From the rotational invariance of the model, D1 is uniformly distributed on the unit sphere in the subspace orthogonal to ÿ. Hence, any finite collection entries is asymptotically Gaussian (Diaconis & Freedman 1987)
E PROOF OF THEOREM 6
Let Q(s) ((3) slng) defined for all \ sp T())
E. PRELIMINARY RESULTS
Let us derive a few useful results for the upcoming analysis.
Lemma 2.
8Qnb (3(3) c.d
Qu,c
+
Qa.b
(
Vnr
d.b
d.a
22

---

Published as a conference paper at ICLR 2024
Proof. Since aQ=
QQ
(T T
Q.
iQ.b
T
Ow(3)
aw(3)
cdd
odd
na, Σ
TT (3)
(3)
Qa,e
(3)
((3)
9.
Qgi
awla) c.d
9.5
aw(3)
e.fg==
c,d
Qae ( S 9.5
+ (. Qg.b
ViT
e.f.g=1
T(3) Q.
+ Qopb T Q.
Q0
aw(3)
nT
d,b
d,a)
c,d
Proposition 4.
E
(3
Q]
12 E
[Q]
E
(na + +1) (Q QQQQQ
(18)
/nT
VTr
(Q (QT+ =B | zz Q
E zm
T
Q
By
(19)
nt
Proof. We prove these two results with Stein's 's lemma (Lemma I and Lemma 2
ning,ng
E
w
33
Σ
E
Q
LA
K1=1
ninginn Σ
OT(3)
(3)
aQu Ow(3) (3) i.k.
E
l,k
Q
+
(3)
(w
(3)
1.k
k1=1
Σ
E
Qui
k,1=1
1
Ringi
E
(((3) ik
Q1,
T
+ Qui
[TIITT] { k.))
/nr
kj
A,1=1
n1112
[Qla.
QT (3 (3T Q Q Q)
Vnr
TuT
n112
E
[ns + 1)Q + QQ Q
VnT
where the last equality comes from (3) (3)
Q Ing +sQ.
E zm
TT(3)
Q
M 2 zz 3r
Σ
E
w/ 1,E
(3)
Qr
i.j
iij
NTT
k,1=1
Ai B2
aQ L
3rE
||M|
zz 2
TQ]
T
+
E
ziTl
PT
Ow(3)
k1==1
|
1.j
22
E
2
Qui
(3))
Q
+
+
(a)T
1=1=1
E
zm. TT3)
Q
=
||M
zz 2
T
E
xm
(T/T (Q (QTQQ+ + (QT+Q+
b.
23

---

Published as a conference paper at ICLR 2024
E.2 A FIRST MATRIX EQUIVALENT
Since Q Inn.
3rzm T
Q+
w T Q =Q Ing
Vnr
and, from equation 18
we have
1 2m
(3))
Q
E [Q]
E
(n3 + 1) ++1+)++++ ( QQTQQ)
sl [Q]
In
nr
10
Let us rearrange the terms
Tr T
n3
Q
113
117
E Ing 3r
2m
(3)T
E Q =Q²
nT
n2y
T/
nr
in order to see that need to following rescaling to counteract the divergence of the spectrum of (3)
(3)
ITS (ng + n1712)
117 TTTT3TTT (na m1n2) Ing 8I Q(5)=
Vn1n2n3
Hence, our equation becomes,
1T
3
RT
+
n2 E
Tr Q Q
+
8+
2nz
E Q
+ Ins
11 R2ng
12
133
1/T
ngg
n n2n23
STAT
E zm T TT(3)TQ
Q
1
E
Q +
n2 + 121122
Q²
(20)
M2
M1
v /nnnnn
Moreover, equation
19 becomes,
E 2m (3)T
(QI+Q+02)) = 37 |IM] zz
T
Q
(21)
Therefore, denoting m3) lim
To Q(a) ns
the Stieltjes transform of the limiting spectral distribution
of Vningns
(3)T nat- VRingng
I the combination of equation 20 and equation 21 yield the
following matrix equivalent,
BIT
m(3) + 3Q
Ing
M x2 QQ.
(22)
T2172
At this point, we are still carrying the random term || in the RHS. This quantity is expected to concentrate rapidly around its mean Bh + 2122. However, because M and Q are not independent, the RHS must be studied carefully.
E.3 ANALYSIS OF THE RHS
Lemma 3.
iQ..b oZ.d
Br
(1Q=), T(3)T
+ +1Q=|p (3)T
VnM
le.0,,8
[c.d],0)
Proof. Since 8Q = QQ (T()) Q.
8Qu.
(TTige FZed
0T
Σ
Que
T + Ti.g.e OZ.a
Qn.b
0Z,
c.f-g.b=1
Br
Que (Zte Teddt + Te.d,eth) Qu.b
VnM
e.h=l
8Q..b
BT
(12=),
T(3)TQ]
+ +Q21, (3() [e.d].b
JZ,dd
VTM
[c,).a)
24

---

Published as a conference paper at ICLR 2024
E
M 2 o = Σ
11.22
E
(BuEui +
1
Zuy
2
Q
VnM
d,==1
Zuu
+28M 2B Zu Q
B
QQ] +
E
+
v
VTM
VnM
u,v=1
E
M
Q
(B
E
[
+
E
Zuu T
+ 22MM )
aQ TZu,e
TMM
M,0=1
where we have used Stein's 's lemma (Lemma I to derive the last equality. Hence, using Lemma 3 becomes
[
-
(Ahr
n1722
))
+
T
is
3T
B1,02
E
Zu,e
223
(1ox),
[T Q (u,0]a
+ +[==1, [T())TQ) (ow))s)
M1M
AM
3r
Σ
E
2mM
Zu,e
[Qx]
T
+ +1Q=1,
T Q (u,t)it/
n
VnM
lu,elu
u,==l
-
3T E
Qum
T
TT(TTQ Q + (
(T())T Q)
nM
3T
[Q=]; [(i)T Q] (u.els
+ +Q21, T Q |
E Zu,"
1&M T
0,20=
and, since 37zm
(3)
(33) and T3) Q Ing + sQ. we have,
/ue
Brzm (3)) Q= Ing + +QQ
(T3) Q
Thus, our expression turns into
E
[M]
B3
11912
nas
iJ
E
[Q
+
=Q2]
+ NM VnT
2
E
Q (Q((3)))())
TT
Q b.j
i.j
nM
BT
E Zu,e
[Q=]
T33)T Q
+ 1Q=1, (T3)T Q
nM
T
[u,ol,s
[u,v),i
4
Gr
E
sQ
A + ATI,,
+
A2 + A
nM
bg
nM /MT
NMM TuM
with
A = T
[A2la
Σ
E
Zu, Q=1;
(3))
0,0=1
25

---

Published as a conference paper at ICLR 2024
Let us develop A with Stein's lemma (Lemma w
Bg.Rs
aQna
aT c.b
aQ
[Aiks]
Σ
E
T
Qns + Qi,
Qus Qi
T(3)
Ow
(3)
ow
(3)
OW (3)
a.b,==1
o.b
a.b
0.6.
n1 E [Q']
bi
nnT
ng Rg ng.
Σ
E
Qiaa
T
+ Qa,a
T
Q
T
Pay
nT
b,
bi
a,0,c=1
1
E
Q
T(3))
c,b
Qc,a
T
+ +0at
T(3)
(.c))
V
v
a,b,c=
n1
E
[Q"]s.
ji.j
1
E
(2Q2
QQ
T
Q
T
T
VnT
VnT
[Atkg]
1172
E [Q"] (..
1
E
VIT
V
since (3) Q Ins s.
Next, we develop A2 with Stein's lemma (Lemma I on Z.
aQia (3) IZn,
OT
(3)
aQ
[A2lis
E
b,ju,u Qo.j + Qi,a Nmn
6.(u.oo
Qui + Qi T
u. 07
a,b=1
[Qzz
VTM
3T
[Q=]
T33)T
=aT (33)
(.(u,))
Quii
VTM
a.
a,b=1
Br
Σ
E
[Qz]a
(3)T
Fa
(3))
Qoai
VIM
[u,u],
u,v=l
a,bml
3T
Σ
Ng.
Σ
E
Qia za (3)
[Q=),
T3))T Q
VTM
b.(u,e]
0,2== a,b=1
Br
ni.
Σ
E
Qi za T(
b.(u,))
[=1,
T33)
V u a,b=1
Brmine
E
[Qzz
BT
E [Qzz"
Q [x]]=] Q)
T
((3)
VnM
VTM
BT
Q2xT
(QT(3)
Q)]
E
VnM
frmine E [Qzz T Q]
BI _ E. [(n3
[A2)a]
+ 2) 22 Q= Q]
VnM
i.j
VnM
BT
sE [QzzT
2Q²) + +[ [q=] Q3]
Vnn
since, again, (3) TQ= Ing + sQ.
26

---

Published as a conference paper at ICLR 2024
Eventually, we have,
M p Q
Rh +
12
E [
4
E Q + +Q*
n.M
RM
4n n2 E [Q]]
E
+ 2) Q (0000000000000000000000000000000
2.3% 11
2
Q22 Q
[(n3 + 2) Qzz
Q Q= Q
2
2
MM
207
20 2M
sE [Qzz
QQ
Tr
Q +
Q2] Q"]
sE
[Qzz T Q² + Q² 2² Q
M
E
M Q
12122
+ 8h,
4
E
[Q]
4
s
n3
11
2
E [Q]]
T1M
T
NM
nT
4ng
TrQ
8
8ns
Tr Q
E
sE [
sI
TM
113
RM
113
2
E
[(ng
711222 + 2) Qzz T + [====] Q]
2
Tr
n2 Qzz Q
+ +[ [=TQ2z] Q2 + Q=z Q² + Q²2z Tz QQ
To
n2
After rescaling, this becomes,
nT
E
|M
2
Q]
V /2
11122
4
nT
E
Q
4
(
(nz + 1)
nU
E
Q
MM
n
n
Vnin2Ma
T2 12
4nr
E
Q
TrQ
8NT
n1 + 117
E
3
+
Tr Q
Rad Ta
n3
nM
13/
n3
2
E
(113 - 7172 + 2) Q=z 'Q
+
T
Q Q
11
TM
2
2.
8 n33 + 11122
I
T23 Q=z
TQ
Tr Q
2 12
113
2,3, n2
$
n1 + n1
E
Q2 Q²
Qzz Q² +
22
Q
n 7222
82
/TT
+
M
E
θ
IF Q22
/nT
nT /
Tr
Q
Tr Q
E
θ
E
E
7
113
n
V
TTT
1T
/
1T
713
32
E
Q2z
Q
E
Q
1T
n
Tr
+
Qzz
Q
1T /IT
113
BC
E
Q
2 +
T2
+
222z
TQ
n T
Hence, as long 37 = =(
3/4
we have
M Q
+
32
72
PTT nr
Q
T&M
73
T2222
27

---

Published as a conference paper at ICLR 2024
E.4
DETERMINISTIC EQUIVALENT
Coming back to equation 22 we are now allowed to write,
BAUT
m $ Q + sQ + Ing
nT
zz Q
nM
M1 n3
Hence, in order to prevent the RHS from either vanishing or exploding, we see that 3T must be O(T this case, Let lim S7
25.222
RMM
ng
Vagugng
Then, we can define Q, the deterministic equivalent of Q such that,
( Q + 3Q + Ing = ezzzz Q Remark. In fact, with the assumption AM = (1), 33
(23)
nr min2 ns /ningns
137 mT NM
n1
V
ns
so we could have kept only this dominant term. However, for finite horizon considerations (as it is the case in practice), adding the θ with the dominant term only, consider "worst-case scenario" BM 0.
term leads to slightly more precise predictions. Indeed,
Var
E.5 LIMITING SPECTRAL DISTRIBUTION
According to the previous deterministic equivalent, the Stieltjes transform of the limiting spectral distribution aT (3) Ba Ing is solution to
m (8) + ()(()) 8) + 1==0 0,
(24)
i.e., it the standard semi-circle law.
PROOF OF THEOREM
F.1 ISOLATED EIGENVALUE
The asympiotic position & of the isolated eigenvalue (when it exists) is a singular point of Q. From equation 23 it is therefore solution
m({) + E =
Following equation 24 { -m(() (E) thus, mm(E) -1 Injecting this in equation 24 yields
E = e -
(25)
F.2 EIGENVECTOR ALIGNMENT
Following Cauchy's integral formula,
2
x (3))) dš
2:t
where ÿ is a positively-oriente complex contour circling around the isolated eigenvalue only.
Hence, using the previously found deterministic equivalent Q we can compute the asymptotic value < of 2/²
< = 2iσ
z [Q())z d8.
This reduces to residue calculus,
< = lim { 5 [m(3) + 3 - á-f
(m(3) 3) 2la=t
m +
28

---

Published as a conference paper at ICLR 2024
Differentiating equation 24 we have,
m
2n (E)(()) + m()) + (m) =0 = mi((E)
2m( + E
- m5)
Ø 2
m'(E)
0
Hence, we conclude,
( 1
(26)
29


Reviews:
[{"review_id": "sdz1x1BbLf", "reviewer": "Reviewer_yQ9E", "summary": "This paper quantifies the performance gap between the nested matrix-tensor model and its unfolding variant in multi-view clustering.   Specifically, the authors theoretically analyze the alignment level between the leading singular vector learned by the matrix-tensor model and the true signals. Their theoretical results give some interesting insights into tensor-based multi-view clustering. Finally, these results are verified by numerical experiments.", "questions": "See the previous box.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. This paper gives a vital result, i.e., under the nested matrix-tensor model, the analysis of the unfolding method shows the theoretical superiority of the original tensor-based method in terms of accuracy.\n2. The proposed theoretical results are interesting and can advance the understanding of tensor data processing in multi-view clustering.", "weaknesses": "1. The nested matrix-tensor model can only handle the multi-view clustering task in which the dimensionality of each view is the same. In real-world multi-view datasets, the dimensionality of each view is usually different. I wonder how this issue can be addressed in the nested matrix-tensor model.\n2. In the summaries of the main contributions of Page 2, the authors can point out the corresponding theorems at the end of each contribution.\n3. There is an error in the definition of $T^{(1)}$. Its element should be $T^{(1)}_{i,n_3 (j-1) +k }$.\n4. What is the definition of \"SNR\"?\n5. The significance of all variables in Eq. (2) should be specified for readability.\n6. What is the definition of the inner product of two tensors?\n7. All theorems lack necessary remarks. It critically hurts the reader's understanding of the proposed results. For example, in Theorem 2, $\\zeta$ reflects the alignment level between $\\hat{y}$ and $y$. However, $\\zeta$ is equal to a complex formula. I can't understand how it can be close to $1$.\n8. The detailed deduction of the last equation on Page 17 should be presented. It seems not apparent.\n9. Cauchy's integral formula on Page 20 is not in a standard form. The authors should give the relevant references.\n10. Some important multi-view clustering literature [1], [2] should be added.\n[1] Efficient and Effective Incomplete Multi-view Clustering.TPAMI, 2021.\n[2] SimpleMKKM: Simple Multiple Kernel K-means. TPAMI, 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XnHO0hqono", "reviewer": "Reviewer_xYze", "summary": "The paper addresses the *nested matrix tensor model* which is the simplest statistical model for the multi-view clustering problem. The multi-view clustering problem assumes that several *views* of a set of clustered points are available. Each view being a function of the input points. Here we consider that a view is defined as a rescaled version of the input signal, up to additive independent noise. \nThe paper studies a solution of the simplified \"nested matrix tensor\" problem, relying on a tensor unfolding schema. Authors provide theoretical results for the proposed solution. The theoretical results borrow tools from random matrix and random tensor theory. REsults allow to identify regimes where the approach works or fails.", "questions": "When authors mention \"impossible\" or \"possible\" recovery, it is unclear to me whether they mean \"information theoretically (im)possible\" or \"computationally (im)possible\". Even though in the matrix case these two match, in random tensor problems there are different asymptotics for the two. It seems to me that authors are not dealing with info theoretical phase transitions but with numerical schemas: \"assume we do unfolding and apply the algorithm proposed, we find a solution in this regime\". Is this correct? \n\nIn a regime where SNR is high, authors mention that one can get good results with a simple tensor power iteration (no unfolding). What if we have a good enough guess for the initialization vector of the tensor power iteration? Are these two cases of any practical interest? \n\n\nWhile authors mention that coefficients c_i are positive and \"This models the fact that, in practice, we deal with large tensors whose dimensions have comparable sizes\", I wonder if it could help the paper to also highlight the (easier) cases where n_3 --> infty while others are constant etc. and provide intuitions on what each of these easier cases mean (many views of the problem makes it easy to identify signal). These simple cases may appear trivial from the viewpoint of the developed theory here, but some may be insightful / useful in practice to know about. \n\nFrom the plot it appears that the main bottleneck is the matrix SNR rho_M. Do we think that in practice (for the multiview clustering problem) it is relevant to consider the tensor formalism to get the bit of signal left in the tensor and get it back through unfolding?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The papers focus is on an interesting theoretical model for a challenging and relevant application. Authors do a good job motivating the work and stating it both in comparison with theoretical related work and applied related work. The contribution of the paper is insightful and results are non-trivial. Authors have done a good job presenting the main results and providing numerical simulations and graphics that make the findings more accessible.", "weaknesses": "Gaps between info-theoretical and computational results are non-trivial in tensor problems and I may have missed it, but I could not see it discussed in this paper (see question).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kHCSOb59Iy", "reviewer": "Reviewer_9jwW", "summary": "This paper studies the problem of estimating a planted signal that is hidden in a nested matrix-tensor model, which generalizes the classical spiked rank-one tensor model. The paper compares the performance of two approaches: tensor-based and matrix-based. The tensor-based approach exploits the tensor structure of the data, while the matrix-based approach uses the unfolding of the tensor. The paper derives the exact algorithmic threshold of the matrix-based approach, and shows that it undergoes a BBP-type transition behavior. The paper also compares and quantifies the performance gap between the two approaches.", "questions": "1. Are the theoretical results of this paper also applicable to tensors with orders greater than 3?\n\n2. How to choose the parameters $(p, n, m)$ in Figure 3?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper compares the performance of tensor-based and matrix-based approaches, providing insights into the advantages of tensor-based methods for structured tensor data.\n\n2. This paper provides a rigorous theoretical analysis of the proposed framework.\n\n3. The paper quantifies the performance gap between these two approaches and derives the precise algorithmic threshold of the matrix-based approach.", "weaknesses": "1. The paper does not provide a detailed comparison with other state-of-the-art methods for multi-view clustering.\n\n2. The paper does not include experimental results on real-world datasets to validate its theoretical findings.\n\n3. It is best to provide more detailed experiments to compare the tensor-based method and matrix-based method.\n\n4. It is better to provide a citation for “BBP-type”.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JeP4PdXp9k", "reviewer": "Reviewer_hX5q", "summary": "This paper focuses on theoretical analysis for Multiview clustering. Specifically, the authors quantify the performance gap between the tensor-based approach and the unfolding approaches.", "questions": "see weakness", "limitations": "", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1.\tThe motivation of this paper is clear.\n2.\tProviding theoretical analysis for tensor-based Multiview clustering is important.\n3.\tThe proofs seem strict.", "weaknesses": "1.\tThere are few tensor-based Multiview clustering methods mentioned, thus, it is difficult to understand which kinds of tensor-based methods are suitable for these theoretical results.\n\n2.\tThe experimental results are not sufficient. For example, in practice, there are many tensor-based and matrix or vector-based Multiview clustering methods, so what about the performance gaps between them and is the theoretical results applicable for them?\n\n3.\tThe potential inspiration for researchers of the work is not clear.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2enXQfNrcP", "reviewer": "Reviewer_sHnH", "summary": "The authors quantify the gap between the best rank-one approximation of a tensor and that of its unfolding matrix.", "questions": "1, It is important to introduce and define all symbols used in the paper when they are first mentioned. So it is better to define symbol $\\otimes$ in Nested Matrix-Tensor Model.", "limitations": "", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The theoretical analysis of the paper is solid and the results is interesting.", "weaknesses": "The assumption that both of Z and W follow the Gaussian distribution with zero mean and unit variance, is too strong. As $X=(\\boldsymbol{\\mu}\\boldsymbol{h}^T)\\otimes\\boldsymbol{\\mu} + \\boldsymbol{Z}\\otimes\\boldsymbol{\\mu}+\\boldsymbol{W}$, thus the variance of Z and W affect the performance of the rank-one approximation in a different manner. But the authors do not discuss the part and simply assume both Z and W follow the normal distribution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)