Fast approximation of matrix coherence and statistical leverage

Details Fast approximation of matrix coherence and statistical leverage Fast approximation of matrix coherence and statistical leverage

2011-09-18

arxiv.org/abs/1109.3843v1

Computer Science

Data Structures and Algorithms

28 pages

Scientific paper

The \emph{statistical leverage scores} of a matrix $A$ are the squared row-norms of the matrix containing its (top) left singular vectors and the \emph{coherence} is the largest leverage score. These quantities have been of interest in recently-popular problems such as matrix completion and Nystr\"{o}m-based low-rank matrix approximation; in large-scale statistical data analysis applications more generally; and since they define the key structural nonuniformity that must be dealt with in developing fast randomized matrix algorithms. Our main result is a randomized algorithm that takes as input an arbitrary $n \times d$ matrix $A$, with $n \gg d$, and that returns as output relative-error approximations to \emph{all} $n$ of the statistical leverage scores. 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 required by the na\"{i}ve algorithm that involves computing an orthogonal basis for the range of $A$. Our analysis may be viewed in terms of computing a relative-error approximation to an \emph{under}constrained least-squares approximation problem, or, relatedly, it may be viewed as an application of Johnson-Lindenstrauss type ideas. Several practically-important extensions of our basic result are also described, including the approximation of so-called cross-leverage scores, the extension of these ideas to matrices with $n \approx d$, and the extension to streaming environments.

Affiliated with

Also associated with

No associations

Rating

Fast approximation of matrix coherence and statistical leverage does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Fast approximation of matrix coherence and statistical leverage, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast approximation of matrix coherence and statistical leverage will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-560476