Algebra, Topology, Differential Calculus, and

Optimization Theory
For Computer Science and Machine Learning

Jean Gallier and Jocelyn Quaintance

Department of Computer and Information Science
University of Pennsylvania
Philadelphia, PA 19104, USA
e-mail: jean@seas.upenn.edu

© Jean Gallier

February 9, 2024
2
Contents

Contents 3

1 Introduction 19

2 Groups, Rings, and Fields 21

2.1 Groups, Subgroups, Cosets . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2 Cyclic Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.3 Rings and Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

I Linear Algebra 47
3 Vector Spaces, Bases, Linear Maps 49
3.1 Motivations: Linear Combinations, Linear Independence, Rank . . . . . . . 49
3.2 Vector Spaces . . . . . . . . . . . . .P . . . . . . . . . . . . . . . . . . . . . . 61
3.3 Indexed Families; the Sum Notation i∈I ai . . . . . . . . . . . . . . . . . . 64
3.4 Linear Independence, Subspaces . . . . . . . . . . . . . . . . . . . . . . . . 70
3.5 Bases of a Vector Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
3.6 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
3.7 Linear Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
3.8 Quotient Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
3.9 Linear Forms and the Dual Space . . . . . . . . . . . . . . . . . . . . . . . . 100
3.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
3.11 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

4 Matrices and Linear Maps 113

4.1 Representation of Linear Maps by Matrices . . . . . . . . . . . . . . . . . . 113
4.2 Composition of Linear Maps and Matrix Multiplication . . . . . . . . . . . 118
4.3 Change of Basis Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
4.4 The Effect of a Change of Bases on Matrices . . . . . . . . . . . . . . . . . 129
4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
4.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134

5 Haar Bases, Haar Wavelets, Hadamard Matrices 141

3
4 CONTENTS

5.1 Introduction to Signal Compression Using Haar Wavelets . . . . . . . . . . 141

5.2 Haar Matrices, Scaling Properties of Haar Wavelets . . . . . . . . . . . . . . 143
5.3 Kronecker Product Construction of Haar Matrices . . . . . . . . . . . . . . 148
5.4 Multiresolution Signal Analysis with Haar Bases . . . . . . . . . . . . . . . 150
5.5 Haar Transform for Digital Images . . . . . . . . . . . . . . . . . . . . . . . 153
5.6 Hadamard Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
5.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
5.8 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162

6 Direct Sums 167

6.1 Sums, Direct Sums, Direct Products . . . . . . . . . . . . . . . . . . . . . . 167
6.2 Matrices of Linear Maps and Multiplication by Blocks . . . . . . . . . . . . 177
6.3 The Rank-Nullity Theorem; Grassmann’s Relation . . . . . . . . . . . . . . 190
6.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
6.5 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197

7 Determinants 205
7.1 Permutations, Signature of a Permutation . . . . . . . . . . . . . . . . . . . 205
7.2 Alternating Multilinear Maps . . . . . . . . . . . . . . . . . . . . . . . . . . 209
7.3 Definition of a Determinant . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
7.4 Inverse Matrices and Determinants . . . . . . . . . . . . . . . . . . . . . . . 222
7.5 Systems of Linear Equations and Determinants . . . . . . . . . . . . . . . . 225
7.6 Determinant of a Linear Map . . . . . . . . . . . . . . . . . . . . . . . . . . 227
7.7 The Cayley–Hamilton Theorem . . . . . . . . . . . . . . . . . . . . . . . . . 228
7.8 Permanents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
7.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
7.10 Further Readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
7.11 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237

8 Gaussian Elimination, LU, Cholesky, Echelon Form 243

8.1 Motivating Example: Curve Interpolation . . . . . . . . . . . . . . . . . . . 243
8.2 Gaussian Elimination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
8.3 Elementary Matrices and Row Operations . . . . . . . . . . . . . . . . . . . 252
8.4 LU -Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255
8.5 P A = LU Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261
8.6 Proof of Theorem 8.5 ~ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
8.7 Dealing with Roundoff Errors; Pivoting Strategies . . . . . . . . . . . . . . . 274
8.8 Gaussian Elimination of Tridiagonal Matrices . . . . . . . . . . . . . . . . . 276
8.9 SPD Matrices and the Cholesky Decomposition . . . . . . . . . . . . . . . . 278
8.10 Reduced Row Echelon Form . . . . . . . . . . . . . . . . . . . . . . . . . . . 287
8.11 RREF, Free Variables, Homogeneous Systems . . . . . . . . . . . . . . . . . 293
8.12 Uniqueness of RREF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296
8.13 Solving Linear Systems Using RREF . . . . . . . . . . . . . . . . . . . . . . 298
CONTENTS 5

8.14 Elementary Matrices and Columns Operations . . . . . . . . . . . . . . . . 304

8.15 Transvections and Dilatations ~ . . . . . . . . . . . . . . . . . . . . . . . . 305
8.16 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311
8.17 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312

9 Vector Norms and Matrix Norms 323

9.1 Normed Vector Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323
9.2 Matrix Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
9.3 Subordinate Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340
9.4 Inequalities Involving Subordinate Norms . . . . . . . . . . . . . . . . . . . 347
9.5 Condition Numbers of Matrices . . . . . . . . . . . . . . . . . . . . . . . . . 349
9.6 An Application of Norms: Inconsistent Linear Systems . . . . . . . . . . . . 358
9.7 Limits of Sequences and Series . . . . . . . . . . . . . . . . . . . . . . . . . 359
9.8 The Matrix Exponential . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362
9.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365
9.10 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367

10 Iterative Methods for Solving Linear Systems 373

10.1 Convergence of Sequences of Vectors and Matrices . . . . . . . . . . . . . . 373
10.2 Convergence of Iterative Methods . . . . . . . . . . . . . . . . . . . . . . . . 376
10.3 Methods of Jacobi, Gauss–Seidel, and Relaxation . . . . . . . . . . . . . . . 378
10.4 Convergence of the Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . 386
10.5 Convergence Methods for Tridiagonal Matrices . . . . . . . . . . . . . . . . 389
10.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394
10.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395

11 The Dual Space and Duality 399

11.1 The Dual Space E ∗ and Linear Forms . . . . . . . . . . . . . . . . . . . . . 399
11.2 Pairing and Duality Between E and E ∗ . . . . . . . . . . . . . . . . . . . . 406
11.3 The Duality Theorem and Some Consequences . . . . . . . . . . . . . . . . 411
11.4 The Bidual and Canonical Pairings . . . . . . . . . . . . . . . . . . . . . . . 417
11.5 Hyperplanes and Linear Forms . . . . . . . . . . . . . . . . . . . . . . . . . 419
11.6 Transpose of a Linear Map and of a Matrix . . . . . . . . . . . . . . . . . . 420
11.7 Properties of the Double Transpose . . . . . . . . . . . . . . . . . . . . . . . 427
11.8 The Four Fundamental Subspaces . . . . . . . . . . . . . . . . . . . . . . . 429
11.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 432
11.10 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433

12 Euclidean Spaces 437

12.1 Inner Products, Euclidean Spaces . . . . . . . . . . . . . . . . . . . . . . . . 437
12.2 Orthogonality and Duality in Euclidean Spaces . . . . . . . . . . . . . . . . 446
12.3 Adjoint of a Linear Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453
12.4 Existence and Construction of Orthonormal Bases . . . . . . . . . . . . . . 456
6 CONTENTS

12.5 Linear Isometries (Orthogonal Transformations) . . . . . . . . . . . . . . . . 463

12.6 The Orthogonal Group, Orthogonal Matrices . . . . . . . . . . . . . . . . . 466
12.7 The Rodrigues Formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 468
12.8 QR-Decomposition for Invertible Matrices . . . . . . . . . . . . . . . . . . . 471
12.9 Some Applications of Euclidean Geometry . . . . . . . . . . . . . . . . . . . 476
12.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477
12.11 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479

13 QR-Decomposition for Arbitrary Matrices 491

13.1 Orthogonal Reflections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 491
13.2 QR-Decomposition Using Householder Matrices . . . . . . . . . . . . . . . . 496
13.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 506
13.4 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 506

14 Hermitian Spaces 513

14.1 Hermitian Spaces, Pre-Hilbert Spaces . . . . . . . . . . . . . . . . . . . . . 513
14.2 Orthogonality, Duality, Adjoint of a Linear Map . . . . . . . . . . . . . . . 522
14.3 Linear Isometries (Also Called Unitary Transformations) . . . . . . . . . . . 527
14.4 The Unitary Group, Unitary Matrices . . . . . . . . . . . . . . . . . . . . . 529
14.5 Hermitian Reflections and QR-Decomposition . . . . . . . . . . . . . . . . . 532
14.6 Orthogonal Projections and Involutions . . . . . . . . . . . . . . . . . . . . 537
14.7 Dual Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 540
14.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 547
14.9 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 548

15 Eigenvectors and Eigenvalues 553

15.1 Eigenvectors and Eigenvalues of a Linear Map . . . . . . . . . . . . . . . . . 553
15.2 Reduction to Upper Triangular Form . . . . . . . . . . . . . . . . . . . . . . 561
15.3 Location of Eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565
15.4 Conditioning of Eigenvalue Problems . . . . . . . . . . . . . . . . . . . . . . 569
15.5 Eigenvalues of the Matrix Exponential . . . . . . . . . . . . . . . . . . . . . 571
15.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 573
15.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 574

16 Unit Quaternions and Rotations in SO(3) 585

16.1 The Group SU(2) and the Skew Field H of Quaternions . . . . . . . . . . . 585
16.2 Representation of Rotation in SO(3) By Quaternions in SU(2) . . . . . . . 587
16.3 Matrix Representation of the Rotation rq . . . . . . . . . . . . . . . . . . . 592
16.4 An Algorithm to Find a Quaternion Representing a Rotation . . . . . . . . 594
16.5 The Exponential Map exp : su(2) → SU(2) . . . . . . . . . . . . . . . . . . 597
16.6 Quaternion Interpolation ~ . . . . . . . . . . . . . . . . . . . . . . . . . . . 600
16.7 Nonexistence of a “Nice” Section from SO(3) to SU(2) . . . . . . . . . . . . 602
16.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604
CONTENTS 7

16.9 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 605

17 Spectral Theorems 609

17.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 609
17.2 Normal Linear Maps: Eigenvalues and Eigenvectors . . . . . . . . . . . . . . 609
17.3 Spectral Theorem for Normal Linear Maps . . . . . . . . . . . . . . . . . . . 615
17.4 Self-Adjoint and Other Special Linear Maps . . . . . . . . . . . . . . . . . . 620
17.5 Normal and Other Special Matrices . . . . . . . . . . . . . . . . . . . . . . . 626
17.6 Rayleigh–Ritz Theorems and Eigenvalue Interlacing . . . . . . . . . . . . . 629
17.7 The Courant–Fischer Theorem; Perturbation Results . . . . . . . . . . . . . 634
17.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 637
17.9 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 638

18 Computing Eigenvalues and Eigenvectors 645

18.1 The Basic QR Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 647
18.2 Hessenberg Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 653
18.3 Making the QR Method More Efficient Using Shifts . . . . . . . . . . . . . 659
18.4 Krylov Subspaces; Arnoldi Iteration . . . . . . . . . . . . . . . . . . . . . . 664
18.5 GMRES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 668
18.6 The Hermitian Case; Lanczos Iteration . . . . . . . . . . . . . . . . . . . . . 669
18.7 Power Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 670
18.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 672
18.9 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 673

19 Introduction to The Finite Elements Method 675

19.1 A One-Dimensional Problem: Bending of a Beam . . . . . . . . . . . . . . . 675
19.2 A Two-Dimensional Problem: An Elastic Membrane . . . . . . . . . . . . . 686
19.3 Time-Dependent Boundary Problems . . . . . . . . . . . . . . . . . . . . . . 689

20 Graphs and Graph Laplacians; Basic Facts 697

20.1 Directed Graphs, Undirected Graphs, Weighted Graphs . . . . . . . . . . . 700
20.2 Laplacian Matrices of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 707
20.3 Normalized Laplacian Matrices of Graphs . . . . . . . . . . . . . . . . . . . 711
20.4 Graph Clustering Using Normalized Cuts . . . . . . . . . . . . . . . . . . . 715
20.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 717
20.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 718

21 Spectral Graph Drawing 721

21.1 Graph Drawing and Energy Minimization . . . . . . . . . . . . . . . . . . . 721
21.2 Examples of Graph Drawings . . . . . . . . . . . . . . . . . . . . . . . . . . 724
21.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 728

22 Singular Value Decomposition and Polar Form 731

8 CONTENTS

22.1 Properties of f ∗ ◦ f . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 731

22.2 Singular Value Decomposition for Square Matrices . . . . . . . . . . . . . . 737
22.3 Polar Form for Square Matrices . . . . . . . . . . . . . . . . . . . . . . . . . 741
22.4 Singular Value Decomposition for Rectangular Matrices . . . . . . . . . . . 743
22.5 Ky Fan Norms and Schatten Norms . . . . . . . . . . . . . . . . . . . . . . 747
22.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 748
22.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 748

23 Applications of SVD and Pseudo-Inverses 753

23.1 Least Squares Problems and the Pseudo-Inverse . . . . . . . . . . . . . . . . 753
23.2 Properties of the Pseudo-Inverse . . . . . . . . . . . . . . . . . . . . . . . . 760
23.3 Data Compression and SVD . . . . . . . . . . . . . . . . . . . . . . . . . . . 765
23.4 Principal Components Analysis (PCA) . . . . . . . . . . . . . . . . . . . . . 767
23.5 Best Affine Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . 778
23.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 782
23.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 783

II Affine and Projective Geometry 787

24 Basics of Affine Geometry 789
24.1 Affine Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 789
24.2 Examples of Affine Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . 798
24.3 Chasles’s Identity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 799
24.4 Affine Combinations, Barycenters . . . . . . . . . . . . . . . . . . . . . . . . 800
24.5 Affine Subspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 805
24.6 Affine Independence and Affine Frames . . . . . . . . . . . . . . . . . . . . . 811
24.7 Affine Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 817
24.8 Affine Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 824
24.9 Affine Geometry: A Glimpse . . . . . . . . . . . . . . . . . . . . . . . . . . 826
24.10 Affine Hyperplanes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 830
24.11 Intersection of Affine Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . 832

25 Embedding an Affine Space in a Vector Space 835

25.1 The “Hat Construction,” or Homogenizing . . . . . . . . . . . . . . . . . . . 835
25.2 Affine Frames of E and Bases of Ê . . . . . . . . . . . . . . . . . . . . . . . 842
25.3 Another Construction of Ê . . . . . . . . . . . . . . . . . . . . . . . . . . . 845
25.4 Extending Affine Maps to Linear Maps . . . . . . . . . . . . . . . . . . . . . 848

26 Basics of Projective Geometry 853

26.1 Why Projective Spaces? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 853
26.2 Projective Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 858
26.3 Projective Subspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 863
CONTENTS 9

26.4 Projective Frames . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 866

26.5 Projective Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 880
26.6 Finding a Homography Between Two Projective Frames . . . . . . . . . . . 886
26.7 Affine Patches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 899
26.8 Projective Completion of an Affine Space . . . . . . . . . . . . . . . . . . . 902
26.9 Making Good Use of Hyperplanes at Infinity . . . . . . . . . . . . . . . . . 907
26.10 The Cross-Ratio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 910
26.11 Fixed Points of Homographies and Homologies . . . . . . . . . . . . . . . . 914
26.12 Duality in Projective Geometry . . . . . . . . . . . . . . . . . . . . . . . . . 928
26.13 Cross-Ratios of Hyperplanes . . . . . . . . . . . . . . . . . . . . . . . . . . . 932
26.14 Complexification of a Real Projective Space . . . . . . . . . . . . . . . . . . 934
26.15 Similarity Structures on a Projective Space . . . . . . . . . . . . . . . . . . 936
26.16 Some Applications of Projective Geometry . . . . . . . . . . . . . . . . . . . 945

III The Geometry of Bilinear Forms 951

27 The Cartan–Dieudonné Theorem 953

27.1 The Cartan–Dieudonné Theorem for Linear Isometries . . . . . . . . . . . . 953
27.2 Affine Isometries (Rigid Motions) . . . . . . . . . . . . . . . . . . . . . . . . 965
27.3 Fixed Points of Affine Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . 967
27.4 Affine Isometries and Fixed Points . . . . . . . . . . . . . . . . . . . . . . . 969
27.5 The Cartan–Dieudonné Theorem for Affine Isometries . . . . . . . . . . . . 975

28 Isometries of Hermitian Spaces 979

28.1 The Cartan–Dieudonné Theorem, Hermitian Case . . . . . . . . . . . . . . . 979
28.2 Affine Isometries (Rigid Motions) . . . . . . . . . . . . . . . . . . . . . . . . 988

29 The Geometry of Bilinear Forms; Witt’s Theorem 993

29.1 Bilinear Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 993
29.2 Sesquilinear Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1001
29.3 Orthogonality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1005
29.4 Adjoint of a Linear Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1010
29.5 Isometries Associated with Sesquilinear Forms . . . . . . . . . . . . . . . . . 1012
29.6 Totally Isotropic Subspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . 1016
29.7 Witt Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1022
29.8 Symplectic Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1030
29.9 Orthogonal Groups and the Cartan–Dieudonné Theorem . . . . . . . . . . . 1034
29.10 Witt’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1041
10 CONTENTS

IV Algebra: PID’s, UFD’s, Noetherian Rings, Tensors,

Modules over a PID, Normal Forms 1047
30 Polynomials, Ideals and PID’s 1049
30.1 Multisets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1049
30.2 Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1050
30.3 Euclidean Division of Polynomials . . . . . . . . . . . . . . . . . . . . . . . 1056
30.4 Ideals, PID’s, and Greatest Common Divisors . . . . . . . . . . . . . . . . . 1058
30.5 Factorization and Irreducible Factors in K[X] . . . . . . . . . . . . . . . . . 1066
30.6 Roots of Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1070
30.7 Polynomial Interpolation (Lagrange, Newton, Hermite) . . . . . . . . . . . . 1077

31 Annihilating Polynomials; Primary Decomposition 1085

31.1 Annihilating Polynomials and the Minimal Polynomial . . . . . . . . . . . . 1087
31.2 Minimal Polynomials of Diagonalizable Linear Maps . . . . . . . . . . . . . 1089
31.3 Commuting Families of Linear Maps . . . . . . . . . . . . . . . . . . . . . . 1092
31.4 The Primary Decomposition Theorem . . . . . . . . . . . . . . . . . . . . . 1095
31.5 Jordan Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1101
31.6 Nilpotent Linear Maps and Jordan Form . . . . . . . . . . . . . . . . . . . . 1104
31.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1110
31.8 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1111

32 UFD’s, Noetherian Rings, Hilbert’s Basis Theorem 1115

32.1 Unique Factorization Domains (Factorial Rings) . . . . . . . . . . . . . . . . 1115
32.2 The Chinese Remainder Theorem . . . . . . . . . . . . . . . . . . . . . . . . 1129
32.3 Noetherian Rings and Hilbert’s Basis Theorem . . . . . . . . . . . . . . . . 1135
32.4 Futher Readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1139

33 Tensor Algebras 1141

33.1 Linear Algebra Preliminaries: Dual Spaces and Pairings . . . . . . . . . . . 1143
33.2 Tensors Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1148
33.3 Bases of Tensor Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1160
33.4 Some Useful Isomorphisms for Tensor Products . . . . . . . . . . . . . . . . 1161
33.5 Duality for Tensor Products . . . . . . . . . . . . . . . . . . . . . . . . . . . 1165
33.6 Tensor Algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1171
33.7 Symmetric Tensor Powers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1178
33.8 Bases of Symmetric Powers . . . . . . . . . . . . . . . . . . . . . . . . . . . 1182
33.9 Some Useful Isomorphisms for Symmetric Powers . . . . . . . . . . . . . . . 1185
33.10 Duality for Symmetric Powers . . . . . . . . . . . . . . . . . . . . . . . . . . 1185
33.11 Symmetric Algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1189
33.12 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1192

34 Exterior Tensor Powers and Exterior Algebras 1195

CONTENTS 11

34.1 Exterior Tensor Powers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1195

34.2 Bases of Exterior Powers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1200
34.3 Some Useful Isomorphisms for Exterior Powers . . . . . . . . . . . . . . . . 1203
34.4 Duality for Exterior Powers . . . . . . . . . . . . . . . . . . . . . . . . . . . 1203
34.5 Exterior Algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1207
34.6 The Hodge ∗-Operator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1211
34.7 Left and Right Hooks ~ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1215
34.8 Testing Decomposability ~ . . . . . . . . . . . . . . . . . . . . . . . . . . . 1225
34.9 The Grassmann-Plücker’s Equations and Grassmannians ~ . . . . . . . . . 1228
34.10 Vector-Valued Alternating Forms . . . . . . . . . . . . . . . . . . . . . . . . 1231
34.11 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1235

35 Introduction to Modules; Modules over a PID 1237

35.1 Modules over a Commutative Ring . . . . . . . . . . . . . . . . . . . . . . . 1237
35.2 Finite Presentations of Modules . . . . . . . . . . . . . . . . . . . . . . . . . 1246
35.3 Tensor Products of Modules over a Commutative Ring . . . . . . . . . . . . 1252
35.4 Torsion Modules over a PID; Primary Decomposition . . . . . . . . . . . . . 1255
35.5 Finitely Generated Modules over a PID . . . . . . . . . . . . . . . . . . . . 1261
35.6 Extension of the Ring of Scalars . . . . . . . . . . . . . . . . . . . . . . . . 1277

36 Normal Forms; The Rational Canonical Form 1283

36.1 The Torsion Module Associated With An Endomorphism . . . . . . . . . . 1283
36.2 The Rational Canonical Form . . . . . . . . . . . . . . . . . . . . . . . . . . 1291
36.3 The Rational Canonical Form, Second Version . . . . . . . . . . . . . . . . . 1298
36.4 The Jordan Form Revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . 1299
36.5 The Smith Normal Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1302

V Topology, Differential Calculus 1315

37 Topology 1317
37.1 Metric Spaces and Normed Vector Spaces . . . . . . . . . . . . . . . . . . . 1317
37.2 Topological Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1324
37.3 Continuous Functions, Limits . . . . . . . . . . . . . . . . . . . . . . . . . . 1333
37.4 Connected Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1341
37.5 Compact Sets and Locally Compact Spaces . . . . . . . . . . . . . . . . . . 1350
37.6 Second-Countable and Separable Spaces . . . . . . . . . . . . . . . . . . . . 1361
37.7 Sequential Compactness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1365
37.8 Complete Metric Spaces and Compactness . . . . . . . . . . . . . . . . . . . 1371
37.9 Completion of a Metric Space . . . . . . . . . . . . . . . . . . . . . . . . . . 1374
37.10 The Contraction Mapping Theorem . . . . . . . . . . . . . . . . . . . . . . 1381
37.11 Continuous Linear and Multilinear Maps . . . . . . . . . . . . . . . . . . . . 1385
37.12 Completion of a Normed Vector Space . . . . . . . . . . . . . . . . . . . . . 1392
12 CONTENTS

37.13 Normed Affine Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1395

37.14 Futher Readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1395

38 A Detour On Fractals 1397

38.1 Iterated Function Systems and Fractals . . . . . . . . . . . . . . . . . . . . 1397

39 Differential Calculus 1405

39.1 Directional Derivatives, Total Derivatives . . . . . . . . . . . . . . . . . . . 1405
39.2 Properties of Derivatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1414
39.3 Jacobian Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1419
39.4 The Implicit and The Inverse Function Theorems . . . . . . . . . . . . . . . 1427
39.5 Tangent Spaces and Differentials . . . . . . . . . . . . . . . . . . . . . . . . 1434
39.6 Second-Order and Higher-Order Derivatives . . . . . . . . . . . . . . . . . . 1436
39.7 Taylor’s formula, Faà di Bruno’s formula . . . . . . . . . . . . . . . . . . . . 1442
39.8 Vector Fields, Covariant Derivatives, Lie Brackets . . . . . . . . . . . . . . . 1447
39.9 Futher Readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1449
39.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1449
39.11 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1450

VI Preliminaries for Optimization Theory 1453

40 Extrema of Real-Valued Functions 1455
40.1 Local Extrema and Lagrange Multipliers . . . . . . . . . . . . . . . . . . . . 1456
40.2 Using Second Derivatives to Find Extrema . . . . . . . . . . . . . . . . . . . 1468
40.3 Using Convexity to Find Extrema . . . . . . . . . . . . . . . . . . . . . . . 1471
40.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1481
40.5 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1482

41 Newton’s Method and Its Generalizations 1485

41.1 Newton’s Method for Real Functions of a Real Argument . . . . . . . . . . 1485
41.2 Generalizations of Newton’s Method . . . . . . . . . . . . . . . . . . . . . . 1487
41.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1496
41.4 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1496

42 Quadratic Optimization Problems 1505

42.1 Quadratic Optimization: The Positive Definite Case . . . . . . . . . . . . . 1505
42.2 Quadratic Optimization: The General Case . . . . . . . . . . . . . . . . . . 1515
42.3 Maximizing a Quadratic Function on the Unit Sphere . . . . . . . . . . . . 1520
42.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1525
42.5 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1526

43 Schur Complements and Applications 1527

CONTENTS 13

43.1 Schur Complements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1527

43.2 SPD Matrices and Schur Complements . . . . . . . . . . . . . . . . . . . . . 1530
43.3 SP Semidefinite Matrices and Schur Complements . . . . . . . . . . . . . . 1531
43.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1533
43.5 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1533

VII Linear Optimization 1535

44 Convex Sets, Cones, H-Polyhedra 1537

44.1 What is Linear Programming? . . . . . . . . . . . . . . . . . . . . . . . . . 1537
44.2 Affine Subsets, Convex Sets, Hyperplanes, Half-Spaces . . . . . . . . . . . . 1539
44.3 Cones, Polyhedral Cones, and H-Polyhedra . . . . . . . . . . . . . . . . . . 1542
44.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1547
44.5 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1548

45 Linear Programs 1549

45.1 Linear Programs, Feasible Solutions, Optimal Solutions . . . . . . . . . . . 1549
45.2 Basic Feasible Solutions and Vertices . . . . . . . . . . . . . . . . . . . . . . 1556
45.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1563
45.4 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1563

46 The Simplex Algorithm 1567

46.1 The Idea Behind the Simplex Algorithm . . . . . . . . . . . . . . . . . . . . 1567
46.2 The Simplex Algorithm in General . . . . . . . . . . . . . . . . . . . . . . . 1576
46.3 How to Perform a Pivoting Step Efficiently . . . . . . . . . . . . . . . . . . 1583
46.4 The Simplex Algorithm Using Tableaux . . . . . . . . . . . . . . . . . . . . 1587
46.5 Computational Efficiency of the Simplex Method . . . . . . . . . . . . . . . 1596
46.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1597
46.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1597

47 Linear Programming and Duality 1601

47.1 Variants of the Farkas Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . 1601
47.2 The Duality Theorem in Linear Programming . . . . . . . . . . . . . . . . . 1607
47.3 Complementary Slackness Conditions . . . . . . . . . . . . . . . . . . . . . 1615
47.4 Duality for Linear Programs in Standard Form . . . . . . . . . . . . . . . . 1616
47.5 The Dual Simplex Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 1619
47.6 The Primal-Dual Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 1626
47.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1636
47.8 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1636
14 CONTENTS

VIII NonLinear Optimization 1641

48 Basics of Hilbert Spaces 1643
48.1 The Projection Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1643
48.2 Duality and the Riesz Representation Theorem . . . . . . . . . . . . . . . . 1656
48.3 Farkas–Minkowski Lemma in Hilbert Spaces . . . . . . . . . . . . . . . . . . 1661
48.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1662
48.5 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1663

49 General Results of Optimization Theory 1665

49.1 Optimization Problems; Basic Terminology . . . . . . . . . . . . . . . . . . 1665
49.2 Existence of Solutions of an Optimization Problem . . . . . . . . . . . . . . 1669
49.3 Minima of Quadratic Functionals . . . . . . . . . . . . . . . . . . . . . . . . 1673
49.4 Elliptic Functionals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1680
49.5 Iterative Methods for Unconstrained Problems . . . . . . . . . . . . . . . . 1683
49.6 Gradient Descent Methods for Unconstrained Problems . . . . . . . . . . . 1686
49.7 Convergence of Gradient Descent with Variable Stepsize . . . . . . . . . . . 1693
49.8 Steepest Descent for an Arbitrary Norm . . . . . . . . . . . . . . . . . . . . 1697
49.9 Newton’s Method For Finding a Minimum . . . . . . . . . . . . . . . . . . . 1699
49.10 Conjugate Gradient Methods; Unconstrained Problems . . . . . . . . . . . . 1703
49.11 Gradient Projection for Constrained Optimization . . . . . . . . . . . . . . 1714
49.12 Penalty Methods for Constrained Optimization . . . . . . . . . . . . . . . . 1717
49.13 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1719
49.14 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1720

50 Introduction to Nonlinear Optimization 1725

50.1 The Cone of Feasible Directions . . . . . . . . . . . . . . . . . . . . . . . . . 1727
50.2 Active Constraints and Qualified Constraints . . . . . . . . . . . . . . . . . 1733
50.3 The Karush–Kuhn–Tucker Conditions . . . . . . . . . . . . . . . . . . . . . 1740
50.4 Equality Constrained Minimization . . . . . . . . . . . . . . . . . . . . . . . 1751
50.5 Hard Margin Support Vector Machine; Version I . . . . . . . . . . . . . . . 1756
50.6 Hard Margin Support Vector Machine; Version II . . . . . . . . . . . . . . . 1761
50.7 Lagrangian Duality and Saddle Points . . . . . . . . . . . . . . . . . . . . . 1769
50.8 Weak and Strong Duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1778
50.9 Handling Equality Constraints Explicitly . . . . . . . . . . . . . . . . . . . . 1786
50.10 Dual of the Hard Margin Support Vector Machine . . . . . . . . . . . . . . 1789
50.11 Conjugate Function and Legendre Dual Function . . . . . . . . . . . . . . . 1794
50.12 Some Techniques to Obtain a More Useful Dual Program . . . . . . . . . . 1804
50.13 Uzawa’s Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1808
50.14 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1814
50.15 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1815

51 Subgradients and Subdifferentials ~ 1817

CONTENTS 15

51.1 Extended Real-Valued Convex Functions . . . . . . . . . . . . . . . . . . . . 1819

51.2 Subgradients and Subdifferentials . . . . . . . . . . . . . . . . . . . . . . . . 1828
51.3 Basic Properties of Subgradients and Subdifferentials . . . . . . . . . . . . . 1840
51.4 Additional Properties of Subdifferentials . . . . . . . . . . . . . . . . . . . . 1846
51.5 The Minimum of a Proper Convex Function . . . . . . . . . . . . . . . . . . 1850
51.6 Generalization of the Lagrangian Framework . . . . . . . . . . . . . . . . . 1857
51.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1860
51.8 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1862

52 Dual Ascent Methods; ADMM 1863

52.1 Dual Ascent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1865
52.2 Augmented Lagrangians and the Method of Multipliers . . . . . . . . . . . . 1869
52.3 ADMM: Alternating Direction Method of Multipliers . . . . . . . . . . . . . 1874
52.4 Convergence of ADMM ~ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1877
52.5 Stopping Criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1886
52.6 Some Applications of ADMM . . . . . . . . . . . . . . . . . . . . . . . . . . 1887
52.7 Solving Hard Margin (SVMh2 ) Using ADMM . . . . . . . . . . . . . . . . . 1892
52.8 Applications of ADMM to `1 -Norm Problems . . . . . . . . . . . . . . . . . 1894
52.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1899
52.10 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1900

IX Applications to Machine Learning 1903

53 Positive Definite Kernels 1905
53.1 Feature Maps and Kernel Functions . . . . . . . . . . . . . . . . . . . . . . 1905
53.2 Basic Properties of Positive Definite Kernels . . . . . . . . . . . . . . . . . . 1912
53.3 Hilbert Space Representation of a Positive Kernel . . . . . . . . . . . . . . . 1918
53.4 Kernel PCA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1921
53.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1924
53.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1925

54 Soft Margin Support Vector Machines 1927

54.1 Soft Margin Support Vector Machines; (SVMs1 ) . . . . . . . . . . . . . . . . 1930
54.2 Solving SVM (SVMs1 ) Using ADMM . . . . . . . . . . . . . . . . . . . . . . 1945
54.3 Soft Margin Support Vector Machines; (SVMs2 ) . . . . . . . . . . . . . . . . 1946
54.4 Solving SVM (SVMs2 ) Using ADMM . . . . . . . . . . . . . . . . . . . . . . 1953
54.5 Soft Margin Support Vector Machines; (SVMs20 ) . . . . . . . . . . . . . . . 1954
54.6 Classification of the Data Points in Terms of ν (SVMs20 ) . . . . . . . . . . . 1964
54.7 Existence of Support Vectors for (SVMs20 ) . . . . . . . . . . . . . . . . . . . 1967
54.8 Solving SVM (SVMs20 ) Using ADMM . . . . . . . . . . . . . . . . . . . . . 1978
54.9 Soft Margin Support Vector Machines; (SVMs3 ) . . . . . . . . . . . . . . . . 1982
54.10 Classification of the Data Points in Terms of ν (SVMs3 ) . . . . . . . . . . . 1989
16 CONTENTS

54.11 Existence of Support Vectors for (SVMs3 ) . . . . . . . . . . . . . . . . . . . 1991

54.12 Solving SVM (SVMs3 ) Using ADMM . . . . . . . . . . . . . . . . . . . . . . 1993
54.13 Soft Margin SVM; (SVMs4 ) . . . . . . . . . . . . . . . . . . . . . . . . . . . 1996
54.14 Solving SVM (SVMs4 ) Using ADMM . . . . . . . . . . . . . . . . . . . . . . 2005
54.15 Soft Margin SVM; (SVMs5 ) . . . . . . . . . . . . . . . . . . . . . . . . . . . 2007
54.16 Solving SVM (SVMs5 ) Using ADMM . . . . . . . . . . . . . . . . . . . . . . 2011
54.17 Summary and Comparison of the SVM Methods . . . . . . . . . . . . . . . 2013
54.18 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2026

55 Ridge Regression, Lasso, Elastic Net 2031

55.1 Ridge Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2032
55.2 Ridge Regression; Learning an Affine Function . . . . . . . . . . . . . . . . 2035
55.3 Kernel Ridge Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2044
55.4 Lasso Regression (`1 -Regularized Regression) . . . . . . . . . . . . . . . . . 2048
55.5 Lasso Regression; Learning an Affine Function . . . . . . . . . . . . . . . . . 2052
55.6 Elastic Net Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2058
55.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2064
55.8 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2064

56 ν-SV Regression 2067

56.1 ν-SV Regression; Derivation of the Dual . . . . . . . . . . . . . . . . . . . . 2067
56.2 Existence of Support Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . 2078
56.3 Solving ν-Regression Using ADMM . . . . . . . . . . . . . . . . . . . . . . . 2088
56.4 Kernel ν-SV Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2094
56.5 ν-Regression Version 2; Penalizing b . . . . . . . . . . . . . . . . . . . . . . 2097
56.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2104
56.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2105

X Appendices 2107
A Total Orthogonal Families in Hilbert Spaces 2109
A.1 Total Orthogonal Families, Fourier Coefficients . . . . . . . . . . . . . . . . 2109
A.2 The Hilbert Space `2 (K) and the Riesz–Fischer Theorem . . . . . . . . . . . 2118
A.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2127
A.4 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2128

B Matlab Programs 2129

B.1 Hard Margin (SVMh2 ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2129
B.2 Soft Margin SVM (SVMs20 ) . . . . . . . . . . . . . . . . . . . . . . . . . . . 2133
B.3 Soft Margin SVM (SVMs3 ) . . . . . . . . . . . . . . . . . . . . . . . . . . . 2141
B.4 ν-SV Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2146
CONTENTS 17

C Zorn’s Lemma; Some Applications 2153

C.1 Statement of Zorn’s Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . 2153
C.2 Proof of the Existence of a Basis in a Vector Space . . . . . . . . . . . . . . 2154
C.3 Existence of Maximal Proper Ideals . . . . . . . . . . . . . . . . . . . . . . 2155

Bibliography 2157

Index 2169