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

Symmetric positive semi-definite (SPSD) matrix approximation methods havebeen extensively used to speed up large-scale eigenvalue computation and kernellearning methods. The standard sketch based method, which we call the prototypemodel, produces relatively accurate approximations, but is inefficient on largesquare matrices. The Nystr\"om method is highly efficient, but can only achievelow accuracy. In this paper we propose a novel model that we call the {\it fastSPSD matrix approximation model}. The fast model is nearly as efficient as theNystr\"om method and as accurate as the prototype model. We show that the fastmodel can potentially solve eigenvalue problems and kernel learning problems inlinear time with respect to the matrix size $n$ to achieve $1+\epsilon$relative-error, whereas both the prototype model and the Nystr\"om method costat least quadratic time to attain comparable error bound. Empirical comparisonsamong the prototype model, the Nystr\"om method, and our fast model demonstratethe superiority of the fast model. We also contribute new understandings of theNystr\"om method. The Nystr\"om method is a special instance of our fast modeland is approximation to the prototype model. Our technique can bestraightforwardly applied to make the CUR matrix decomposition more efficientlycomputed without much affecting the accuracy.

Towards More Efficient SPSD Matrix Approximation and CUR Matrix Decomposition