Matrix Coherence and the Nystrom Method

By Ameet Talwalkar, Afshin Rostamizadeh. 2010

89 citations recorded by the source corpus.

The Nystrom method is an efficient technique used to speed up large-scale learning applications by generating low-rank approximations. Crucial to the performance of this technique is the assumption that a matrix can be well approximated by working exclusively with a subset of its columns. In this work we relate this assumption to the concept of matrix coherence, connecting coherence to the performance of the Nystrom method. Making use of related work in the compressed sensing and the matrix completion literature, we derive novel coherence-based bounds for the Nystrom method in the low-rank setting. We then present empirical results that corroborate these theoretical bounds. Finally, we present more general empirical results for the full-rank setting that convincingly demonstrate the ability of matrix coherence to measure the degree to which information can be extracted from a subset of columns.

Subfields: Biomedical Engineering, Computational Mechanics, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Biomedical Engineering

In Computational Mechanics

In Signal Processing

Citations in the corpus

Sharp analysis of low-rank kernel matrix approximations (2012, neutral): “For further experimental evaluations, see Cortes et al. (2010); Talwalkar and Rostamizadeh (2010).”
Improved Bounds for the Nyström Method With Application to Kernel Classification (2011, unknown): “3A similar assumption was used in the previous analysis of the Nyström method [10], [13], [14].”
Analyze gauss: optimal bounds for privacy-preserving principal component analysis (2014, background): “We achieve this better bound by, satisfyingly, borrowing insights and tools from differential privacy!”
Beating randomized response on incoherent matrices (2011, background): “[15], Talwalkar and Rostamizadeh [22], Mohri and Tal .e.= v . am walkar [18].”
Beyond worst-case analysis in private singular vector computation (2012, background): “Talwalkar and Rostamizadeh recently used low-coherence assumptions for the problem of (non-private) low-rank matrix approximation [14].”
Learning Semantic Image Representations at a Large Scale (2014, background): “1 Error Bounds on the Approximation Many existing analyses have computed bounds on the error made in estimating C by C′ by sampling c columns, such as [103, 67], but not between K = CC> and K′ = C′C′>, which we aim to analyze in this section.”
Divide-and-Conquer Matrix Factorization (2011, methodology): “Following the treatment of the Nyström method in Talwalkar and Rostamiza deh [36], we note that Σ − 1 2 L Z = V ⊤ L and hence that Z1 Σ − 1 2 L = Vl whereVl ∈ R contains the first l components of the leading r right singular vectors of L.”