Generalized Principal Component Analysis
豆瓣
René Vidal / Yi Ma …
简介
This book provides a comprehensive introduction to the latest advances in the mathematical theory and computational tools for modeling high-dimensional data drawn from one or multiple low-dimensional subspaces (or manifolds) and potentially corrupted by noise, gross errors, or outliers. This challenging task requires the development of new algebraic, geometric, statistical, and computational methods for efficient and robust estimation and segmentation of one or multiple subspaces. The book also presents interesting real-world applications of these new methods in image processing, image and video segmentation, face recognition and clustering, and hybrid system identification etc.
This book is intended to serve as a textbook for graduate students and beginning researchers in data science, machine learning, computer vision, image and signal processing, and systems theory. It contains ample illustrations, examples, and exercises and is made largely self-contained with three Appendices which survey basic concepts and principles from statistics, optimization, and algebraic-geometry used in this book.
contents
1 Introduction .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Modeling Data with a Parametric Model. . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.1 The Choice of a Model Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.2 Statistical Models versus Geometric Models .. . . . . . . . . . . . . 4
1.2 Modeling Mixed Data with a Mixture Model . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.1 Examples of Mixed Data Modeling . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.2 Mathematical Representations of Mixture Models . . . . . . . 12
1.3 Clustering via Discriminative or Nonparametric Methods . . . . . . . . . 16
1.4 Noise, Errors, Outliers, and Model Selection . . . . . . . . . . . . . . . . . . . . . . . 18
Part I Modeling Data with a Single Subspace
2 Principal Component Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.1 Classical Principal Component Analysis (PCA) . . . . . . . . . . . . . . . . . . . . 25
2.1.1 A Statistical View of PCA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.1.2 A Geometric View of PCA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.1.3 A Rank Minimization View of PCA. . . . . . . . . . . . . . . . . . . . . . . 34
2.2 Probabilistic Principal Component Analysis (PPCA) . . . . . . . . . . . . . . 38
2.2.1 PPCA from Population Mean and Covariance . . . . . . . . . . . . 39
2.2.2 PPCA by Maximum Likelihood . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.3 Model Selection for Principal Component Analysis. . . . . . . . . . . . . . . . 45
2.3.1 Model Selection by Information-Theoretic Criteria . . . . . . 46
2.3.2 Model Selection by Rank Minimization .. . . . . . . . . . . . . . . . . . 49
2.3.3 Model Selection by Asymptotic Mean Square Error . . . . . 51
2.4 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
2.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3 Robust Principal Component Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.1 PCA with Robustness to Missing Entries . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.1.1 Incomplete PCA by Mean and Covariance Completion . . 68
3.1.2 Incomplete PPCA by Expectation Maximization . . . . . . . . . 69
3.1.3 Matrix Completion by Convex Optimization . . . . . . . . . . . . . 73
3.1.4 Incomplete PCA by Alternating Minimization.. . . . . . . . . . . 78
3.2 PCA with Robustness to Corrupted Entries . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.2.1 Robust PCA by Iteratively Reweighted Least Squares . . . 89
3.2.2 Robust PCA by Convex Optimization .. . . . . . . . . . . . . . . . . . . . 92
3.3 PCA with Robustness to Outliers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
3.3.1 Outlier Detection by Robust Statistics . . . . . . . . . . . . . . . . . . . . . 101
3.3.2 Outlier Detection by Convex Optimization . . . . . . . . . . . . . . . 107
3.4 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
3.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
4 Nonlinear and Nonparametric Extensions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
4.1 Nonlinear and Kernel PCA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
4.1.1 Nonlinear Principal Component Analysis (NLPCA) . . . . . 126
4.1.2 NLPCA in a High-dimensional Feature Space . . . . . . . . . . . . 128
4.1.3 Kernel PCA (KPCA) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
4.2 Nonparametric Manifold Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
4.2.1 Multidimensional Scaling (MDS) . . . . . . . . . . . . . . . . . . . . . . . . . 134
4.2.2 Locally Linear Embedding (LLE) . . . . . . . . . . . . . . . . . . . . . . . . . 135
4.2.3 Laplacian Eigenmaps (LE) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
4.3 K-Means and Spectral Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
4.3.1 K-Means Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
4.3.2 Spectral Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
4.4 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
4.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
4.A Laplacian Eigenmaps: Continuous Formulation .. . . . . . . . . . . . . . . . . . . 166
Part II Modeling Data with Multiple Subspaces
5 Algebraic-GeometricMethods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
5.1 Problem Formulation of Subspace Clustering . . . . . . . . . . . . . . . . . . . . . . 172
5.1.1 Projectivization of Affine Subspaces . . . . . . . . . . . . . . . . . . . . . . 172
5.1.2 Subspace Projection and Minimum Representation . . . . . . 174
5.2 Introductory Cases of Subspace Clustering . . . . . . . . . . . . . . . . . . . . . . . . . 176
5.2.1 Clustering Points on a Line . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
5.2.2 Clustering Lines in a Plane . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
5.2.3 Clustering Hyperplanes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
5.3 Subspace Clustering Knowing the Number of Subspaces.. . . . . . . . . 184
5.3.1 An Introductory Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
5.3.2 Fitting Polynomials to Subspaces. . . . . . . . . . . . . . . . . . . . . . . . . . 186
5.3.3 Subspaces from Polynomial Differentiation . . . . . . . . . . . . . . 188
5.3.4 Point Selection via Polynomial Division . . . . . . . . . . . . . . . . . . 190
5.3.5 The Basic Algebraic Subspace Clustering Algorithm . . . . 193
5.4 Subspace Clustering not Knowing the Number of Subspaces . . . . . 196
5.4.1 Introductory Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
5.4.2 Clustering Subspaces of Equal Dimension .. . . . . . . . . . . . . . . 198
5.4.3 Clustering Subspaces of Different Dimensions . . . . . . . . . . . 200
5.5 Model Selection for Multiple Subspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
5.5.1 Effective Dimension of Samples of Multiple Subspaces . 202
5.5.2 Minimum Effective Dimension of Noisy Samples . . . . . . . . 204
5.5.3 Recursive Algebraic Subspace Clustering .. . . . . . . . . . . . . . . . 205
5.6 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
5.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
6 StatisticalMethods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
6.1 K-Subspaces .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
6.1.1 K-Subspaces Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
6.1.2 K-Subspaces Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
6.1.3 Convergence of the K-Subspaces Algorithm .. . . . . . . . . . . . . 221
6.1.4 Advantages and Disadvantages of K-Subspaces . . . . . . . . . . 222
6.2 Mixture of Probabilistic PCA (MPPCA). . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
6.2.1 MPPCA Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
6.2.2 Maximum Likelihood Estimation for MPPCA. . . . . . . . . . . . 223
6.2.3 Maximum a Posteriori (MAP) Estimation for MPPCA . . 226
6.2.4 Relationship between K-Subspaces and MPPCA. . . . . . . . . 228
6.3 Compression-Based Subspace Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
6.3.1 Model Estimation and Data Compression .. . . . . . . . . . . . . . . . 231
6.3.2 Minimium Coding Length via Agglomerative Clustering 233
6.3.3 Lossy Coding of Multivariate Data . . . . . . . . . . . . . . . . . . . . . . . . 238
6.3.4 Coding Length of Mixed Gaussian Data . . . . . . . . . . . . . . . . . . 242
6.4 Simulations and Applications. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
6.4.1 Statistical Methods on Synthetic Data . . . . . . . . . . . . . . . . . . . . . 247
6.4.2 Statistical Methods on Gene Expression
Clustering, Image Segmentation, and Face Clustering . . . 254
6.5 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
6.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261
6.A Lossy Coding Length for Subspace-like Data . . . . . . . . . . . . . . . . . . . . . . 263
7 Spectral Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
7.1 Spectral Subspace Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268
7.2 Local Subspace Affinity (LSA) and Spectral Local
Best-Fit Flats (SLBF) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
7.3 Locally Linear Manifold Clustering (LLMC). . . . . . . . . . . . . . . . . . . . . . . 274
7.4 Spectral Curvature Clustering (SCC). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276
7.5 Spectral Algebraic Subspace Clustering (SASC) . . . . . . . . . . . . . . . . . . . 279
7.6 Simulations and Applications. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
7.6.1 Spectral Methods on Synthetic Data . . . . . . . . . . . . . . . . . . . . . . . 281
7.6.2 Spectral Methods on Face Clustering. . . . . . . . . . . . . . . . . . . . . . 285
7.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
8 Sparse and Low-Rank Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
8.1 Self-Expressiveness and Subspace-Preserving Representations . . . 294
8.1.1 Self-Expressiveness Property . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294
8.1.2 Subspace-Preserving Representation . . . . . . . . . . . . . . . . . . . . . . 296
8.2 Low-Rank Subspace Clustering (LRSC) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
8.2.1 LRSC with Uncorrupted Data. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
8.2.2 LRSC with Robustness to Noise . . . . . . . . . . . . . . . . . . . . . . . . . . . 302
8.2.3 LRSC with Robustness to Corruptions . . . . . . . . . . . . . . . . . . . . 308
8.3 Sparse Subspace Clustering (SSC) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
8.3.1 SSC with Uncorrupted Data. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
8.3.2 SSC with Robustness to Outliers . . . . . . . . . . . . . . . . . . . . . . . . . . 324
8.3.3 SSC with Robustness to Noise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326
8.3.4 SSC with Robustness to Corrupted Entries.. . . . . . . . . . . . . . . 330
8.3.5 SSC for Affine Subspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332
8.4 Simulations and Applications. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333
8.4.1 Low-Rank and Sparse Methods on Synthetic Data . . . . . . . 333
8.4.2 Low-Rank and Sparse Methods on Face Clustering . . . . . . 336
8.5 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344
8.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345
Part III Applications
9 Image Representation .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349
9.1 Seeking Compact and Sparse Image Representations . . . . . . . . . . . . . . 349
9.1.1 Prefixed Linear Transformations.. . . . . . . . . . . . . . . . . . . . . . . . . . 350
9.1.2 Adaptive, Overcomplete, and Hybrid Representations . . . 351
9.1.3 Hierarchical Models for Multiscale Structures. . . . . . . . . . . . 353
9.2 Image Representation with Multiscale Hybrid Linear Models . . . . . 354
9.2.1 Linear versus Hybrid Linear Models . . . . . . . . . . . . . . . . . . . . . . 354
9.2.2 Multiscale Hybrid Linear Models. . . . . . . . . . . . . . . . . . . . . . . . . . 361
9.2.3 Experiments and Comparisons.. . . . . . . . . . . . . . . . . . . . . . . . . . . . 365
9.3 Multiscale Hybrid Linear Models in Wavelet Domain . . . . . . . . . . . . . 369
9.3.1 Imagery Data Vectors in the Wavelet Domain . . . . . . . . . . . . 369
9.3.2 Hybrid Linear Models in the Wavelet Domain . . . . . . . . . . . . 371
9.3.3 Comparison with Other Lossy Representations .. . . . . . . . . . 372
9.4 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376
10 Image Segmentation .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377
10.1 Basic Models and Principles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378
10.1.1 Problem Formulation .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378
10.1.2 Image Segmentation as Subspace Clustering . . . . . . . . . . . . . 380
10.1.3 Minimum Coding Length Principle . . . . . . . . . . . . . . . . . . . . . . . 381
10.2 Encoding Image Textures and Boundaries . . . . . . . . . . . . . . . . . . . . . . . . . . 382
10.2.1 Construction of Texture Features . . . . . . . . . . . . . . . . . . . . . . . . . . 382
10.2.2 Texture Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383
10.2.3 Boundary Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384
10.3 Compression-Based Image Segmentation.. . . . . . . . . . . . . . . . . . . . . . . . . . 386
10.3.1 Minimizing Total Coding Length . . . . . . . . . . . . . . . . . . . . . . . . . . 386
10.3.2 Hierarchical Implementation .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 387
10.3.3 Choosing the Proper Distortion Level . . . . . . . . . . . . . . . . . . . . . 389
10.4 Experimental Evaluation .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 392
10.4.1 Color Spaces and Compressibility .. . . . . . . . . . . . . . . . . . . . . . . . 392
10.4.2 Experimental Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394
10.4.3 Results and Discussions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395
10.5 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399
11 Motion Segmentation.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401
11.1 The 3D Motion Segmentation Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402
11.2 Motion Segmentation from Multiple Affine Views . . . . . . . . . . . . . . . . . 405
11.2.1 Affine Projection of a Rigid-Body Motion . . . . . . . . . . . . . . . . 405
11.2.2 Motion Subspace of a Rigid-Body Motion .. . . . . . . . . . . . . . . 406
11.2.3 Segmentation of Multiple Rigid-Body Motions. . . . . . . . . . . 406
11.2.4 Experiments on Multiview Motion Segmentation . . . . . . . . 407
11.3 Motion Segmentation from Two Perspective Views . . . . . . . . . . . . . . . . 413
11.3.1 Perspective Projection of a Rigid-Body Motion . . . . . . . . . . 414
11.3.2 Segmentation of 3D Translational Motions . . . . . . . . . . . . . . . 415
11.3.3 Segmentation of Rigid-Body Motions .. . . . . . . . . . . . . . . . . . . . 416
11.3.4 Segmentation of Rotational Motions or Planar Scenes . . . 417
11.3.5 Experiments on Two-View Motion Segmentation . . . . . . . . 418
11.4 Temporal Motion Segmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 421
11.4.1 Dynamical Models of Time-Series Data . . . . . . . . . . . . . . . . . . 422
11.4.2 Experiments on Temporal Video Segmentation .. . . . . . . . . . 423
11.4.3 Experiments on Segmentation of Human
Motion Data. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425
11.5 Bibliographical Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428
12 Hybrid System Identification. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431
12.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433
12.2 Identification of a Single ARX System. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434
12.3 Identification of Hybrid ARX Systems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 438
12.3.1 The Hybrid Decoupling Polynomial .. . . . . . . . . . . . . . . . . . . . . . 439
12.3.2 Identifying the Hybrid Decoupling Polynomial .. . . . . . . . . . 440
12.3.3 Identifying System Parameters and Discrete States . . . . . . . 443
12.3.4 The Basic Algorithm and Its Extensions . . . . . . . . . . . . . . . . . . 445
12.4 Simulations and Experiments .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 446
12.4.1 Error in the Estimation of the Model Parameters . . . . . . . . . 447
12.4.2 Error as a Function of the Model Orders . . . . . . . . . . . . . . . . . . 447
12.4.3 Error as a Function of Noise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 448
12.4.4 Experimental Results on Test Data Sets . . . . . . . . . . . . . . . . . . . 449
12.5 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 450
13 FinalWords . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453
13.1 Unbalanced and Multimodal Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454
13.2 Unsupervised and Semisupervised Learning.. . . . . . . . . . . . . . . . . . . . . . . 454
13.3 Data Acquisition and Online Data Analysis . . . . . . . . . . . . . . . . . . . . . . . . 455
13.4 Other Low-DimensionalModels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456
13.5 Computability and Scalability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457
13.6 Theory, Algorithms, Systems, and Applications.. . . . . . . . . . . . . . . . . . . 459
A Basic Facts from Optimization .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 461
A.1 Unconstrained Optimization .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 461
A.1.1 Optimality Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462
A.1.2 Convex Set and Convex Function.. . . . . . . . . . . . . . . . . . . . . . . . . 462
A.1.3 Subgradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 464
A.1.4 Gradient Descent Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465
A.1.5 Alternating Direction Minimization . . . . . . . . . . . . . . . . . . . . . . . 466
A.2 Constrained Optimization .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 468
A.2.1 Optimality Conditions and Lagrangian Multipliers . . . . . . . 468
A.2.2 Augmented Lagrange Multipler Methods . . . . . . . . . . . . . . . . . 470
A.2.3 Alternating Direction Method of Multipliers. . . . . . . . . . . . . . 471
A.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474
B Basic Facts from Mathematical Statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475
B.1 Estimation of Parametric Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475
B.1.1 Sufficient Statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476
B.1.2 Mean Square Error, Efficiency, and Fisher Information . . 477
B.1.3 The Rao–Blackwell Theorem and Uniformly
Minimum-Variance Unbiased Estimator . . . . . . . . . . . . . . . . . . 479
B.1.4 Maximum Likelihood (ML) Estimator . . . . . . . . . . . . . . . . . . . . 480
B.1.5 Consistency and Asymptotic Efficiency of the
ML Estimator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 481
B.2 ML Estimation for Models with Latent Variables . . . . . . . . . . . . . . . . . . 485
B.2.1 Expectation Maximization (EM). . . . . . . . . . . . . . . . . . . . . . . . . . . 486
B.2.2 Maximum a Posteriori Expectation
Maximization (MAP-EM). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 488
B.3 Estimation of Mixture Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 490
B.3.1 EM for Mixture Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 490
B.3.2 MAP-EM for Mixture Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 492
B.3.3 A Case in Which EM Fails . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494
B.4 Model-Selection Criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 496
B.4.1 Akaike Information Criterion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497
B.4.2 Bayesian Information Criterion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 498
B.5 Robust Statistical Methods.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 498
B.5.1 Influence-Based Outlier Detection . . . . . . . . . . . . . . . . . . . . . . . . . 499
B.5.2 Probability-Based Outlier Detection . . . . . . . . . . . . . . . . . . . . . . . 501
B.5.3 Random-Sampling-Based Outlier Detection . . . . . . . . . . . . . . 503
B.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 506
C Basic Facts from Algebraic Geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 509
C.1 Abstract Algebra Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 509
C.1.1 Polynomial Rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 509
C.1.2 Ideals and Algebraic Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 511
C.1.3 Algebra and Geometry: Hilbert’s Nullstellensatz . . . . . . . . . 513
C.1.4 Algebraic Sampling Theory .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514
C.1.5 Decomposition of Ideals and Algebraic Sets . . . . . . . . . . . . . . 516
C.1.6 Hilbert Function, Polynomial, and Series . . . . . . . . . . . . . . . . . 517
C.2 Ideals of Subspace Arrangements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 519
C.3 Subspace Embedding and PL-Generated Ideals . . . . . . . . . . . . . . . . . . . . 522
C.4 Hilbert Functions of Subspace Arrangements . . . . . . . . . . . . . . . . . . . . . . 524
C.4.1 Hilbert Function and Algebraic Subspace Clustering. . . . . 525
C.4.2 Special Cases of the Hilbert Function . . . . . . . . . . . . . . . . . . . . . 528
C.4.3 Formulas for the Hilbert Function . . . . . . . . . . . . . . . . . . . . . . . . . 530
C.5 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 534
References. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 535
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 553