DLEFT-MKC: Dynamic Late Fusion Multiple Kernel Clustering with Robust Tensor Learning via Min-Max Optimization

Thank you so much for the recognition and valuable comments! We have revised the manuscript significantly. Also, the corresponding responses are as follows.

1. Notation Table

Thanks. To improve clarity and readability, we have included a notation table as shown in Tab.4, which provides a comprehensive list and explanation of the main symbols used in this article.

2. Descent Direction Expression

when $\gamma_p=0$ and $\nabla\leq 0$, the descent direction is the normal form: $-\left[\bigtriangledown\mathcal{G}(\boldsymbol{\gamma})\right]_{p}$. We have fixed the equation in the manuscript. To ensure that all cases are covered, we have revised Eq.(14) in the manuscript.

\quad \quad \ \ | \ 0 \quad \quad \quad \quad \quad \ \ if $\gamma_p = 0$ and $[\nabla\mathcal{G}(\boldsymbol{\gamma})]_p > 0$,

$v_p = \ | - [\nabla\mathcal{G}(\boldsymbol{\gamma})]_{u} \quad$ if $p=u$,

$\quad \quad \ \ | - [\nabla\mathcal{G}(\boldsymbol{\gamma})]_{p} \quad$ otherwise.

3. Computational Complexity

Thanks. Although the objective function of the proposed algorithm appears complex, we have designed an efficient and effective optimization strategy to solve it. The computational complexity of this strategy is $\mathcal{O}(nmk \log(m) + nmk^2)$ per iteration. Despite the complexity, the algorithm maintains high computational efficiency and achieves excellent clustering performance. The detailed derivation process is as follows:

The time complexity of the proposed DLEFT-MKC algorithm is $\mathcal{O}(nmk \log(m) + nmk^2)$ per iteration, with the following detailed derivation:

(1) Updating $\hat{F}_p$ and $T_p$:

• According to Eq.8 and Eq.16, these updates require $2m$ times economic SVD operations with a complexity of $\mathcal{O}(nk^2)$.
• Therefore, the total complexity for these updates is $\mathcal{O}(2m \cdot nk^2) = \mathcal{O}(2mnk^2)$.

(2) Updating $\boldsymbol{\beta}$ and $F^{*}$:

• Based on Eq.11, these updates involve a reduced gradient descent method with a complexity of $\mathcal{O}(nk^2 l)$, where $l$ is the number of iterations, typically small.

(3) Updating $\mathcal{A}$:

• Based on Eq.15, this update involves solving proximal operators, with a complexity of $\mathcal{O}(nmk \log(m) + nmk^2)$.

Given that $n \gg k$ and $n \gg m$, the overall time complexity of the algorithm is dominated by the most complex term, resulting in $\mathcal{O}(nmk \log(m) + nmk^2)$.

Comparison with Other Algorithms

Furthermore, we list the time complexity of all compared methods in Tab.5 for a theoretical comparison of time complexity with other algorithms. As evident, the computational efficiency of the proposed DLEFT-MKC algorithm is linear, contrasting sharply with the cubic time complexity $\mathcal{O}(n^3 mk)$ of common MKC algorithms. This aligns well with our efficiency goals.

Our proposed algorithm is similar in complexity to other late fusion-based methods, such as OPLFMVC and LFMVC. OPLFMVC generally maintains the best efficiency due to its one-pass method. Yet, the proposed DLEFT-MKC algorithm not only achieves superior clustering performance but also maintains high computational efficiency. This makes it a valuable tool for handling large-scale and complex datasets, where both performance and efficiency are critical.

4. Explanation of Experimental Results

Thanks. To facilitate easier and clearer distinguishing, we normalized the partition matrices and updated the visual cluster structure, as shown in Fig.2. We observe that during the clustering process, the cluster structure becomes increasingly clear and distinguishable as the DLEFT algorithm iterates. This clearly demonstrates the effectiveness of the DLEFT algorithm's learning process. The well-defined cluster structure also explains why the algorithm achieves such high clustering accuracy.

On the other hand, some deep clustering methods or classification algorithms can achieve around 94% accurancy, and even 99% purity on the Reuters dataset [Automatic classification of national health service feedback(2022), Classification of multi-labeled text articles with reuters dataset using SVM(2022), Analysis of the Influence of Preprocessing Techniques on Text Classification Accuracy: An Investigation with the Naive Bayes Model and the Reuters-21578 Dataset(2021), A set theory based similarity measure for text clustering and classification(2020), Efficient deep embedded subspace clustering(2022), Transformed K-means clusterin(2021)]. To further evaluate the performance of GMC, LTBPL, UGLBL, and WTNNM on the Reuters dataset, we try to conduct tests on a computer with larger memory (since the 64GB memory was insufficient for these algorithms to run on the Reuters dataset). And achieve the following results:

• GMC: 40% ACC, 19% PUR, 48% PUR, 15% RI, with 1657.2s running time.
• UGLBL: 79% ACC, 70% PUR, 84% PUR, 66% RI, with 17095s running time.
• LTBPL: We were unable to obtain results on a computer with 128GB of memory due to out-of-memory errors.
• WTNNM: We were unable to obtain the results within the 8 days of running the algorithms (updated: 23 Nov), and we will update the results as soon as they are completed.

Note: By comparing these tensor-based clustering algorithms, particularly LTBPL and WTNNM, the efficiency of the proposed algorithm in this paper can be significantly highlighted.

These results indicate that most algorithms achieve only around 45% accuracy on the Reuters dataset primarily due to their inability to fully extract information from the complex data structure and learn an ideal data representation. In contrast, our proposed algorithm demonstrates very encouraging clustering performance on this dataset. The evolving clustering performance and visualized cluster structures (see Fig.1 and Fig.2) further confirm this.

5. Source Code and Reproductivity

Thanks. We upload the source codes to Anonymous GitHub: https://anonymous.4open.science/r/DLEFT-MKC-3F8F/. All experimental information is provided, including all utilized functions and selected parameters.

Last

We are happy to any questions, suggestions or comments. Please do not hesitate to tell us. We will response timely.

Dear Reviewer Noi6,

We highly appreciate your valuable and insightful reviews. We hope the above response has addressed your concerns. If you have any other suggestions or questions, feel free to discuss them. We are very willing to discuss them with you in this period.

Thank you so much for the recognition, professional comments, and valuable time! It is very important for us and this research.

Best wishes,

Authors

Dear Reviewer Noi6,

Thank you for your support and recognition of our contributions.

We will make comprehensive revisions based on your valuable feedback in the final version to further improve and perfect the quality of the paper.

We sincerely appreciate the time and effort you have invested in providing such profound and insightful suggestions.

Best regards,

Authors of Paper 1283

Thank you so much for the recognition and valuable comments! We have revised the manuscript significantly. Also, the corresponding responses are as follows.

1. Computational Complexity of the Proposed DLEFT-MKC Algorithm

Thanks. The time complexity of the proposed DLEFT-MKC algorithm is $\mathcal{O}(nmk \log(m) + nmk^2)$ per iteration, with the following detailed derivation:

(1) Updating $\hat{F}_p$ and $T_p$:

• According to Eq.8 and Eq.16, these updates require $2m$ times economic SVD operations with a complexity of $\mathcal{O}(nk^2)$.
• Therefore, the total complexity for these updates is $\mathcal{O}(2m \cdot nk^2) = \mathcal{O}(2mnk^2)$.

(2) Updating $\boldsymbol{\beta}$ and $F^{*}$:

• Based on Eq.11, these updates involve a reduced gradient descent method with a complexity of $\mathcal{O}(nk^2 l)$, where $l$ is the number of iterations, typically small.

(3) Updating $\mathcal{A}$:

• Based on Eq.15, this update involves solving proximal operators, with a complexity of $\mathcal{O}(nmk \log(m) + nmk^2)$.

Given that $n \gg k$ and $n \gg m$, the overall time complexity of the algorithm is dominated by the most complex term, resulting in $\mathcal{O}(nmk \log(m) + nmk^2)$.

Comparison with Other Algorithms

Furthermore, we list the time complexity of all compared methods in Tab.5 for a theoretical comparison of time complexity with other algorithms. As evident, the computational efficiency of the proposed DLEFT-MKC algorithm is linear, contrasting sharply with the cubic time complexity $\mathcal{O}(n^3 mk)$ of common MKC algorithms. This aligns well with our efficiency goals.

Our proposed algorithm is similar in complexity to other late fusion-based methods, such as OPLFMVC and LFMVC. OPLFMVC generally maintains the best efficiency due to its one-pass method. Yet, the proposed DLEFT-MKC algorithm not only achieves superior clustering performance but also maintains high computational efficiency. This makes it a valuable tool for handling large-scale and complex datasets, where both performance and efficiency are critical.

2. Dynamic Reconstruction of Base Partition Matrices

Thanks. Base partition matrices can directly capture information from multiple kernels. However, this process has limitations. Specifically, the information captured is often limited (in amount or quality) and heavily dependent on the initialization. As a result, the captured information may not be sufficient; poor initialization can lead to suboptimal partitions, thereby causing performance bottlenecks.

To address this issue, we have designed a dynamic reconstruction strategy that adaptively learns more optimal partitions. This approach enables the algorithm to continuously capture more beneficial information, thereby enhancing the subsequent clustering tasks. This is achieved through iterative refinement, where the algorithm continuously updates the base partitions based on the current state; and this continuous learning process ensures that the algorithm remains adaptive and responsive to the underlying data structure. By dynamically learning base partitions, we can guide the learning process more effectively and mitigate the negative impact of poor initialization.

3. Explanation of Experimental Results

Thanks. From Tab.2, it can be observed that the standard deviation (std) of the proposed algorithm is relatively high on the Reuters and CCV datasets. This indicates that in the learned clustering structures, there are some sample instances that exhibit ambiguity, meaning they have similar distances to multiple clusters. Due to the inherent randomness of the k-means algorithm, these ambiguous samples may be assigned to different clusters across multiple runs, leading to higher variance.

Despite this, the high standard deviation is not necessarily a drawback, especially given the high clustering accuracy achieved by the proposed algorithm. In practice, maintaining a high clustering accuracy while allowing for higher variance can actually highlight samples that are difficult to classify or ambiguous. This can serve as a useful indicator for researchers to re-examine and verify these instances, potentially leading to further improvements in real-world clustering applications.

Moreover, even in the worst-case scenario (when the std is at its lower bound), the proposed algorithm's clustering performance still significantly outperforms other algorithms. This underscores the robustness and effectiveness of the proposed DLEFT-MKC.

Overall, the high standard deviation observed in the proposed algorithm on the Reuters and CCV datasets is not a significant drawback. It reflects the presence of ambiguous samples and the algorithm's ability to highlight them. This can aid researchers in verifying and improving the clustering results. Moreover, the algorithm's strong performance, even in the worst-case scenario, further validates its effectiveness and robustness.

4. More Comparative Experiment

Thanks. We conduct additional experiments on Caltech datasets to evaluate the clustering performance of compared algorithms, where Caltech101-30T (3060 samples, 48 views, 102 clusters) denotes that each cluster has 30 samples. The results are shown below, and we will revise the manuscript and include them in the final version according to the page space.

Note: Some results were not reported due to out-of-memory errors or because the computations had not been completed within the allotted time (exceeding 7 days)

Last

We are happy to any questions, suggestions or comments. Please do not hesitate to tell us. We will response timely.

Dear Reviewer xS8p,

We highly appreciate your valuable and insightful reviews. We hope the above response has addressed your concerns. If you have any other suggestions or questions, feel free to discuss them. We are very willing to discuss them with you in this period.

If your concerns have been addressed, would you please consider raising the score? It is very important for us and this research. Thanks again for your professional comments and valuable time!

Best wishes,

Authors

Thank you so much for the recognition and valuable comments! We have revised the manuscript significantly. Also, the corresponding responses are as follows.

1. Definition, Motivation, and Explanation

Thanks. Definition of base partition: We define the base partition as the matrices of n*k for each kernel view, as the Fp, obtained by directly performing eigenvalue decomposition on kernel matrices and obtaining the large k eigenvalue corresponding eigenvectors consisting of the matrices.

Adaptive mechanisms: Adaptive mechanisms refer to the dynamic reconstruction of partition matrices and the min-max paradigm.

• Dynamic Reconstruction: Base partition matrices can directly capture information from multiple kernels. However, this process has limitations. Specifically, the information captured is often limited (in amount or quality) and heavily dependent on the initialization. As a result, the captured information may not be sufficient; poor initialization can lead to suboptimal partitions, thereby causing performance bottlenecks.

To address this issue, we have designed a dynamic reconstruction strategy that adaptively learns more optimal partitions. This approach enables the algorithm to continuously capture more beneficial information, thereby enhancing the subsequent clustering tasks. This is achieved through iterative refinement, where the algorithm continuously updates the base partitions based on the current state; and this continuous learning process ensures that the algorithm remains adaptive and responsive to the underlying data structure. By dynamically learning base partitions, we can guide the learning process more effectively and mitigate the negative impact of poor initialization.

• Min-max Paradigm: The min-max paradigm introduced in our proposed algorithm is centered around the philosophical concept of "finding optimism in pessimism." Specifically, the algorithm aims to minimize the parameter $\gamma$ while simultaneously maximizing the overall objective function. This adversarial approach enhances the stability and robustness of the algorithm.

In traditional optimization paradigms, if a particular view temporarily achieves better performance, the algorithm tends to increase the weight of that view, thereby diminishing the influence of other views. This can lead to the algorithm becoming overly reliant on a single kernel view, which may compromise its overall performance. In contrast, our proposed min-max paradigm avoids this issue by preventing the algorithm from overly favoring any single view. This ensures a balanced and stable performance across different views.

To further validate the robustness of our proposed algorithm, we conducted additional experiments with noisy data. The visual comparisons of clustering results are presented in Fig.7 in the Appendix.

The results show that our proposed algorithm consistently outperforms compared algorithms in terms of clustering performance and exhibits more excellent stability when subjected to noise interference. Unlike other algorithms, which show significant degradation in performance under noisy conditions, our proposed algorithm demonstrates minimal fluctuation, highlighting its superior robustness.

Based on these positive effects, our proposed algorithm achieves more stable and reliable clustering results, especially in the presence of noise. As demonstrated in Fig.7, the proposed algorithm not only outperforms baseline algorithms in terms of clustering performance but also shows minimal fluctuation when subjected to noise interference, highlighting its superior robustness.

2. Framework diagram

Thanks. To aid understanding, we have added a framework diagram of the proposed DELFT-MKC, as shown in Fig.8.

The proposed DLEFT-MKC algorithm represents a significant advancement in the field of multiple kernel clustering. By combining the late fusion paradigm, tensor techniques, and min-max optimization in a novel and integrated manner, we achieve substantial improvements in both computational efficiency and clustering performance. The dynamic reconstruction of base partitions and the new optimization strategy further enhance the algorithm's robustness and adaptability, making it a valuable tool for a wide range of applications.

4. Analysis of Computational Complexity

Thanks. It may be due to page limitations, therefore, we will include enough theoretical analysis of computational complexity in the final version with extra page space. We analyze the computational complexity as follows,

The time complexity of the proposed DLEFT-MKC algorithm is $\mathcal{O}(nmk \log(m) + nmk^2)$ per iteration, with the following detailed derivation:

(1) Updating $\hat{F}_p$ and $T_p$:

• According to Eq.8 and Eq.16, these updates require $2m$ times economic SVD operations with a complexity of $\mathcal{O}(nk^2)$.
• Therefore, the total complexity for these updates is $\mathcal{O}(2m \cdot nk^2) = \mathcal{O}(2mnk^2)$.

(2) Updating $\boldsymbol{\beta}$ and $F^{*}$:

• Based on Eq.11, these updates involve a reduced gradient descent method with a complexity of $\mathcal{O}(nk^2 l)$, where $l$ is the number of iterations, typically small.

(3) Updating $\mathcal{A}$:

• Based on Eq.15, this update involves solving proximal operators, with a complexity of $\mathcal{O}(nmk \log(m) + nmk^2)$.

Given that $n \gg k$ and $n \gg m$, the overall time complexity of the algorithm is dominated by the most complex term, resulting in $\mathcal{O}(nmk \log(m) + nmk^2)$.

Comparison with Other Algorithms

Furthermore, we list the time complexity of all compared methods in Tab.5 for a theoretical comparison of time complexity with other algorithms. As evident, the computational efficiency of the proposed DLEFT-MKC algorithm is linear, contrasting sharply with the cubic time complexity $\mathcal{O}(n^3 mk)$ of common MKC algorithms. This aligns well with our efficiency goals.

Our proposed algorithm is similar in complexity to other late fusion-based methods, such as OPLFMVC and LFMVC. OPLFMVC generally maintains the best efficiency due to its one-pass method. Yet, the proposed DLEFT-MKC algorithm not only achieves superior clustering performance but also maintains high computational efficiency. This makes it a valuable tool for handling large-scale and complex datasets, where both performance and efficiency are critical.

5. Running Time Comparison

Thanks. The table (Tab.10) comparing running time was included in the appendix of the submitted manuscript. Note that, due to page limitations, we had to take it into the appendix, and We had to adopt a way to visually compare and save space to demonstrate the comparison and discussion of computational efficiency.

We will replace it in the final version with extra page space to provide a clearer and more intuitive representation.

6. Reference List Revision

Thank you for pointing out the issues with the references. We have carefully revised and standardized the references, including the full names and abbreviations of conferences and journals, capitalization, and other information.

Last

We are happy to any questions, suggestions or comments. Please do not hesitate to tell us. We will response timely.

3. Novelty and Contributions of the Proposed DLEFT-MKC Algorithm

Although the proposed DLEFT-MKC algorithm leverages tensor techniques, late fusion paradigm, and min-max optimization, it is not a simple combination of existing methods but a novel and innovative approach.

(1) Late Fusion Paradigm in Tensor Techniques:

• Existing algorithms apply tensor techniques to Multiple Kernel Clustering (MKC) by stacking kernel matrices or affinity matrices into an $n \times n \times m$ tensor. However, DLEFT-MKC introduces the late fusion paradigm, which allows us to construct an $n \times k \times m$ tensor. This significantly improves the computational efficiency of using tensor techniques by reducing the dimensionality and complexity of the tensor operations.

(2) Min-Max Optimization in Tensor-Based MKC:

• For the first time, we incorporate min-max optimization into tensor-based MKC. This is a highly novel approach that enhances the robustness of the algorithm. By integrating the philosophical concept of "finding optimism in pessimism," the proposed algorithm ensures robust performance even when faced with less favorable datasets. This results in better clustering outcomes under various conditions.
• We propose a new optimization algorithm that combines Alternating Direction Method of Multipliers (ADMM) and Reduced Gradient Descent Method (RGDM). This hybrid approach effectively solve the resultant problem and provide optimization method references for the community.

(3) Dynamical Reconstruction and Calibration of Base Partition Matrices:

• Another first-of-its-kind contribution is the dynamical reconstruction and calibration of base partition matrices. This innovation overcomes the representational bottleneck of traditional base partition matrices, leading to enhanced clustering performance. By dynamically learning the base partitions, the algorithm can better adapt to the underlying data structure, thereby improving the overall clustering quality.

Overall Contributions

• Unified Framework: The late fusion paradigm, tensor techniques, and min-max optimization have been individually explored in the literature. However, DLEFT-MKC is the first to organically integrate these components into a unified framework. This integration results in significant improvements in both computational efficiency and clustering performance.
• Dynamic Reconstruction and New Optimization Strategy: We introduce dynamic reconstruction of base partition matrices and a novel optimization strategy that effectively addresses the challenges posed by our proposed problem. These contributions ensure that the algorithm remains robust and efficient, even in complex and diverse datasets.

Conclusion

The proposed DLEFT-MKC algorithm represents a significant advancement in the field of multiple kernel clustering. By combining the late fusion paradigm, tensor techniques, and min-max optimization in a novel and integrated manner, we achieve substantial improvements in both computational efficiency and clustering performance. The dynamic reconstruction of base partitions and the new optimization strategy further enhance the algorithm's robustness and adaptability, making it a valuable tool for a wide range of applications.

Dear Reviewer JfTa,

We highly appreciate your valuable and insightful reviews. We hope the above response has addressed your concerns. If you have any other suggestions or questions, feel free to discuss them. We are very willing to discuss them with you in this period.

If your concerns have been addressed, would you please consider raising the score? It is very important for us and this research. Thanks again for your professional comments and valuable time!

Best wishes,

Authors

Thank you for your response. Most of my concerns have been resolved.

Thank you so much for the recognition and valuable comments! We have revised the manuscript significantly. Also, the corresponding responses are as follows.

1. Robustness and Generalization

Thanks. Robustness refers to an algorithm's ability to maintain its clustering performance in adverse conditions, specifically its capability to withstand pessimistic scenarios and noise interference. This robustness is a direct result of the min-max paradigm introduced in our proposed algorithm, which embodies the philosophical concept of "searching optimism in pessimism." Generalization refers to the algorithm's ability to achieve excellent clustering performance across a wide range of datasets.

Additional Noise Experiments: To further validate the robustness of our proposed algorithm, we conducted additional experiments with noisy data. The visual comparisons of clustering results are presented in Fig.7 in the Appendix.

The results show that our proposed algorithm consistently outperforms compared algorithms in terms of clustering performance and exhibits more excellent stability when subjected to noise interference. Unlike other algorithms, which show significant degradation in performance under noisy conditions, our proposed algorithm demonstrates minimal fluctuation, highlighting its superior robustness.

2. Min-Max Paradigm and Its Benefits

Thanks. The min-max paradigm introduced in our proposed algorithm is centered around the philosophical concept of "finding optimism in pessimism." Specifically, the algorithm aims to minimize the parameter $\gamma$ while simultaneously maximizing the overall objective function. This adversarial approach enhances the stability and robustness of the algorithm.

In traditional optimization paradigms, if a particular view temporarily achieves better performance, the algorithm tends to increase the weight of that view, thereby diminishing the influence of other views. This can lead to the algorithm becoming overly reliant on a single kernel view, which may compromise its overall performance. In contrast, our proposed min-max paradigm avoids this issue by preventing the algorithm from overly favoring any single view. This ensures a balanced and stable performance across different views.

Based on these positive effects, our proposed algorithm achieves more stable and reliable clustering results, especially in the presence of noise. As demonstrated in Fig.7, the proposed algorithm not only outperforms baseline algorithms in terms of clustering performance but also shows minimal fluctuation when subjected to noise interference, highlighting its superior robustness.

3. Constraints on $\gamma_p$

Thanks. The constraints on $\gamma_p$ in Eq.(4) and Eq.(6) differ. Specifically, in Eq.(4), the constraint $\gamma \in \nabla$ denotes that the sum of $\gamma_p^2$ is 1, i.e., $\sum_{p=1}^m \gamma_p^2 = 1$. In contrast, in Eq.(6), the constraint $\gamma \in \Delta$ denotes that the sum of $\gamma_p$ is 1, i.e., $\sum_{p=1}^m \gamma_p = 1$.

• Eq.(4): $\gamma \in \nabla$ implies $\sum_{p=1}^m \gamma_p^2 = 1$, which is a quadratic constraint. When $\gamma$ is subject to a quadratic constraint, we use $\gamma_p$ directly.
• Eq.(6): $\gamma \in \Delta$ implies $\sum_{p=1}^m \gamma_p = 1$, which is a linear constraint. When $\gamma$ is subject to a linear constraint, we use $\gamma_p^2$ instead.

In this way, the constraint ensures that the weights are distributed more evenly across different views, preventing the trivial solution: any single view from dominating the others, i.e., one $\gamma_p$ is 1 and the others are 0.

In addition, we believe that the algorithm would maintain its good performance if the constraint $\gamma \in \Delta$ (linear constraint) is adjusted to $\gamma_p^2 \in \nabla$ (quadratic constraint). The linear constraint $\gamma \in \Delta$ is more intuitive and easier to interpret, as it directly represents the weights of different views summing to one.

4. Computational Efficiency of the Proposed DLEFT-MKC Algorithm

Although computing the full t-SVD for an $n_1 \times n_2 \times n_3$ tensor incurs a significant time cost, with a complexity of $\mathcal{O}(n_1 n_2 n_3^2 + n_1^3 n_3 + n_2^3 n_3 + n_1 n_2 \min(n_1, n_2) n_3)$, the proposed DLEFT-MKC algorithm does not require a complete t-SVD during the optimization process. Instead, it only needs to compute partial t-SVDs when updating the tensor $\pmb{\mathcal{A}}$. Specifically, updating $\pmb{\mathcal{A}}$ in Eq.15 involves solving proximal operators, with a complexity of $\mathcal{O}(nmk \log(m) + nmk^2)$.

The time complexity of the proposed DLEFT-MKC algorithm is $\mathcal{O}(nmk \log(m) + nmk^2)$ per iteration, with the following detailed derivation:

(1) Updating $\hat{F}_p$ and $T_p$:

• According to Eq.8 and Eq.16, these updates require $2m$ times economic SVD operations with a complexity of $\mathcal{O}(nk^2)$.
• Therefore, the total complexity for these updates is $\mathcal{O}(2m \cdot nk^2) = \mathcal{O}(2mnk^2)$.

(2) Updating $\boldsymbol{\beta}$ and $F^{*}$:

• Based on Eq.11, these updates involve a reduced gradient descent method with a complexity of $\mathcal{O}(nk^2 l)$, where $l$ is the number of iterations, typically small.
• Therefore, the total complexity for these updates is $\mathcal{O}(nk^2 l)$.

(3) Updating $\pmb{\mathcal{A}}$ in Eq.15:

• This update requires a complexity of $\mathcal{O}(nmk \log(m) + nmk^2)$.

Given that $n \gg k$ and $n \gg m$, the overall time complexity of the algorithm is dominated by the most complex term, resulting in $\mathcal{O}(nmk \log(m) + nmk^2)$.

Comparison with Other Algorithms

Furthermore, we list the time complexity of all compared methods in Tab.5 for a theoretical comparison of time complexity with other algorithms. As evident, the computational efficiency of the proposed DLEFT-MKC algorithm is linear, contrasting sharply with the cubic time complexity $\mathcal{O}(n^3 mk)$ of common MKC algorithms. This aligns well with our efficiency goals.

Our proposed algorithm is similar in complexity to other late fusion-based methods, such as OPLFMVC and LFMVC. On several small datasets, factors such as the number of iterations, specific computational mechanisms, and CPU usage can influence running time. OPLFMVC generally maintains the best efficiency due to its one-pass method. Yet, the proposed DLEFT-MKC algorithm not only achieves superior clustering performance but also maintains high computational efficiency. This makes it a valuable tool for handling large-scale and complex datasets, where both performance and efficiency are critical.

5. Novelty and Contributions of the Proposed DLEFT-MKC Algorithm

Although the proposed DLEFT-MKC algorithm leverages tensor techniques, late fusion paradigm, and min-max optimization, it is not a simple combination of existing methods but a novel and innovative approach.

(1) Late Fusion Paradigm in Tensor Techniques:

• Existing algorithms apply tensor techniques to Multiple Kernel Clustering (MKC) by stacking kernel matrices or affinity matrices into an $n \times n \times m$ tensor. However, DLEFT-MKC introduces the late fusion paradigm, which allows us to construct an $n \times k \times m$ tensor. This significantly improves the computational efficiency of using tensor techniques by reducing the dimensionality and complexity of the tensor operations.

(2) Min-Max Optimization in Tensor-Based MKC:

• For the first time, we incorporate min-max optimization into tensor-based MKC. This is a highly novel approach that enhances the robustness of the algorithm. By integrating the philosophical concept of "finding optimism in pessimism," the proposed algorithm ensures robust performance even when faced with less favorable datasets. This results in better clustering outcomes under various conditions.
• We propose a new optimization algorithm that combines Alternating Direction Method of Multipliers (ADMM) and Reduced Gradient Descent Method (RGDM). This hybrid approach effectively solve the resultant problem and provide optimization method references for the community.

(3) Dynamical Reconstruction and Calibration of Base Partition Matrices:

• Another first-of-its-kind contribution is the dynamical reconstruction and calibration of base partition matrices. This innovation overcomes the representational bottleneck of traditional base partition matrices, leading to enhanced clustering performance. By dynamically learning the base partitions, the algorithm can better adapt to the underlying data structure, thereby improving the overall clustering quality.

Overall Contributions

• Unified Framework: The late fusion paradigm, tensor techniques, and min-max optimization have been individually explored in the literature. However, DLEFT-MKC is the first to organically integrate these components into a unified framework. This integration results in significant improvements in both computational efficiency and clustering performance.
• Dynamic Reconstruction and New Optimization Strategy: We introduce dynamic reconstruction of base partition matrices and a novel optimization strategy that effectively addresses the challenges posed by our proposed problem. These contributions ensure that the algorithm remains robust and efficient, even in complex and diverse datasets.

Conclusion

The proposed DLEFT-MKC algorithm represents a significant advancement in the field of multiple kernel clustering. By combining the late fusion paradigm, tensor techniques, and min-max optimization in a novel and integrated manner, we achieve substantial improvements in both computational efficiency and clustering performance. The dynamic reconstruction of base partitions and the new optimization strategy further enhance the algorithm's robustness and adaptability, making it a valuable tool for a wide range of applications.

Last

We are happy to any questions, suggestions or comments. Please do not hesitate to tell us. We will response timely.

Dear Reviewer UZb7,

We highly appreciate your valuable and insightful reviews. We hope the above response has addressed your concerns. If you have any other suggestions or questions, feel free to discuss them. We are very willing to discuss them with you in this period.

If your concerns have been addressed, would you please consider raising the score? It is very important for us and this research. Thanks again for your professional comments and valuable time!

Best wishes,

Authors