Numerical Methods For Maximal Correlation Problem

Canonical correlation analysis (CCA) is an important and effective tool for assessing the relationship between sets of random variables. CCA has been wildly used in various fields such as cluster analysis, pattern recognition, data classification, principal component analysis, bioinformatics.The maximal correlation problem (MCP) as a generalization of the canonical correlation analysis aiming at optimizing correlations between sets of variables plays an important role in several areas of statistical applications. Upon employing the Lagrange multiplier theory, it is easy to see that the first order necessary optimality condition for MCP is to solve the multivariate eigenvalue problem (MEP). Horst algorithm has been regarded as an early numerical method for solving the MEP. This algorithm later was recognized as the classical power iteration. As a natural improvement on the power method, Gauss-Seidel-type iteration has been proposed by Chu and Watterson for the MEP. Combining the accelerated thoughts of SOR method with Horst method, the P-SOR iteration is proposed and analyzed by Sun, which is a generalization of the Gauss-Seidel method. P-SSOR iteration is an improvement of P-SOR. However, existing theoretical proofs show that though the above methods can obtain a solution of MEP, none of these algorithms can guarantee convergence to a global maximize of MCP. Alternating variable method (AVM) which is established by Zhang and Liao is an effective numerical method for tacking MCP directly. This method can not guarantee convergence, and can not obtain a global solution of MCP when it convergences.Numerical methods and related theories are studied for MCP in this paper and this paper contains three main contributions. Firstly, some distinctive properties of MCP are characterized, the lower and upper bounds for the MCP value are presented, which makes it possible to propose an effective starting point strategy for obtaining a global maximizer. Secondly, a unified and concise proof of the monotone convergence of these iterative methods is presented. Finally, employing an idea of the multigrid method for PDEs, a new method for MCP is proposed in the present paper. At the same time, this paper presents a symmetric form of Gauss-Seidel algorithm (symmetric Gauss-Seidel). Numerical tests suggest that the numbers of iterations needed for symmetric Gauss-Seidel are significantly reduced compared with Horst、 Gauss-Seidel and P-SOR methods. By applying the starting point strategy, an optimal solution can be obtained with a high probability, and experimental results indicate superior performance of the new method (take AVM or symmetric Gauss-Seidel as candidate for internal iterative format) to the others in finding a global optimal solution of MCP.