| 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
\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
| 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.