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

Thank you for your relevant feedback, which has helped us improve the clarity of the paper.

Weaknesses The assumption that $\mathbf{Z}$ and $\mathbf{W}$ are Gaussian is, in fact, not restrictive in our case, but greatly simplifies the presentation. In order to extend our results to non-Gaussian noise, see the work of Anna Lytova and Leonid Pastur, "Central limit theorem for linear eigenvalue statistics of random matrices with independent entries". Their Corollary 3.1 can be viewed as a generalized Stein's lemma (Lemma 1 in our paper) for non-Gaussian distributions. All Gaussian expectations of our proofs can then be expressed as their non-Gaussian form plus a residual term controlled by the moments of the distribution. A reference to this "interpolation trick" has been added to the presentation of the model at the beginning of Section 3.

Questions We have added a clarification on the symbol $\otimes$ after its first use in the introduction.

Thank you so much for your valuable feedback. We have carefully examined your remarks and hope that our answers will improve the quality of our paper.

Weaknesses

1. It is important to note that the goal of our work is not to propose a new algorithmic method to solve our estimation problem, but rather to compare from a theoretical standpoint the achievable performances between tensor-based and matrix-based approaches. In this context, experimental comparisons between different algorithms are out of our scope.
2. Our main goal is to give rigorous theoretical results quantifying the performance gap between tensor-based and matrix-based approaches for multi-view clustering. However, in all this generality, such a task is quite difficult, and therefore our work considers a simplified model (the particular choice of view function $f_k$) as a first step towards more general rigorous theoretical results. As a result of this simplification, we lack relevant real-world data for the moment. Nevertheless, our theoretical findings give a precise understanding of tensor- and matrix-based approaches, supported by rigorous mathematical proofs, which per se do not need validation (the experimental results are only meant to illustrate them).
3. Please note that the main goal is to provide a theoretical analysis of the performance gap, with the numerical experiments serving only as illustrations of our findings. In this regard, we believe that the current results already cover the main aspects of our analysis. Could you please point out which additional comparison would be useful?
4. A reference for "BBP-type" has been added to the abstract (Baik et al., 2005, "Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices").

Questions

1. In principle, extensions of the model to higher-order cases, such as one in which the signal is given by $\mathbf{M} \otimes \mathbf{z}_1 \otimes \mathbf{z}_2$, can be handled with the same tools and pose no conceptual difficulty. In particular, a matrix-base spectral (i.e., unfolding) method can be similarly employed (see, e.g., Gérard Ben Arous, Daniel Zhengyu Huang, and Jiaoyang Huang, "Long Random Matrices and Tensor Unfolding"). However, we are unaware of any machine learning problem which might motivate such an extension, and for that reason we did not discuss it in the manuscript.
2. In practice, these parameters are not chosen, they depend on the data: there are $n$ points of dimension $p$ split into two clusters that are seen from $m$ different views. In the particular setting of Figure 3, we have chosen realistic values of $p$, $n$, and $m$ to perform the simulations.

Thank you for your profitable feedback. We hope that our answers will adequately address your comments.

1. As they are, our theoretical results specifically concern the estimation of the clusters in our nested model via either a tensor-based or a matrix-based spectral approach, that is, either best rank-1 tensor or best rank-1 matrix approximation. As stated in the Introduction, the goal is to rigorously study performance gaps between tensor-based approaches and matrix-based ones in a setting where the sought signal has tensor structure, and thus the latter method can be seen as a relaxation. This study is one example of this general idea, but more work is needed to rigorously extend its conclusions beyond the considered model.
2. Please note that our main goal is to give rigorous theoretical results quantifying the performance gap between tensor-based and matrix-based approaches in a specific setting, with a simplified model. Hence, the numerical results are only meant to illustrate our theoretical findings, showing their implications in practice. However, our paper does not purport to explain the performance gap between any tensor-based and any matrix-based multi-view clustering methods. Other comparisons need further study, and are out of the scope of this paper. We have outlined this point in our introduction.
3. The main message the paper is meant to convey is that, in the case of the nested matrix-tensor model, which serves a simplified model of multi-view clustering, we can rigorously prove that there is a significant performance gap between tensor-based and matrix-based approaches, confirming intuition and previous empirical evidence. We hope this will inspire similar works in this direction, which precisely elucidate the gain brought by taking into account the tensor structure of a given model's signal.

We would like to sincerely thank you for your valuable feedback. We hope that our answers will fully address your questions.

1. The Reviewer is right, thank you for raising this point. Accordingly, we have added a remark in Section 3.1 to avoid any confusion in this sense.
2. We assume the Reviewer refers to our comment in the Conclusion. Please note that it already mentions the use of power iteration method initialized by a good enough guess, namely, that given by the unfolding method (that is, the dominant singular vectors of the unfoldings). This combination of methods (unfolding + power iteration) is what is usually done in practice, and can bridge the gap between the dashed lines and the dash-dotted lines of Figure 3, since then the tensor structure is taken into account by the second step.
3. In fact, results presented in section 3 remain valid as long as $n_1$ and $n_2$ grow at the same rate. If one wants to consider, as the Reviewer proposes, a case where $n_3 \gg n_1, n_2$, one must only be careful to the fact that $\rho_T = \beta_T^2 n_T / \sqrt{n_1 n_2 n_3}$ must converge to a positive quantity, which changes the non-trivial regime! Here, we would have $\beta_T \ll n_T^{1 / 4}$ in the non-trivial regime, so the case $\beta_T = \Theta(n_T^{1 / 4})$ dealt with in our work corresponds to the limit $\rho_T \to +\infty$ when one considers $n_3 \gg n_1, n_2$. Due to these subtlelties, we are unsure whether such a remark would be productive (without spending significant space explaining this point, it could lead to some confusion). Hence we choose not to add it.
4. We are not sure that we understood your question. Can you please reformulate it? The "tensor approach" and the (matrix) "unfolding approach" are two distinct methods, which cannot be combined, to solve the estimation problem considered in our work.

We are truly grateful to the time and dedication you have given to our work, which has brought us many avenues for improvement. We hope that our answers will plainly address your reviews.

1. We concur with the reviewer's observation that, in real-world applications, the dimensionality often varies across different views. In our work, our main goal is to give rigorous theoretical results quantifying the performance gap between tensor-based and matrix-based approaches for multi-view clustering, which is a difficult task in all its generality. Therefore, we study the simpler model with proportional views of the same size as a first step towards more general rigorous theoretical results. Further work is needed to rigorously extend our conclusions beyond the considered model.
2. References to the corresponding theorems have been added in the summary of contributions.
3. This has been corrected, thank you for your careful reading.
4. The acronym "SNR" is used only twice in the last paragraph of page 4. In the previous paragraphs it was explicitely written "signal-to-noise ratio" to indicate the strength of the signal relatively to the noise. In the considered model, this is controled by the two parameters $\beta_M$ and $\beta_T$. This is explained in the introduction of Section 3. We have added a clarification on the use of the acronym "SNR".
5. We have added a sentence explaining the significance of all variables in equation (2).
6. Given to tensors $\mathbf{T}, \mathbf{T}' \in \mathbb{R}^{n_1 \times n_2 \times n_3}$, their tensor product is $\langle \mathbf{T}, \mathbf{T}' \rangle = \sum_{i, j, k = 1}^{n_1, n_2, n_3} T_{i, j, k} T'_{i, j, k}$. This definition has been added to Section 2.2, where tensor notations are introduced.
7. We acknowledge that the formula for $\zeta$ given in Theorem 2 is complex. However, Figure 2 precisely shows the behavior of the quantity $\zeta$ depending on the values of $\beta_M$ and $\rho_T$. We can see that $\zeta$ is close to $1$ only if both SNR parameters are large enough (i.e., far from the phase transition given by the red curve $\zeta = 0$). Another way to see it is by taking $\rho_T = \Theta(\beta^2)$ and $\beta_M = \Theta(\beta)$. Then, from the formula in Theorem 2, $\zeta$ behaves like $1 - \frac{1}{\beta^4} \left[ \left( \frac{\beta^2}{\beta^4} \right)^2 + \beta^2 \right]$, which clearly goes to $1$ as $\beta \to +\infty$ (corresponding to the top right corner of Figure 2).
8. Thank you for taking the time of reading of the Appendix as well. We have added details on the deduction of this equation: $Q^{-1} Q = I_{n_2}$ and $Q^{-1} = T^{(2)} T^{(2) \top} - s I_{n_2}$, we use the expression of $T^{(2)}$ given in equation (3) and take the expectation to obtain the formula given at the end of page 17.
9. The expression of the alignments relies on the eigendecomposition $\tilde{Q}(\tilde{s}) = \sum_{i = 1}^n \frac{1}{\tilde{\lambda} - \tilde{s}} u_i u_i^\top$ where $\tilde{\lambda}_i$ and $u_i$ are eigenvalues and eigenvectors of $\frac{n_T}{\sqrt{n_1 n_2 n_3}} T^{(2)} T^{(2) \top} - \frac{n_2 + n_1 n_3}{\sqrt{n_1 n_2 n_3}} I_n$. Hence, we isolate the spike $\hat{y} \hat{y}^\top$ (corresponding to some $u_i u_i^\top$) using the standard Cauchy's integral formula with a contour circling around the spike eigenvalue only. We have explained this in the paper as well.
10. Thank you for the relevant references. They have been added to our "Related work" paragraph.