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 statistical leverage scores of a matrix $A$ are the squared row-norms ofthe matrix containing its (top) left singular vectors and the coherence is thelargest leverage score. These quantities are of interest in recently-popularproblems such as matrix completion and Nystr\"{o}m-based low-rank matrixapproximation as well as in large-scale statistical data analysis applicationsmore generally; moreover, they are of interest since they define the keystructural nonuniformity that must be dealt with in developing fast randomizedmatrix algorithms. Our main result is a randomized algorithm that takes asinput an arbitrary $n \times d$ matrix $A$, with $n \gg d$, and that returns asoutput relative-error approximations to all $n$ of the statistical leveragescores. The proposed algorithm runs (under assumptions on the precise values of$n$ and $d$) in $O(n d \log n)$ time, as opposed to the $O(nd^2)$ time requiredby the na\"{i}ve algorithm that involves computing an orthogonal basis for therange of $A$. Our analysis may be viewed in terms of computing a relative-errorapproximation to an underconstrained least-squares approximation problem, or,relatedly, it may be viewed as an application of Johnson-Lindenstrauss typeideas. Several practically-important extensions of our basic result are alsodescribed, including the approximation of so-called cross-leverage scores, theextension of these ideas to matrices with $n \approx d$, and the extension tostreaming environments.

Fast approximation of matrix coherence and statistical leverage