Foundations of Data Science∗ Avrim Blum, John Hopcroft and Ravindran Kannan Thursday 9th June, 2016

∗

Copyright 2015. All rights reserved

1

Contents 1 Introduction

8

2 High-Dimensional Space 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2.2 The Law of Large Numbers . . . . . . . . . . . . . . . 2.3 The Geometry of High Dimensions . . . . . . . . . . . 2.4 Properties of the Unit Ball . . . . . . . . . . . . . . . . 2.4.1 Volume of the Unit Ball . . . . . . . . . . . . . 2.4.2 Most of the Volume is Near the Equator . . . . 2.5 Generating Points Uniformly at Random from a Ball . 2.6 Gaussians in High Dimension . . . . . . . . . . . . . . 2.7 Random Projection and Johnson-Lindenstrauss Lemma 2.8 Separating Gaussians . . . . . . . . . . . . . . . . . . . 2.9 Fitting a Single Spherical Gaussian to Data . . . . . . 2.10 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . 2.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

11 11 11 14 15 15 17 20 21 23 25 27 29 30

3 Best-Fit Subspaces and Singular Value Decomposition (SVD) 3.1 Introduction and Overview . . . . . . . . . . . . . . . . . . . . . . . 3.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Singular Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Singular Value Decomposition (SVD) . . . . . . . . . . . . . . . . . 3.5 Best Rank-k Approximations . . . . . . . . . . . . . . . . . . . . . 3.6 Left Singular Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . 3.7 Power Method for Computing the Singular Value Decomposition . . 3.7.1 A Faster Method . . . . . . . . . . . . . . . . . . . . . . . . 3.8 Singular Vectors and Eigenvectors . . . . . . . . . . . . . . . . . . . 3.9 Applications of Singular Value Decomposition . . . . . . . . . . . . 3.9.1 Centering Data . . . . . . . . . . . . . . . . . . . . . . . . . 3.9.2 Principal Component Analysis . . . . . . . . . . . . . . . . . 3.9.3 Clustering a Mixture of Spherical Gaussians . . . . . . . . . 3.9.4 Ranking Documents and Web Pages . . . . . . . . . . . . . 3.9.5 An Application of SVD to a Discrete Optimization Problem 3.10 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

38 38 39 41 44 45 47 49 50 52 52 52 53 54 59 60 63 64

. . . . .

71 71 72 77 79 87

4 Random Graphs 4.1 The G(n, p) Model . . . . . . . . . . . . . 4.1.1 Degree Distribution . . . . . . . . . 4.1.2 Existence of Triangles in G(n, d/n) 4.2 Phase Transitions . . . . . . . . . . . . . . 4.3 The Giant Component . . . . . . . . . . . 2

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . . . . . . . . . .

. . . . .

. . . . . . . . . . . . .

. . . . .

. . . . . . . . . . . . .

. . . . .

. . . . . . . . . . . . .

. . . . .

. . . . . . . . . . . . .

. . . . .

. . . . . . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

4.4 4.5

Branching Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 Cycles and Full Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . 102 4.5.1 Emergence of Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . 102 4.5.2