000			18648cam a22003738i 4500
999			_c35243 _d35243
003			CUTN
005			20210706151605.0
008			200405m20209999nju b 001 0 eng
020			_a9789811206399
020			_a9789811207716
020			_z9789811206405
020			_z9789811206412
020			_a9789811216565
020			_z9789811216589
020			_z9789811216572
041			_aEnglish
042			_apcc
082	0	0	_a512.5 _223 _bGAL
100	1		_aGallier, Jean H.,
245	1	0	_aLinear algebra and optimization with applications to machine learning _cJean Gallier, Jocelyn Quaintance.
300			_avolume : _billustrations (some color) ; _c24 cm
505	1		_aVolume I. Linear algebra for computer vision, robotics, and machine learning -- Volume II. Fundamentals of optimization theory with applications to machine learning _t1 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
520			_a"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"--
650		0	_aAlgebras, Linear.
650		0	_aMachine learning
700	1		_aQuaintance, Jocelyn,
942			_2ddc _cBOOKS
100	1		_eauthor.
504			_aIncludes bibliographical references and index.
650		0	_xMathematics.
700	1		_eauthor.
906			_a7 _bcbc _corignew _d1 _eecip _f20 _gy-gencatlg