On Sparse Canonical Correlation Analysis

Summary

The paper presents an efficient MISDP algorithm for sparse CCA.

Strengths

Sparse CCA is an important and interesting problem. The analysis is useful for this area.

Weaknesses

- Typos: optimiality -> optimality line 167 - Limitations are not fully addressed - No separate evaluation of sparsity in the experiments (see Questions) - Most experiments have running time of exactly 1 second, it would be clearer to show more decimal digits.

Questions

- Your analysis is to compute the first pair of basis vectors, how does your algorithm work to compute multiple pairs? - Why is the MIPGap always 0 (except when timed out)? Does a dataset exist where it is not zero? - Related to above, can the authors expand on the limitations of the proposed method? - In experiments, to evaluate the different algorithms, you use the distance with the optimum. Do you also compare sparsity explicitly?

Rating

6

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

See above

Summary

The paper proposes several algorithms for the Sparse Canonical Correlation Analysis (SCCA) problem. First, the authors present an exact semidefinite programming representation of the classic CCA problem. These results are then used to derive an equivalent combinatorial formulation of the Sparse CCA problem, which can be optimized using greedy and local search algorithms. For the case that the sample covariance matrix has low rank, the paper then derives a polynomial time algorithm to solve SCCA to global optimality. Next, the authors show the NP-hardness for the case where the cross-covariance matrix has rank one, and then discuss how the problem can be solved using two Mixed-Integer Convex Quadratic Programs. The authors then derive an equivalent mixed integer semidefinite programming reformulation for the SCCA problem, which can be simplified so that it allows them to develop a tailored branch-and-cut algorithm to solve SCCA to global optimality. Finally, the paper performs numerical evaluation of the proposed algorithms on synthetic data as well as several real-world datasets. It is shown that their approximate algorithms can solve small-to medium scale problems in a few seconds, while achieving the optimal value in most cases. In the rank-one case, they can globally solve problems up to size 200x200 within one hour.

Strengths

The paper proposed several new algorithms for the sparse CCA problem in different scenarios. The authors prove the equivalence of their reformulations as well as the convergence of their exact algorithm for SCCA in the low rank case in O(n^3+m^3). In the experiments the approach is shown to be applicable to several synthetic and real-world datasets.

Weaknesses

An experimental comparison of the approach to other state-of-the-art methods for sparse CCA is missing and should be added to the paper, e.g. the methods introduced by Witten et al. [41] or Parkhomenko et al.[37].

Questions

What are the results of the buzz dataset, which is included in the data description in Appendix E but not included in the results in Table 2?

Rating

6

Confidence

3

Soundness

2

Presentation

3

Contribution

3

Limitations

As also discussed by the authors, the proposed algorithms have certain preconditions such as low rank which does not make them applicable to all cases. Moreover, the exact branch-and-cut based algorithms do not scale to large datasets.

Summary

To enhance the interpretability of CCA, the authors explore sparse CCA. It is interesting to note that sparse CCA generalizes sparse PCA, sparse SVD, and sparse regression. The authors derive efficient algorithms to solve sparse CCA and perform the theoretical analysis for sparse CCA. The effectiveness of the proposed method is verified through numerical experiments.

Strengths

1.The paper is well-written and well-organized. 2.The paper works on sparse CCA and gives a derivation of an equivalent mixed-integer semi-definite programming model. The authors verify the effectiveness of the proposed method via numerical experiments.

Weaknesses

I have several minor concerns and hope to hear from the authors, 1. The work in [10] also addresses the sparsity of CCA. Why not give experimental results on the reference [10] or other sparse methods? 2. In section 4, the authors give a mixed-integer semidefinite program. In toy examples, it is much better to discuss this model.

Questions

Please see the above weaknesses.

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

The authors have explained some of the limitations in the article, and others can be seen from weaknesses.

Summary

This paper presented analyses on sparse canonical correlation analysis (SCCA) with optimization tools, including an SDP relaxation formulation. The authors discussed the theoretical properties and demonstrated numerical experiments.

Strengths

The paper presented detailed theoretical developments supported by numerical evaluations. The presentation is generally easy to follow.

Weaknesses

1. The current manuscript focused mostly on the mathematical properties of SCCA with optimization tools. Though such analyses are valuable, it would be more helpful to the community if the authors could provide connections to learning practices/applications, i.e., how the algorithms help understand the real datasets. 2. Technically, it would be valuable to have more discussions on the covariance structure of the matrix, instead of treating them as $A, B, C$ blocks. For example, line 136 (observation 1) becomes a trivial fact if we treat CCA as finding the principal angle/vector of two subspaces, so the cosine of the principal angle cannot exceed one.

Questions

1. Sec 2.1, the **exact** *semidefinite programming (SDP) reformulation* seems to be in contradiction to the fact that this is a **relaxation** of the original problem.

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

None.

Response to Rebuttal

Thank you for your rebuttal. The authors reponded to my concerns and provided additional experimental results, comparing the proposed local search algorithm with the SCCA methods of [10,32,41,37], as also pointed out by other reviewers. They also added the results of the buzz dataset to the evaluation, even though the dimensions do not quite match, as in the table we have n=38 and m=39 but in the dataset description in the appendix it says n=33 and m=34. Could you please clarify this? Moreover, the authors also added further discussions on the limitations of the approaches.