Free Book: Foundations of Data Science (from Microsoft Research Lab)

By Avrim Blum, John Hopcroft, and Ravindran Kannan (2018). 

Computer science as an academic discipline began in the 1960s. Emphasis was on programming languages, compilers, operating systems, and the mathematical theory that supported these areas. Courses in theoretical computer science covered finite automata, regular expressions, context-free languages, and computability. In the 1970s, the study of algorithms was added as an important component of theory. The emphasis was on making computers useful. Today, a fundamental change is taking place and the focus is more on applications. There are many reasons for this change. The merging of computing and communications has played an important role. The enhanced ability to observe, collect, and store data in the natural sciences, in commerce, and in other fields calls for a change in our understanding of data and how to handle it in the modern setting. The emergence of the web and social networks as central aspects of daily life presents both opportunities and challenges for theory.

The book is available and freely downloadable here. For more information, visit this Microsoft webpage. More free books are available here. 

Contents

1 Introduction 9

2 High-Dimensional Space 12

2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2 The Law of Large Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 The Geometry of High Dimensions . . . . . . . . . . . . . . . . . . . . . . 15
2.4 Properties of the Unit Ball . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

• 2.4.1 Volume of the Unit Ball . . . . . . . . . . . . . . . . . . . . . . . . 17
• 2.4.2 Volume Near the Equator . . . . . . . . . . . . . . . . . . . . . . . 19

2.5 Generating Points Uniformly at Random from a Ball . . . . . . . . . . . . 22
2.6 Gaussians in High Dimension . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.7 Random Projection and Johnson-Lindenstrauss Lemma . . . . . . . . . . . 25
2.8 Separating Gaussians . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.9 Fitting a Spherical Gaussian to Data . . . . . . . . . . . . . . . . . . . . . 29
2.10 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

3 Best-Fit Subspaces and Singular Value Decomposition (SVD) 40

3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.3 Singular Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.4 Singular Value Decomposition (SVD) . . . . . . . . . . . . . . . . . . . . . 45
3.5 Best Rank-k Approximations . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.6 Left Singular Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.7 Power Method for Singular Value Decomposition . . . . . . . . . . . . . . . 51

• 3.7.1 A Faster Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

3.8 Singular Vectors and Eigenvectors . . . . . . . . . . . . . . . . . . . . . . . 54
3.9 Applications of Singular Value Decomposition . . . . . . . . . . . . . . . . 54

• 3.9.1 Centering Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
• 3.9.2 Principal Component Analysis . . . . . . . . . . . . . . . . . . . . . 56
• 3.9.3 Clustering a Mixture of Spherical Gaussians . . . . . . . . . . . . . 56
• 3.9.4 Ranking Documents and Web Pages . . . . . . . . . . . . . . . . . 62
• 3.9.5 An Application of SVD to a Discrete Optimization Problem . . . . 63

3.10 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

4 Random Walks and Markov Chains 76

4.1 Stationary Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
4.2 Markov Chain Monte Carlo . . . . . . . . . . . . . . . . . . . . . . . . . . 81

• 4.2.1 Metropolis-Hasting Algorithm . . . . . . . . . . . . . . . . . . . . . 83
• 4.2.2 Gibbs Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

4.3 Areas and Volumes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
4.4 Convergence of Random Walks on Undirected Graphs . . . . . . . . . . . . 88

• 4.4.1 Using Normalized Conductance to Prove Convergence . . . . . . . . 94

4.5 Electrical Networks and Random Walks . . . . . . . . . . . . . . . . . . . . 97
4.6 Random Walks on Undirected Graphs with Unit Edge Weights . . . . . . . 102
4.7 Random Walks in Euclidean Space . . . . . . . . . . . . . . . . . . . . . . 109
4.8 The Web as a Markov Chain . . . . . . . . . . . . . . . . . . . . . . . . . . 112
4.9 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
4.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

5 Machine Learning 129

5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
5.2 The Perceptron algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
5.3 Kernel Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
5.4 Generalizing to New Data . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
5.5 Overfitting and Uniform Convergence . . . . . . . . . . . . . . . . . . . . . 135
5.6 Illustrative Examples and Occam’s Razor . . . . . . . . . . . . . . . . . . . 138

• 5.6.1 Learning Disjunctions . . . . . . . . . . . . . . . . . . . . . . . . . 138
• 5.6.2 Occam’s Razor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
• 5.6.3 Application: Learning Decision Trees . . . . . . . . . . . . . . . . . 140

5.7 Regularization: Penalizing Complexity . . . . . . . . . . . . . . . . . . . . 141
5.8 Online Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141

• 5.8.1 An Example: Learning Disjunctions . . . . . . . . . . . . . . . . . . 142
• 5.8.2 The Halving Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 143
• 5.8.3 The Perceptron Algorithm . . . . . . . . . . . . . . . . . . . . . . . 143
• 5.8.4 Extensions: Inseparable Data and Hinge Loss . . . . . . . . . . . . 145

5.9 Online to Batch Conversion . . . . . . . . . . . . . . . . . . . . . . . . . . 146
5.10 Support-Vector Machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
5.11 VC-Dimension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148

• 5.11.1 Definitions and Key Theorems . . . . . . . . . . . . . . . . . . . . . 149
• 5.11.2 Examples: VC-Dimension and Growth Function . . . . . . . . . . . 151
• 5.11.3 Proof of Main Theorems . . . . . . . . . . . . . . . . . . . . . . . . 153
• 5.11.4 VC-Dimension of Combinations of Concepts . . . . . . . . . . . . . 156
• 5.11.5 Other Measures of Complexity . . . . . . . . . . . . . . . . . . . . . 156

5.12 Strong and Weak Learning – Boosting . . . . . . . . . . . . . . . . . . . . . 157
5.13 Stochastic Gradient Descent . . . . . . . . . . . . . . . . . . . . . . . . . . 160
5.14 Combining (Sleeping) Expert Advice . . . . . . . . . . . . . . . . . . . . . 162
5.15 Deep Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164

• 5.15.1 Generative Adversarial Networks (GANs) . . . . . . . . . . . . . . . 170

5.16 Further Current Directions . . . . . . . . . . . . . . . . . . . . . . . . . . . 171

• 5.16.1 Semi-Supervised Learning . . . . . . . . . . . . . . . . . . . . . . . 171
• 5.16.2 Active Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
• 5.16.3 Multi-Task Learning . . . . . . . . . . . . . . . . . . . . . . . . . . 174

5.17 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
5.18 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176

6 Algorithms for Massive Data Problems: Streaming, Sketching, and Sampling 181

6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
6.2 Frequency Moments of Data Streams . . . . . . . . . . . . . . . . . . . . . 182

• 6.2.1 Number of Distinct Elements in a Data Stream . . . . . . . . . . . 183
• 6.2.2 Number of Occurrences of a Given Element. . . . . . . . . . . . . . 186
• 6.2.3 Frequent Elements . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
• 6.2.4 The Second Moment . . . . . . . . . . . . . . . . . . . . . . . . . . 189

6.3 Matrix Algorithms using Sampling . . . . . . . . . . . . . . . . . . . . . . 192

• 6.3.1 Matrix Multiplication using Sampling . . . . . . . . . . . . . . . . . 193
• 6.3.2 Implementing Length Squared Sampling in Two Passes . . . . . . . 197
• 6.3.3 Sketch of a Large Matrix . . . . . . . . . . . . . . . . . . . . . . . . 197

6.4 Sketches of Documents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
6.5 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
6.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204

7 Clustering 208

7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208

• 7.1.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
• 7.1.2 Two General Assumptions on the Form of Clusters . . . . . . . . . 209
• 7.1.3 Spectral Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
• 7.2 k-Means Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
• 7.2.1 A Maximum-Likelihood Motivation . . . . . . . . . . . . . . . . . . 211
• 7.2.2 Structural Properties of the k-Means Objective . . . . . . . . . . . 212
• 7.2.3 Lloyd’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
• 7.2.4 Ward’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
• 7.2.5 k-Means Clustering on the Line . . . . . . . . . . . . . . . . . . . . 215

7.3 k-Center Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
7.4 Finding Low-Error Clusterings . . . . . . . . . . . . . . . . . . . . . . . . . 216
7.5 Spectral Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216

• 7.5.1 Why Project? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
• 7.5.2 The Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
• 7.5.3 Means Separated by Ω(1) Standard Deviations . . . . . . . . . . . . 219
• 7.5.4 Laplacians . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
• 7.5.5 Local spectral clustering . . . . . . . . . . . . . . . . . . . . . . . . 221

7.6 Approximation Stability . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224

• 7.6.1 The Conceptual Idea . . . . . . . . . . . . . . . . . . . . . . . . . . 224
• 7.6.2 Making this Formal . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
• 7.6.3 Algorithm and Analysis . . . . . . . . . . . . . . . . . . . . . . . . 225

7.7 High-Density Clusters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227

• 7.7.1 Single Linkage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
• 7.7.2 Robust Linkage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228

7.8 Kernel Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
7.9 Recursive Clustering based on Sparse Cuts . . . . . . . . . . . . . . . . . . 229
7.10 Dense Submatrices and Communities . . . . . . . . . . . . . . . . . . . . . 230
7.11 Community Finding and Graph Partitioning . . . . . . . . . . . . . . . . . 233
7.12 Spectral clustering applied to social networks . . . . . . . . . . . . . . . . . 236
7.13 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
7.14 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240

8 Random Graphs 245

8.1 The G(n, p) Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245

• 8.1.1 Degree Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
• 8.1.2 Existence of Triangles in G(n, d/n) . . . . . . . . . . . . . . . . . . 250

8.2 Phase Transitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
8.3 Giant Component . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261

• 8.3.1 Existence of a giant component . . . . . . . . . . . . . . . . . . . . 261
• 8.3.2 No other large components . . . . . . . . . . . . . . . . . . . . . . . 263
• 8.3.3 The case of p < 1/n . . . . . . . . . . . . . . . . . . . . . . . . . . . 264

8.4 Cycles and Full Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . 265

• 8.4.1 Emergence of Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . 265
• 8.4.2 Full Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266
• 8.4.3 Threshold for O(ln n) Diameter . . . . . . . . . . . . . . . . . . . . 268

8.5 Phase Transitions for Increasing Properties . . . . . . . . . . . . . . . . . . 270
8.6 Branching Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272
8.7 CNF-SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277

• 8.7.1 SAT-solvers in practice . . . . . . . . . . . . . . . . . . . . . . . . . 278
• 8.7.2 Phase Transitions for CNF-SAT . . . . . . . . . . . . . . . . . . . . 279

8.8 Nonuniform Models of Random Graphs . . . . . . . . . . . . . . . . . . . . 284

• 8.8.1 Giant Component in Graphs with Given Degree Distribution . . . . 285

8.9 Growth Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286

• 8.9.1 Growth Model Without Preferential Attachment . . . . . . . . . . . 287
• 8.9.2 Growth Model With Preferential Attachment . . . . . . . . . . . . 293

8.10 Small World Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294
8.11 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
8.12 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301

9 Topic Models, Nonnegative Matrix Factorization, Hidden Markov Models, and Graphical Models 310

9.1 Topic Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
9.2 An Idealized Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
9.3 Nonnegative Matrix Factorization – NMF . . . . . . . . . . . . . . . . . . . 315
9.4 NMF with Anchor Terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
9.5 Hard and Soft Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
9.6 The Latent Dirichlet Allocation Model for Topic Modeling . . . . . . . . . 320
9.7 The Dominant Admixture Model . . . . . . . . . . . . . . . . . . . . . . . 322
9.8 Formal Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324
9.9 Finding the Term-Topic Matrix . . . . . . . . . . . . . . . . . . . . . . . . 327
9.10 Hidden Markov Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332
9.11 Graphical Models and Belief Propagation . . . . . . . . . . . . . . . . . . . 337
9.12 Bayesian or Belief Networks . . . . . . . . . . . . . . . . . . . . . . . . . . 338
9.13 Markov Random Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339
9.14 Factor Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340
9.15 Tree Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341
9.16 Message Passing in General Graphs . . . . . . . . . . . . . . . . . . . . . . 342
9.17 Graphs with a Single Cycle . . . . . . . . . . . . . . . . . . . . . . . . . . 344
9.18 Belief Update in Networks with a Single Loop . . . . . . . . . . . . . . . . 346
9.19 Maximum Weight Matching . . . . . . . . . . . . . . . . . . . . . . . . . . 347
9.20 Warning Propagation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351
9.21 Correlation Between Variables . . . . . . . . . . . . . . . . . . . . . . . . . 351
9.22 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355
9.23 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357

10 Other Topics 360

10.1 Ranking and Social Choice . . . . . . . . . . . . . . . . . . . . . . . . . . . 360

• 10.1.1 Randomization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362
• 10.1.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363

10.2 Compressed Sensing and Sparse Vectors . . . . . . . . . . . . . . . . . . . 364

• 10.2.1 Unique Reconstruction of a Sparse Vector . . . . . . . . . . . . . . 365
• 10.2.2 Efficiently Finding the Unique Sparse Solution . . . . . . . . . . . . 366

10.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368

• 10.3.1 Biological . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368
• 10.3.2 Low Rank Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . 369

10.4 An Uncertainty Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370

• 10.4.1 Sparse Vector in Some Coordinate Basis . . . . . . . . . . . . . . . 370
• 10.4.2 A Representation Cannot be Sparse in Both Time and Frequency Domains .. . . . 371

10.5 Gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373
10.6 Linear Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375

• 10.6.1 The Ellipsoid Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 375

10.7 Integer Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377
10.8 Semi-Definite Programming . . . . . . . . . . . . . . . . . . . . . . . . . . 378
10.9 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380
10.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381

11 Wavelets 385

11.1 Dilation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385
11.2 The Haar Wavelet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386
11.3 Wavelet Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390
11.4 Solving the Dilation Equation . . . . . . . . . . . . . . . . . . . . . . . . . 390
11.5 Conditions on the Dilation Equation . . . . . . . . . . . . . . . . . . . . . 392
11.6 Derivation of the Wavelets from the Scaling Function . . . . . . . . . . . . 394
11.7 Sufficient Conditions for the Wavelets to be Orthogonal . . . . . . . . . . . 398
11.8 Expressing a Function in Terms of Wavelets . . . . . . . . . . . . . . . . . 401
11.9 Designing a Wavelet System . . . . . . . . . . . . . . . . . . . . . . . . . . 402
11.10Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402
11.11 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402
11.12 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403

12 Appendix 406

12.1 Definitions and Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406
12.2 Asymptotic Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406
12.3 Useful Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408
12.4 Useful Inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413
12.5 Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 420

• 12.5.1 Sample Space, Events, and Independence . . . . . . . . . . . . . . . 420
• 12.5.2 Linearity of Expectation . . . . . . . . . . . . . . . . . . . . . . . . 421
• 12.5.3 Union Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422
• 12.5.4 Indicator Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . 422
• 12.5.5 Variance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422
• 12.5.6 Variance of the Sum of Independent Random Variables . . . . . . . 423
• 12.5.7 Median . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423
• 12.5.8 The Central Limit Theorem . . . . . . . . . . . . . . . . . . . . . . 423
• 12.5.9 Probability Distributions . . . . . . . . . . . . . . . . . . . . . . . . 424
• 12.5.10 Bayes Rule and Estimators . . . . . . . . . . . . . . . . . . . . . . . 428

12.6 Bounds on Tail Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . 430

• 12.6.1 Chernoff Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . 430
• 12.6.2 More General Tail Bounds . . . . . . . . . . . . . . . . . . . . . . . 433

12.7 Applications of the Tail Bound . . . . . . . . . . . . . . . . . . . . . . . . 436
12.8 Eigenvalues and Eigenvectors . . . . . . . . . . . . . . . . . . . . . . . . . 437

• 12.8.1 Symmetric Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . 439
• 12.8.2 Relationship between SVD and Eigen Decomposition . . . . . . . . 441
• 12.8.3 Extremal Properties of Eigenvalues . . . . . . . . . . . . . . . . . . 441
• 12.8.4 Eigenvalues of the Sum of Two Symmetric Matrices . . . . . . . . . 443
• 12.8.5 Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445
• 12.8.6 Important Norms and Their Properties . . . . . . . . . . . . . . . . 446
• 12.8.7 Additional Linear Algebra . . . . . . . . . . . . . . . . . . . . . . . 448
• 12.8.8 Distance between subspaces . . . . . . . . . . . . . . . . . . . . . . 450
• 12.8.9 Positive semidefinite matrix . . . . . . . . . . . . . . . . . . . . . . 451

12.9 Generating Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451

• 12.9.1 Generating Functions for Sequences Defined by Recurrence Relationships . . . . . . 452
• 12.9.2 The Exponential Generating Function and the Moment Generating Function . . . . . . . 454

12.10 Miscellaneous . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456

• 12.10.1 Lagrange multipliers . . . . . . . . . . . . . . . . . . . . . . . . . . 456
• 12.10.2 Finite Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457
• 12.10.3 Application of Mean Value Theorem . . . . . . . . . . . . . . . . . 457
• 12.10.4 Sperner’s Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459
• 12.10.5 Prufer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459

12.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460

Index