Linear algebra and optimization with applications to machine learning Jean Gallier, Jocelyn Quaintance.

Volume I. Linear algebra for computer vision, robotics, and machine learning -- Volume II. Fundamentals of optimization theory with applications to machine learning 1 Introduction 11
2 Vector Spaces, Bases, Linear Maps 15
2.1 Motivations: Linear Combinations, Linear Independence, Rank . . . . . . . 15
2.2 Vector Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3 Indexed Families; the Sum Notation P
i2I ai . . . . . . . . . . . . . . . . . . 34
2.4 Linear Independence, Subspaces . . . . . . . . . . . . . . . . . . . . . . . . 40
2.5 Bases of a Vector Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.6 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
2.7 Linear Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
2.8 Linear Forms and the Dual Space . . . . . . . . . . . . . . . . . . . . . . . . 65
2.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
2.10 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
3 Matrices and Linear Maps 77
3.1 Representation of Linear Maps by Matrices . . . . . . . . . . . . . . . . . . 77
3.2 Composition of Linear Maps and Matrix Multiplication . . . . . . . . . . . 82
3.3 Change of Basis Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.4 The E↵ect of a Change of Bases on Matrices . . . . . . . . . . . . . . . . . 90
3.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
3.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
4 Haar Bases, Haar Wavelets, Hadamard Matrices 101
4.1 Introduction to Signal Compression Using Haar Wavelets . . . . . . . . . . 101
4.2 Haar Matrices, Scaling Properties of Haar Wavelets . . . . . . . . . . . . . . 103
4.3 Kronecker Product Construction of Haar Matrices . . . . . . . . . . . . . . 108
4.4 Multiresolution Signal Analysis with Haar Bases . . . . . . . . . . . . . . . 110
4.5 Haar Transform for Digital Images . . . . . . . . . . . . . . . . . . . . . . . 112
4.6 Hadamard Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
4.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
4.8 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
5 Direct Sums, Rank-Nullity Theorem, Ane Maps 125
5.1 Direct Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
5.2 Sums and Direct Sums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
5.3 The Rank-Nullity Theorem; Grassmann’s Relation . . . . . . . . . . . . . . 131
5.4 Ane Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
5.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
5.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
6 Determinants 153
6.1 Permutations, Signature of a Permutation . . . . . . . . . . . . . . . . . . . 153
6.2 Alternating Multilinear Maps . . . . . . . . . . . . . . . . . . . . . . . . . . 158
6.3 Definition of a Determinant . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
6.4 Inverse Matrices and Determinants . . . . . . . . . . . . . . . . . . . . . . . 170
6.5 Systems of Linear Equations and Determinants . . . . . . . . . . . . . . . . 173
6.6 Determinant of a Linear Map . . . . . . . . . . . . . . . . . . . . . . . . . . 175
6.7 The Cayley–Hamilton Theorem . . . . . . . . . . . . . . . . . . . . . . . . . 176
6.8 Permanents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
6.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
6.10 Further Readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
6.11 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
7 Gaussian Elimination, LU, Cholesky, Echelon Form 191
7.1 Motivating Example: Curve Interpolation . . . . . . . . . . . . . . . . . . . 191
7.2 Gaussian Elimination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
7.3 Elementary Matrices and Row Operations . . . . . . . . . . . . . . . . . . . 200
7.4 LU-Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
7.5 P A = LU Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
7.6 Proof of Theorem 7.5 ~ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
7.7 Dealing with Roundo↵ Errors; Pivoting Strategies . . . . . . . . . . . . . . . 223
7.8 Gaussian Elimination of Tridiagonal Matrices . . . . . . . . . . . . . . . . . 224
7.9 SPD Matrices and the Cholesky Decomposition . . . . . . . . . . . . . . . . 226
7.10 Reduced Row Echelon Form . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
7.11 RREF, Free Variables, Homogeneous Systems . . . . . . . . . . . . . . . . . 241
7.12 Uniqueness of RREF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
7.13 Solving Linear Systems Using RREF . . . . . . . . . . . . . . . . . . . . . . 246
7.14 Elementary Matrices and Columns Operations . . . . . . . . . . . . . . . . 253
7.15 Transvections and Dilatations ~ . . . . . . . . . . . . . . . . . . . . . . . . 254
7.16 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
7.17 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261
8 Vector Norms and Matrix Norms 273
8.1 Normed Vector Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273
8.2 Matrix Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
8.3 Subordinate Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
8.4 Inequalities Involving Subordinate Norms . . . . . . . . . . . . . . . . . . . 296
8.5 Condition Numbers of Matrices . . . . . . . . . . . . . . . . . . . . . . . . . 298
8.6 An Application of Norms: Inconsistent Linear Systems . . . . . . . . . . . . 307
8.7 Limits of Sequences and Series . . . . . . . . . . . . . . . . . . . . . . . . . 308
8.8 The Matrix Exponential . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311
8.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314
8.10 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316
9 Iterative Methods for Solving Linear Systems 323
9.1 Convergence of Sequences of Vectors and Matrices . . . . . . . . . . . . . . 323
9.2 Convergence of Iterative Methods . . . . . . . . . . . . . . . . . . . . . . . . 326
9.3 Methods of Jacobi, Gauss–Seidel, and Relaxation . . . . . . . . . . . . . . . 328
9.4 Convergence of the Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . 336
9.5 Convergence Methods for Tridiagonal Matrices . . . . . . . . . . . . . . . . 339
9.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343
9.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344
10 The Dual Space and Duality 347
10.1 The Dual Space E⇤ and Linear Forms . . . . . . . . . . . . . . . . . . . . . 347
10.2 Pairing and Duality Between E and E⇤ . . . . . . . . . . . . . . . . . . . . 354
10.3 The Duality Theorem and Some Consequences . . . . . . . . . . . . . . . . 359
10.4 The Bidual and Canonical Pairings . . . . . . . . . . . . . . . . . . . . . . . 364
10.5 Hyperplanes and Linear Forms . . . . . . . . . . . . . . . . . . . . . . . . . 366
10.6 Transpose of a Linear Map and of a Matrix . . . . . . . . . . . . . . . . . . 367
10.7 Properties of the Double Transpose . . . . . . . . . . . . . . . . . . . . . . . 372
10.8 The Four Fundamental Subspaces . . . . . . . . . . . . . . . . . . . . . . . 374
10.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377
10.10 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378
11 Euclidean Spaces 381
11.1 Inner Products, Euclidean Spaces . . . . . . . . . . . . . . . . . . . . . . . . 381
11.2 Orthogonality and Duality in Euclidean Spaces . . . . . . . . . . . . . . . . 390
11.3 Adjoint of a Linear Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397
11.4 Existence and Construction of Orthonormal Bases . . . . . . . . . . . . . . 400
11.5 Linear Isometries (Orthogonal Transformations) . . . . . . . . . . . . . . . . 407
11.6 The Orthogonal Group, Orthogonal Matrices . . . . . . . . . . . . . . . . . 410
11.7 The Rodrigues Formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412
11.8 QR-Decomposition for Invertible Matrices . . . . . . . . . . . . . . . . . . . 415
11.9 Some Applications of Euclidean Geometry . . . . . . . . . . . . . . . . . . . 420
11.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 421
11.11 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423
12 QR-Decomposition for Arbitrary Matrices 435
12.1 Orthogonal Reflections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435
12.2 QR-Decomposition Using Householder Matrices . . . . . . . . . . . . . . . . 440
12.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 450
12.4 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 450
13 Hermitian Spaces 457
13.1 Hermitian Spaces, Pre-Hilbert Spaces . . . . . . . . . . . . . . . . . . . . . 457
13.2 Orthogonality, Duality, Adjoint of a Linear Map . . . . . . . . . . . . . . . 466
13.3 Linear Isometries (Also Called Unitary Transformations) . . . . . . . . . . . 471
13.4 The Unitary Group, Unitary Matrices . . . . . . . . . . . . . . . . . . . . . 473
13.5 Hermitian Reflections and QR-Decomposition . . . . . . . . . . . . . . . . . 476
13.6 Orthogonal Projections and Involutions . . . . . . . . . . . . . . . . . . . . 481
13.7 Dual Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484
13.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 491
13.9 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 492
14 Eigenvectors and Eigenvalues 497
14.1 Eigenvectors and Eigenvalues of a Linear Map . . . . . . . . . . . . . . . . . 497
14.2 Reduction to Upper Triangular Form . . . . . . . . . . . . . . . . . . . . . . 505
14.3 Location of Eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 509
14.4 Conditioning of Eigenvalue Problems . . . . . . . . . . . . . . . . . . . . . . 512
14.5 Eigenvalues of the Matrix Exponential . . . . . . . . . . . . . . . . . . . . . 515
14.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517
14.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 518
15 Unit Quaternions and Rotations in SO(3) 529
15.1 The Group SU(2) and the Skew Field H of Quaternions . . . . . . . . . . . 529
15.2 Representation of Rotation in SO(3) By Quaternions in SU(2) . . . . . . . 531
15.3 Matrix Representation of the Rotation rq . . . . . . . . . . . . . . . . . . . 536
15.4 An Algorithm to Find a Quaternion Representing a Rotation . . . . . . . . 538
15.5 The Exponential Map exp: su(2) ! SU(2) . . . . . . . . . . . . . . . . . . 541
15.6 Quaternion Interpolation ~ . . . . . . . . . . . . . . . . . . . . . . . . . . . 543
15.7 Nonexistence of a “Nice” Section from SO(3) to SU(2) . . . . . . . . . . . . 545
15.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 547
15.9 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 548
16 Spectral Theorems 551
16.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 551
16.2 Normal Linear Maps: Eigenvalues and Eigenvectors . . . . . . . . . . . . . . 551
16.3 Spectral Theorem for Normal Linear Maps . . . . . . . . . . . . . . . . . . . 557
16.4 Self-Adjoint and Other Special Linear Maps . . . . . . . . . . . . . . . . . . 562
16.5 Normal and Other Special Matrices . . . . . . . . . . . . . . . . . . . . . . . 568
16.6 Rayleigh–Ritz Theorems and Eigenvalue Interlacing . . . . . . . . . . . . . 571
16.7 The Courant–Fischer Theorem; Perturbation Results . . . . . . . . . . . . . 576
16.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 579
16.9 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 580
17 Computing Eigenvalues and Eigenvectors 587
17.1 The Basic QR Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 589
17.2 Hessenberg Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 595
17.3 Making the QR Method More Ecient Using Shifts . . . . . . . . . . . . . 601
17.4 Krylov Subspaces; Arnoldi Iteration . . . . . . . . . . . . . . . . . . . . . . 606
17.5 GMRES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 610
17.6 The Hermitian Case; Lanczos Iteration . . . . . . . . . . . . . . . . . . . . . 611
17.7 Power Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 612
17.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 614
17.9 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 615
18 Graphs and Graph Laplacians; Basic Facts 617
18.1 Directed Graphs, Undirected Graphs, Weighted Graphs . . . . . . . . . . . 620
18.2 Laplacian Matrices of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 627
18.3 Normalized Laplacian Matrices of Graphs . . . . . . . . . . . . . . . . . . . 631
18.4 Graph Clustering Using Normalized Cuts . . . . . . . . . . . . . . . . . . . 635
18.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 637
18.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 638
19 Spectral Graph Drawing 641
19.1 Graph Drawing and Energy Minimization . . . . . . . . . . . . . . . . . . . 641
19.2 Examples of Graph Drawings . . . . . . . . . . . . . . . . . . . . . . . . . . 644
19.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 648
20 Singular Value Decomposition and Polar Form 651
20.1 Properties of f ⇤ f . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 651
20.2 Singular Value Decomposition for Square Matrices . . . . . . . . . . . . . . 655
20.3 Polar Form for Square Matrices . . . . . . . . . . . . . . . . . . . . . . . . . 658
20.4 Singular Value Decomposition for Rectangular Matrices . . . . . . . . . . . 661
20.5 Ky Fan Norms and Schatten Norms . . . . . . . . . . . . . . . . . . . . . . 664
20.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 665
20.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 665
21 Applications of SVD and Pseudo-Inverses 669
21.1 Least Squares Problems and the Pseudo-Inverse . . . . . . . . . . . . . . . . 669
21.2 Properties of the Pseudo-Inverse . . . . . . . . . . . . . . . . . . . . . . . . 676
21.3 Data Compression and SVD . . . . . . . . . . . . . . . . . . . . . . . . . . . 681
21.4 Principal Components Analysis (PCA) . . . . . . . . . . . . . . . . . . . . . 683
21.5 Best Ane Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . 694
21.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 698
21.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 699
22 Annihilating Polynomials; Primary Decomposition 703
22.1 Basic Properties of Polynomials; Ideals, GCD’s . . . . . . . . . . . . . . . . 705
22.2 Annihilating Polynomials and the Minimal Polynomial . . . . . . . . . . . . 710
22.3 Minimal Polynomials of Diagonalizable Linear Maps . . . . . . . . . . . . . 711
22.4 Commuting Families of Linear Maps . . . . . . . . . . . . . . . . . . . . . . 714
22.5 The Primary Decomposition Theorem . . . . . . . . . . . . . . . . . . . . . 717
22.6 Jordan Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 724
22.7 Nilpotent Linear Maps and Jordan Form . . . . . . . . . . . . . . . . . . . . 726
22.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 732
22.9 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 733
Bibliography 735

"This book provides the mathematical fundamentals of linear algebra to practicers in computer vision, machine learning, robotics, applied mathematics, and electrical engineering. By only assuming a knowledge of calculus, the authors develop, in a rigorous yet down to earth manner, the mathematical theory behind concepts such as: vectors spaces, bases, linear maps, duality, Hermitian spaces, the spectral theorems, SVD, and the primary decomposition theorem. At all times, pertinent real-world applications are provided. This book includes the mathematical explanations for the tools used which we believe that is adequate for computer scientists, engineers and mathematicians who really want to do serious research and make significant contributions in their respective fields"--

Includes bibliographical references and index.