Optimization Online


Branch-and-bound Algorithm for Optimal Sparse Canonical Correlation Analysis

Akihisa Watanabe (ka41922***at***gmail.com)
Ryuta Tamura (r.tamura.cbc***at***gmail.com)
Yuichi Takano (ytakano***at***sk.tsukuba.ac.jp)
Ryuhei Miyashiro (r-miya***at***cc.tuat.ac.jp)

Abstract: Canonical correlation analysis (CCA) is a family of multivariate statistical methods for extracting mutual information contained in multiple datasets. To improve the interpretability of CCA, here we focus on the mixed-integer optimization (MIO) approach to sparse estimation. This approach was first proposed for sparse linear regression in the 1970s, but it has recently received renewed attention due to advances in optimization algorithms and computer hardware. We first derive an MIO problem for optimal sparse CCA estimation. To solve this MIO problem exactly, we propose a branch-and-bound algorithm based on the generalized eigenvalue problem for computing effective lower and upper bounds. We prove that our algorithm finds a solution with guaranteed optimality in terms of the canonical correlation. Computational results demonstrate that our method is much faster than direct application of optimization software to the MIO problem. Moreover, our method can provide better-quality solutions than can forward stepwise selection and L1-regularized estimation in terms of generalization performance. These results enhance the potential of optimal sparse estimation in multivariate statistical analyses.

Keywords: canonical correlation analysis; branch-and-bound algorithm; sparse estimation; mixed-integer optimization; statistics

Category 1: Applications -- Science and Engineering (Statistics )


Download: [PDF]

Entry Submitted: 04/24/2021
Entry Accepted: 04/24/2021
Entry Last Modified: 04/25/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society