On the low-rank approximation by the pivoted Cholesky decomposition (Q412313)

The paper focuses on the application of the pivoted Cholesky decomposition to compute low-rank approximations of dense, positive semi-definite matrices. The first section is an introduction in nature. The second section gives a survey on the algorithm of the Cholesky decomposition for positive semi-definite matrices. The use of pivoted Cholesky decomposition to calculate low-rank approximations of matrices is motivated in the third section. It is also proved that the pivoted Cholesky decomposition converges exponentially if the eigenvalues of the symmetric and positive semi-definite matrix \(A\) of size \(n\times n\) decay exponentially with a sufficiently high rate: for a given \(\varepsilon>0\) it computes a rank-\(m\) approximation \(A_m\) such that trace\((A-A_m)\leq\varepsilon\) and \(m\) being proportional to \(|log(\varepsilon/n)|.\) The convergence proof presented in the paper is purely algebraically. The resulting truncation error is rigorously controlled in terms of the trace norm. The fourth section concerns the efficiency of the pivoted Cholesky decomposition by the mean of some numerical applications arising from the context of partial differential equations: the computing of the variance of an elliptic second order boundary value problem with stochastic right-hand side, the fast eigenpair computation of symmetric and positive semi-definite Hilbert-Schmidt operators and the application of the pivoted Cholesky decomposition for the fast computation of the two-electron integral matrix in quantum chemistry.