CMStatistics 2022: Start Registration
View Submission - CMStatistics
B1805
Title: Efficient inversion of sparse positive definite matrices based on the dyadic orthogonalization algorithm Authors:  Hanqing Wu - Lund University (Sweden) [presenting]
Krzysztof Podgorski - Lund University (Sweden)
Abstract: The problem of inverting large sparse positive definite matrices is at the center of many high-dimensional statistical methods. Recently, a highly efficient dyadic algorithm has been proposed for diagonalization and inversion of the band matrices, i.e. matrices that are zero outside of a narrow band of the entries around the main diagonal. Random permutation of a band matrix creates a sparse matrix for which it is easy to find the permutation that reverses it back to the band form. Using this simple observation, we propose an algorithm that allows efficient diagonalization and thus also inversion of a class of sparse matrices that can be decomposed into a small dimensional block and a number of not connected blocks of permuted band matrices. We formulate and prove mathematical results as well as compare the efficiency of our algorithms with other existing methods of inverting high-dimensional sparse matrices.