ABSTRACT

In recent years, the amount of data that has been generated and recorded has grown enormously, and data are now seen to be at the heart of modern economic activity, innovation, and growth. See, for example, the report by the McKinsey Global Institute [51], which identifies ways in which Big Data have transformed the modern world, as well as the report by the National Research Council [19], which discusses reasons for and technical challenges in massive data analysis. In many cases, these so-called Big Data are modeled as matrices, basically since an m×n matrix A provides a natural mathematical structure with which to encode information about m objects, each of which is described by n features. As a result, while linear algebra algorithms have been of interest for decades in areas such as numerical linear algebra (NLA) and scientific computing, in recent years, there has been renewed interest in developing matrix algorithms that are appropriate for the analysis of large datasets that are represented in the form of matrices. For example, tools such as the singular value decomposition (SVD) and the related principal components analysis (PCA) [38] permit the low-rank approximation of a matrix, and they have have had a profound impact in diverse areas of science and engineering. They have also been studied extensively in large-scale machine learning and data analysis applications, in settings

of

ranging from web search engines and social network analysis to the analysis of astronomical and biological data.