Stat260/cs294: Randomized Algorithms for Matrices and Data

How researchers see this paper

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

Citations in the corpus

On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions (2015, background): “-bounded explicitly for many examples, as we now explain. The computation of dmax(1,λ) in the operator setting (for which we may use q= 1), a quantity often referred to as the maximal leverage score (Mahoney, 2011), remains an open problem. The quantity d(λ) only depends on the integral operator Σ, ”
Sharp analysis of low-rank kernel matrix approximations (2012, neutral): “…increases, the decay of the relative prediction error is much faster than the error in matrix approximation, suggesting that relying on good kernel matrix approximation may be suboptimal if the goal is simply to predict well. for linear prediction problems (Mahoney, 2011; Maillard and Munos, 2009).”
Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm (2013, neutral): “sampling – where it goes by the name of leverage score sampling. The resulting sampling methods are again proportional to the squared Euclidean norms of rows and columns of the underlying matrix. See [5, 25, 44, 9], and references therein for applications to the column subset selection problem and m”
Straggler Mitigation in Distributed Optimization Through Data Encoding (2017, methodology): “Our technique is also closely related to randomized linear algebra and sketching techniques [14, 6, 17], used for dimensionality reduction of large convex optimization problems.”
Randomized numerical linear algebra: Foundations and algorithms (2020, methodology): “M. W. Mahoney (2011), ‘Randomized algorithms for matrices and data’, Foundations and Trends R© in Machine Learning 3(2), 123–224.”
Efficient Multi-label Classification with Many Labels (2013, background): “Empirically , a proper choice of c can be sensitive to the label matrix (Mahoney, 2011).”
Efficient matrix completion for seismic data reconstruction (2015, methodology): “…seismic data reconstruction with the method of projection onto convex sets, where they use a low-rank approximation of the Hankel matrix via the randomized singular value decomposition (Liberty et al., 2007; Halko et al., 2011; Mahoney, 2011) to interpolate seismic temporal frequency slices.”
Learning Two Layer Rectified Neural Networks in Polynomial Time (2018, background): “For an excellent survey on leverage scores, we refer the reader to Mahoney et al. (2011). We note that the set of leverage scores of M does not depend on the choice of orthonormal basis P or Q Woodruff et al. (2014). Thus, to obtain the bounds given in Equation 7, it suffices let P be any matrix wit”
An Introduction to Matrix Concentration Inequalities (2015, unknown): “The survey [80] explains how to implement this method in practice, while the two monographs [120, 193] cover more theoretical aspects.”
Fast approximation of matrix coherence and statistical leverage (2011, methodology): “For our main results, we will also need a stronger requirement than the simple ǫ-JLT and so we will use a version of the Fast Johnson-Lindenstrauss Transform (FJLT), which was originally introduced in [2, 3].”