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

Share:

Description

Let

Φ (\bold{D}) = {∑\limits_{i = 1}^G {{n_i}} \ log{≤ft[ {{{\det (diag(\bold{D}'{\bold{S}_i}\bold{D}))}}} \right]}} -{∑\limits_{i = 1}^G {{n_i}} \ log{≤ft[ {{{\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 Φ (\bold{D})≥ 0 that depends on a orthonormal matrix \bold{D} is required for a potpourri of statistical problems. Φ (\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 Φ (\bold{D}). ALS algorithm is based on the update formula

\bold{D_{k+1}} = R_{\bold{D_k}} (-β^{m_k} \ α \ grad(Φ (\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(Φ(\bold{D}_k))=\overline{grad}(Φ(\bold{D}_k)) -\bold{D}_k≤ft[\frac{\bold{D}'_k\ \overline{grad}(Φ(\bold{D}_k))+\overline{grad}(Φ(\bold{D}_k))' \bold{D}_k }{2}\right]

where

\overline{grad}(Φ(\bold{D}_k))= {∑\limits_{i = 1}^G 2{{n_i}}{\bold{S}'_i}{\bold{D}_k} {≤ft[ {{{diag(\bold{D}'_k{\bold{S}_i}\bold{D}_k)}}} \right]^{-1}}},

and for β, σ \in (0,1) and α>0, m_k is the smallest nonnegative integer m such that

Φ(\bold{D}_k)-Φ (\bold{D}_{k+1}) ≥ -σ <grad(Φ(\bold{D}_k)) \ , \ -β^{m} \ α \ grad(Φ(\bold{D}_k))>

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

|Φ(\bold{D}_k)-Φ (\bold{D}_{k+1})| ≤ ε.

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.

Want to suggest features or report bugs for rdrr.io? Use the GitHub issue tracker.