A greedy approach to sparse canonical correlation analysis

We consider the problem of sparse canonical correlation analysis (CCA), i.e., the search for two linear combi nations, one for each multivariate, that yield maximum correlation using a specified number of variables. We propose an efficient numeri cal approximation based on a direct greedy approach which bound s the correlation at each stage. The method is specifically des igned to cope with large data sets and its computational complexit y depends only on the sparsity levels. We analyze the algorith m’s performance through the tradeoff between correlation and parsimony. The results of numerical simulation suggest that a significant portion of the correlation may be captured using a relatively small number of variables. In addition, we exami ne the use of sparse CCA as a regularization method when the number of available samples is small compared to the dimensions of t he multivariates. I. I NTRODUCTION Canonical correlation analysis (CCA), introduced by Harol d Hotelling , is a standard technique in multivariate data n lysis for extracting common features from a pair of data sourc es , . Each of these data sources generates a random vecto r that we call a multivariate. Unlike classical dimensionali ty reduction methods which address one multivariate, CCA take s into account the statistical relations between samples fro m two spaces of possibly different dimensions and structure. In particular, it searches for two linear combinations, one fo r each multivariate, in order to maximize their correlation. It is used in different disciplines as a stand-alone tool or as a preprocessing step for other statistical methods. Further more, CCA is a generalized framework which includes numerous classical methods in statistics, e.g., Principal Componen t Analysis (PCA), Partial Least Squares (PLS) and Multiple Linear Regression (MLR) . CCA has recently regained attention with the advent of kernel CCA and its application to independent component analysis , . The last decade has witnessed a growing interest in the search for sparse representations of signals and sparse numerical methods. Thus, we consider the problem of sparse CCA, i.e., the search for linear combinations with maximal correlation using a small number of variables. The quest for sparsity can be motivated through various reasonings. First is the ability to interpret and visualize the results. A small number of variables allows us to get the “big picture”, while sacrificing some of the small details. Moreover, spars e representations enable the use of computationally efficien t The first two authors contributed equally to this manuscript . This work was supported in part by an AFOSR MURI under Grant FA9550-06-1-0 324. numerical methods, compression techniques, as well as nois e reduction algorithms. The second motivation for sparsity i s regularization and stability. One of the main vulnerabilit ies of CCA is its sensitivity to a small number of observations. Thu s, regularized methods such as ridge CCA [7] must be used. In this context, sparse CCA is a subset selection scheme which allows us to reduce the dimensions of the vectors and obtain a stable solution. To the best of our knowledge the first reference to sparse CCA appeared in  where backward and stepwise subset selection were proposed. This discussion was of qualitativ e nature and no specific numerical algorithm was proposed. Recently, increasing demands for multidimensional data pr ocessing and decreasing computational cost has caused the topic to rise to prominence once again [8]–[13]. The main disadvantages with these current solutions is that there is no direct control over the sparsity and it is difficult (and nonintuitive) to select their optimal hyperparameters. In add ition, the computational complexity of most of these methods is too high for practical applications with high dimensional data sets. Sparse CCA has also been implicitly addressed in ,  an d is intimately related to the recent results on sparse PCA  , [15]–[17]. Indeed, our proposed solution is an extension of the results in  to CCA. The main contribution of this work is twofold. First, we derive CCA algorithms with direct control over the sparsity in each of the multivariates and examine their performance. Our computationally efficient methods are specifically aime d at understanding the relations between two data sets of larg e dimensions. We adopt a forward (or backward) greedy approach which is based on sequentially picking (or dropping) variables. At each stage, we bound the optimal CCA solution and bypass the need to resolve the full problem. Moreover, the computational complexity of the forward greedy method does not depend on the dimensions of the data but only on the sparsity parameters. Numerical simulation results show th at a significant portion of the correlation can be efficiently cap tured using a relatively low number of non-zero coefficients. Our second contribution is investigation of sparse CCA as a regularization method. Using empirical simulations we examin e the use of the different algorithms when the dimensions of the multivariates are larger than (or of the same order of) the number of samples and demonstrate the advantage of sparse CCA. In this context, one of the advantages of the greedy approach is that it generates the full sparsity path i n a single run and allows for efficient parameter tuning using