Energy-based sequential sampling for low-rank PSD-matrix approximation

Hutchings, Matthew and Gauthier, Bertrand ORCID: https://orcid.org/0000-0001-5469-814X 2024. Energy-based sequential sampling for low-rank PSD-matrix approximation. SIAM Journal on Mathematics of Data Science

Preview

PDF - Accepted Post-Print Version Download (998kB) | Preview

Abstract

We introduce a pseudoconvex differentiable relaxation of the column-sampling problem for the Nyström approximation of positive-semidefinite (PSD) matrices. The relaxation is based on the interpretation of PSD matrices as integral operators and relies on the supports of measures to characterise samples of columns. We describe a class of gradient-based sequential sampling strategies which leverages the properties of the considered framework, and demonstrate its ability to produce accurate Nyström approximations. The time complexity of the stochastic variants of the discussed strategies is linear in the order of the considered PSD matrices, and the underlying computations can be easily parallelised.

Item Type:	Article
Status:	In Press
Schools:	Mathematics
Publisher:	Society for Industrial and Applied Mathematics
ISSN:	2577-0187
Funders:	EPSRC grant EP/T517951/1
Date of First Compliant Deposit:	20 August 2024
Date of Acceptance:	29 July 2024
Last Modified:	21 Aug 2024 07:32
URI:	https://orca.cardiff.ac.uk/id/eprint/171109

Actions (repository staff only)

Edit Item