Rice condition numbers of QR and Cholesky factorizations

A condition number is an amplification coefficient due to errors in computing. Thus the theory of condition numbers plays an important role in error analysis. In this paper, following the approach of Rice, condition numbers are defined for factors of some matrix factorizations such as the Cholesky factorization of a symmetric positive definite matrix and QR factorization of a general matrix. The condition numbers are derived by a technique of analytic expansion of the factor dependent on one parameter and matrix-vector equation. Condition numbers of the Cholesky and QR factors are different from the ones previously introduced by other authors, but similar to Chang's results. In Cholesky factorization, corresponding with the condition number of the factor matrix L , K _L is a low bound of Stewart's condition number K .

Improved Square-Root UKF Algorithm for State Estimation of Nonlinear Systems

The square-root unscented Kalman filter （SR- UKF） for state estimation probably encounters the problem that Cholesky factor update of the covariance matrices can＇t be implemented when the zero＇th weight of sigma points is negative or the mnnerical computation error becomes large during the faltering procedure. Consequently the filter becomes invalid. An improved SR-UKF algorithm （ISR- UKF） is presented for state estimation of arbitrary nonlinear systems with linear measurements. It adopts a modified form of predicted covariance matrices, and modifies the Cholesky factor calculation of the updated covariance matrix originating from the square-root covariance filtering method. Discussions have been given on how to avoid the filter invalidation and further error accumulation. The comparison between the ISR-UKF and the SR-UKF by simulation also shows both have the same accuracy for state estimation. Finally the performance of the improved filter is evaluated under the impact of model mismatch. The error behavior shows that the ISR-UKF can overcome the impact of model mismatch to a certain extent and has excellent trace capability.

A High-Quality Preconditioning Technique for Multi-Length-Scale Symmetric Positive Definite Linear Systems

We study preconditioning techniques used in conjunction with the conjugate gradient method for solving multi-length-scale symmetric positive definite linear systems originating from the quantum Monte Carlo simulation of electron interaction of correlated materials. Existing preconditioning techniques are not designed to be adaptive to varying numerical properties of the multi-length-scale systems. In this paper, we propose a hybrid incomplete Cholesky （HIC） preconditioner and demonstrate its adaptivity to the multi-length-scale systems. In addition, we propose an extension of the compressed sparse column with row access （CSCR） sparse matrix storage format to efficiently accommodate the data access pattem to compute the HIC preconditioner. We show that for moderately correlated materials, the HIC preconditioner achieves the optimal linear scaling of the simulation. The development of a linear-scaling preconditioner for strongly correlated materials remains an open topic.

Efficient Generalized Inverse for Solving Simultaneous Linear Equations

Solving large scale system of Simultaneous Linear Equations (SLE) has been (and continue to be) a major challenging problem for many real-world engineering and science applications. Solving SLE with singular coefficient matrices arises from various engineering and sciences applications [1]-[6]. In this paper, efficient numerical procedures for finding the generalized (or pseudo) inverse of a general (square/rectangle, symmetrical/unsymmetrical, non-singular/singular) matrix and solving systems of Simultaneous Linear Equations (SLE) are formulated and explained. The developed procedures and its associated computer software (under MATLAB [7] computer environment) have been based on “special Cholesky factorization schemes” (for a singular matrix). Test matrices from different fields of applications have been chosen, tested and compared with other existing algorithms. The results of the numerical tests have indicated that the developed procedures are far more efficient than the existing algorithms.

Fast implementation of kernel simplex volume analysis based on modified Cholesky factorization for endmember extraction

Endmember extraction is a key step in the hyperspectral image analysis process. The kernel new simplex growing algorithm （KNSGA）, recently developed as a nonlinear alternative to the simplex growing algorithm （SGA）, has proven a promising endmember extraction technique. However, KNSGA still suffers from two issues limiting its application. First, its random initialization leads to inconsistency in final results; second, excessive computation is caused by the iterations of a simplex volume calculation. To solve the first issue, the spatial pixel purity index （SPPI） method is used in this study to extract the first endrnember, eliminating the initialization dependence. A novel approach tackles the second issue by initially using a modified Cholesky fac- torization to decompose the volume matrix into triangular matrices, in order to avoid directly computing the determinant tauto- logically in the simplex volume formula. Theoretical analysis and experiments on both simulated and real spectral data demonstrate that the proposed algorithm significantly reduces computational complexity, and runs faster than the original algorithm.

Maximum-likelihood detection based on branch and bound algorithm for MIMO systems

Maximum likelihood detection for MIMO systems can be formulated as an integer quadratic programming problem. In this paper, we introduce depth-first branch and bound algorithm with variable dichotomy into MIMO detection. More nodes may be pruned with this structure. At each stage of the branch and bound algorithm, active set algorithm is adopted to solve the dual subproblem. In order to reduce the complexity further, the Cholesky factorization update is presented to solve the linear system at each iteration of active set algorithm efficiently. By relaxing the pruning conditions, we also present the quasi branch and bound algorithm which implements a good tradeoff between performance and complexity. Numerical results show that the complexity of MIMO detection based on branch and bound algorithm is very low, especially in low SNR and large constellations.

Cholesky-based model averaging for covariancematrix estimation

Estimation of large covariance matrices is of great importance in multivariate analysis.The modified Cholesky decomposition is a commonly used technique in covariance matrix estimation given a specific order of variables.However,information on the order of variables is often unknown,or cannot be reasonably assumed in practice.In this work,we propose a Choleskybased model averaging approach of covariance matrix estimation for high dimensional datawith proper regularisation imposed on the Cholesky factor matrix.The proposed method not only guarantees the positive definiteness of the covariance matrix estimate,but also is applicable in general situations without the order of variables being pre-specified.Numerical simulations are conducted to evaluate the performance of the proposed method in comparison with several other covariance matrix estimates.The advantage of our proposed method is further illustrated by a real case study of equity portfolio allocation.