Sparse Factorizations of Dense Matrices using the Screening Effect

Sparse factorization algorithms, such as incomplete Cholesky factorization, are most commonly used for sparse problems, with sparsity patterns derived from the sparsity graph of the original matrix. In this talk, I will present a probabilistic perspective for identifying sparse factorization of dense positive-definite matrices. Cholesky factors encode conditional independence. Thus, the conditional independence of densely correlated Gaussian vectors directly translates to sparse Cholesky factorizations of dense covariance matrices. In certain spatial (statistical) problems, the screening effect provides a powerful heuristic for identifying conditional independence and thus discovering fast algorithms, asymptotically and in practice.