2016 RandNLARandomizedNumericalLinea

• (Drineas & Mahoney, 2016) ⇒ Petros Drineas, and Michael W. Mahoney. (2016). “RandNLA: Randomized Numerical Linear Algebra.” In: Communications of the ACM Journal, 59(6). doi:10.1145/2842602

Subject Headings: Randomized Linear Algebra.

Cited By

• http://scholar.google.com/scholar?q=%222016%22+RandNLA%3A+Randomized+Numerical+Linear+Algebra
• http://dl.acm.org/citation.cfm?id=2942427.2842602&preflayout=flat#citedby

Quotes

Abstract

Randomization offers new benefits for large-scale linear algebra computations.

1. Introduction

Matrices are ubiquitous in computer science, statistics, and applied mathematics. An m × n matrix can encode information about m objects (each described by n features), or the behavior of a discretized differential operator on a finite element mesh; an n × n positive-definite matrix can encode the correlations between all pairs of n objects, or the edge-connectivity between all pairs of nodes in a social network; and so on. Motivated largely by technological developments that generate extremely large scientific and Internet datasets, recent years have witnessed exciting developments in the theory and practice of matrix algorithms. Particularly remarkable is the use of randomization — typically assumed to be a property of the input data due to, for example, noise in the data generation mechanisms — as an algorithmic or computational resource for the development of improved algorithms for fundamental matrix problems such as matrix multiplication, least-squares (LS) approximation, low-rank matrix approximation, and Laplacian-based linear equation solvers.

Randomized Numerical Linear Algebra (RandNLA) is an interdisciplinary research area that exploits randomization as a computational resource to develop improved algorithms for large-scale linear algebra problems.32 From a foundational perspective, RandNLA has its roots in theoretical computer science (TCS), with deep connections to mathematics (convex analysis, probability theory, metric embedding theory) and applied mathematics (scientific computing, signal processing, numerical linear algebra). From an applied perspective, RandNLA is a vital new tool for machine learning, statistics, and data analysis. Well-engineered implementations have already outperformed highly optimized software libraries for ubiquitous problems such as least-squares, 4, 35 with good scalability in parallel and distributed environments.52 Moreover, RandNLA promises a sound algorithmic and statistical foundation for modern large-scale data analysis.

…

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2016 RandNLARandomizedNumericalLinea	Michael W. Mahoney Petros Drineas			RandNLA: Randomized Numerical Linear Algebra				10.1145/2842602		2016