Accelerated line search algorithm for simultaneous orthogonal transformation of several positive definite symmetric matrices to nearly diagonal form.

Description

Let

\Phi (\bold{D}) = {\sum\limits_{i = 1}^G {{n_i}} \ log{\left[ {{{\det (diag(\bold{D}'{\bold{S}_i}\bold{D}))}}} \right]}} -{\sum\limits_{i = 1}^G {{n_i}} \ log{\left[ {{{\det (\bold{D}'{\bold{S}_i}\bold{D})}}} \right]}}

where G is a positive integer and called as the number of groups, {n_1}+1, {n_2}+1, ..., {n_G}+1 are positive integers and called as the sample sizes, \bold{D} is an orthonormal matrix, and \bold{S}_1, \bold{S}_2, ..., \bold{S}_G are positive-definite and are usually sample covariance matrices. The minimization of the objective function \Phi (\bold{D})\ge 0 that depends on a orthonormal matrix \bold{D} is required for a potpourri of statistical problems. \Phi (\bold{D})= 0 means that \bold{S}_1, \bold{S}_2, ..., \bold{S}_G are simultaneously simultaneously diagonalizable. This situation is encountered when looking for common principal components, for example, and the Flury and Gautschi (1986) method is a popular approach. Lefkomtch (2004), Boik (2007), and Browne and McNicholas (2012) report that the Flury and Gautschi method is not effective for higher dimensional problems. Browne and McNicholas (2013) obtain several simple majorization-minizmation (MM) algorithms that provide solutions to this problem and are effective in higher dimensions. They compare these solutions with each others in terms of convergence and computational time. They found that the accelerated line search (ALS) algorithm is a computationally efficient procedure to this problem. Extensive review of the this algorithm and similar algorithms can be found in Absil et al. (2008). In the following, we briefly describe the ALS algorithm used to minimize the objective function \Phi (\bold{D}). ALS algorithm is based on the update formula

\bold{D_{k+1}} = R_{\bold{D_k}} (-\beta^{m_k} \ \alpha \ grad(\Phi (\bold{D}_k)))

where R_{\bold{D_k}}(\bold{V}) = qf({\bold{D_k}} + \bold{V}), where qf(\bold{M}) = \bold{Q} in the sense of the QR decomposition of a matrix \bold{M}; The \bold{Q}\bold{R} decomposition of a matrix \bold{M} is the decomposition of \bold{M} as \bold{M}=\bold{Q}\bold{R}, where \bold{Q} belongs to the orthogonal group and \bold{R} belongs to the set of all upper triangular matrices with strictly positive diagonal elements,

grad(\Phi(\bold{D}_k))=\overline{grad}(\Phi(\bold{D}_k)) -\bold{D}_k\left[\frac{\bold{D}'_k\ \overline{grad}(\Phi(\bold{D}_k))+\overline{grad}(\Phi(\bold{D}_k))' \bold{D}_k }{2}\right]

where

\overline{grad}(\Phi(\bold{D}_k))= {\sum\limits_{i = 1}^G 2{{n_i}}{\bold{S}'_i}{\bold{D}_k} {\left[ {{{diag(\bold{D}'_k{\bold{S}_i}\bold{D}_k)}}} \right]^{-1}}},

and for \beta, \sigma \in (0,1) and \alpha>0, m_k is the smallest nonnegative integer m such that

\Phi(\bold{D}_k)-\Phi (\bold{D}_{k+1}) \ge -\sigma <grad(\Phi(\bold{D}_k)) \ , \ -\beta^{m} \ \alpha \ grad(\Phi(\bold{D}_k))>

where < . \ , \ . > is the Frobenius inner product. Starting from initial iterate \bold{D}_0, for a given \epsilon > 0, we stop the algorithm when

|\Phi(\bold{D}_k)-\Phi (\bold{D}_{k+1})| \le \epsilon.

Details

Author(s)

Dariush Najarzadeh

Maintainer: Dariush Najarzadeh <D_Najarzadeh@sbu.ac.ir>

References

Absil, P. A., Mahony, R., & Sepulchre, R. (2009). Optimization algorithms on matrix manifolds. Princeton University Press.

Boik, R. J. (2007). Spectral models for covariance matrics. Biometrika, 89, 159-182.

Browne, R. P., and McNicholas, P. D. (2012). Orthogonal Stiefel manifold optimization for eigen-decomposed covariance parameter estimation in mixture models. Statistics and Computing, 1-8.

Browne, R. P., and McNicholas, P. D. (2013). Estimating common principal components in high dimensions. arXiv preprint arXiv:1302.2102.

Flury, B. N., and Gautschi, W. (1986). An algorithm for simultaneous orthogonal transformation of several positive definite symmetric matrices to nearly diagonal form. SIAM Journal on Scientific and Statistical Computing, 7(1), 169-184.

Lefkomtch, L. P. (2004). Consensus principal components. Biometrical Journal, 35, 567-580.

minimize the objective function \Phi(\bold{D}) by using of the accelerated line search algorithm

Description

The ALS.CPC function implement ALS algorithm based on the update formula

\bold{D_{k+1}} = R_{\bold{D_k}} (-\beta^{m_k} \ \alpha \ grad(\Phi (\bold{D}_k)))

until convergence (i.e. |\Phi(\bold{D}_k)-\Phi (\bold{D}_{k+1})| \le \epsilon) and return the orthogonal matrix \bold{D}_r, r is the smallest nonnegative integer k such that |\Phi(\bold{D}_k)-\Phi (\bold{D}_{k+1})| \le \epsilon.

Usage

ALS.CPC(alpha,beta,sigma,epsilon,G,nval,D,S)

Arguments

Value

An orthogonal matrix such that minimize \Phi(\bold{D}).

Author(s)

Dariush Najarzadeh

References

Absil, P. A., Mahony, R., & Sepulchre, R. (2009). Optimization algorithms on matrix manifolds. Princeton University Press.

Examples

nval<-numeric(3) 
nval[[1]]<-49
nval[[2]]<-49
nval[[3]]<-49
S<-vector("list",length=3)
setosa<-iris[1:50,1:4]; names(setosa)<-NULL
versicolor<-iris[51:100,1:4]; names(versicolor)<-NULL
virginica<-iris[101:150,1:4]; names(virginica)<-NULL
S[[1]]<-as.matrix(var(versicolor))
S[[2]]<-as.matrix(var(virginica))
S[[3]]<-as.matrix(var(setosa))
D<-diag(4)
ALS.CPC(10,0.5,0.4,1e-5,G=3,nval,D,S)