Matrix Analysis and Applications

Contents......Page 8
Preface......Page 18
Notation......Page 22
Abbreviations......Page 32
Algorithms......Page 35
PART I MATRIX ALGEBRA......Page 38
1.1.1 Vectors and Matrices......Page 40
1.1.2 Basic Vector Calculus......Page 43
1.1.3 Basic Matrix Calculus......Page 45
1.1.5 Matrix Functions......Page 48
1.2.1 Elementary Row Operations......Page 50
1.2.2 Gauss Elimination Methods......Page 53
1.3.1 Sets......Page 57
1.3.2 Fields and Vector Spaces......Page 59
1.3.3 Linear Mapping......Page 61
1.4.1 Inner Products of Vectors......Page 64
1.4.2 Norms of Vectors......Page 65
1.4.3 Similarity Comparison Between Vectors......Page 69
1.4.4 Banach Space, Euclidean Space, Hilbert Space......Page 72
1.4.5 Inner Products and Norms of Matrices......Page 73
1.5 Random Vectors......Page 77
1.5.1 Statistical Interpretation of Random Vectors......Page 78
1.5.2 Gaussian Random Vectors......Page 81
1.6.1 Quadratic Forms......Page 84
1.6.2 Determinants......Page 86
1.6.3 Matrix Eigenvalues......Page 89
1.6.4 Matrix Trace......Page 91
1.6.5 Matrix Rank......Page 93
1.7.1 Definition and Properties of Inverse Matrices......Page 96
1.7.2 Matrix Inversion Lemma......Page 97
1.7.3 Inversion of Hermitian Matrices......Page 98
1.7.4 Left and Right Pseudo-Inverse Matrices......Page 100
1.8.1 Definition and Properties......Page 102
1.8.2 Computation of Moore–Penrose Inverse Matrix......Page 106
1.9.1 Direct Sum of Matrices......Page 108
1.9.2 Hadamard Product......Page 109
1.10.1 Kronecker Products......Page 112
1.10.2 Generalized Kronecker Products......Page 114
1.10.3 Khatri–Rao Product......Page 115
1.11.1 Vectorization and Commutation Matrix......Page 116
1.11.2 Matricization of a Vector......Page 119
1.11.3 Properties of Vectorization Operator......Page 120
1.12.1 Sparse Vectors and Sparse Representations......Page 121
1.12.2 Sparse Representation of Face Recognition......Page 123
Exercises......Page 124
2.1 Hermitian Matrices......Page 132
2.2 Idempotent Matrix......Page 133
2.3.1 Permutation Matrix and Exchange Matrix......Page 135
2.3.2 Generalized Permutation Matrix......Page 138
2.4 Orthogonal Matrix and Unitary Matrix......Page 141
2.5.2 Triangular Matrix......Page 144
2.6 Summing Vector and Centering Matrix......Page 146
2.6.1 Summing Vector......Page 147
2.6.2 Centering Matrix......Page 148
2.7.1 Vandermonde Matrix......Page 149
2.7.2 Fourier Matrix......Page 151
2.7.3 Index Vectors......Page 153
2.7.4 FFT Algorithm......Page 155
2.8 Hadamard Matrix......Page 158
2.9.1 Symmetric Toeplitz Matrix......Page 160
2.9.2 Discrete Cosine Transform of Toeplitz Matrix......Page 162
Exercises......Page 163
3.1 Jacobian Matrix and Gradient Matrix......Page 166
3.1.1 Jacobian Matrix......Page 167
3.1.2 Gradient Matrix......Page 169
3.1.3 Calculation of Partial Derivative and Gradient......Page 170
3.2.1 Calculation of Real Matrix Differential......Page 176
3.2.2 Jacobian Matrix Identification......Page 178
3.2.3 Jacobian Matrix of Real Matrix Functions......Page 184
3.3.1 Real Hessian Matrix......Page 187
3.3.2 Real Hessian Matrix Identification......Page 189
3.4.1 Holomorphic Function and Complex Partial Derivative......Page 194
3.4.2 Complex Matrix Differential......Page 198
3.4.3 Complex Gradient Matrix Identification......Page 206
3.5 Complex Hessian Matrices and Identification......Page 211
3.5.1 Complex Hessian Matrices......Page 212
3.5.2 Complex Hessian Matrix Identification......Page 214
Exercises......Page 216
PART II MATRIX ANALYSIS......Page 218
4.1 Real Gradient Analysis......Page 220
4.1.1 Stationary Points and Extreme Points......Page 221
4.1.2 Real Gradient Analysis of f(x)......Page 223
4.1.3 Real Gradient Analysis of f(X)......Page 225
4.2.1 Extreme Point of Complex Variable Function......Page 227
4.2.2 Complex Gradient Analysis......Page 232
4.3.1 Standard Constrained Optimization Problems......Page 235
4.3.2 Convex Sets and Convex Functions......Page 237
4.3.3 Convex Function Identification......Page 240
4.4.1 Gradient Method......Page 242
4.4.2 Conjugate Gradient Method......Page 247
4.4.3 Convergence Rates......Page 252
4.5.1 Lipschitz Continuous Function......Page 254
4.5.2 Nesterov Optimal Gradient Algorithms......Page 257
4.6 Nonsmooth Convex Optimization......Page 260
4.6.1 Subgradient and Subdifferential......Page 261
4.6.2 Proximal Operator......Page 265
4.6.3 Proximal Gradient Method......Page 269
4.7.1 Lagrange Multiplier Method......Page 274
4.7.2 Penalty Function Method......Page 275
4.7.3 Augmented Lagrange Multiplier Method......Page 277
4.7.4 Lagrangian Dual Method......Page 279
4.7.5 Karush–Kuhn–Tucker Conditions......Page 281
4.7.6 Alternating Direction Method of Multipliers......Page 285
4.8.1 Newton Method for Unconstrained Optimization......Page 288
4.8.2 Newton Method for Constrained Optimization......Page 291
4.9.1 Original–Dual Problems......Page 297
4.9.2 First-Order Original–Dual Interior-Point Method......Page 298
4.9.3 Second-Order Original–Dual Interior-Point Method......Page 300
Exercises......Page 305
5.1 Numerical Stability and Condition Number......Page 308
5.2.1 Singular Value Decomposition......Page 311
5.2.2 Properties of Singular Values......Page 314
5.2.3 Rank-Deficient Least Squares Solutions......Page 317
5.3.1 PSVD Problem......Page 320
5.3.2 Accurate Calculation of PSVD......Page 321
5.4 Applications of Singular Value Decomposition......Page 322
5.4.1 Static Systems......Page 323
5.4.2 Image Compression......Page 324
5.5.1 Definition and Properties......Page 326
5.5.2 Algorithms for GSVD......Page 329
5.5.3 Two Application Examples of GSVD......Page 331
5.6 Low-Rank–Sparse Matrix Decomposition......Page 333
5.6.1 Matrix Decomposition Problems......Page 334
5.6.2 Singular Value Thresholding......Page 335
5.6.3 Robust Principal Component Analysis......Page 337
5.7 Matrix Completion......Page 339
5.7.1 Matrix Completion Problems......Page 340
5.7.2 Matrix Completion Model and Incoherence......Page 342
5.7.3 Singular Value Thresholding Algorithm......Page 343
5.7.4 Fast and Accurate Matrix Completion......Page 345
Exercises......Page 349
6 Solving Matrix Equations......Page 352
6.1.1 Ordinary Least Squares Methods......Page 353
6.1.2 Properties of Least Squares Solutions......Page 354
6.1.3 Data Least Squares......Page 357
6.2.1 Tikhonov Regularization......Page 358
6.2.2 Regularized Gauss–Seidel Method......Page 361
6.3.1 TLS Problems......Page 365
6.3.2 TLS Solution......Page 366
6.3.3 Performances of TLS Solution......Page 370
6.3.4 Generalized Total Least Squares......Page 372
6.3.5 Total Least Squares Fitting......Page 374
6.3.6 Total Maximum Likelihood Method......Page 379
6.4 Constrained Total Least Squares......Page 381
6.4.1 Constrained Total Least Squares Method......Page 382
6.4.2 Harmonic Superresolution......Page 384
6.4.3 Image Restoration......Page 385
6.5 Subspace Method for Solving Blind Matrix Equations......Page 387
6.6.1 Nonnegative Matrices......Page 390
6.6.2 Nonnegativity and Sparsity Constraints......Page 392
6.6.3 Nonnegative Matrix Factorization Model......Page 393
6.6.4 Divergences and Deformed Logarithm......Page 398
6.7.1 Multiplication Algorithms......Page 403
6.7.2 Nesterov Optimal Gradient Algorithm......Page 409
6.7.3 Alternating Nonnegative Least Squares......Page 411
6.7.4 Quasi-Newton Method......Page 414
6.7.5 Sparse Nonnegative Matrix Factorization......Page 415
6.8.1 ℓ1-Norm Minimization......Page 418
6.8.2 Lasso and Robust Linear Regression......Page 421
6.8.3 Mutual Coherence and RIP Conditions......Page 424
6.8.4 Relation to Tikhonov Regularization......Page 426
6.8.5 Gradient Analysis of ℓ1-Norm Minimization......Page 427
6.9.1 Basis Pursuit Algorithms......Page 428
6.9.3 Barzilai–Borwein Gradient Projection Algorithm......Page 431
6.9.4 ADMM Algorithms for Lasso Problems......Page 434
6.9.5 LARS Algorithms for Lasso Problems......Page 435
6.9.6 Covariance Graphical Lasso Method......Page 437
6.9.7 Homotopy Algorithm......Page 439
6.9.8 Bregman Iteration Algorithms......Page 440
Exercises......Page 446
7.1.1 Eigenvalue Problem......Page 450
7.1.2 Characteristic Polynomial......Page 452
7.2.1 Eigenvalues......Page 453
7.2.2 Eigenvectors......Page 456
7.3 Similarity Reduction......Page 459
7.3.1 Similarity Transformation of Matrices......Page 460
7.3.2 Similarity Reduction of Matrices......Page 463
7.3.3 Similarity Reduction of Matrix Polynomials......Page 467
7.4.1 Smith Normal Forms......Page 471
7.4.2 Invariant Factor Method......Page 474
7.4.3 Conversion of Jordan Form and Smith Form......Page 478
7.4.4 Finding Smith Blocks from Jordan Blocks......Page 479
7.4.5 Finding Jordan Blocks from Smith Blocks......Page 480
7.5.1 Cayley–Hamilton Theorem......Page 483
7.5.2 Computation of Inverse Matrices......Page 485
7.5.3 Computation of Matrix Powers......Page 487
7.5.4 Calculation of Matrix Exponential Functions......Page 489
7.6.1 Pisarenko Harmonic Decomposition......Page 492
7.6.2 Discrete Karhunen–Loeve Transformation......Page 495
7.6.3 Principal Component Analysis......Page 498
7.7.1 Generalized Eigenvalue Decomposition......Page 500
7.7.2 Total Least Squares Method for GEVD......Page 504
7.7.3 Application of GEVD: ESPRIT......Page 505
7.7.4 Similarity Transformation in GEVD......Page 508
7.8.1 Definition and Properties of Rayleigh Quotient......Page 511
7.8.2 Rayleigh Quotient Iteration......Page 512
7.8.3 Algorithms for Rayleigh Quotient......Page 513
7.9.1 Definition and Properties......Page 515
7.9.2 Effectiveness of Class Discrimination......Page 517
7.9.3 Robust Beamforming......Page 519
7.10.1 Description of Quadratic Eigenvalue Problems......Page 521
7.10.2 Solving Quadratic Eigenvalue Problems......Page 523
7.10.3 Application Examples......Page 527
7.11.1 Joint Diagonalization Problems......Page 532
7.11.2 Orthogonal Approximate Joint Diagonalization......Page 534
7.11.3 Nonorthogonal Approximate Joint Diagonalization......Page 537
Exercises......Page 540
8.1.1 Bases of Subspaces......Page 548
8.1.2 Disjoint Subspaces and Orthogonal Complement......Page 550
8.2.1 Definitions and Properties......Page 553
8.2.2 Subspace Basis Construction......Page 557
8.2.3 SVD-Based Orthonormal Basis Construction......Page 559
8.2.4 Basis Construction of Subspaces Intersection......Page 562
8.3.1 Signal Subspace and Noise Subspace......Page 563
8.3.2 Multiple Signal Classification (MUSIC)......Page 566
8.3.3 Subspace Whitening......Page 568
8.4.1 Equivalent Subspaces......Page 569
8.4.2 Grassmann Manifold......Page 570
8.4.3 Stiefel Manifold......Page 572
8.5 Projection Approximation Subspace Tracking (PAST)......Page 573
8.5.1 Basic PAST Theory......Page 574
8.5.2 PAST Algorithms......Page 577
8.6.1 Rayleigh–Ritz Approximation......Page 579
8.6.2 Fast Subspace Decomposition Algorithm......Page 581
Exercises......Page 583
9.1 Projection and Orthogonal Projection......Page 588
9.1.1 Projection Theorem......Page 589
9.1.2 Mean Square Estimation......Page 591
9.2.1 Projector and Orthogonal Projector......Page 593
9.2.2 Projection Matrices......Page 595
9.2.3 Derivatives of Projection Matrix......Page 598
9.3.1 Updating Formulas for Projection Matrices......Page 599
9.3.2 Prediction Filters......Page 601
9.3.3 Updating of Lattice Adaptive Filter......Page 604
9.4 Oblique Projector of Full Column Rank Matrix......Page 607
9.4.1 Definition and Properties of Oblique Projectors......Page 608
9.4.2 Geometric Interpretation of Oblique Projectors......Page 612
9.4.3 Recursion of Oblique Projectors......Page 615
9.5.1 Definition and Properties......Page 616
9.5.2 Calculation of Oblique Projection......Page 618
9.5.3 Applications of Oblique Projectors......Page 620
Exercises......Page 622
PART III HIGHER-ORDER MATRIX ANALYSIS......Page 624
10.1.1 Tensors......Page 626
10.1.2 Tensor Representation......Page 629
10.2.1 Vectorization and Horizontal Unfolding......Page 634
10.2.2 Longitudinal Unfolding of Tensors......Page 638
10.3.1 Inner Product, Norm and Outer Product......Page 643
10.3.2 Mode-n Product of Tensors......Page 645
10.3.3 Rank of Tensor......Page 649
10.4 Tucker Decomposition of Tensors......Page 651
10.4.1 Tucker Decomposition (Higher-Order SVD)......Page 652
10.4.2 Third-Order SVD......Page 654
10.4.3 Alternating Least Squares Algorithms......Page 658
10.5.1 Bilinear Model......Page 662
10.5.2 Parallel Factor Analysis......Page 664
10.5.3 Uniqueness Condition......Page 672
10.5.4 Alternating Least Squares Algorithm......Page 674
10.6 Applications of Low-Rank Tensor Decomposition......Page 678
10.6.1 Multimodal Data Fusion......Page 679
10.6.2 Fusion of Multimodal Brain Images......Page 681
10.6.3 Process Monitoring......Page 683
10.6.4 Note on Other Applications......Page 685
10.7.1 Tensor–Vector Products......Page 686
10.7.2 Determinants and Eigenvalues of Tensors......Page 688
10.7.3 Generalized Tensor Eigenvalues Problems......Page 693
10.7.4 Orthogonal Decomposition of Symmetric Tensors......Page 695
10.8 Preprocessing and Postprocessing......Page 696
10.8.1 Centering and Scaling of Multi-Way Data......Page 697
10.8.2 Compression of Data Array......Page 698
10.9.1 Multiplication Algorithm......Page 701
10.9.2 ALS Algorithms......Page 704
10.10 Tensor Completion......Page 707
10.10.1 Simultaneous Tensor Decomposition and Completion......Page 708
10.10.2 Smooth PARAFAC Tensor Completion......Page 711
10.11 Software......Page 713
Exercises......Page 715
References......Page 718
Index......Page 745