Fast approximation of matrix coherence and statistical leverage

Abstraction: Randomized O(nd log n) algorithm for all statistical leverage scores

Key points:

• Authors: Drineas, Magdon-Ismail, Mahoney, Woodruff (arXiv 1109.3843, 2011)
• Statistical leverage scores = squared row-norms of the top left singular vectors of a matrix; coherence = the largest leverage score
• Leverage scores define structural nonuniformity critical for fast randomized matrix algorithms (e.g., matrix completion, Nystrom approximation)
• Naive algorithm requires O(nd^2) time; proposed randomized algorithm runs in O(nd log n) for n >> d
• Algorithm returns relative-error approximations to all n leverage scores simultaneously
• Analysis uses Johnson-Lindenstrauss ideas; extensions cover cross-leverage scores and streaming settings

Connections: Statistical Leverage · Randomized Algorithms · Low Rank Matrix Approximation · Johnson Lindenstrauss · Arxiv

Source: http://arxiv.org/abs/1109.3843