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

Low-rank approximation is a task of critical importance in modern science,engineering, and statistics. Many low-rank approximation algorithms, such asthe randomized singular value decomposition (RSVD), project their input matrixinto a subspace approximating the span of its leading singular vectors. Otheralgorithms compress their input into a small subset of representative rows orcolumns, leading to a so-called interpolative decomposition. This paperinvestigates how the accuracy of interpolative decompositions is affected bythe structural properties of the input matrix being operated on, including howthese properties affect the performance comparison between interpolativedecompositions and RSVD. We also introduce a novel method of interpolativedecomposition in the form of the randomized Golub-Klema-Stewart (RGKS)algorithm, which combines RSVD with a pivoting strategy for column subsetselection. Through numerical experiments, we find that matrix structuresincluding singular subspace geometry and singular spectrum decay play asignificant role in determining the performance comparison between thesedifferent algorithms. We also prove inequalities which bound the error of ageneral interpolative decomposition in terms of these matrix structures.Lastly, we develop forms of these bounds specialized to RGKS while consideringhow randomization affects the approximation error of this algorithm.

Structure-Aware Analyses and Algorithms for Interpolative Decompositions