Hi, This PR https://github.com/scipy/scipy/pull/16499 is an attempt at getting Cholesky rank-1 and rank-k up/downdates into SciPy, by introducing a `scipy.linalg.cholesky_update` function. I borrowed heavily from a previous half-finished PR which did the same thing (https://github.com/scipy/scipy/pull/8286), and added rank-k support. The PR includes a benchmark showing that at least the rank-1 update is much faster than redoing the factorization from scratch. Thanks for taking the time to review this. Kind regards, Giacomo
hi, in case it helps note that scikit-learn does such cholesky updates and downdates in the LARS solver. See eg https://github.com/scikit-learn/scikit-learn/blob/main/sklearn/linear_model/... Alex On Thu, Jun 30, 2022 at 2:48 AM <giacomo.meanti@gmail.com> wrote:
Hi, This PR https://github.com/scipy/scipy/pull/16499 is an attempt at getting Cholesky rank-1 and rank-k up/downdates into SciPy, by introducing a `scipy.linalg.cholesky_update` function. I borrowed heavily from a previous half-finished PR which did the same thing (https://github.com/scipy/scipy/pull/8286), and added rank-k support.
The PR includes a benchmark showing that at least the rank-1 update is much faster than redoing the factorization from scratch.
Thanks for taking the time to review this.
Kind regards, Giacomo _______________________________________________ SciPy-Dev mailing list -- scipy-dev@python.org To unsubscribe send an email to scipy-dev-leave@python.org https://mail.python.org/mailman3/lists/scipy-dev.python.org/ Member address: alexandre.gramfort@inria.fr
Hi Alex, I'm not sure the scikit-learn code is doing the same thing. From what I understand, at every iteration the 'active' portion of the covariance matrix is expanded by adding an extra active feature, and the Cholesky factorization is updated to reflect the new covariance. So if C = X.T @ X, then C = L @ L.T where X is [n, d]. At each iteration I think the LARS algorithm is adding a column to X, making it [n, d + 1] which then requires expanding the covariance matrix and the Cholesky factor. The Cholesky up/downdate (proposed in the mentioned PR) instead considers a rank-1 modification to matrix X: [n, n]. Take vector z: [1, n], the updated matrix is X' = X + z @ z.T. The updated matrix has the same size as the original, and so will its Cholesky factor, but the actual values will be different - and since this is a 'small' update to the original matrix it can be done in O(n^2) operations compared to O(n^3) for a full Cholesky factorization. Do let me know if you have further comments about whether there is interest in merging this PR. Giacomo
participants (2)
-
Alexandre Gramfort -
giacomo.meanti@gmail.com