Statistics – Machine Learning
Scientific paper
2010-09-04
Statistics
Machine Learning
Scientific paper
Low-rank matrix approximations are often used to help scale standard machine learning algorithms to large-scale problems. Recently, matrix coherence has been used to characterize the ability to extract global information from a subset of matrix entries in the context of these low-rank approximations and other sampling-based algorithms, e.g., matrix com- pletion, robust PCA. Since coherence is defined in terms of the singular vectors of a matrix and is expensive to compute, the practical significance of these results largely hinges on the following question: Can we efficiently and accurately estimate the coherence of a matrix? In this paper we address this question. We propose a novel algorithm for estimating coherence from a small number of columns, formally analyze its behavior, and derive a new coherence-based matrix approximation bound based on this analysis. We then present extensive experimental results on synthetic and real datasets that corroborate our worst-case theoretical analysis, yet provide strong support for the use of our proposed algorithm whenever low-rank approximation is being considered. Our algorithm efficiently and accurately estimates matrix coherence across a wide range of datasets, and these coherence estimates are excellent predictors of the effectiveness of sampling-based matrix approximation on a case-by-case basis.
Mohri Mehryar
Talwalkar Ameet
No associations
LandOfFree
On the Estimation of Coherence 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 On the Estimation of Coherence, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Estimation of Coherence will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-285021