2013/02/05 by Jan Rupnik, Primoz Skraba, Rupnik, Jan +7 · 11 citations
Agricultural and Biological Sciences · Computer Science · Decision Sciences · Mathematics · #Algorithm #Animal Nutrition and Physiology #Blind Source Separation Techniques #Canonical correlation #Combinatorics #Computer science #FOS: Computer and information sciences #Face and Expression Recognition #Greedy algorithm #Kernel (algebra) #Machine Learning (cs.LG) #Mathematical optimization #Mathematics #Multi-Criteria Decision Making #Multiset #Quadratic growth #Regular polygon #Relaxation (psychology) #Semidefinite programming #Set (abstract data type) #Statistics #Variety (cybernetics) #cs.LG
paper · pdf · doi:10.48550/arxiv.1302.0974
published in arXiv (Cornell University) (Cornell University)
arxiv created 2013/02/05 · openalex publication_date 2013/02/05 · arxiv updated 2013/02/06 · openalex created_date 2022/10/04 · openalex updated_date 2026/08/06
Canonical correlation analysis is a statistical technique that is used to\nfind relations between two sets of variables. An important extension in pattern\nanalysis is to consider more than two sets of variables. This problem can be\nexpressed as a quadratically constrained quadratic program (QCQP), commonly\nreferred to Multi-set Canonical Correlation Analysis (MCCA). This is a\nnon-convex problem and so greedy algorithms converge to local optima without\nany guarantees on global optimality. In this paper, we show that despite being\nhighly structured, finding the optimal solution is NP-Hard. This motivates our\nrelaxation of the QCQP to a semidefinite program (SDP). The SDP is convex, can\nbe solved reasonably efficiently and comes with both absolute and\noutput-sensitive approximation quality. In addition to theoretical guarantees,\nwe do an extensive comparison of the QCQP method and the SDP relaxation on a\nvariety of synthetic and real world data. Finally, we present two useful\nextensions: we incorporate kernel methods and computing multiple sets of\ncanonical vectors.\n