ABSTRACT
CONTENTS 29.1 Introduction 648 29.2 Matrices in Large-Scale Scientific Data Analysis 649
29.2.1 A Brief Background on Matrices 649 29.2.2 Motivating Scientific Applications 650 29.2.3 Randomization as a Resource 652
29.3 Randomization Applied to Matrix Problems 652 29.3.1 Random Sampling and Random Projections 652 29.3.2 Randomization for Large-Scale Matrix Problems 655 29.3.3 A Retrospective and a Prospective 656
29.4 Randomized Algorithms for LS Approximation 657 29.4.1 Different Perspectives on LS Approximation 657 29.4.2 A Simple Algorithm for Approximating LS Approximation 658 29.4.3 A Basic Structural Result 659 29.4.4 Making This Algorithm Practical: In Theory 660 29.4.5 Making This Algorithm Practical: In Practice 661
29.5 Randomized Algorithms for Low-Rank Matrix Approximation 662 29.5.1 A Random Sampling Algorithm 662 29.5.2 A Second Random Sampling Algorithm 664 29.5.3 Several Random Projection Algorithms 666
29.6 Conclusion 668 Acknowledgments 668 References 669
29.1 INTRODUCTION This chapter reviews recent work on randomized matrix algorithms. By “randomized matrix algorithms,” we refer to a class of recently developed random sampling and random projection algorithms for ubiquitous linear algebra problems such as least-squares (LS) regression and low-rank matrix approximation. These developments have been driven by applications in large-scale data analysis-applications which place very different demands on matrices than traditional scientific computing applications. Thus, in this review, we will focus on highlighting the simplicity and generality of several core ideas that underlie the usefulness of these randomized algorithms in scientific applications such as genetics (where these algorithms have already been applied) and astronomy (where, hopefully, in part due to this review they will soon be applied).
