Introduction to Applied Linear Algebra Vectors, Matrices, and Least Squares

I Vectors 1 1 Vectors 3 1.1 Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Vector addition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.3 Scalar-vector multiplication . . . . . . . . . . . . . . . . . . . . . . . . 15 1.4 Inner product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.5 Complexity of vector computations . . . . . . . . . . . . . . . . . . . . 22 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2 Linear functions 29 2.1 Linear functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.2 Taylor approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.3 Regression model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3 Norm and distance 45 3.1 Norm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.2 Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.3 Standard deviation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 3.4 Angle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.5 Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4 Clustering 69 4.1 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 4.2 A clustering objective . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 4.3 The k-means algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 74 4.4 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 4.5 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 viii Contents 5 Linear independence 89 5.1 Linear dependence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 5.2 Basis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 5.3 Orthonormal vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 5.4 Gram{Schmidt algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 97 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 II Matrices 105 6 Matrices 107 6.1 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 6.2 Zero and identity matrices . . . . . . . . . . . . . . . . . . . . . . . . 113 6.3 Transpose, addition, and norm . . . . . . . . . . . . . . . . . . . . . . 115 6.4 Matrix-vector multiplication . . . . . . . . . . . . . . . . . . . . . . . . 118 6.5 Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 7 Matrix examples 129 7.1 Geometric transformations . . . . . . . . . . . . . . . . . . . . . . . . 129 7.2 Selectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 7.3 Incidence matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 7.4 Convolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 8 Linear equations 147 8.1 Linear and ane functions . . . . . . . . . . . . . . . . . . . . . . . . 147 8.2 Linear function models . . . . . . . . . . . . . . . . . . . . . . . . . . 150 8.3 Systems of linear equations . . . . . . . . . . . . . . . . . . . . . . . . 152 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 9 Linear dynamical systems 163 9.1 Linear dynamical systems . . . . . . . . . . . . . . . . . . . . . . . . . 163 9.2 Population dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 9.3 Epidemic dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 9.4 Motion of a mass . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 9.5 Supply chain dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . 171 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 10 Matrix multiplication 177 10.1 Matrix-matrix multiplication . . . . . . . . . . . . . . . . . . . . . . . 177 10.2 Composition of linear functions . . . . . . . . . . . . . . . . . . . . . . 183 10.3 Matrix power . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 10.4 QR factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 Contents ix 11 Matrix inverses 199 11.1 Left and right inverses . . . . . . . . . . . . . . . . . . . . . . . . . . . 199 11.2 Inverse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202 11.3 Solving linear equations . . . . . . . . . . . . . . . . . . . . . . . . . . 207 11.4 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210 11.5 Pseudo-inverse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 III Least squares 223 12 Least squares 225 12.1 Least squares problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 12.2 Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227 12.3 Solving least squares problems . . . . . . . . . . . . . . . . . . . . . . 231 12.4 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239 13 Least squares data tting 245 13.1 Least squares data tting . . . . . . . . . . . . . . . . . . . . . . . . . 245 13.2 Validation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260 13.3 Feature engineering . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279 14 Least squares classication 285 14.1 Classication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285 14.2 Least squares classier . . . . . . . . . . . . . . . . . . . . . . . . . . . 288 14.3 Multi-class classiers . . . . . . . . . . . . . . . . . . . . . . . . . . . 297 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305 15 Multi-objective least squares 309 15.1 Multi-objective least squares . . . . . . . . . . . . . . . . . . . . . . . 309 15.2 Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314 15.3 Estimation and inversion . . . . . . . . . . . . . . . . . . . . . . . . . 316 15.4 Regularized data tting . . . . . . . . . . . . . . . . . . . . . . . . . . 325 15.5 Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334 16 Constrained least squares 339 16.1 Constrained least squares problem . . . . . . . . . . . . . . . . . . . . 339 16.2 Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344 16.3 Solving constrained least squares problems . . . . . . . . . . . . . . . . 347 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352