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

Learning sketching matrices for fast and accurate low-rank approximation(LRA) has gained increasing attention. Recently, Bartlett, Indyk, and Wagner(COLT 2022) presented a generalization bound for the learning-based LRA.Specifically, for rank-$k$ approximation using an $m \times n$ learnedsketching matrix with $s$ non-zeros in each column, they proved an$\tilde{\mathrm{O}}(nsm)$ bound on the \emph{fat shattering dimension}($\tilde{\mathrm{O}}$ hides logarithmic factors). We build on their work andmake two contributions.  1. We present a better $\tilde{\mathrm{O}}(nsk)$ bound ($k \le m$). En routeto obtaining this result, we give a low-complexity \emph{Goldberg--Jerrumalgorithm} for computing pseudo-inverse matrices, which would be of independentinterest.  2. We alleviate an assumption of the previous study that sketching matriceshave a fixed sparsity pattern. We prove that learning positions of non-zerosincreases the fat shattering dimension only by ${\mathrm{O}}(ns\log n)$. Inaddition, experiments confirm the practical benefit of learning sparsitypatterns.

Improved Generalization Bound and Learning of Sparsity Patterns for Data-Driven Low-Rank Approximation