ALSCPC-package {ALSCPC}R Documentation

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

Description

Let

Φ(D)=i=1Gni log[det(diag(DSiD))]i=1Gni log[det(DSiD)] \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 GG is a positive integer and called as the number of groups, n1+1{n_1}+1, n2+1{n_2}+1, ..., nG+1{n_G}+1 are positive integers and called as the sample sizes, D\bold{D} is an orthonormal matrix, and S1\bold{S}_1, S2\bold{S}_2, ..., SG\bold{S}_G are positive-definite and are usually sample covariance matrices. The minimization of the objective function Φ(D)0\Phi (\bold{D})\ge 0 that depends on a orthonormal matrix D\bold{D} is required for a potpourri of statistical problems. Φ(D)=0\Phi (\bold{D})= 0 means that S1\bold{S}_1, S2\bold{S}_2, ..., SG\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 Φ(D)\Phi (\bold{D}). ALS algorithm is based on the update formula

Dk+1=RDk(βmk α grad(Φ(Dk)))\bold{D_{k+1}} = R_{\bold{D_k}} (-\beta^{m_k} \ \alpha \ grad(\Phi (\bold{D}_k)))

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

grad(Φ(Dk))=grad(Φ(Dk))Dk[Dk grad(Φ(Dk))+grad(Φ(Dk))Dk2] 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

grad(Φ(Dk))=i=1G2niSiDk[diag(DkSiDk)]1,\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 β,σ(0,1)\beta, \sigma \in (0,1) and α>0\alpha>0, mkm_k is the smallest nonnegative integer mm such that

Φ(Dk)Φ(Dk+1)σ<grad(Φ(Dk)) , βm α grad(Φ(Dk))> \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 D0\bold{D}_0, for a given ϵ>0\epsilon > 0, we stop the algorithm when

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

Details

Package: ALSCPC
Version: 1.0
Date: 2013-09-05
License: GPL (>= 2)

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.


[Package ALSCPC version 1.0 Index]