Alternating Algorithms for Sparse CCA

Why Alternate Between the Two Weight Vectors?

In sparse canonical correlation analysis (sparse CCA), each block of measurements is summarized by a weighted score. The two weight vectors are chosen to find scores that are strongly associated while limiting the number or size of their nonzero coefficients. The central computational difficulty is that the two vectors are coupled: changing one changes which values of the other are useful.

An alternating algorithm handles this coupling by optimizing one vector while holding the other fixed, then reversing their roles. Each step is a constrained optimization problem. The method is useful only if the updates respect both the covariance normalization and the sparsity constraints; normalizing a vector alone does not guarantee that it is feasible.

The covariance-normalization constraints make the two score variances equal to one. Consequently, \(a^\mathsf{T}S_{xy}b\) is the sample correlation between the scores \(Xa\) and \(Yb\). The \(L_1\) bounds restrict the weights and can encourage zero coefficients. A feasible pair must satisfy all four constraints simultaneously.

Block Updates and Their Assumptions

Assume the observations in the two blocks are matched and centered in the same way, and that \(S_{xx}\) and \(S_{yy}\) are positive definite. When the starting pair is feasible, each block feasible set is nonempty. Positive definiteness makes each covariance-normalized set bounded, and the constraints define closed feasible sets; thus each block feasible set is compact, so its continuous objective attains a maximum. If covariance matrices are singular, additional care is needed; the positive-definite assumption here avoids that complication.

Starting from a feasible pair \((a^{(0)},b^{(0)})\), an exact alternating iteration is defined by these block maximizations:

The first update chooses the best feasible \(a\) for the current \(b^{(t)}\); the second chooses the best feasible \(b\) for the updated \(a^{(t+1)}\). If a subproblem has multiple maximizers, a consistent tie-breaking rule helps make the numerical output reproducible. The signs of both vectors matter only through their product: flipping both signs leaves the objective unchanged. A convention such as choosing signs so that the reported covariance is nonnegative can make results easier to compare.

In practice, an update may be obtained by a numerical solver or an approximate block procedure. In either case, check feasibility after every update. A Euclidean normalization is not generally the same as covariance normalization unless the relevant covariance matrix is the identity. Also, rescaling a vector to satisfy its covariance constraint can change its \(L_1\) norm, so both conditions must be checked after normalization.

Why the Objective Does Not Decrease

For exact block maximizations, monotonicity follows directly from feasibility. The old \(a^{(t)}\) remains a permissible candidate in the \(a\) subproblem, so the new \(a\) cannot produce a smaller objective at the fixed \(b^{(t)}\). Next, \(b^{(t)}\) remains permissible in the \(b\) subproblem, so that update cannot reduce the objective either.

The objective is also bounded above by one in this covariance-normalized formulation. The covariance Cauchy–Schwarz inequality gives \(\left|a^\mathsf{T}S_{xy}b\right|\leq\sqrt{a^\mathsf{T}S_{xx}a}\sqrt{b^\mathsf{T}S_{yy}b}=1\). Therefore, the sequence of objective values from exact updates is nondecreasing and bounded, and hence converges. This statement concerns objective values; it does not by itself prove that the weight vectors converge, that the limit is unique, or that it is a global maximum.

Monitoring Updates and Recognizing Failure

A practical implementation should monitor more than the objective. At each iteration, record the objective, both covariance norms, and both \(L_1\) norms. Also record the number of nonzero coefficients, using a stated numerical tolerance when values are very small. A useful stopping rule requires the objective change to be small relative to its scale for several iterations and the constraints to remain satisfied. For example, one may stop when \(|J^{(t+1)}-J^{(t)}|/\max(1,|J^{(t)}|)\) is below a chosen tolerance, while separately verifying the constraints. The tolerance is a computational choice, not a guarantee of statistical accuracy.

For instance, with \(S_{xx}=\operatorname{diag}(4,1)\), the vector \(a=(0.4,0.6)^\mathsf{T}\) has covariance norm \(\sqrt{4(0.4)^2+(0.6)^2}=1\) and \(L_1\) norm \(1.0\). A proposed \(b=(0.8,0.6)^\mathsf{T}\) has Euclidean—and thus covariance—norm one if \(S_{yy}=I_2\), but its \(L_1\) norm is \(1.4\). With \(c_y=1.2\), this pair is not feasible. Replacing it with \(b=(\sqrt{0.99},0.1)^\mathsf{T}\) gives covariance norm one and \(L_1\) norm approximately \(1.095\), so the replacement is feasible. This check matters because a plausible-looking normalized vector can still violate the sparsity bound.

How Alternation Compares With Other Choices

Classical CCA solves a non-sparse covariance-normalized problem and can be computed through matrix factorizations when its required conditions hold. Sparse CCA adds constraints that make the optimization non-smooth and can produce interpretable zero patterns, but its alternating optimization may settle at a local solution and may depend on initialization. Ridge-regularized CCA instead stabilizes the problem by penalizing or regularizing weights; it does not impose the same direct \(L_1\) sparsity bounds. PLS maximizes covariance under a different normalization and objective, so its weight vectors should not be interpreted as solutions to this sparse CCA problem.

Alternating updates are attractive because each step focuses on one block and the objective can be monitored. Their limitations are equally important: objective monotonicity is not a proof of global optimality, and a converged objective does not establish that selected variables are stable across samples. In applications, initialization sensitivity, small changes in the objective, and support changes should all be reported or investigated rather than hidden by a single stopping criterion.

Common Mistakes

• Calling an initialization feasible after checking only one constraint. Feasibility requires both covariance normalization and the relevant \(L_1\) bound for each vector.
• Using Euclidean normalization automatically. It is correct only when the corresponding covariance matrix is the identity; otherwise use the covariance norm.
• Assuming each alternating run finds the global solution. Blockwise improvement and objective convergence do not establish global optimality.
• Treating a stable objective as proof of stable weights. Multiple or nearly tied block maximizers can have similar objective values but different supports.