机器学习数学全书：面向CS的线性代数、拓扑、微积分和最优化

【实例截图】英文版pdf ，1962页

【核心代码】

Contents
Contents 3
1 Introduction 17
2 Groups, Rings, and Fields 19
2.1 Groups, Subgroups, Cosets . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2 Cyclic Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.3 Rings and Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
I Linear Algebra 43
3 Vector Spaces, Bases, Linear Maps 45
3.1 Motivations: Linear Combinations, Linear Independence, Rank . . . . . . . 45
3.2 Vector Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.3 Indexed Families; the Sum Notation P
i∈I
ai
. . . . . . . . . . . . . . . . . . 60
3.4 Linear Independence, Subspaces . . . . . . . . . . . . . . . . . . . . . . . . 66
3.5 Bases of a Vector Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
3.6 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
3.7 Linear Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
3.8 Quotient Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
3.9 Linear Forms and the Dual Space . . . . . . . . . . . . . . . . . . . . . . . . 94
3.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
3.11 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
4 Matrices and Linear Maps 107
4.1 Representation of Linear Maps by Matrices . . . . . . . . . . . . . . . . . . 107
4.2 Composition of Linear Maps and Matrix Multiplication . . . . . . . . . . . 112
4.3 Change of Basis Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
4.4 The Effect of a Change of Bases on Matrices . . . . . . . . . . . . . . . . . 120
4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
4.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
5 Haar Bases, Haar Wavelets, Hadamard Matrices 131
3
4 CONTENTS
5.1 Introduction to Signal Compression Using Haar Wavelets . . . . . . . . . . 131
5.2 Haar Matrices, Scaling Properties of Haar Wavelets . . . . . . . . . . . . . . 133
5.3 Kronecker Product Construction of Haar Matrices . . . . . . . . . . . . . . 138
5.4 Multiresolution Signal Analysis with Haar Bases . . . . . . . . . . . . . . . 140
5.5 Haar Transform for Digital Images . . . . . . . . . . . . . . . . . . . . . . . 142
5.6 Hadamard Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
5.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
5.8 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
6 Direct Sums 155
6.1 Sums, Direct Sums, Direct Products . . . . . . . . . . . . . . . . . . . . . . 155
6.2 The Rank-Nullity Theorem; Grassmann’s Relation . . . . . . . . . . . . . . 165
6.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
6.4 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
7 Determinants 181
7.1 Permutations, Signature of a Permutation . . . . . . . . . . . . . . . . . . . 181
7.2 Alternating Multilinear Maps . . . . . . . . . . . . . . . . . . . . . . . . . . 185
7.3 Definition of a Determinant . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
7.4 Inverse Matrices and Determinants . . . . . . . . . . . . . . . . . . . . . . . 197
7.5 Systems of Linear Equations and Determinants . . . . . . . . . . . . . . . . 200
7.6 Determinant of a Linear Map . . . . . . . . . . . . . . . . . . . . . . . . . . 203
7.7 The Cayley–Hamilton Theorem . . . . . . . . . . . . . . . . . . . . . . . . . 203
7.8 Permanents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
7.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
7.10 Further Readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
7.11 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
8 Gaussian Elimination, LU, Cholesky, Echelon Form 219
8.1 Motivating Example: Curve Interpolation . . . . . . . . . . . . . . . . . . . 219
8.2 Gaussian Elimination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
8.3 Elementary Matrices and Row Operations . . . . . . . . . . . . . . . . . . . 228
8.4 LU-Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
8.5 P A = LU Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
8.6 Proof of Theorem 8.5 ~ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
8.7 Dealing with Roundoff Errors; Pivoting Strategies . . . . . . . . . . . . . . . 251
8.8 Gaussian Elimination of Tridiagonal Matrices . . . . . . . . . . . . . . . . . 252
8.9 SPD Matrices and the Cholesky Decomposition . . . . . . . . . . . . . . . . 254
8.10 Reduced Row Echelon Form . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
8.11 RREF, Free Variables, Homogeneous Systems . . . . . . . . . . . . . . . . . 269
8.12 Uniqueness of RREF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272
8.13 Solving Linear Systems Using RREF . . . . . . . . . . . . . . . . . . . . . . 274
8.14 Elementary Matrices and Columns Operations . . . . . . . . . . . . . . . . 281
CONTENTS 5
8.15 Transvections and Dilatations ~ . . . . . . . . . . . . . . . . . . . . . . . . 282
8.16 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287
8.17 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
9 Vector Norms and Matrix Norms 301
9.1 Normed Vector Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301
9.2 Matrix Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312
9.3 Subordinate Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
9.4 Inequalities Involving Subordinate Norms . . . . . . . . . . . . . . . . . . . 324
9.5 Condition Numbers of Matrices . . . . . . . . . . . . . . . . . . . . . . . . . 326
9.6 An Application of Norms: Inconsistent Linear Systems . . . . . . . . . . . . 335
9.7 Limits of Sequences and Series . . . . . . . . . . . . . . . . . . . . . . . . . 336
9.8 The Matrix Exponential . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339
9.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342
9.10 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344
10 Iterative Methods for Solving Linear Systems 351
10.1 Convergence of Sequences of Vectors and Matrices . . . . . . . . . . . . . . 351
10.2 Convergence of Iterative Methods . . . . . . . . . . . . . . . . . . . . . . . . 354
10.3 Methods of Jacobi, Gauss–Seidel, and Relaxation . . . . . . . . . . . . . . . 356
10.4 Convergence of the Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . 364
10.5 Convergence Methods for Tridiagonal Matrices . . . . . . . . . . . . . . . . 367
10.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372
10.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373
11 The Dual Space and Duality 375
11.1 The Dual Space E
∗ and Linear Forms . . . . . . . . . . . . . . . . . . . . . 375
11.2 Pairing and Duality Between E and E
∗
. . . . . . . . . . . . . . . . . . . . 382
11.3 The Duality Theorem and Some Consequences . . . . . . . . . . . . . . . . 387
11.4 The Bidual and Canonical Pairings . . . . . . . . . . . . . . . . . . . . . . . 393
11.5 Hyperplanes and Linear Forms . . . . . . . . . . . . . . . . . . . . . . . . . 395
11.6 Transpose of a Linear Map and of a Matrix . . . . . . . . . . . . . . . . . . 396
11.7 Properties of the Double Transpose . . . . . . . . . . . . . . . . . . . . . . . 403
11.8 The Four Fundamental Subspaces . . . . . . . . . . . . . . . . . . . . . . . 405
11.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408
11.10 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409
12 Euclidean Spaces 413
12.1 Inner Products, Euclidean Spaces . . . . . . . . . . . . . . . . . . . . . . . . 413
12.2 Orthogonality and Duality in Euclidean Spaces . . . . . . . . . . . . . . . . 422
12.3 Adjoint of a Linear Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 429
12.4 Existence and Construction of Orthonormal Bases . . . . . . . . . . . . . . 432
12.5 Linear Isometries (Orthogonal Transformations) . . . . . . . . . . . . . . . . 439
6 CONTENTS
12.6 The Orthogonal Group, Orthogonal Matrices . . . . . . . . . . . . . . . . . 442
12.7 The Rodrigues Formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444
12.8 QR-Decomposition for Invertible Matrices . . . . . . . . . . . . . . . . . . . 447
12.9 Some Applications of Euclidean Geometry . . . . . . . . . . . . . . . . . . . 452
12.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453
12.11 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455
13 QR-Decomposition for Arbitrary Matrices 467
13.1 Orthogonal Reflections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 467
13.2 QR-Decomposition Using Householder Matrices . . . . . . . . . . . . . . . . 472
13.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 482
13.4 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 482
14 Hermitian Spaces 489
14.1 Hermitian Spaces, Pre-Hilbert Spaces . . . . . . . . . . . . . . . . . . . . . 489
14.2 Orthogonality, Duality, Adjoint of a Linear Map . . . . . . . . . . . . . . . 498
14.3 Linear Isometries (Also Called Unitary Transformations) . . . . . . . . . . . 503
14.4 The Unitary Group, Unitary Matrices . . . . . . . . . . . . . . . . . . . . . 505
14.5 Hermitian Reflections and QR-Decomposition . . . . . . . . . . . . . . . . . 508
14.6 Orthogonal Projections and Involutions . . . . . . . . . . . . . . . . . . . . 513
14.7 Dual Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 516
14.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 523
14.9 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 524
15 Eigenvectors and Eigenvalues 529
15.1 Eigenvectors and Eigenvalues of a Linear Map . . . . . . . . . . . . . . . . . 529
15.2 Reduction to Upper Triangular Form . . . . . . . . . . . . . . . . . . . . . . 537
15.3 Location of Eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 541
15.4 Conditioning of Eigenvalue Problems . . . . . . . . . . . . . . . . . . . . . . 544
15.5 Eigenvalues of the Matrix Exponential . . . . . . . . . . . . . . . . . . . . . 547
15.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 549
15.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 550
16 Unit Quaternions and Rotations in SO(3) 561
16.1 The Group SU(2) and the Skew Field H of Quaternions . . . . . . . . . . . 561
16.2 Representation of Rotation in SO(3) By Quaternions in SU(2) . . . . . . . 563
16.3 Matrix Representation of the Rotation rq . . . . . . . . . . . . . . . . . . . 568
16.4 An Algorithm to Find a Quaternion Representing a Rotation . . . . . . . . 570
16.5 The Exponential Map exp: su(2) → SU(2) . . . . . . . . . . . . . . . . . . 573
16.6 Quaternion Interpolation ~ . . . . . . . . . . . . . . . . . . . . . . . . . . . 575
16.7 Nonexistence of a “Nice” Section from SO(3) to SU(2) . . . . . . . . . . . . 577
16.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 579
16.9 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 580
CONTENTS 7
17 Spectral Theorems 583
17.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583
17.2 Normal Linear Maps: Eigenvalues and Eigenvectors . . . . . . . . . . . . . . 583
17.3 Spectral Theorem for Normal Linear Maps . . . . . . . . . . . . . . . . . . . 589
17.4 Self-Adjoint and Other Special Linear Maps . . . . . . . . . . . . . . . . . . 594
17.5 Normal and Other Special Matrices . . . . . . . . . . . . . . . . . . . . . . . 600
17.6 Rayleigh–Ritz Theorems and Eigenvalue Interlacing . . . . . . . . . . . . . 603
17.7 The Courant–Fischer Theorem; Perturbation Results . . . . . . . . . . . . . 608
17.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 611
17.9 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 612
18 Computing Eigenvalues and Eigenvectors 619
18.1 The Basic QR Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 621
18.2 Hessenberg Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 627
18.3 Making the QR Method More Efficient Using Shifts . . . . . . . . . . . . . 633
18.4 Krylov Subspaces; Arnoldi Iteration . . . . . . . . . . . . . . . . . . . . . . 638
18.5 GMRES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 642
18.6 The Hermitian Case; Lanczos Iteration . . . . . . . . . . . . . . . . . . . . . 643
18.7 Power Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 644
18.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 646
18.9 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 647
19 Introduction to The Finite Elements Method 649
19.1 A One-Dimensional Problem: Bending of a Beam . . . . . . . . . . . . . . . 649
19.2 A Two-Dimensional Problem: An Elastic Membrane . . . . . . . . . . . . . 660
19.3 Time-Dependent Boundary Problems . . . . . . . . . . . . . . . . . . . . . . 663
20 Graphs and Graph Laplacians; Basic Facts 671
20.1 Directed Graphs, Undirected Graphs, Weighted Graphs . . . . . . . . . . . 674
20.2 Laplacian Matrices of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 681
20.3 Normalized Laplacian Matrices of Graphs . . . . . . . . . . . . . . . . . . . 685
20.4 Graph Clustering Using Normalized Cuts . . . . . . . . . . . . . . . . . . . 689
20.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 691
20.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 692
21 Spectral Graph Drawing 695
21.1 Graph Drawing and Energy Minimization . . . . . . . . . . . . . . . . . . . 695
21.2 Examples of Graph Drawings . . . . . . . . . . . . . . . . . . . . . . . . . . 698
21.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 702
22 Singular Value Decomposition and Polar Form 705
22.1 Properties of f
∗ ◦ f . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 705
22.2 Singular Value Decomposition for Square Matrices . . . . . . . . . . . . . . 709
8 CONTENTS
22.3 Polar Form for Square Matrices . . . . . . . . . . . . . . . . . . . . . . . . . 712
22.4 Singular Value Decomposition for Rectangular Matrices . . . . . . . . . . . 715
22.5 Ky Fan Norms and Schatten Norms . . . . . . . . . . . . . . . . . . . . . . 718
22.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 719
22.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 719
23 Applications of SVD and Pseudo-Inverses 723
23.1 Least Squares Problems and the Pseudo-Inverse . . . . . . . . . . . . . . . . 723
23.2 Properties of the Pseudo-Inverse . . . . . . . . . . . . . . . . . . . . . . . . 730
23.3 Data Compression and SVD . . . . . . . . . . . . . . . . . . . . . . . . . . . 735
23.4 Principal Components Analysis (PCA) . . . . . . . . . . . . . . . . . . . . . 737
23.5 Best Affine Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . 748
23.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 752
23.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 753
II Affine and Projective Geometry 757
24 Basics of Affine Geometry 759
24.1 Affine Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 759
24.2 Examples of Affine Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . 768
24.3 Chasles’s Identity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 769
24.4 Affine Combinations, Barycenters . . . . . . . . . . . . . . . . . . . . . . . . 770
24.5 Affine Subspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 775
24.6 Affine Independence and Affine Frames . . . . . . . . . . . . . . . . . . . . . 781
24.7 Affine Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 787
24.8 Affine Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 794
24.9 Affine Geometry: A Glimpse . . . . . . . . . . . . . . . . . . . . . . . . . . 796
24.10 Affine Hyperplanes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 800
24.11 Intersection of Affine Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . 802
25 Embedding an Affine Space in a Vector Space 805
25.1 The “Hat Construction,” or Homogenizing . . . . . . . . . . . . . . . . . . . 805
25.2 Affine Frames of E and Bases of Eˆ . . . . . . . . . . . . . . . . . . . . . . . 812
25.3 Another Construction of Eˆ . . . . . . . . . . . . . . . . . . . . . . . . . . . 815
25.4 Extending Affine Maps to Linear Maps . . . . . . . . . . . . . . . . . . . . . 818
26 Basics of Projective Geometry 823
26.1 Why Projective Spaces? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 823
26.2 Projective Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 828
26.3 Projective Subspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 833
26.4 Projective Frames . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 836
26.5 Projective Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 850
CONTENTS 9
26.6 Finding a Homography Between Two Projective Frames . . . . . . . . . . . 856
26.7 Affine Patches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 869
26.8 Projective Completion of an Affine Space . . . . . . . . . . . . . . . . . . . 872
26.9 Making Good Use of Hyperplanes at Infinity . . . . . . . . . . . . . . . . . 877
26.10 The Cross-Ratio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 880
26.11 Fixed Points of Homographies and Homologies . . . . . . . . . . . . . . . . 884
26.12 Duality in Projective Geometry . . . . . . . . . . . . . . . . . . . . . . . . . 898
26.13 Cross-Ratios of Hyperplanes . . . . . . . . . . . . . . . . . . . . . . . . . . . 902
26.14 Complexification of a Real Projective Space . . . . . . . . . . . . . . . . . . 904
26.15 Similarity Structures on a Projective Space . . . . . . . . . . . . . . . . . . 906
26.16 Some Applications of Projective Geometry . . . . . . . . . . . . . . . . . . . 915
III The Geometry of Bilinear Forms 921
27 The Cartan–Dieudonn´e Theorem 923
27.1 The Cartan–Dieudonn´e Theorem for Linear Isometries . . . . . . . . . . . . 923
27.2 Affine Isometries (Rigid Motions) . . . . . . . . . . . . . . . . . . . . . . . . 935
27.3 Fixed Points of Affine Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . 937
27.4 Affine Isometries and Fixed Points . . . . . . . . . . . . . . . . . . . . . . . 939
27.5 The Cartan–Dieudonn´e Theorem for Affine Isometries . . . . . . . . . . . . 945
28 Isometries of Hermitian Spaces 949
28.1 The Cartan–Dieudonn´e Theorem, Hermitian Case . . . . . . . . . . . . . . . 949
28.2 Affine Isometries (Rigid Motions) . . . . . . . . . . . . . . . . . . . . . . . . 958
29 The Geometry of Bilinear Forms; Witt’s Theorem 963
29.1 Bilinear Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 963
29.2 Sesquilinear Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 971
29.3 Orthogonality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 975
29.4 Adjoint of a Linear Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 980
29.5 Isometries Associated with Sesquilinear Forms . . . . . . . . . . . . . . . . . 982
29.6 Totally Isotropic Subspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . 986
29.7 Witt Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 992
29.8 Symplectic Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1000
29.9 Orthogonal Groups and the Cartan–Dieudonn´e Theorem . . . . . . . . . . . 1004
29.10 Witt’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1011
IV Algebra: PID’s, UFD’s, Noetherian Rings, Tensors,
Modules over a PID, Normal Forms 1017
30 Polynomials, Ideals and PID’s 1019
10 CONTENTS
30.1 Multisets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1019
30.2 Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1020
30.3 Euclidean Division of Polynomials . . . . . . . . . . . . . . . . . . . . . . . 1026
30.4 Ideals, PID’s, and Greatest Common Divisors . . . . . . . . . . . . . . . . . 1028
30.5 Factorization and Irreducible Factors in K[X] . . . . . . . . . . . . . . . . . 1036
30.6 Roots of Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1040
30.7 Polynomial Interpolation (Lagrange, Newton, Hermite) . . . . . . . . . . . . 1047
31 Annihilating Polynomials; Primary Decomposition 1055
31.1 Annihilating Polynomials and the Minimal Polynomial . . . . . . . . . . . . 1057
31.2 Minimal Polynomials of Diagonalizable Linear Maps . . . . . . . . . . . . . 1059
31.3 Commuting Families of Linear Maps . . . . . . . . . . . . . . . . . . . . . . 1062
31.4 The Primary Decomposition Theorem . . . . . . . . . . . . . . . . . . . . . 1065
31.5 Jordan Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1071
31.6 Nilpotent Linear Maps and Jordan Form . . . . . . . . . . . . . . . . . . . . 1074
31.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1080
31.8 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1081
32 UFD’s, Noetherian Rings, Hilbert’s Basis Theorem 1085
32.1 Unique Factorization Domains (Factorial Rings) . . . . . . . . . . . . . . . . 1085
32.2 The Chinese Remainder Theorem . . . . . . . . . . . . . . . . . . . . . . . . 1099
32.3 Noetherian Rings and Hilbert’s Basis Theorem . . . . . . . . . . . . . . . . 1105
32.4 Futher Readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1109
33 Tensor Algebras 1111
33.1 Linear Algebra Preliminaries: Dual Spaces and Pairings . . . . . . . . . . . 1113
33.2 Tensors Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1118
33.3 Bases of Tensor Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1130
33.4 Some Useful Isomorphisms for Tensor Products . . . . . . . . . . . . . . . . 1131
33.5 Duality for Tensor Products . . . . . . . . . . . . . . . . . . . . . . . . . . . 1135
33.6 Tensor Algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1141
33.7 Symmetric Tensor Powers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1148
33.8 Bases of Symmetric Powers . . . . . . . . . . . . . . . . . . . . . . . . . . . 1152
33.9 Some Useful Isomorphisms for Symmetric Powers . . . . . . . . . . . . . . . 1155
33.10 Duality for Symmetric Powers . . . . . . . . . . . . . . . . . . . . . . . . . . 1155
33.11 Symmetric Algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1159
33.12 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1162
34 Exterior Tensor Powers and Exterior Algebras 1165
34.1 Exterior Tensor Powers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1165
34.2 Bases of Exterior Powers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1170
34.3 Some Useful Isomorphisms for Exterior Powers . . . . . . . . . . . . . . . . 1173
34.4 Duality for Exterior Powers . . . . . . . . . . . . . . . . . . . . . . . . . . . 1173
CONTENTS 11
34.5 Exterior Algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1177
34.6 The Hodge ∗-Operator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1181
34.7 Left and Right Hooks ~ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1185
34.8 Testing Decomposability ~ . . . . . . . . . . . . . . . . . . . . . . . . . . . 1195
34.9 The Grassmann-Pl¨ucker’s Equations and Grassmannians ~ . . . . . . . . . 1198
34.10 Vector-Valued Alternating Forms . . . . . . . . . . . . . . . . . . . . . . . . 1201
34.11 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1205
35 Introduction to Modules; Modules over a PID 1207
35.1 Modules over a Commutative Ring . . . . . . . . . . . . . . . . . . . . . . . 1207
35.2 Finite Presentations of Modules . . . . . . . . . . . . . . . . . . . . . . . . . 1216
35.3 Tensor Products of Modules over a Commutative Ring . . . . . . . . . . . . 1222
35.4 Torsion Modules over a PID; Primary Decomposition . . . . . . . . . . . . . 1225
35.5 Finitely Generated Modules over a PID . . . . . . . . . . . . . . . . . . . . 1231
35.6 Extension of the Ring of Scalars . . . . . . . . . . . . . . . . . . . . . . . . 1247
36 Normal Forms; The Rational Canonical Form 1253
36.1 The Torsion Module Associated With An Endomorphism . . . . . . . . . . 1253
36.2 The Rational Canonical Form . . . . . . . . . . . . . . . . . . . . . . . . . . 1261
36.3 The Rational Canonical Form, Second Version . . . . . . . . . . . . . . . . . 1268
36.4 The Jordan Form Revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . 1269
36.5 The Smith Normal Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1272
V Topology, Differential Calculus 1285
37 Topology 1287
37.1 Metric Spaces and Normed Vector Spaces . . . . . . . . . . . . . . . . . . . 1287
37.2 Topological Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1294
37.3 Continuous Functions, Limits . . . . . . . . . . . . . . . . . . . . . . . . . . 1303
37.4 Connected Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1311
37.5 Compact Sets and Locally Compact Spaces . . . . . . . . . . . . . . . . . . 1320
37.6 Second-Countable and Separable Spaces . . . . . . . . . . . . . . . . . . . . 1331
37.7 Sequential Compactness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1335
37.8 Complete Metric Spaces and Compactness . . . . . . . . . . . . . . . . . . . 1341
37.9 Completion of a Metric Space . . . . . . . . . . . . . . . . . . . . . . . . . . 1344
37.10 The Contraction Mapping Theorem . . . . . . . . . . . . . . . . . . . . . . 1351
37.11 Continuous Linear and Multilinear Maps . . . . . . . . . . . . . . . . . . . . 1355
37.12 Completion of a Normed Vector Space . . . . . . . . . . . . . . . . . . . . . 1362
37.13 Normed Affine Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1365
37.14 Futher Readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1365
38 A Detour On Fractals 1367
12 CONTENTS
38.1 Iterated Function Systems and Fractals . . . . . . . . . . . . . . . . . . . . 1367
39 Differential Calculus 1375
39.1 Directional Derivatives, Total Derivatives . . . . . . . . . . . . . . . . . . . 1375
39.2 Jacobian Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1389
39.3 The Implicit and The Inverse Function Theorems . . . . . . . . . . . . . . . 1397
39.4 Tangent Spaces and Differentials . . . . . . . . . . . . . . . . . . . . . . . . 1401
39.5 Second-Order and Higher-Order Derivatives . . . . . . . . . . . . . . . . . . 1402
39.6 Taylor’s formula, Fa`a di Bruno’s formula . . . . . . . . . . . . . . . . . . . . 1407
39.7 Vector Fields, Covariant Derivatives, Lie Brackets . . . . . . . . . . . . . . . 1411
39.8 Futher Readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1413
VI Preliminaries for Optimization Theory 1415
40 Extrema of Real-Valued Functions 1417
40.1 Local Extrema and Lagrange Multipliers . . . . . . . . . . . . . . . . . . . . 1417
40.2 Using Second Derivatives to Find Extrema . . . . . . . . . . . . . . . . . . . 1427
40.3 Using Convexity to Find Extrema . . . . . . . . . . . . . . . . . . . . . . . 1430
40.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1440
41 Newton’s Method and Its Generalizations 1441
41.1 Newton’s Method for Real Functions of a Real Argument . . . . . . . . . . 1441
41.2 Generalizations of Newton’s Method . . . . . . . . . . . . . . . . . . . . . . 1442
41.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1448
42 Quadratic Optimization Problems 1449
42.1 Quadratic Optimization: The Positive Definite Case . . . . . . . . . . . . . 1449
42.2 Quadratic Optimization: The General Case . . . . . . . . . . . . . . . . . . 1458
42.3 Maximizing a Quadratic Function on the Unit Sphere . . . . . . . . . . . . 1463
42.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1468
43 Schur Complements and Applications 1469
43.1 Schur Complements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1469
43.2 SPD Matrices and Schur Complements . . . . . . . . . . . . . . . . . . . . . 1472
43.3 SP Semidefinite Matrices and Schur Complements . . . . . . . . . . . . . . 1473
VII Linear Optimization 1475
44 Convex Sets, Cones, H-Polyhedra 1477
44.1 What is Linear Programming? . . . . . . . . . . . . . . . . . . . . . . . . . 1477
44.2 Affine Subsets, Convex Sets, Hyperplanes, Half-Spaces . . . . . . . . . . . . 1479
44.3 Cones, Polyhedral Cones, and H-Polyhedra . . . . . . . . . . . . . . . . . . 1482
CONTENTS 13
45 Linear Programs 1489
45.1 Linear Programs, Feasible Solutions, Optimal Solutions . . . . . . . . . . . 1489
45.2 Basic Feasible Solutions and Vertices . . . . . . . . . . . . . . . . . . . . . . 1495
46 The Simplex Algorithm 1503
46.1 The Idea Behind the Simplex Algorithm . . . . . . . . . . . . . . . . . . . . 1503
46.2 The Simplex Algorithm in General . . . . . . . . . . . . . . . . . . . . . . . 1512
46.3 How to Perform a Pivoting Step Efficiently . . . . . . . . . . . . . . . . . . 1519
46.4 The Simplex Algorithm Using Tableaux . . . . . . . . . . . . . . . . . . . . 1523
46.5 Computational Efficiency of the Simplex Method . . . . . . . . . . . . . . . 1532
47 Linear Programming and Duality 1535
47.1 Variants of the Farkas Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . 1535
47.2 The Duality Theorem in Linear Programming . . . . . . . . . . . . . . . . . 1540
47.3 Complementary Slackness Conditions . . . . . . . . . . . . . . . . . . . . . 1548
47.4 Duality for Linear Programs in Standard Form . . . . . . . . . . . . . . . . 1550
47.5 The Dual Simplex Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 1553
47.6 The Primal-Dual Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 1558
VIII NonLinear Optimization 1569
48 Basics of Hilbert Spaces 1571
48.1 The Projection Lemma, Duality . . . . . . . . . . . . . . . . . . . . . . . . 1571
48.2 Farkas–Minkowski Lemma in Hilbert Spaces . . . . . . . . . . . . . . . . . . 1588
49 General Results of Optimization Theory 1591
49.1 Optimization Problems; Basic Terminology . . . . . . . . . . . . . . . . . . 1591
49.2 Existence of Solutions of an Optimization Problem . . . . . . . . . . . . . . 1594
49.3 Minima of Quadratic Functionals . . . . . . . . . . . . . . . . . . . . . . . . 1599
49.4 Elliptic Functionals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1605
49.5 Iterative Methods for Unconstrained Problems . . . . . . . . . . . . . . . . 1608
49.6 Gradient Descent Methods for Unconstrained Problems . . . . . . . . . . . 1612
49.7 Convergence of Gradient Descent with Variable Stepsize . . . . . . . . . . . 1617
49.8 Steepest Descent for an Arbitrary Norm . . . . . . . . . . . . . . . . . . . . 1622
49.9 Newton’s Method For Finding a Minimum . . . . . . . . . . . . . . . . . . . 1624
49.10 Conjugate Gradient Methods; Unconstrained Problems . . . . . . . . . . . . 1628
49.11 Gradient Projection for Constrained Optimization . . . . . . . . . . . . . . 1640
49.12 Penalty Methods for Constrained Optimization . . . . . . . . . . . . . . . . 1642
49.13 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1644
50 Introduction to Nonlinear Optimization 1647
50.1 The Cone of Feasible Directions . . . . . . . . . . . . . . . . . . . . . . . . . 1647
14 CONTENTS
50.2 Active Constraints and Qualified Constraints . . . . . . . . . . . . . . . . . 1654
50.3 The Karush–Kuhn–Tucker Conditions . . . . . . . . . . . . . . . . . . . . . 1660
50.4 Equality Constrained Minimization . . . . . . . . . . . . . . . . . . . . . . . 1672
50.5 Hard Margin Support Vector Machine; Version I . . . . . . . . . . . . . . . 1677
50.6 Hard Margin Support Vector Machine; Version II . . . . . . . . . . . . . . . 1681
50.7 Lagrangian Duality and Saddle Points . . . . . . . . . . . . . . . . . . . . . 1690
50.8 Weak and Strong Duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1699
50.9 Handling Equality Constraints Explicitly . . . . . . . . . . . . . . . . . . . . 1707
50.10 Dual of the Hard Margin Support Vector Machine . . . . . . . . . . . . . . 1710
50.11 Conjugate Function and Legendre Dual Function . . . . . . . . . . . . . . . 1715
50.12 Some Techniques to Obtain a More Useful Dual Program . . . . . . . . . . 1725
50.13 Uzawa’s Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1729
50.14 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1735
51 Subgradients and Subdifferentials 1737
51.1 Extended Real-Valued Convex Functions . . . . . . . . . . . . . . . . . . . . 1739
51.2 Subgradients and Subdifferentials . . . . . . . . . . . . . . . . . . . . . . . . 1748
51.3 Basic Properties of Subgradients and Subdifferentials . . . . . . . . . . . . . 1760
51.4 Additional Properties of Subdifferentials . . . . . . . . . . . . . . . . . . . . 1766
51.5 The Minimum of a Proper Convex Function . . . . . . . . . . . . . . . . . . 1770
51.6 Generalization of the Lagrangian Framework . . . . . . . . . . . . . . . . . 1776
51.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1780
52 Dual Ascent Methods; ADMM 1783
52.1 Dual Ascent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1785
52.2 Augmented Lagrangians and the Method of Multipliers . . . . . . . . . . . . 1789
52.3 ADMM: Alternating Direction Method of Multipliers . . . . . . . . . . . . . 1794
52.4 Convergence of ADMM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1797
52.5 Stopping Criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1806
52.6 Some Applications of ADMM . . . . . . . . . . . . . . . . . . . . . . . . . . 1807
52.7 Applications of ADMM to `
1
-Norm Problems . . . . . . . . . . . . . . . . . 1810
52.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1815
IX Applications to Machine Learning 1817
53 Ridge Regression and Lasso Regression 1819
53.1 Ridge Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1819
53.2 Lasso Regression (`
1
-Regularized Regression) . . . . . . . . . . . . . . . . . 1829
53.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1835
54 Positive Definite Kernels 1837
54.1 Basic Properties of Positive Definite Kernels . . . . . . . . . . . . . . . . . . 1837
CONTENTS 15
54.2 Hilbert Space Representation of a Positive Kernel . . . . . . . . . . . . . . . 1848
54.3 Kernel PCA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1852
54.4 ν-SV Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1855
55 Soft Margin Support Vector Machines 1865
55.1 Soft Margin Support Vector Machines; (SVMs1) . . . . . . . . . . . . . . . . 1868
55.2 Soft Margin Support Vector Machines; (SVMs2) . . . . . . . . . . . . . . . . 1878
55.3 Soft Margin Support Vector Machines; (SVMs2
0) . . . . . . . . . . . . . . . 1885
55.4 Soft Margin SVM; (SVMs3) . . . . . . . . . . . . . . . . . . . . . . . . . . . 1900
55.5 Soft Margin Support Vector Machines; (SVMs4) . . . . . . . . . . . . . . . . 1903
55.6 Soft Margin SVM; (SVMs5) . . . . . . . . . . . . . . . . . . . . . . . . . . . 1911
55.7 Summary and Comparison of the SVM Methods . . . . . . . . . . . . . . . 1914
X Appendices 1927
A Total Orthogonal Families in Hilbert Spaces 1929
A.1 Total Orthogonal Families, Fourier Coefficients . . . . . . . . . . . . . . . . 1929
A.2 The Hilbert Space `
2
(K) and the Riesz-Fischer Theorem . . . . . . . . . . . 1937
B Zorn’s Lemma; Some Applications 1947
B.1 Statement of Zorn’s Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . 1947
B.2 Proof of the Existence of a Basis in a Vector Space . . . . . . . . . . . . . . 1948
B.3 Existence of Maximal Proper Ideals . . . . . . . . . . . . . . . . . . . . . . 1949
Bibliography 1951