On Sparse Canonical Correlation Analysis
Authors: Yongchun Li
Santanu Dey
Weijun Xie
Venue: NeurIPS 2024 poster (2024)
Keywords: Sparse canonical correlation analysis
low rank
exact and approximation algorithms
Primary area: optimization

Abstract: The classical Canonical Correlation Analysis (CCA) identifies the correlations between two sets of multivariate variables based on their covariance, which has been widely applied in diverse fields such as computer vision, natural language processing, and speech analysis. Despite its popularity, CCA can encounter challenges in explaining correlations between two variable sets within high-dimensional data contexts. Thus, this paper studies Sparse Canonical Correlation Analysis (SCCA) that enhances the interpretability of CCA. We first show that SCCA generalizes three well-known sparse optimization problems, sparse PCA, sparse SVD, and sparse regression, which are all classified as NP-hard problems. This result motivates us to develop strong formulations and efficient algorithms. Our main contributions include (i) the introduction of a combinatorial formulation that captures the essence of SCCA and allows the development of exact and approximation algorithms; (ii) the establishment of the complexity results for two low-rank special cases of SCCA; and (iii) the derivation of an equivalent mixed-integer semidefinite programming model that facilitates a specialized branch-and-cut algorithm with analytical cuts. The effectiveness of our proposed formulations and algorithms is validated through numerical experiments.

On Sparse Canonical Correlation Analysis
Yongchun Li University of Tennessee ycli@utk.edi
Santanu S. Dey
Weijun Xie Georgia Tech
Georgia Tech
wxie@gatech. edu
Abstract
The classical Canonical Correlation Analysis (CCA) identifies the correlations be- tween of multivariate variables based on their covariance, which has been widely applied in diverse fields such as computer vision, natural language process- ing, and speech analysis. Despite its popularity, CCA can encounter challenges explaining correlations between two variable sets within sigh-dimensiona data con- texts. Thus, this paper studies Sparse Canonical Correlation Analysis (SCCA) that enhances the interpretability of CCA. We first show that SCCA generalizes three well-known sparse optimization problems, sparse PCA, sparse SVD, and sparse regression, which all classified NP-hard problems. This result motivates to develop strong formulations and efficient algorithms. Our main contributions include (i) the introduction of combinatorial formulation that captures the essence SCCA and allows the development of approximation algorithms: (ii) the estab- lishment of the complexity results for two low-rank special cases of SCCA; and (iii) the derivation of an equivalent mixeed-nteeer semidefinite programming model that facilitates specialized branch-and annch-nnd-cut algorithm with analytical cuts. The effectiveness of our proposed formulations and algorithms validated through numerical experiments.
Introduction
The Canonical Correlation Analysis (CCA), proposed by H. Hotelling [23], aims identify the correlations between two sets of multivariate variables based on their covariance. Since then, CCA has become a powerful statistical technique used for multivariate data analysis. with its applications across diverse fields such as computer vision [24], natural language processing [38], and speech analysis [21]. Despite its popularity, CCA can encounter challenges in explaining correlations between two variable sets within high-dimensional data contexts, such genomic datasets [36]. In contrast, Sparse Canonical Correlation Analysis (SCCA), which seeks sparse linear combinations of these variable sets, offers substantially enhanced interpretability [41, 42, 44).
Formally, this paper studies the SCCA problem:
{xr Ay x. Bæ $1 Cy 1,||o S 81, Illllo $2),
(SCCA)
ØER" yERm
B
A C'
where 81 S 52
positive integers and
denotes covariance matrix of (n + m)
A
random variables. Specifically, and C are the covariance matrices the n and m random variables, respectively, and A Raxm is the covariane matrix between and m random variables.
B
A
A..B. C are positive semidefinite matrices of size (n + m), and m, respectively.
Hence. A
Here, matrices B. can be singular, i.e., some random variables may be dependent on others. In fact, the covariance matrices B, C' are often low-rank, especially within the high-dimension low-sample size data context (see, e.g., the gene expression data in [41]).
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

optimization problems as special cases, which are sparse PCA [2. 13, 27], sparse SVD [28, 41], and sparse regression [22, 3]. To be specific, when n = m,, 81 $2, B, C' are identity matrices, and A is positive semidefinite matrix, SCCA reduces to the classic sparse PCA problem; when B, C' are identity matrices, SCCA becomes the sparse SVD problem; and when A is rank-one, Section 3 shows that SCCA is equivalent to two sparse linear regression subproblems.
The SCCA problem generalizes three widely-studied
1.1 Main contributions
SCCA is generally NP-hard, given that its special cases, sparse PCA, sparse SVD, and sparse regression are all classified as NP-hard problems. We are motivated to develop efficient formulations and algorithms for SCCA through mixed-integer optimization lens. The main contributions, along with the structure of the remainder of this paper, are the following:
In Section
we present an exact semidefinite programming (SDP) reformulation and derive closed-form optimal value of classic CCA problem. We also develop an equivalent combinatorial formulation of SCCA, which allows the development of approximation algorithms;
A C
(ii) When the covariance matrix
is low-rank, Section studies the complexity of two
A
special cases of SCCA. This motivates to develop polynomial-time exact algorithm of complexity On + m²) for solving SCCA to global optimiality when the sparsity levels (i.c., 81 and $2) meet exceed the ranks of B and C:
(ii) Section 4 derives an equivalent mixed-integer SDP (MISDP) reformulation for SCCA. When applying the Benders decomposition approach, instead of solving the large-scale SDPs, we design customized branch-and algorithm with closed-form cuts, which successfully solve SCCA to optimality; and
(iv) Section numerically test the proposed formulations and algorithms. It is noted that our polynomial -tme exact algorithm can solve real-world instances with 19, 672 and 2, 149 variables in seconds, provided that both 81 and 82 are at least the ranks of B and C.
Our analyses and results can be extended to SCCA with multiple pairs of basis vectors (æ, y). allowing for a more flexible and comprehensive exploration of correlations among data sets. The detailed formulations of multiple SCCA, along with the computational results, are provided in Appendix F.
1.2 Relevant literature
SCCA. To the best of our knowledge, the work [36] was the first paper that introduced the concept of SCCA to select only small subsets of variables to better explain the relationship between many genetic loci and gene expression phenotypes. A handful subset of features enhances interpretability, a desirable property, especially in complex data analysis, which has been successfully demonstrated in Sparse PCA [25]. To obtain sparse canonical loadings (z, y). [39] first applied elastic net penalty to the classical CCA via an iterative regression procedure. In seminal work on SCCA [41], the authors proposed a rigorous formulation by enforcing the & constraints on variables (x. y) and developed penalized matrix decomposition method solve the penalized CCA problem. Then, extensive research has focused on various penalty norm functions to obtain sparse canonical loadings (see, e.g., [20, 26, 39, 42, 10]). In particular, [10] penalized multiple canonical loadings by l norm and computed the sparse solution by the linearized Bregman method. It should be noted that under the assumption that the leading canonical loadings are sparse, [7, 17, 18] established theoretical guarantees of iterative approaches for estimating sparse solutions. Another research direction in SCCA introduced penalty functions based on group structural information of input data and developed group SCCA methods [29, 30]. For comprehensive overview of CCA and SCCA methods, we refer readers to the survey by [44] and the references therein. These approaches, however, do not strictly enforce the exact sparsity requirement but only approximate the sparsity requirement (i.e., to norm) by a convex function. Another relevant work [40] introduced binary variables to recast SCCA as mixed-integer nonconvex program under the assumption of positive definite matrices B, C, based on which they designed a branch-and-boun algorithm. Different from the literature, work does not require positive definiteness assumption of matrices B, C. and able to

---

obtain mixed mixed-integer conic and semidefinite programming reformulations, allowing for better exact and approximation algorithms.
Connections to and differences with sparse PCA and sparse SVD. Analogous to SCCA, both sparse PCA [13, 25] and sparse SVD [28] select small subsets of variables to improve the interpretability of dimensionality reduction methods: PCA and SVD. Considerable investigation has been conducted on solving sparse PCA and sparse SVD from three angles: convex relaxations [12-14], approximation algorithms [6, 9, 28], and exact algorithms [2, 27, 28]. As mentioned before. in sparse PCA and sparse SVD, the covariance matrices B. C are identity. Such setting dramatically simplifies the subset selection problems of sparse PCA and sparse SVD compared to that of SCCA, as in these problems, suffices to focus on the selection
submatrix of the matrix A. Specifically, is shown in [11, 27, 35] that sparse PCA reduces to selecting a principal submatrix of A to maximize the largest eigenvalue(s) and sparse SVD reduces to selecting possibly non-symmetric submatrix of A to maximize the largest singular value(s) [28]. Quite differently, the combinatorial reformulation (1) of SCCA aims to simultaneously select sized-(s1 81) principal submatrix of B, sized-(s2 2 x 82) principal submatrix of C, and a sized-(s) $2) submatrix of A. These fundamental differences in the underlying formulations of sparse PCA and sparse SVD preclude the direct application of their existing algorithms to the SCCA.
Notations:
The following notation used throughout the paper. We use bold lower-case letters (e.g.. 2) and bold upper-car case letters (e.g.. X) to denote vectors and matrices, respectively, and we use corresponding non-bold letters (e.g.. xz) denote their components. We let S" , S denote the set of all the n x symmetric real matrices, the set of all the n x symmetric positive semidefinite matrices, and the set of all the n symmetric positive definite matrices, respectively. We let denote the identity matrix and let O denote the vector or matrix with all all-zero entries. We let TR denote the set of all n--dimnnsinnal nonnegative vectors. We let [n] = {1,2, ... n). [s, n] {s, 1.... .n.. Given matrix A E Raxm and two subsets S [n]. T S [m]. we let At denote the pseudo inverse of matrix A, let As,r denote submatrix of A with rows and columns indexed by sets S, T. respectively, and let (As.r)* denote the pseudo inverse of submatrix AS.r. For a set S and an integer k, we define the set 5 + k (i + klj 5). Given a vector a E R" and a subset S S [n]], we let as denote a subvector of in the subset S. We define [A] = max (x, 0}. We let mmax (-) denote the largest singular value function and let Xmax (-) denote the largest eigenvalue value function.
2 A combinatorial reformulation of SCCA
This section introduces an equivalent combinatorial optimization reformulation SCCA. This reformulation serves as the foundation for developing two effective approximation algorithms.
2.1 An exact semidefinite programming representation of CCA
To begin with, let us focus on the classic CCA problem, which refers to SCCA without zero-norm constraints, as defined below:
max
{x.J Ay xx Ba S 1,y Cy $1}
(CCA)
#ER" DER"
This formulation of CCA can be regarded as quadratically constrained quadratic program concerning the variables the presentation of our results.
R xxm We next define three-block matrices of size (n + m) below that aid in
y
0
A/2
B 0
0
AT/2
A
/2
0
B
0
C
By introducing size-(n + m) matrix variable X
and removing the rank-one
y
constraint on X, we can obtain an SDP relaxation of (CCA), as described below
for (xx)
tr Bxx) < 1, čx $1
max
(SDP Relaxation)
X XES tm
3

---

Next, let us present key lemma regarding properties of block matrices being positive semidefinite, fundamental for reformulating the SCCA.
B
A C
Lemma ([16]) For any symmetric matrix
E Satmm, the followings equivalent:
AT
(i) The block matrix is positive semidefinite;
(ii B E S2, (I (B-BBB) = 0, C - A B A E S4; and
(iii) C $4, -C-CC' A B AC E
Inspired by Lemma 1, we hereby establish the equivalence between CCA and its SDP Relaxation. Remarkably, both of these problems achieve the same optimal value, namely max (v Bi Av)...
Proposition 1 For the CCA problem, we have the following results.
(i) Both CCA and its SDP Relaxation have optimal value Fmax BiAVCt):
(ii) A pair of optimal solutions (x", .y") CCA satisfies
x = Biq, y² =V=Vp.p.
P where q RR, RD denote pair of leading singular vectors of matrix v AVACI and (ili) An optimal solution X to the SDP Relaxation is
T
2"
X
y
y
Proof. See Appendix A.1.
Proposition motivates the following observation on the optimal values of CCA and SCCA.
Observation 1 The optimal value of CCA is upper bounded by 1, is the optimal value of SCCA.
It is noteworthy that the results presented in Proposition are established through distinct method- ology. This methodology leverages the positive semidefinite condition block matrices, as shown in Lemma I, and incorporates duality theory. This approach differs from most prior research [31, 37, 44], which proved Part (i) of Proposition by relying on the singular value decomposition and assuming that matrices B and C' are positive definite (i.e., full rank). To the best of our knowledge, [10] showed parts (i) and (ii) of Proposition for a special low-rank CCA problem, where the authors assumed that the covariance matrices defined as A UV B UU and C' VV Remarkably, Proposition extends this result to a more general scenario where B and C' are not constrained to be strictly positive definite and A is not constrained to directly depend on B, C, allowing for rank deficiencies and flexible data structure.
2.2 An equivalent formulation of SCCA
In this subsection, we transform SCCA into combinatorial optimization problem, according to the insights provided by Proposition
Theorem SCCA is equivalent to the following combinatorial optimization:
Tmax (V(Bs,ss)) As, V(Cs
max
(1)
Proof. See Appendix A.2.
The combinatorial formulation (1) presents significant computational difficulties when attempting to solve SCCA. The primary obstacles are two-fold: first, simultaneously selecting submatrices from the matrices A. B, C' requires sophisticated optimization across multiple dimensions. Second,

---

the selection criterion is particularly complex, as it involves optimizing the largest singular value of the product of the selected submatrix of A and the square root of pseudo-inverse submatrices of B and C. These complexities necessitate effective optimization solution procedures to address the high-dimensional and non-convex nature of the problem.
Motivated by Theorem I, we customize the greedy and local search algorithms for SCCA (1) that has been widely used in the literature solve special cases of SCCA, such as sparse PCA and sparse SVD in literature (see, e.g., [27, 28J). The detailed implementations can be found in Appendix B.
3 Low-rank SCCA
B A A
In practice, it is common that the sample covariance matrix
C exhibits low-rank characteris-
tics. This phenomenon is especially prominent when dealing with high-dimensional, low-sample size data, e.g., the real gene expression data in [41]. In this section, we study two special cases of low-rank SCCA and their computational complexities. Specifically, we develop polynomial-time exact algorithm of complexity On + m²) for solving SCCA to global optimiality when sparsity levels (i.e.,& $1 and s2) exceed or equal the ranks of B and C. Besides, we recast SCCA into mixed-integer convex quadratic programming when matrix A is rank-one.
3.1 Special Case I: SCCA with low-rank covariance matrices
In this section, we show that the computational complexity of SCCA is contingent upon the ranks of the covariance matrices B and C. To be more precise, when the sparsity level 8 (or 82) is equal to greater than the rank (or f' of the covariance matrix B (or C), the imposition of a zero-norm constraint over a (or y) in SCCA becomes redundant. Consequently, lower ranks in the covariance matrices correspond to better computational complexity in solving SCCA.
Theorem Suppose r = rank(B) and f rank(C), then SCCA takes a complexity of On Onn"-1m 1 nn-1 + m 1. The following results hold:
(i) When 81 2 r and 82 2 f, the SCCA problem is equivalent to CCA, i.e.
v*
max =ER"" yER
(a: T Ay: : T Bæ S 11, Cy $ 11;;
(2)
(ii) When 81 2 r and 82 < i, the SCCA problem can be reduced to
v² max
{x {x
Ay: Ay:aa x. Bæ S 1, Cy S 1, 1, S $2)
(3)
*ER" M
(ii) When 81 r and 82 2 f, the SCCA problem can be reduced
6"
max #E yERm
Tyyy: x Bx S 1, Cy S 1, |2/10| S $1
Proof. See Appendix A.3.
The results in Theorem 2 build the covariance structure of the data matrix. Specifically, if B and C are of rank r' and f, respectively, there are only and f linearly independent vectors in the subspaces corresponding B and C. Thus, the cosine of the principal angle can always be represented by these and f vectors. As result, the canonical directions of CCA consist of only and f nonzero elements. We further make the following remarks about Theorem 2:
Theorem 2 implies the complexity of solving SCCA, as summarized in the corollary below.
(ii) Inspired by Part (i) of Theorem
also develop polynomial-time exact algorithm yielding an optimal solution to SCCA (1) when 81 2 and 82 2 f. The detailed implementation can be found in Algorithm 1, which successfully solves some large instances with up and m = 2, 149 variables in seconds in our numerical experiments; and
172 672
(iii) The proof of Theorem 2 implies that CCA always admits an optimal sparse solution (a* y satisfying ||0: < and | llo < A. We show in Proposition that the SDP Relaxation of CCA exact. Therefore, as side product, we provide the krowt sufficient condition about (i.e., 2 and s2 2 f) when the convex SDP Relaxation matches SCCA.
5

---

Corollary Suppose = rank( and ē = rran(()) C). There exists algorithm that can find an optimal solution to SCCA O(n"~1m 1) time complexity.
Proposition 2 Suppose rank( B) and rank(C)). Then Algorithm 1 returns optimal solution to SCCA (1) in On + m²) time complexity when $1 2 r and $2 2 f.
Proof. Following the proof of Theorem 2, optimal to SCCA (1). In addition, the Step of Algorithm needs computing the eigendecomposition of matrix E ST. which takes a time of (n²)) Given a matrix Q E (*-)( also takes time of (n))) to find its (n - r) linearly independent rows at Step 3 through the QR decomposition [19]. Hence, Algorithm takes a complexity of O(n + m²).
show that the output solution of Algorithm is
Algorithm An exact algorithm for SCCA (1) when 81 and 82 2
1: Input: Matrices A Rmxn B Sth C E S and integers E [r, $2 [f,
2: Compute the eigenvectors Q E R (n-r) of B that correspond to its (n r) zero eigenvalues,
3: Find (n - r) linearly independent rows in Q, and collect their indices into subset T S [n]
4: Perform the same procedure on matrix C to obtain the subset T2 S [m]
5: Define the subsets Si
[n] TT and S2 [m] \ T2. and compute
v² max (V (VBst Asi s; (Cst.s;)
6: Output: An optimal solution (1) and optimal value o*
3.2 Special Case II: SCCA with a rank-one cross-covariance matrix
In this subsection, we study the other interesting low-rank special case of SCCA where the cross- covariance matrix A is rank-one. For this special case, we prove its NP-hardness with reduction to the sparse regression problem. We further demonstrate that rank-one SCCA can be simplified to solving two Mixed-Integee Integer Convex Quadratic Programs (MICQPs) which can be more scalable than directly solving SCCA. Our numerical findings confirm this improved scalability.
We observe that SCCA can be separable over variables æ and for the rank-one A. In fact, suppose that A ab" then SCCA is equivalent
e"
Tab ab y x Bæ 11 Cy s Cy
1,11///o
S $1 11 S $2)
(5)
EER" WER",YER"
which can be equivalently the product of the optimal values of the following two subproblems:
Ux max {a x. Ba < 1, ||a|| |oo S $1}, *ER"
(6)
by max (b y: Cy < 1, ||yl|o - $2) MERm
TCy
That is, the identity e" U2 vy holds. Next, show that each subproblem in (6) can be reduced to the classic sparse regression problem [1, 33] and is thus NP-hard as shown below.
Theorem When matrix A = T is rank-one, each maximization problem in (6) is NP-hard.
Proof. See Appendix A.4.
Theorem 3 links the maximization problem (6) and the well-known sparse regression problem, implying that even solving the rank-one SCCA problem (5) is NP-hard. However, also motivates us to adapt existing mixed-integer optimization techniques from sparse regression (see, e.g., [1, 4, 43]) tackle each subproblem in (6). By introducing binary variables to model the zero-norm constraint, we derive equivalent MICQP formulations for subproblems (6) in Appendix C. There are two types of formulations depending on whether matrices B and C are positive definite, which build on the Big-M and perspective techniques, respectively.

---

Reformulating SCCA as a mixed-integer semidefinite program (MISD))
While the combinatorial formulation (1) is elegant in its structure, it poses significant challenges when attempting to solve it to optimality using branch-and-bound based methods. To fill this gap, in this section, derive equivalent MISDP formulation for SCCA, amenable for developing exact methods.
) First, it is noted that an optimal solution (æ",y") to SCCA is always bounded that satisfies || I1 < M1 and "1 S M2, where we specify the construction of the coefficients M₁ and M2 in Appendix C.1. Such bounds essential to the derivation of the MISDP. It is convenient to introduce the following notation about {M [e]
MR = M1, Vi E [n], Ma M2, Vi E [n + 1, m...
Theorem 4 The SCCA is equivalent to the following MISDP:
(tr(AX) tr (B( S 1, txx( X1 Ma4, Vi In (n+m)) ml}. (7)
XES
#E2
where the feasible set is defined as Z = f2 {0, 10.1) Eie(n) 24 $1, Exenntinm 82).
Proof. See Appendix A.5.
Note that the proposed MISDP formulation (7) is of size (n + m) x (n+ + m) since our matrix variable
X replaces
in SCCA.
y/
We have formulated SCCA as a mixed-integer convex optimization problem in Theorem 4. Unfor- tunately, no commercial solvers can efficiently solve MISDP problems. We derive an equivalent mixed-integer linear program of SCCA with exponentially many linear constraints and efficient separation oracle based on the approach introduced by [15], which allows us to develop a tailored branch-and-cut algorithm. First, by separating the binary variables z, we rewrite the MISDP (7) as
max {u S f(z)), 2
(8)
where the function f(z) defined as
f(z) = max EEST
(r((A) tr(Bx) & (,,x)( $1, S Masi Vi E [n [n+ml]
For any feasible solution E Z of the problem (8), by leveraging the concavity of function f(),, the linear inequality
S f()) a)()) (=-
cuts off the solution unless it happened to be optimal in (8), which paves the way for delayed cut- out-generation procedure within a branch-and-bous
framework. As the linear inequality of the above type needs be added dynamically given different solutions 2 at each iteration, it calls for an efficient evaluation of function f(2) and its subgradient. To speed up the computation, we derive the closed-form expression for both of them. The detailed derivations can be found in Appendix D).
Strategies to improve computational speed in practice: First, we provide a variable- fixing method that can identify some binary variables of the MISDP (7) being one at optimality. Removing these pre-selected variables from the feasible set reduces the problem size of SCCA. Second, we enhance the branch-and-cee algorithm with a high-quality warm start solution obtained from the local search algorithm. Third, by relaxing the binary variables in the MISDP (7) to be continuous or computing CCA, obtain upper bound of SCCA, and the gap between this bound and the local search output gives an initial gap at the root node. Finally, at each iteration, the branching node is selected based on its potential to decrease the current upper bound instead of random branching.
5 Numerical results
This section tests the numerical performance our formulations and algorithms on synthetic and real data. All the experiments are conducted in Python 3.6 with calls to Gurobi 9.5.2 and MOSEK 10.0.29 on a PC with 10-core CPU, 16-core GPU, and 16GB of memory. The codes and data used in experiments are available at https: h github..... com commyoonchunli- 1aeelll--11///// 13/SCCA, .it..
7

---

5.1 Experimental setup
Synthetic data generation: Before we present the empirical results, we first describe the properties of the synthetic data which shall be used throughout this section. By following [32], given parameters (n, m, $1. 82), we first symthetically generate positive definite matrices B E S and C E + by B = BB + I and CH = -ÒČT + I, respectively, where B and C consist of elements generated from a normal distribution (o 1). Then, we let A" E IR= XB' we C*, where we generate uniformly from (0, 1), and vectors
are generated from a normal distribution ((, 1) that satisfy ||u||o |/e||o = 82, u B²u and e7
"" === Next, we sample N 5, 000 data samples A") A
00. from a normal distribution .V
B"
C² ) and compute their sample covariance matrix to
(At)T
obtain the testing data
T
C
To obtain comprehensive understanding of the overall performance of our algorithms, we further conduct experiments on six UCI datasets [5] with sizes ranging from 34 to 385 variables. The dataset is split into the first v. variables and the remaining
Real data:
variables construct the sample covariance matrices A, B, C. Besides, we examine the performance of the proposed algorithms on the real breast cancer dataset [8] that contain on each dataset is summarized in Appendix E.
19, 672 and = 2, 149 variables. The information
Throughout, the computational time is in seconds, the time limit is one hour, and the dashed line "L" denotes the unsolved case within the time limit. Note that we let LB denote the lower bound obtained from the approximation algorithm, and we let UB denote the upper bound obtained from convex relaxations of SCCA. Besides, we define gap( % > 100 x (UB e²) 3/v" to be the optimality gap. and we replace v* with the best lower bound when 8r is not available. We define MIPGap( % ) to be the gap of exact algorithms at termination. Notably, the complexity analysis of the SCCA problems in Section indicates that its solution process depends on the ranks of the data matrices. Therefore, present the numerical results under both full-rank and low-rank cases for a comprehensive evaluation.
5.2 Illustration of the impact sparsity levels on SCCA
In this subsection, we apply the local search algorithm to evaluating the performance of SCCA against different sparsity levels 51 and 82. Specifically, for given dataset, compute the ratio of correlations between SCCA and CCA for various $1, $2 parameters. We test the real UCI data and synthetic data, and the results displayed in Figure and Figure 2. This visualization provides insights for the maximum sparsity SCCA can achieve while maintaining the correlation of full data. For the real UCI data, SCCA almost recovers the correlation of CCA when 81 n/2 and 82 R m/2.
Figure 1: On UCI data with n, m 28, 29
Figure 2: On synthetic data with n, m 80, 80
5.3
Solving SCCA with full-rank matrices
The numerical results on synthetic and real data are presented in Table I and Table 2, respectively, which include multiple instances with various parameters (n, m, $1, 82). First, we observe that the greedy and local search algorithms are scalable, and their outputs match the optimal values for most solved testing cases. That is, they achieve zero optimality gaps on these cases. In the "Convex relaxation" column, we compute an upper bound by solving either the continuous relaxation of MISDP (7) CCA, and we use CCA for 2 40 and > 40 cases for efficiency. It is seen that the upper bound maintains an optimality gap at most 2. 2.78%. Then, we apply the branch-and-cut algorithm to solve SCCA to optimality, which can handle the case up to a size of = 120 in
8

---

Table 1. The unsolved case in Table may be because the initial gap is weak at the root node, implying that the branch-and-a algorithm explores a considerable amount nodes before termination (see,
e.g. n 80 and 81 $2 = 10). Hence, the branch-and-cut algorithm may struggle with large-scale instances with weak initial gaps.
Table 1: Evaluation of algorithms synthetic data
Greedy
Local search
Convex relaxation
Branch-and-cod
71
m
81
82
LB
time
LB
time
UB
gap(%)
time
MIPGap((%
time
20
20
0.244
0.01 0.244
0.02
0.256
1.23
0.244
0.00
9
20
20
10
10
0.275
0.02 0.275
0.04
0.278
1.23
0.275
0.00
4
40
40
0.695
0.03 0.695
0.05
0.701
0.83
0.695
0.00
1
40
40
10
10
0.705 0.06 0.705
0.12 0.708
0.45
0.705
0.00
7
60
60
0.885
0.04 0.885
0.09 0.887
0.28
0.885
0,00
1
60
60
10
10
0,884
0.09 0.884
0.19 0.887
0.28
0.884
0.00
8
80
0.633 0.06 0.633
0.12 0.650
2.78
0.633
0.00
1705
80
80
10
10
0.631
0.13 0.631
0.26 0.644
2.02
0.643
1,85
100
100
0.942
0.09 0.942
0.16 0.944
0.23
0.942
0,00
4
100
100
10
10
0.940
0.17 0.940
0.34
0.942
0.23
0.940
0.00
15
120
120
0.845
0.11 0.845
0.27
0.853
0.97
0.845
0.00
924
120
120
10
10
0.848
0.21 0.848
0.43
0.856
0.85
0.855
0.80
Table 2: Evaluation of algorithms on six UCI datasets
Greedy
Local search
Convex relaxation
YT
81
82
LB
time
LB
time
gap( %)
time
MIPGap(S% %)
time
17
17
5
0.970
0.01
0.971
0.04
0.984
1.35
0.980
0.00
17
10
0.981
0.02
0.983
0.14
0.984
0.09
0.983
0.00
28
29
5
0.761
0.02
0.761
0.05
0.769
1.11
0.761
0.00
6
28
29
0.766
0.04
0.766
0.07
0.769
0.45
0.766
0.00
32
32
5
0.991
0.02
0.991
0.04
0.993
0.17
0.991
0.00
1
32
10
0.992
0.04
0.992
0.12
0.993
0.05
0.992
0.00
38
39
5
1 0.02
0.02
0.06
0.16
0.00
0.01
0.00
2
39
1 0.04
0.05
0.07
0.47
0.00
0.01
0.00
2
64
64
5
0.998
0.05
0.998
0.39
0.999
0.07
0.998
0.00
1
64
64
10
10
0.999
0.09
0.999
0.59
0.999
0.02
0.999
0.00
2
192
193
5
1
0.21
0.46
0.00
0.00
36
192
193
10
10
1
0.36
0.68
0.00
0.00
37
5.4
Solving SCCA with low-rank matrices
Despite the high dimensions of the breast cancer dataset [8], the resulting sample covariance matrices B and C have rank of 89, i.e., solving SCCA that returns optimal solutions and values in one second, as shown in Table 3. If s1 < and $2 < f, Algorithm cannot applied and the proposed branch-and-cut algorithm is hard to scale to this dataset. Hence, we only consider using approximation algorithms to solve SCCA for small 81 and 82 cases Table 4. To be specific, we randomly sample n and m variables from the breast cancer data to construct testing cases. As displayed in Table 4, the greedy and local search algorithms run fast, and the local search algorithm slightly outperforms the greedy output.
89. When 81 2 and 82 A, we apply Algorithm 1 to
Table 3: Solving SCCA by Algorithm 1 on breast cancer data when 81 2 r and &2 2
Table 4: Approximation algorithms breast
cancer data when 81 S and 82 <
Algorithm
Greedy Local search
m
D" MIPGap(SS %) time
m
82
LB time LB
time
I00)
100
0.00
100
100
10
0.983 0.17
0.17 0.995
0.63
150 150
0,00
I
500
500
10
10
0.991
0.993
6
19,672 2,149
200
200
0.00
800
800
10
10
0.993
0.993
37
250 250
1
0.00
1
1000
1000
20 20
12
146
The SCCA (5) problem with a rank-one matrix can be more tractable, as we can equivalently decompose it into two MICQPs (see Appendix C). By approximating A with rank-one matrix

---

including leading singular value and vectors, Table 5 presents the numerical results for solving rank-one SCCA (5). The continuous relaxation of the MICQPs also provides an upper bound and is denoted by the Perspective relaxation in Table 5. We see that the perspective relaxation is computationally efficient and yields small optimality gaps. Besides, we can directly solve two MICQPs below via Gurobi to find the optimal value of rank-one SCCA (5), i.e., v" Ug where the performance can be found in the last column of Table 5. We can address the rank-one SCCA (5) problem up to size 200 200 within one hour, improving the problem-so sollem--olving capacity compared to the size-128 x 120 full-rank SCCA (5) Table 1. However, should be pointed out that the SCCA may not be mixed- integer convex quadratic representable in general.
Table 5: Solving SCCA on synthetic data with rank-one matrix A
Greedy
Local Search
Perspective relaxation
SCCA
7
m
81
$2
LB
time
LB
time
UB
gap (6)
time
(9)))
time
50
50
0.753 0.04
0.753
0.07
0.757
0.57
0.753
0.00
I
50
50
10
10
0.753
0.07
0.753
0.15
0.757
0,46
0.753
0.00
9
100
100
0.975
0.09
0.975
0.16
0.977
0.21
0,975
0.00
2
100
100
10
10
0.966
0.17
0.966
0.33 0.969
0.35
0.966
0.00
25
150
150
0.850
0.15
0.850
0.26 0.859
1.08
0.850
0.00
9
150
150
10
10
0.857
0.27
0.857
0.53 0.867
1.13
0.857
0.00
167
200
200
0.810
0.23
0.810
0.37
0.828
2.19
0.810
0.00
55
200
200
10
10
0.816 0.39 0.816
0.74
0.833
2.11
2
00816
0.00
1692
5.5
Experimental comparison of SCCA algorithms
This section compares the proposed local search algorithm with the SCCA methods of [10, 37, 41] in correlation (Corr) value, the zero norm of æ (denoted by S.æ), the zero norm of y (denoted by S.y), and running time. The computational results on synthetic, UCI, and breast cancer data are presented in Table 6, where we highlight the best correlation and sparsity results in bold. Unlike the local search algorithm, these existing methods do strictly enforce the exact sparsity requirement, i.e, the zero-norm constraints the best sparsity for nearly all testing cases. More importantly, the local search algorithm yields larger correlation value than these existing methods in 16 out of 22 testing cases. Finally, the running time of the local search algorithm dominates that of [10, 37].
variables y. Consequently, the local search algorithm achieves
Table 6: Comparison of SCCA algorithms in Correlation, sparsity, and time
Local search
[4]]
[37]
[10]
n
Corr S.r: S.y time
Corr
S.r
S.y time Corr
S.c. S.y time Corr
S.r
S.y time
20
20
5
5
0.244
5
$
0.04
0.01 0.239
13
14
0.256
18
16
15
20
20
10
0.275
10
10
0.212
8 0.01 0.259
19
14
0.278
18
18
12
40
40
5
0.695
5
0.08 0.594
23
30 0.03 0.659
26
19
0.696
17
18
13
40
40
10 1.70.
10
10
0.17
17
15 0.01 0.660
19
22
0.704
16
20
15
60
60
5 0.885
5
5.133
37
45 0.01 0.865
27
25
3 0.880
10
8
23
60
60
10 0.884
10
10
0.27 0.777
33
36
0.01 0.847
31
31
0.879
12
15
23
80
80
5 0.633
5
5..17
0.534
55
43
0.606
36
32
0.634
33
23
34
80
80
10 10663
10
10
0.37
0.528
53
0.02 0.603
0.603
29
41
0.632
41
32
100
100
5 0.942
5
5..22
0.813
58
63 0.02
46
33
0.941
5
5
38
100
100
10 0.940
10
10
0.49
0.768
54
0.02 0.884
47
37
0.938
10
10
37
120
120
5 0.845
5
5
0.681
83
74 0.02 0.804
37
43
0.833
10
8
47
120
120
10
0.848
10
0.59 0.720
0.02 0.821
39
36
0.840
12
17
17
5
0.971
5
5
0.044
9 0.01 0.742
10
8
0.970
14
16
15
28
29
5
0.761
5
5.05 0.704
23
29 0.01 0.667
3
0.744
24
19
15
32
32
5
0.991
5
5.004 0.730
31
23 0.01 0.904
15
10
2 0.906
18
15
43
38
39
5
5..15
0.43 0.997
38
23
32
29
64
64
5
0.998
5
5
0.38 0.897
64
64 0.01 0.990
7
6
0.997
33
31
19
192
193
5
5
0.45
0.103
82
0.21 0.856
13 12
10
6
45
100
100
1090
10
0.63
0.63
0.936
18
41 0.01 0.686
42 43
0.952
75
76
36
500
500
10
10
0.993
10
10
6.9777
78 200 0.78 0.871
173 371
31 0.935
74
44
50
800
800
10
10
0.993
10
10
37
0.974
133
316 1.94 0.879
280
526
50 0.990
84
63
57
1000
1000
10
10
0.995
10
10
11
0.980
166 401
7.30 0.848
401 558
58 0.985
80
59
60
10

---

Acknowledgments and Disclosure of Funding
Santanu S. Dey would like to gratefully acknowledge the support from ONR grant N00014-22-1- 2632. Yongchun Li (when was a graduate student) and Weijun Xie were supported in part by the National Science Foundation grant # 2246417 and ONR grant 180011-24-1-2000 The authors also would like to gratefully acknowledge undergraduate researcher Quill O Healey for his help with the initial version of branch-and-bour codes.
References
Alper Atamturk and Andres Gomez. Rank-one convexification for sparse regression. arXiv preprint arXiv:191.10333 2019.
[2]
Dimitris Bertsimas and Ryan Cory-Wright. Solving large-scale sparse PCA to certifiable (near) optimality, The Journal of Machine Learning Research, 23(1):566 600, 2022.
[3] Dimitris Bertsimas, Angela King, and Rahul Mazumder. Best subset selection via modern optimization lens. The Annals of Statistics, 44(2):813 852, 2016.
[4] Dimitris Bertsimas, Jean Pauphilet, and Bart Van Parys. Rejoinder: Sparse regression: Scalable algorithms and empirical performance. Statistical Science, 35(4):623-624, 2020.
[5] Catherine L Blake. UCI repository of machine learning databases. http:///ww. ics. uci. eduf mlearm/MLRepostonn html, 1998.
[6] Siu On Chan, Dimitris Papailliopoulos, and Aviad Rubinstein. On the approximability of sparse PCA. In Conference on Learning Theory, pages 623 646. PMLR, 2016.
[7] Mengjie Chen, Chao Gao,, Zhao Ren, and Harrison H Zhou. Sparse cca via precision adjusted iterative thresholding. arXiv preprint arXiv: 131 1...3111.1166 1.6186, 2013.
[8] Koei Chin, Sandy Derries, Jane Fridlyand, Paul Spellman, Ritu Roydasgupta, Wen-Lin Kuo, Anna Lapuk, Richard Neve, Zuwei Qian, Tom Ryder, et al. Genomic and transcriptional aberrations linked to breast cancer pathophysiologies. Cancer cell, 10(6):529 541, 2006.
[9] Agniva Chowdhury, Petros Drineas, David P Woodruff, and Samson Zhou. Approximation algorithms for sparse principal component analysis. arXiv preprint arXiv:2006. 12748, 2020.
[10] Delin Chu, Li-Zhi Liao, Michael K Ng, and Xiaowei Zhang. Sparse canonical correlation analysis: New formulation and algorithm. IEEE transactions on pattern analysis and machine intelligence, 35(12)30050- 3065, 2013.
[1]] Alexandre d' d'Aspremont. Francis Bach, and Laurent El Ghaoui. Optimal solutions for sparse principal component analysis. Journal Machine Learning Research, 9(7), 2008
[12] Alexandre d' A'Apremont, Laurent Ghaoui, Michael Jordan, and Gert Lanckriet. A direct formulation for sparse PCA using semidefinite programming. Advances in neural information processing systems, 17, 2004.
[13] Santanu S Dey, Rahul Mazumder, and Guanyi Wang. Using l-rrelxation and integer programming to obtain dual bounds for sparse PCA. Operations Research, 7013):191--1922, 2022.
[14] Santanu S Dey, Marco Molinaro, and Guanyi Wang. Solving sparse principal component analysis with global support. Mathematical Programming, 199(1-2)441-459, 2023.
[15] Marco A Duran and Ignacio E Grossmann. An aproo-appro algorithm for a class of mixed-intege nonlinear programs. Mathernatiaal programming, 36:307-339, 1986.
[16] Jean Gallier al. The schur complement and symmetric positive semidefinite (and definite) matrices (2019). URL https://www. cis, upenn. edufjean/schur-cong pdf, 2020.
[17] Chao Gao, Zongming Ma, Zhao Ren, and Harrison H Zhou. Minimax estimation in sparse canonical correlation analysis. 2015.
[18] Chao Gao, Zongming Ma, and Harrison H Zhou. Sparse cea: Adaptive estimation and computational barriers. 2017.
[19] Colin R Goodall. 13 computation using the qr decomposition. 1993.
[20] David R Hardoon and John Shawe-Taylor. Sparse canonical correlation analysis. Machine Learning, 83:331-353. 2011.
[21] Hynek Hermansky and Nelson Morgan. Rasta processing of speech. IEEE transactions on speech and audio processing, 2(4):578-55) 1994.
[22] Ronald R Hocking and RN Leslie. Selection of the best subset in regression analysis. Technometrics, 9(4):531-540, 1967.
[23] Harold Hotelling. The most predictable criterion. Journal of educational Psychology. 26(2):139, 1935.
11

---

[24]
Hua Huang, Huiting He. Xin Fan, and Junping Zhang. Super-resolution of human face image using canonical correlation analysis. Puttern Recognition, 43(7):5532-2443, 2010.
[25] John NR Jeffers. Two case studies in the application principal component analysis. Journal of the Royal Statistical Sociery: Series C (ApplieedStarristees)) Statistics), (6(3):225-366, 1967.
[26] Kim-Anh Lè Cao, Pascal GP Martin, Christèle Robert-Granié, and Philippe Besse. Sparse canonical
methods for biological data integration: application to cross-platform study. BMC bioinformatics.
10:1-17, 2009.
[27] Yongchun Li and Weijun Xie. Exact and approximation algorithms for sparse PCA. arXiv preprint arXiv:2008. 12438, 2020.
[28] Yongchun Li and Weijun Xie. Beyond symmetry: Best submatrix selection for the sparse truncated svd. arXiv preprint arXiv:2105.03/ 2021.
[29] Dongdong Lin, Vince D Calhoun, and Yu-Ping Wang. Correspondence between finri and snp data by group sparse canonical correlation analysis. Medical image analysis. 18(6):891-902 2014.
[30] Dongdong Lin, Jigang Zhang. Jingyao Li, Vince D Calhoun, Hong- Wen Deng, and Yu-Ping Wang. Group sparse canonical correlation analysis for genomic data integration. BMC bioinformatics, 14(1):1-16, 2013.
[31] Yichao Lu and Dean P Foster. Large scale canonical correlation analysis with iterative least squares. Advances in Neural Information Processing Systems, 27, 2014.
[32] Qing Mai and Xin Zhang. An iterative penalized least squares approach to sparse canonical correlation analysis. Biometrics, (53))733-744, 2019.
[33] Alan Miller. Subset selection in regression. CRC Press, 2002.
[34] Balas Kausik Natarajan. Sparse approximate solutions to linear systems. SIAM journal on computing, 24(2):227-234, 1995.
[35] Dimitris Papailiopoulos, Alexandros Dimakis, and Stavros Korokythakis. Sparse PCA through low-rank approximations. In International Conference on Machine Learning, pages 747-755, PMLR, 2013.
[36] Elena Parkhomenko, David Tritchler, and Joseph Beyene. Genome-wide sparse canonical correlation of gene expression with genotypes. In BMC proceedings, volume pages 1-5. BioMed Central, 2007.
[37] Elena Parkhomenko, David Tritchler, and Joseph Beyene. Sparse canonical correlation analysis with application to genomic data integration. Statistical applications in genetics and molecular biology, 8(1), 2009.
[38] Alexci Vinokourov, Nello Cristianini, and John Shawe-Taylor, Inferring semantic representation of text via cross-language correlation amalysis. Advances neural information processing systems, 15, 2002.
[39] Sandra Waaijenhorg, Philip C Verselewel de Witt Hamer, and Aeilko H Zwinderman. Quantifying the association between gene expressions and dna-markers by penalized canonical correlation analysis. Statistical applications in genetics and molecular biology. 7(1), 2008.
[40] Akihisa Watanabe, Ryuta Tamura, Yuichi Takano, and Ryuhei Miyashiro. Branch- mad-bound algorithm for optimal sparse canonical correlation analysis. Expert Systems with Applications, 217:1 19530, 2023.
[41] Daniela M Witten, Robert Tibshirani, and Trevor Hastie. A penalized matrix decomposition, with applications to sparse principal components and canonical correlation analysis. Bioxtatistics, 10(3)5155- 534, 2009.
[42] Daniela M Witten and Robert Tibshirani. Extensions of sparse canonical correlation analysis with applications genomic data. Statistical applications in genetics and molecular biology. 8(1). 2009.
[43] Weijun Xic and Xinwei Deng. Scalable algorithms for the sparse ridge regression. SIAM Journal on Optimization, 30(4):335933336 2020.
[44] Xinghao Yang, Weifeng Liu, Wei Liu, and Dacheng Tao. A survey on canonical correlation analysis. JEEE Transactions on Knowledge and Data Engineering, 33(6):2349 2368, 2019.
12

---

Appendices
A Proofs of technical results
A.1 Proof of Proposition 1
Proof. The proof includes three parts.
Part (i) To prove the equivalence between CCA and its SDP Relaxation, let us introduce the Lagrangian multiplies 01 2 0, 02 > 0 corresponding to two constraints in SDP Relaxation, which leads to the following Lagrangian dual problem
0 B
{0- 02 0 02 = a}= 0:200,20
min
min 8, 0,20,2200
01 + 02:
A
02
(10)
-
where the equation results from the definition of block matrices A, B, and Ć. Given the nonzero
matrices A * B, * 0, C' * and positive semidefinite matrices B > 0, ž 0, following
Lemma 1, must have BgC A (0, B) A/4 ž 0 and 81 B A A /4 = 0, implying that
either 0 = or 0g = is infeasible to the minimization problem above. That is, 0 and 02 >
must hold.
B A
A C
According to Lemma 1, the block matrix
is positive semidefinite, implying that (T
CCt)A = 0, BBBB 0. Then, it is easy to show
AT
- (--2C(02C)))
0, 0.
2
Given 01,0g and using Lemma 1, the result above allows us further simplify the right-hand side minimization problem in (10) to
min 20.8
{11 + 0g 40,0, ACTAT)
01 + 02 40,02 2 omax (VBiAVOT) O (VBIAVOH).
min 6, 20,8.20 20
where the first equation is because
40,0, ACTAT
+ 40 VA V QV AC AC'A'AAA
AC Q
40,02 2 Amax
= 40,02 2 Amax
(VCIATB'AVC))
40,02 0t
(VBiAVCt).
where we = QAQ"
denote the eigendecomposition of matrix B with containing all the
positive eigenvalues.
As result, the dual problem SDP Relaxation admits an optimal value of max (VBiAVC) which gives upper bound of the CCA and its SDP Relaxation. Next, we construct their optimal solutions, which exactly attain this upper bound. Thus, this upper bound is achievable and equals their optimal values.
Part (ii). For the CCA, let us consider a part of optimal solutions (x", ,y*) below
VBgg, y" VCPp.
with q E R" p E R denoting pair of leading singular vectors of matrix / AVACC First, (x",y") y²" is feasible to the CCA as
(x")T Bx" = q"
where the inequalities stem from the facts that I VBBB and Iz VCiCvVC.
13

---

On the other hand, according to the definitions of q. we can show that (x",y" is optimal to the CCA, i.e. (x") VVVA-VVVVAVC max (VBiAVCi)
(ax"'
xx"
Part (iit). In similar vein, can show that X
is optimal to SDP Relaxation
y
with the optimal value mnax (VBiAVCi)
A.2 Proof of Theorem
Proof. By introducing the subsets (Si, S2) to denote the supports of variables (æ, 3) in SCCA, then can remove the zero-norm constraints (I,, y) and reformulate SCCA as
Cs..y { {or T S, Bs, x 1, y 1 (11)
max S C m S Sil
max mERiS1
S. S2 PER|P2
Following from the Part (i) in Proposition I, we can show that for any subsets S S [n], S [m]. the following identity holds.
{ar As,.syy x Bs, x $1 Cs,,Cs,,s Ss $1}
max WER 111 VERISA!
(V(Bs..s)) As (
= dmax
Plugging the result above into the inner maximization problem in (11), we complete the proof.
A.3 Proof of Theorem 2
Proof. The proof is split into three parts.
Part (i). It suffices prove that CCA admits an optimal solution (x",y") satisfying ||=="lo S r and ly llo & f. Then, (xx, y²) is also feasible and optimal to SCCA, which implies the equivalence between SCCA and CCA.
First, according to Part (ii) in Proposition 1, we can obtain closed-form optimal solution (œ, ÿ) for the CCA. By adjusting (dr, ÿ). will construct new optimal sparse solution (x",y") satisfying || llo S and l Ilo I f.
For matrix B S we let {q: (qeee(r--] R" denote the eigenvectors corresponding to (n - zero eigenvalues of B. Thus, {qi (q:)ie(n-) are orthonormal. There exists size-(n subset S S [n] ((qi)))efpn-)) hie[n-]] are linearly independent, where (qi)s denotes the subvector of qi indexed by S for each E [n r]. As result, there exist a vector (71, 7n-r) such that
such that the subvectors {(q:)s
as = Σ w(q)ss
(12)
iE|n]
Let us now construct solution
sE[n-r]
where o = 0 for all i E S based on the equation (12) and |S| = n r, implying ||0*|| < r. In
addition, we show that the new solution x² is still optimal to CCA. First, feasible since
(x") B(x") = à Bd < 1,
where the equation due Bq: for all [n
r].
B
A
Given the positive semidefinite block matrix
uusin Part (ii) of Lemma 1, the identity
AT
C
II (BBBB A 0 is equivalent to Eie(n-)) 9:9, A 0. Then, for each E [n r], multiplying
14

---

q: on both sides of this equation leads to
qf
Σ [5 A) A - q. - qi A= JE[n-r]
where the result follows from q: qj 0 for any i 7 j. Then, we can show the optimality of the new solution x": (x*) Aÿ t Aø + Σ
= Ag.
:Ein-rl
Similarly, can also construct optimal sparse solution y" by leveraging ÿ and eigenvectors of zero eigenvalues of such that |/3/'|o S 52.
Therefore, there exists an optimal solution (æ", y") ) to the CCA whose zero norms are bounded from above by r, F, respectively. Adding the constraints ||a:||o S llyllo S f to the CCA does not affect the optimality, which gives equivalent formulation (2) of CCA.
Part (ii). Suppose that (ă, 3) denotes optimal solution problem (3). When $1 following the proof of Part (I), σ. we can construct another optimal solution x whose zero norm is bounded by
and (x", ÿ) is feasible and optimal to SCCA.
Part (iii). Similarly, we can reduce SCCA to problem (4). We thus complete the proof.
A.4 Proof of Theorem 3
Proof. Let us first consider the maximization problem over æ in (6), i.e.
U/2 max {a T Ja x: Bæ S 1, ||2/||| S $1}.
(13)
#e
Then, we derive combinatorial optimization reformulation of problem (13) based the result below.
Claim For any subset S C [n]]. max x. Bs,s S 1 = V
B ab
Proof. Given A ab" since the matrix
is positive semidefinite, using Lemma 1,
b aTa
C
the identity (I - Bs,s B (ssss)ssb"
must hold for any subset S. As a result, we have as
Bs,sBissas
vector is nonzero.
Next, the Lagrangian dual of the problem max si {afx: x Bs,s S 13 can be written as max {agar Bs,sæ 11 #ERIS
min max ag + t pa Bs,s #20 mERiS
a B Bs
min + #20
V a (Bs,s)
4p
where the second equation builds on the identity as - Bs 0 and optimal solution
Suppose that an optimal solution to problem (13) admits the support S According to Claim 1, we have
max V Va (Bs,)ss))aa V ag. (Bs (Bs-ss-)tas-. Sc
Ur
On the other hand, the Lagrangian dual of problem (13) can be written as
Ux S min max (a TaTan x + À Ax Bæ
||2|||a I 81}
AER; mERn
a (Bs,s)ta. tas
min ACR S8
max A +
41
a (Bs.s)
max Scin), Ss
V aa.. (Bs taas S Un-
4X*
15

---

where the first equation is due to Claim 1, the second inequality is by plugging the feasible solution X ya.. (Bs into minimization problem, and the last equation is from the optimality of subset S Since both left-hand and right-hand sides above equal Uz, the strong duality of problem (13) holds, and all the inequalities above must attain the equalities. That is, problem (13) equivalent to
min max {a "a"a x + X - Xx Bæ || S 81}-
x =ER"
Since the outer minimization is one-dimensional convex program that can be solved efficiently, as a result, for any given À > 0, the inner maximization is equivalent solving
max
Ax Bx
|| S $1}-
(14)
mER
Next, let us consider the NP-hard sparse regression problem (see, e.g., [34]), which admits
min BER
| - Uxll | $}
max
(2v Uz - x U UB ||0||o S s).
(15)
=gR
where data matrix U consists of observations of n variables and vector v denotes the corresponding response variables.
Suppose that the problem (14), let define XB = U and a 20 T Tr. Then using the singular value decomposition of matrix U, we that the following equation still holds.
as - Bs.s s, = 0, VS C [n].
Thus, for any given À > problem (15). This shows that problem (13) is NP-hard.
0, the maximization problem (14) is equivalent to the sparse regression
Similarly, the maximization problem over in (6) can also be reduced to the sparse regression problem.
A.5 Proof of Theorem 4
Proof. For the SCCA (11), according to Proposition 1, the inner maximization problem admits an exact semidefinite programming formulation. Using the variables E 2 to describe the set constraints SCCA (11), we can reformulate it as
= max max { (ir(Ax) Ir BX < 11,r((x 1
2E2 XES,
(16)
Xa(1 - 2;) = 0, vi E [m + n1}.
Proposition 3 shows that there is an optimal solution (x",y") to SCCA that satisfies ||x < M1
and |1y" 113 < M2. Based on this, we can construct an optimal solution (z*, X*) for SCCA (16) by letting
[I if 0 vi [m], zitz
{
if + if og 0
X
to if =
vi E [m),
3"
where the optimal solution X satisfies the following inequalities
x = (xt)² < M1 Vi E [m]. ((+nXi+n) (vt)² < My Vi E [m].
This allows to recast the SCCA (16) into an MISDP formulation (7).
B Implementations of greedy and local search algorithms
This section presents the detailed implementations of greedy and local search algorithms based on the combinatorial formulation (1) of SCCA.
C Mixed-integer convex quadratic programming reformulations
This section shows that each subproblem in (6) can be equivalently formulated by a MICQP. Therefore, SCCA (5) is tixed-integer convex quadratic representable when matrix A is rank-one.
16

---

Algorithm 2 Greedy algorithm for SCCA (1)
1: Input: Matrices A IR B St. C ST and integers #1 E [n]. 82 [m]]
2: Compute (²) E jml.l V (B.)) Ay
3: Define subsets $ = { and S2 = {j*}
4: for f. 2, max 81, 82) do
5: i S (11, 82) then
6:
E argmax |g]]) mmax
7:
Update $1 $1 0(*) j" j mmax
(BBs,,s)) As (Ss
8:
9:
else if 81 S 82 then
j argmaxzelm maxx (SsSsss))
11:
Update $2 S2 U {jt}
12: else
1 arrmaax |E|n|| max ( (B As,ui,, /
13:
Update $ S1 U {i
15:
end if
end for Output: S1
17:
Algorithm 3 Local search algorithm for SSVD (1)
1: Input: Matrices A m2x"" B E S C E S and integers E [n]. $2 E [m]
2: Initialize ($1, 32) as the output of greedy Algorithm 2
3: do
4: for each pair (11, $1 ([m] $1) do
5: if maxx
(BsuudiN())) SLUG)))))) (Cso,8))
Tmax (V As, /
(Cs,,s)) then
6:
Update $₁ $1 U {i1} {i1}
7: end
8: end for
9: for each pair (12, E S2 x ((m) \ S2) do
10: if
Tmax
B (BSutti)(i)))suu AustaauuuunaaaAAuusssssaaaaa Assua)M V (Cs,.s))
Tmax (V ) A As (C,,,s))) then
Update S2 S, (jz) (12]
12:
end if
13:
end for
14: while there is still improvement
15:
Output: S, S2
C.1 Valid inequalities for SCCA
Before deriving the formulations, we first prove that there exists a bounded optimal solution (x".y") of the SCCA. To be specific, we show that there exists an optimal solution (x" y²) of the SCCA satisfying the constraints > < Mi and I [1 < M2, where M1 and M2 are finite-valued parameters.
Proposition 3 The SCCA admits an optimal solution (a" , 11") satisfying 1|at S Mi and 1 S
M2, where M1 = 1/>,(BB) (B) (B), CC) being the smallest nonzero eigenvalues of matrices B,C and 8min RR) being the smallest nonzero singular value of all the submatrices of the zero eigenvectors of matrix R.
- 1 (B)) and M2 (C) +1/(2((C) miim (C) with
17

---

Proof. Let (x", y²) denote an optimal solution to SCCA. We bound ||~||2 first and the same technique can also straightforwardly applied bound 1 122
For matrix B E S4 of rank r, we let (q))e(m) E IR" denote the eigenvectors corresponding to n eigenvalues À of B such that A 2 2 Ar > Ar+1 = _... An O. Thus, (q:iven) are orthonormal and span the space of I Hence, there exists a E R" such that x² = -ie(m) a:gi
Given that (x*)² Bx* 1, we have
E CaNsI iE|r]
Hence, the values of {ar [e(r) are bounded. On the other hand, let us define a subset S S [m]] of size at most 81 such that 2; * for each E S and zj = for each j [n] \ S. Then for each j E [n] \ S, we arrive at the following linear system:
Σ jE|++IM
ووره = Σ a.q.
(17)
sEIrl
where d: denote a subvector of zi with indices [n:] \ for each E [n]. For fixed {as since the linear system (17) is nonempty, let Qa q denote its minimal linear subsystem such that
submatrix is non-singular and the index set S of is a subset of [n] \ S. Thus, we can construct
an alternative solution á such that
i E [r]. i S otherwise,
d;
Q 9)
0,
and a Eie(n) a.q; According Lemma have
a B& S 1, Ay" = (x*) Ay
i... (ft, y²) is also optimal to SCCA. Hence,
||قع|| S
12 1011 +
kE(r)
Note that Eiety of 1/>, and
1
912 < QQ 12
Smin B XS
where Smin () denotes the smallest nonzero singular values of all the submatrices of [q++1.... 9n). In summary, we have
| V1/2, + 1/(2p (B)).
This completes the proof.
The proof of Proposition 3 is straightforward in the case when B and C' are of full rank as in this case the feasible region is a bounded set. In order to prove the result in the case when B is not full-rank, one has to show that it is possible to construct sparse solutions that are not "too far" away.
In fact, the bounds M1, M2 in Proposition also hold for any given feasible subsets (S1, S2) of SCCA (1).
Corollary 2 For any given feasible subsets (S1, S2) of 1, there exists SCCA feasible solution (x, y) such that the supports of æ, y are S,, S2. respectively and we have that || 2 < M1 and l < My, where M1, M2 defined in Proposition 3.
C.2 Equivalent mixed-integer convex quadratic program of rank-one SCCA
When matrix A is rank-one, let us focus on analyzing the subproblem over in (6), i...
Ux max {a xx Bæ < 1, || - $1). R
(18)
18

---

Then the second subproblem over in (6) simply follows. According Corollary 2, introducing the binary variables 2¹ E [0, 13" reformulate the problem (18) as
aa axz:x' B 1,,, mER" E(0,1)"
Vie [n], Σ + $ iE(n)
1/2
max
When matrix B is positive definite, there is a positive vector E R and a positive semidefinite matrix B such that B = B + Diag(b). Given this equation, by leveraging the perspective techniques (see, e.g., [1, 43]), we can derive another equivalent MICQP formulation of the problem (18):
TT x: : Bx +
Σ 44 14 S m Vi [n],
Σ EE
2 S
2/2
max ø (0.1)"
sE/n]
which is often stronger than the above formulation.
D A branch-and-cut algorithm with closed-form cuts
By dualizing the inner maximization problem over X in the MISDP (7), in this subsection, we derive equivalent mixed-integer linear program for SCCA, which motivates to develop branch-and-cut algorithm.
By introducing the Lagrangian multipliers (01, 0z A), the Lagrangian dual of the maximization problem (9) can be written as
f(z) min 0, 20,0220, AER
max tr(Ax) - 01 (rtr( 02 tr(xx) + 01 + 02.
XEST
Σ ic(n+mm
X +
Σ
MiMizzi
(19)
iE(n+mm
min 0, 20,0220, AERTI
02
Σ
A:Maz::
-AT/2
B
-A/2 0gC
- -Diaag(A)
4E(n+m]
where the strong duality holds due to the function (z) being concave, bounded, and thus continuous the set 2 and Slater condition holds for any interior point in the set 3.
Below, we derive the closed-form expression of the function f(z) with the given binary variable Z. This allows reformulate SCCA (8) as mixed-integer linear program with exponentially many linear constraints and an efficient separation oracle.
Proposition 4 The SCCA (8) is equivalent to
0" max 2E2,0
ViU max
(V
L Ast. V
(20)
X VS S [n] S s1, S2 C [m], |S2l 82 $2).
(S,ta))
where for a pair of subsets (2), the scalar X is defined as the largest positive eigenvalue of
matrix D D D2 - Dy with
8 B Bs.
As
D2 = (
07 Bs.
D =
A /2,5//2
87 O7
AT -A $2.1n11,,12
07 03
and
87 Bl]/sssis
A (n) Am/)SS..(m/////2)
D3
- -A (1
03 [mC[m])sS...mm)
where 0f = =0;- = xmax (V(Bs,,si) JT A / (Cs),s,)T) /2.
19

---

Proof. First, for any binary variable z E 2, suppose S1 = {i 2; = 1,
[n]], S2 = {i
2 Vi + I, + m]}, and T - [n + m] denotes the support of z. Then following the
x x
proof of Proposition 1, we can construct a rank-one optimal solution X
to the
y
y
maximization problem below that admits the optimal value max (V(Bs,.s)) As,
1 V V.C.,.((CC
i.e,,
(tr(AX) (xx S tx( S 1, Vi In + ml \T}
X T
maax (V Ass.s (Csg.s.)* 2 (()),
where the inequality is because the maximization problem above relaxes the valid constraints X S Mú for all i T in maximization problem (9). The result in Corollary 2 suggests that x", can be bounded and their two norms must not exceed M1, M2, which means that the optimal solution X satisfies the X < Ma for all i T. Therefore, X* is feasible and optimal to maximization problem (9) and we have that
f(z) max (B As (Css,sa))
According to strong duality, the minimization problem (19) admits an optimal value Tmax ((Bs AA v (Css,s))T) Next, we construct its optimal solution (0i, 02 X*).
For any given e we let 07 f22)/2, 02 f(z)/2. Sa(e)
Malyy for all T. and
(e(e) (e) for all i E [n] T. where
(=))) Xmax
DJ_ (D (Di- Diag (Ar(e))) D2 D3)
(e:D)) 1=
It is easy to compute that Of + 02 EiE(etm) (c) = f(z) + Thus, for any > 0, if (0i, 0j X()) were feasible, then is an e-optimal solution to the minimization problem (19). remains to verify the feasibility of the solution (07, 02 A(c)), i.e., checking the constraint below
g B
A/2 + Diag (((e) = O.
A
/2
C3C
By performing the permutation of the rows and columns of the above matrix, it is sufficient to show that the new block matrix
Di + Diag Ar(E))
D2
20,
(21)
D
D3 D3+
is positive semidefinite.
B
Ss,, principal submatrix of positive semidefinite matrix Csa.52
Since
A
/2
B
-A/2)
it also positive semidefinite. According to Lemma 1 and the fact that
A /2
C
Asi.s AS..sv(Css.. V(Css.s)))) /2, the matrix Dj is also positive semidefinite. As E > the matrix D + Diag (2r(e)) must be positive definite, which means that
01 03 = Tmax
(V(Bs,.si)
(D- Diag Diag (Ar(e)) (Di + Diag (ar(e)) D2 =
Besides, according to the definition of (c), we obtain
D3 D DJ (D1 + Diag (2r(e))) D2 0.
20

---

Taking these results together, according to Lemma 1, the constraint in (21) must hold for given solution (0 f2.. X()). Since the objective value corresponding to (0), 07 A(e) is at most larger than the optimal value of problem (19), letting e ++ 0 and using the closedness of the feasible set in problem (19), we can confirm the optimality of (0i, 02 X*) with X for all E ' and X X*
for E [m] \
Given the closed-fore form optimal solution to problem (19), the rest of the proof follows from [28. theorem
We note that SCCA (20) can be implemented via a delayed cut-generation procedure. That is, at each feasible branch-and-hound node with binary solution 2, let S1 {i å 1, Vi [n]] and S2 = (i - n 2 = 1, Vi E [n + 1, n + m]]. Then we can compute the corresponding scalar X* and generate the following valid inequality based on (20):
(B (CSss,s))
M (ES;U(Satt)
Σ
maxx
E
Data description
Table 7: Description of UCI and breast cancer datasets used
Dataset
# of variables
# of samples
rank
rank f
dermatology
34
366
17
17
spambase
57
4601
28
29
28
29
digits
64
1797
32
32
32
32
buzz
77
583250
38
39
39
gas
128
2565
64
64
64
64
slice
385
53500
192
193
192
193
breast cancer
21821
89
19,672
2,149
89
89
F
Multiple Sparse Canonical Correlation Analysis
The multiple CCA problem can be formulated as follows:
trr( Ay) x Bx I Cy 1x}
max # DERmx
where & denotes the number of pairs of basis vectors and I denotes the identity matrix of size k.
As æ, y can matrices, we propose adding row sparse constraints extend SCCA for multiple vectors, which is defined as:
{ (tr(x (Ay) x Bx = Ik.y Iyy = Ik. |01lo S $1, ll I $2).
max BRRXX ".R
x
where we let ||æ]|o and l/yl|o denote the number of nonzero rows of x and y, respectively.
This multiple SCCA model can (i) compute the multiple weight vectors (z, y) simultaneously and (ii) enforce the sparsity and orthogonality strictly. To be specific, the constraints x. Ba = I,. y Cy I ensure the orthogonal left- and right-canonical loading vectors multiple SCCA. By the definition of row sparsity, the resultant multiple left- and right-basis vectors, i.c., the columns of x and share the same nonzero rows, respectively.
More importantly, the row-sparsity enables us to readily extend the proposed algorithms to solve multiple SCCA. We have tested them on UCI data, and the computational results presented in Table 8, As & increases, it takes branch-and-cu a longer time to return an optimal solution.
21

---

Table 8: Evaluation of algorithms for solving multiple SCCA UCI datasets
Greedy
Local search
Convex relaxation
Branch-and-cut
81
82
LB
time
LB
time
UB
gap(%)
time
2"
MIPGap(%% (%)
time
17
17
5
5
1.907
0.01
1.935
0.06
1.957
1.14
0.01
1.935
0.00
2
17
17
10
10
2.879
0.02
2.884
0.09
2.898
0.45
0.01
2.884
0.00
6
28
29
5
5
1.182
0.02
1.233
0.09
1.358
10.19
0.01
1.233
0.00
234
28
29
10
10
1.579
0.04
1.586
0.14
1.685
6.23
0.01
1.587
5.33
32
32
5
5
1.906
0.02
1.906
0.04
1.935
1.55
0.01
1.916
0.00
32
32
10
10
2.736
0.04
2.741
0.19
2.770
1.05
0.01
2.742
0.00
3093
38
39
5
5
2 0.03
0.25
2
0.00
0.01
2
0.00
38
39
10
10
3 0.05
0.59
3
0.00
0.01
3
0.00
10
64
64
5
5
1.947
0.05
1.991
0.34
1.997
0.29
0.01
1.993
0.15
64
64
10
10
2.983
0.09
2.989
0.71
2.993
0.14
0.02
2.989
0.14
192
193
5
5
1.911
0.21
1.991
2.36
1.995
0.22
0.04
1.991
0,21
192
193
10
10
2.907
0.38
2.951
5.78
2.977
0.90
0.04
2.954
0.78
22

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and/or introduction should clearly state the claims made, including the629 contributions made in the paper and important assumptions and limitation
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The paper discusses the limitations of the proposed algorithms when analyzing the numerical results each table Section The paper points out the preconditions to apply Algorithm 1 and to reduce SCCA to MICQPs in Subsection 3.2.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
23

---

Answer: [Yes]
Justification:
The proofs can either appear in the main paper or the supplemental material.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: Section 5 discusses the generation of experimental results. The supplementary material also contains necessary codes and data used for result reproducibility.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
24

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
The supplementary material contains necessary codes and data.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/twpps.ccppubll// http:ccccpppccccccecceeccccccccc htpppuulccuuuideessssepppppepsel guides/ CCoeeSumm ssi ssisssoolooooooooo oonooiiyyyylolooooiomoooomiiiilp for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We describe the experimental setting in Subsection 5.1.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: The paper focus on solving optimization problem with deterministic data and evaluates the optimality performance the algorithms. Hence, the paper does not include error bars other statistical significance measures of the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
25

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide the details on the compute resources in the beginning of Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question:
Does the research conducted in the paper conform, in every respect, with the wwtpppplc//epciiceooooooooococle
NeurlPS Code of Ethics https: /
Answer: [Yes]
Justification: We have reviewed the NeurlPS Code of Ethics and make sure that we have conformed with it.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The paper improves the interpretability the widely-used CCA method, making it more convincing when applied real data analytics, e.g., genetic analytics of breast cancer data. We do not foresee any negative societal impact of this work.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
26

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
We have cited the original paper that produced the code package or dataset.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswi wwwode.hhoe...c. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
27

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The paper does not release new assets
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
28


Reviews:
[{"review_id": "HQ7eewBdiT", "reviewer": "Reviewer_WJMv", "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.", "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.", "limitations": "None.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "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.\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful comments and feedback. In the following, we provide detailed responses to each of the issues raised by the reviewer.\n\n1. [Q1: Understand the real datasets] We have applied the local search algorithm to evaluate the performance of SCCA against different sparsity levels. Specifically, for a given dataset, we compute the ratio of correlations between SCCA and CCA for various $s_1, s_2$ parameters. Note that CCA leverages all $n, m$ variables by default and does not change with $s_1, s_2$. We test the real $\\textit{spambase}$ data and synthetic data, and the results are displayed in Figure 1 in the PDF. This visualization provides insights for the maximum sparsity SSCA can achieve while maintaining the correlation of full data. For the real $\\textit{spambase}$ data, SCCA almost recovers the correlation of CCA when $s_1\\approx n/2$ and $s_2\\approx m/2$, as seen in Figure 1(a) in the PDF. This also indicates the underlying sparse structure of the dataset.\n\n[]()\n\n2. [Q2: Covariance structure] As the reviewer suggested. We will add a remark to explain Observation 1. We are also inspired to expand on the discussion of Theorem 2 using the covariance structure, as detailed below. We will add this remark immediately after Theorem 2. It is worth noting that the covariance structure offers an intuitive explanation but not rigorous proof. Therefore, we will keep the original proof to ensure that Theorem 2 is proven rigorously and that the subsequent Algorithm 1 can be developed. \n>Specifically, if matrices $B$ and $C$ are of rank $r$ and $\\hat{r}$, respectively, there are only $r$ and $\\hat{r}$ linearly independent vectors in the subspaces corresponding to $B$ and $C$. Thus, the cosine of the principal angle can always be represented by these $r$ and $\\hat{r}$ vectors. As a result, the weight vectors of CCA consist of only $r$ and $\\hat{r}$ nonzero elements.\n\n\n[]()\n\n3. [Q3: About SDP] When an SDP relaxation yields the same optimal value as the original problem, we say it achieves the objective exactness, commonly termed exact SDP in the literature. According to Proposition 1, CCA coincides with its SDP relaxation. That is, we obtain an exact SDP reformulation of CCA.", "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": "bbGHoXWx1D", "reviewer": "Reviewer_f5tE", "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.", "questions": "Please see the above weaknesses.", "limitations": "The authors have explained some of the limitations in the article, and others can be seen from weaknesses.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.The paper is well-written and well-organized.\n2.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,\n1. The work in [10] also addresses the sparsity of CCA. Why not give experimental results on the reference [10] or other sparse methods?  \n2. In section 4, the authors give a mixed-integer semidefinite program. In toy examples, it is much better to discuss this model.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to the reviewer for their careful evaluation and valuable suggestions. We have addressed the reviewer’s comments below.\n\n1. [Q1: Experimental comparison] We have compared the proposed local search algorithm with the SCCA methods of [10, 32, 41, 37] in correlation value, sparsity, and running time. The computational results on synthetic, UCI, and breast cancer data are presented in Table 1 in the PDF file. Please note that we highlight the best correlation and sparsity results in bold. \n* Unlike the local search algorithm, these existing methods do not strictly enforce the exact sparsity requirement, i.e., the $\\ell_0$ norm constraints on variables $ x,  y$. Consequently, the local search algorithm achieves the best sparsity for nearly all testing cases.\n* More importantly, the local search algorithm yields a larger correlation value than these existing methods in 15 out of 22 testing cases.\n* Finally, the running time of the local search algorithm outperforms that of [10, 32, 37].\n\nNote that the performance of these existing methods highly relies on the penalty parameters. We have tuned the parameters using the ranges recommended in the literature and have reported the best results. We hope these efforts are satisfactory.\n\n2. [Q2: About MISDP] The mixed-integer semidefinite program (MISDP) is an equivalent formulation of SCCA.  Below is a detailed discussion of the equivalence. Suppose $x, y$ is a pair of solutions to SCCA. \n\n* For each $i\\in [n]$, $z_i$ is the binary characteristic variable of the entry $x_i$, i.e., $z_i=0$ if $x_i=0$ and $z_i=1$ if $x_i\\neq 0$. Analogously, the binary variable $z_{j+n}$ corresponds to whether $y_j$ equals zero for each $j \\in [m]$. Notably, the sparsity thresholds $s_1$ and $s_2$ result in the constraints $\\sum_{i\\in [n]} x_i \\le s_1$ and $\\sum_{j\\in [m]} x_{j+n} \\le s_2$  in MISDP.\n* For each $i\\in [n+m]$, MISDP has the constraint $X_{ii} \\le M_{ii} z_i$, implying that $X_{ii} =0$ if $z_i=0$. Since matrix $X$ is positive semidefinite, it is easy to check that the $i$th column and $i$th row of $X$ are all zeros if $z_i=0$. For example, suppose $n+m=2$. Then, given a solution $z_1=1$ and $z_2=0$, $X$ is a $2\\times 2$ matrix and admits the form of  $\\begin{pmatrix}\nX_{11} & 0\\\\\\\\\n0 & 0 \\end{pmatrix}$.\n* Therefore, the variable $X$ in MISDP is a sparse matrix and its zero entries is consistent with the vector $\\begin{pmatrix}\nx\\\\\\\\\ny \\end{pmatrix}$, provided that the binary vector $z$ corresponds to $\\begin{pmatrix}\nx\\\\\\\\\ny \\end{pmatrix}$.\n\nBy leveraging Part (iii) of Proposition 1 and the above results, we can show that there is a one-to-one correspondence between $(X, z)$ of MISDP and $(x, y)$ of SCCA. This allows for the equivalence of MISDP and SCCA. We will add the discussion immediately after MISDP in the revision. Hope these explain our MISDP well.", "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": "1knetbEY46", "reviewer": "Reviewer_qq9k", "summary": "The paper proposes several algorithms for the Sparse Canonical Correlation Analysis (SCCA) problem.\n\nFirst, 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.\n\nFor 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.\n\nThe 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.\n\nFinally, 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.", "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?", "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.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "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].", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to the reviewer for their careful evaluation and valuable suggestions. We have addressed the reviewer’s comments below.\n\n1. [Q1: Experimental comparison] We have compared the proposed local search algorithm with the SCCA methods of [10, 32, 41, 37] in correlation value, sparsity, and running time. The computational results on synthetic, UCI, and breast cancer data are presented in Table 1 in the PDF file. Please note that we highlight the best correlation and sparsity results in bold. \n* Unlike the local search algorithm, these existing methods do not strictly enforce the exact sparsity requirement, i.e., the $\\ell_0$ norm constraints on variables $x, y$. Consequently, the local search algorithm achieves the best sparsity for nearly all testing cases.\n* More importantly, the local search algorithm yields a larger correlation value than these existing methods in 15 out of 22 testing cases.\n* Finally, the running time of the local search algorithm outperforms that of [10, 32, 37].\n\nNote that the performance of these existing methods highly relies on the penalty parameters. We have tuned the parameters using the ranges recommended in the literature and have reported the best results. Hope these efforts are satisfactory.\n\n2. [Q2: Buzz] We have included the numerical experiments for the buzz dataset, as presented in the last two rows of Table 2 in the PDF file.\n\n[]()\n\n3. [Q3: Limitations] In practice, the branch-and-cut algorithm can quickly find a high-quality solution at the beginning of the iterations, but proving its optimality takes a long time. Hence, we recommend setting a short time limit for practical applications. \nIn addition, please note that our proposed greedy and local search algorithms are scalable and do not require preconditions. They yield a near-optimal solution to SCCA for all testing instances. The supplementary experimental comparison further demonstrates the superior scalability and high-quality outputs of our local search algorithm compared to existing SCCA methods, as seen in Table 1 in the PDF file. Hope these mitigate the limitations well.", "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": "i2FtGWS4F6", "reviewer": "Reviewer_Dvxm", "summary": "The paper presents an efficient MISDP algorithm for sparse CCA.", "questions": "- Your analysis is to compute the first pair of basis vectors, how does your algorithm work to compute multiple pairs?\n- Why is the MIPGap always 0 (except when timed out)? Does a dataset exist where it is not zero?\n- Related to above, can the authors expand on the limitations of the proposed method?\n- In experiments, to evaluate the different algorithms, you use the distance with the optimum. Do you also compare sparsity explicitly?", "limitations": "See above", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Sparse CCA is an important and interesting problem. The analysis is useful for this area.", "weaknesses": "- Typos: optimiality -> optimality line 167\n- Limitations are not fully addressed\n- No separate evaluation of sparsity in the experiments (see Questions)\n- Most experiments have running time of exactly 1 second, it would be clearer to show more decimal digits.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful comments and feedback. In the following, we provide detailed responses to each of the issues raised by the reviewer.\n\n1. [Q1: Typo] We will fix the typo in the revision.\n\n[]()\n\n2. [Q2: Limitations] The limitations mainly arise from two aspects: Algorithm 1 and the proposed MICQP are efficient but require low-rank data matrices, and the branch-and-cut algorithm does not scale to large instances. However, we respectfully believe that addressing these limitations fully may not be feasible, as SCCA is generally an NP-hard problem. \n\nTo alleviate these limitations, we propose scalable greedy and local search algorithms without any precondition to approximately solve SCCA. They successfully yield a near-optimal solution to SCCA for all testing instances. Besides, in Table 1 in the PDF file, the supplementary experimental comparison demonstrates the superior scalability and high-quality outputs of our local search algorithm compared to existing SCCA methods. Therefore, we recommend using the approximation greedy and local search algorithms within the high-dimensional and full-rank data contexts. \n\nIn practice, the branch-and-cut algorithm can quickly find a high-quality solution at the beginning of the iterations, but proving its optimality takes a long time. Hence, we recommend setting a short time limit for practical applications. \nHope these mitigate the limitations well. \n\n[]()\n\n3. [Q3: About sparsity] This paper studies SCCA with $\\ell_0$ norm constraints on the weight vectors $x$ and $y$, restricting the number of nonzero weights exactly to be no larger than the sparsity thresholds $s_1$ and $s_2$, respectively. Hence, our approximation and exact algorithms can guarantee the desired sparsity of SCCA. \n\nWe have compared the proposed local search algorithm with the SCCA methods of [10, 32, 41, 37] in correlation value, sparsity, and running time. The computational results on synthetic, UCI, and breast cancer data are presented in Table 1 in the PDF file. Please note that we highlight the best correlation and sparsity results in bold. \n\n* Unlike the local search algorithm, these existing methods do not strictly enforce the exact sparsity requirement, i.e., the $\\ell_0$ norm constraints. Consequently, the local search algorithm achieves the best sparsity for nearly all testing cases.\n\nNote that the performance of these existing methods highly relies on the penalty parameters. We have tuned the parameters using the ranges recommended in the literature and have reported the best results. Hope these explain us well.\n\n[]()\n\n4. [Q4: Time] We have presented two decimal digits to differentiate the running time of less than one second. Please refer to Tables 1 and 2 in the PDF file.\n\n[]()\n\n5. [Q5: Multiple SCCA] First, the multiple CCA problem can be formulated as follows:\n$$ \n\\max_{x\\in \\mathbb{R}^{n\\times k}, y\\in \\mathbb{R}^{m\\times k}} \\big\\\\{\\text{tr}(x^{\\top} A y): x^{\\top} B x = I_k,  y^{\\top} C y = I_k \\big\\\\},\n$$\nwhere $k$ denotes the number of pairs of basis vectors and $I_k$ denotes the identity matrix of size $k$.\n\nAs $x, y$ can be matrices, we propose adding row sparse constraints to obtain multiple SCCA, which is defined as:\n$$ \n\\max_{x\\in \\mathbb{R}^{n\\times k}, y\\in \\mathbb{R}^{m\\times k}} \\big\\\\{\\text{tr}(x^{\\top} A y): x^{\\top} B x = I_k,  y^{\\top} C y = I_k, \\\\|x\\\\|_0\\le s_1, \\\\|y\\\\|_0\\le s_2 \\big\\\\},\n$$\nwhere we let $\\\\|x\\\\|_0$ and $\\\\| y\\\\|_0$ denote the number of nonzero rows of $x$ and $y$, respectively. \n\nThe proposed multiple SCCA model can (i) compute the multiple weight vectors $(x, y)$ simultaneously and (ii) enforce the sparsity and orthogonality strictly. To be specific, the constraints $x^{\\top} B x = I_k,  y^{\\top} C y = I_k$ ensure the orthogonal left- and right-canonical loading vectors in multiple SCCA. By the definition of row sparsity, the resultant multiple left- and right-basis vectors, i.e., the columns of $x$ and $y$, share the same nonzero rows, respectively.\n\nMore importantly, the row-sparsity enables us to readily extend the proposed algorithms to solve multiple SCCA. We have tested them on UCI data, and the computational results are presented in Table 2 in the PDF file. As $k$ increases, it takes branch-and-cut a longer time to return an optimal solution.\n\n6. [Q6: MIPGap & Branch-and-cut] MIPGap is a key performance measure for branch-and-cut, which is an iterative algorithm designed for solving mixed integer programming (MIP) to global optimality. By leveraging the proposed mixed-integer semidefinite program, we develop a customized branch-and-cut algorithm to exactly solve SCCA. \n\nSpecifically, MIPGap is defined as \"(UB – LB)/LB\" at each iteration of branch-and-cut, where LB is the objective value computed from the best-known feasible solution, and UB denotes the best-known upper bound.\n\nHowever, branch-and-cut is hard to scale for large instances. Thus, we set a time limit of one hour. If MIPGap reaches 0 within one hour, branch-and-cut successfully yields an optimal solution. If not, we report the MIPGap to indicate how far the current solution is from optimality. In practice, the branch-and-cut algorithm can quickly find a high-quality solution at the beginning of the iterations, but proving its optimality takes a long time. Hence, we recommend setting a short time limit for practical applications. \n\nBesides, the complexity of branch-and-cut depends on the initial MIPGap, known as the root gap in the literature. We compute the root gap by using the local search algorithm’s output as LB and the convex relaxation value as UB.  A small root gap often leads to a fast convergence of MIPGap to 0. Therefore, if the local search algorithm is near-optimal and the convex relaxation is tight, branch-and-cut will efficiently solve SCCA to optimality. In summary, the limitation of branch-and-cut is that it may struggle with solving large-scale instances especially when the root gap is large.", "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:
We thank the review team for their insightful comments and feedback, which significantly improve the quality of our paper. In the following, we provide detailed responses to the key issues raised by the reviewers. 

1. [Experimental comparison] We have compared the proposed local search algorithm with the SCCA methods of [10, 32, 41, 37] in correlation value, sparsity, and running time. The computational results on synthetic, UCI, and breast cancer data are presented in Table 1 in the PDF file. Please note that we highlight the best correlation and sparsity results in bold. 
* Unlike the local search algorithm, these existing methods do not strictly enforce the exact sparsity requirement, i.e., the $\ell_0$ norm constraints on variables $ x,  y$. Consequently, the local search algorithm achieves the best sparsity for nearly all testing cases.
* More importantly, the local search algorithm yields a larger correlation value than these existing methods in 15 out of 22 testing cases.
* Finally, the running time of the local search algorithm outperforms that of [10, 32, 37].

Note that the performance of these existing methods highly relies on the penalty parameters. We have tuned the parameters using the ranges recommended in the literature and have reported the best results. We hope these efforts are satisfactory.

[]()

2. [Limitations] The limitations mainly arise from two aspects: Algorithm 1 and the proposed MICQP are efficient but require low-rank data matrices, and the branch-and-cut algorithm does not scale to large instances. However, we respectfully believe that addressing these limitations fully may not be feasible, as SCCA is generally an NP-hard problem. 

To alleviate these limitations, we propose scalable greedy and local search algorithms without any precondition to approximately solve SCCA. They successfully yield a near-optimal solution to SCCA for all testing instances. Besides, in Table 1 in the PDF file, the supplementary experimental comparison demonstrates the superior scalability and high-quality outputs of our local search algorithm compared to existing SCCA methods. Therefore, we recommend using the approximation greedy and local search algorithms within the high-dimensional and full-rank data contexts. 

In practice, the branch-and-cut algorithm can quickly find a high-quality solution at the beginning of the iterations, but proving its optimality takes a long time. Hence, we recommend setting a short time limit for practical applications. 
Hope these mitigate the limitations well. 

[]()

3. [Multiple SCCA] First, the multiple CCA problem can be formulated as follows:
$$ 
\max_{x\in \mathbb{R}^{n\times k}, y\in \mathbb{R}^{m\times k}} \big\\{\text{tr}(x^{\top} A y): x^{\top} B x = I_k,  y^{\top} C y = I_k \big\\},
$$
where $k$ denotes the number of pairs of basis vectors and $I_k$ denotes the identity matrix of size $k$.

As $x, y$ can be matrices, we propose adding row sparse constraints to obtain multiple SCCA, which is defined as:
$$ 
\max_{x\in \mathbb{R}^{n\times k}, y\in \mathbb{R}^{m\times k}} \big\\{\text{tr}(x^{\top} A y): x^{\top} B x = I_k,  y^{\top} C y = I_k, \\|x\\|_0\le s_1, \\|y\\|_0\le s_2 \big\\},
$$
where we let $\\|x\\|_0$ and $\\| y\\|_0$ denote the number of nonzero rows of $x$ and $y$, respectively. 

The proposed multiple SCCA model can (i) compute the multiple weight vectors $(x, y)$ simultaneously and (ii) enforce the sparsity and orthogonality strictly. To be specific, the constraints $x^{\top} B x = I_k,  y^{\top} C y = I_k$ ensure the orthogonal left- and right-canonical loading vectors in multiple SCCA. By the definition of row sparsity, the resultant multiple left- and right-basis vectors, i.e., the columns of $x$ and $y$, share the same nonzero rows, respectively.

More importantly, the row-sparsity enables us to readily extend the proposed algorithms to solve multiple SCCA. We have tested them on UCI data, and the computational results are presented in Table 2 in the PDF file. As $k$ increases, it takes branch-and-cut a longer time to return an optimal solution.

Meta-review: The authors study the problem of sparse Canonical Correlation Analysis (CCA). Sparse CCA is useful for projecting paired observations (modalities) into a maximally correlated space while subselecting only a small set of variables from both modalities. This is important in high-dimensional or low-sample-size settings when classical CCA breaks. The paper presents three main contributions: a combinatorial formulation for SCCA problem complexity results for a low-rank SCCA setting, deriving an equivalent mixed-integer semi-definite programming reformulation for the SCCA problem. Reviewers are all positive about the paper, and the rebuttal has helped clarify some minor issues with the paper. As some reviewers pointed out, and I concur, the main weakness of the paper is the experimental results. Namely, those could be improved by more extensive evaluations and comparisons to leading methods demonstrating when the method shines. Nonetheless, since the paper includes other algorithmic and theoretical contributions, I recommend accepting it.
Decision: Accept (poster)