The following results on the block Cholesky factorization of bi-infinite and semi-infinite matrices are obtained. A method is proposed for computing the $LDM^T$- and block Cholesky factors of a bi-infinite banded block Toeplitz matrix. An equivalence relation is introduced to describe when two semi-infinite matrices with entries $A_{ij}$ coincide exponentially as $i,j,i+j\to\infty$. If two equivalent bi-infinite matrices have block Cholesky factorizations, then their block Cholesky factors and their inverses are equivalent. If a bi-infinite block matrix $A$ has a block Cholesky factorization whose lower triangular factor $L$ and its lower triangular inverse decay exponentially away from the diagonal, then the semi-infinite truncation of $A$ has a lower triangular block Cholesky factor whose elements approach those of $L$ exponentially. These results are then applied to studying the asymptotic behavior of vectors of functions obtained by orthonormalizing a large finite set of integer translates of an exponentially decaying vector of functions.