English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The Column Subset Selection Problem (CSSP) and the Nystr\"om method are amongthe leading tools for constructing small low-rank approximations of largedatasets in machine learning and scientific computing. A fundamental questionin this area is: how well can a data subset of size k compete with the bestrank k approximation? We develop techniques which exploit spectral propertiesof the data matrix to obtain improved approximation guarantees which go beyondthe standard worst-case analysis. Our approach leads to significantly betterbounds for datasets with known rates of singular value decay, e.g., polynomialor exponential decay. Our analysis also reveals an intriguing phenomenon: theapproximation factor as a function of k may exhibit multiple peaks and valleys,which we call a multiple-descent curve. A lower bound we establish shows thatthis behavior is not an artifact of our analysis, but rather it is an inherentproperty of the CSSP and Nystr\"om tasks. Finally, using the example of aradial basis function (RBF) kernel, we show that both our improved bounds andthe multiple-descent curve can be observed on real datasets simply by varyingthe RBF parameter.

Improved guarantees and a multiple-descent curve for Column Subset Selection and the Nystr\"om method