具体描述
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.
广义主成分分析：超越线性降维的探索 在海量数据涌现的时代，有效的数据降维技术是洞察数据本质、提取关键信息、构建高效模型的基石。传统的主成分分析（Principal Component Analysis, PCA）以其简洁的数学框架和强大的线性降维能力，在数据科学领域占据着举足轻重的地位。然而，现实世界中的数据往往蕴含着复杂的非线性关系，简单的线性投影可能无法充分捕捉数据的内在结构，甚至可能丢失重要的信息。正是在这样的背景下，“广义主成分分析”的概念应运而生，它致力于突破线性PCA的局限，提供更强大、更灵活的数据降维解决方案。 本书并非对“广义主成分分析”这一特定学术术语的定义或现有方法的详细罗列。相反，它将是一次深刻的、探索性的旅程，深入剖析数据降维的哲学思想，审视现有方法的优势与不足，并由此引申出对更广阔、更具通用性降维框架的思考。本书将不会局限于任何已有的“广义主成分分析”的文献或具体的算法实现，而是站在一个更高的视角，探讨“广义”二字所蕴含的深刻含义，以及如何构建一种能够适应更多数据类型、更复杂数据结构的降维范式。 数据降维的基石：理解“维”与“信息” 在展开“广义”的探讨之前，我们必须首先清晰地理解“维度”和“信息”在数据分析中的含义。高维数据之所以难以处理，不仅仅是因为其计算量庞大，更重要的是，高维空间中的点与点之间的距离往往变得模糊，数据的稀疏性问题尤为突出，使得许多传统的机器学习算法表现不佳。降维的目的，本质上是将数据从高维空间映射到一个低维空间，同时最大程度地保留原始数据中的“关键信息”。 那么，何为“关键信息”？在PCA的框架下，关键信息被定义为数据的方差，即数据在各个方向上的散布程度。最大化方差意味着寻找数据变化最显著的方向，这些方向被认为是蕴含数据主要变化模式的“主成分”。然而，在许多实际应用中，数据的“信息”可能并非仅仅体现在方差上。例如，在图像识别任务中，人脸的关键信息可能在于其特定的结构特征（如眼睛、鼻子、嘴巴的相对位置），而非像素值整体的方差。在文本挖掘中，词语的共现频率、语义关联可能比简单的词频统计更能揭示文本的主题。因此，对“信息”的定义，是走向“广义”降维的第一步。 线性PCA的洞察与局限 本书将首先回顾线性PCA的核心思想。通过特征值分解或奇异值分解，PCA能够找到一组正交的基向量（主成分），使得原始数据在这些基向量上的投影方差最大。这一过程直观且易于理解，并且在线性可分或数据主要变化方向接近线性的情况下，PCA表现出色。例如，在图像压缩、噪声过滤、特征提取等领域，PCA已经证明了其强大的实用性。 然而，线性PCA的局限性也同样显著。它假设数据之间的关系是线性的，对于存在复杂非线性结构的观测值，线性PCA可能无法捕捉到数据中的重要模式。例如，在处理Swiss roll（瑞士卷）或Moons（月牙）等经典非线性数据集时，线性PCA会将其“压扁”，丢失其原本的二维流形结构。此外，PCA对数据的尺度敏感，需要进行预处理（如标准化）来避免某些特征因为量级较大而主导主成分的计算。更深层次的问题在于，PCA关注的是全局的方差，而忽略了局部数据的结构信息，这在一些需要精细分析的场景下可能成为瓶颈。 “广义”的内涵：拥抱多样化的数据结构与信息度量 “广义”二字，意味着我们将超越线性假设，去拥抱更丰富的数据结构和更灵活的信息度量方式。这包括但不限于： 非线性流形学习： 许多现实世界的数据，即使在高维空间中，也可能隐藏在一个低维度的“流形”上。这些流形可能是弯曲的、非线性的。因此，一种广义的降维方法需要能够捕捉和保持这些非线性的局部结构。这可能涉及到将数据嵌入到一个低维的、保持局部邻域关系的流形空间中。 度量学习与相似性保持： 在某些应用中，我们更关心的是数据点之间的相对相似性或距离关系。例如，在推荐系统中，我们希望将相似的用户或物品映射到低维空间中的相近位置。这意味着我们需要一种降维方法，能够学习一个度量，并以此来指导降维过程，确保在低维空间中保留原始数据的高维相似性。 信息论视角： 除了方差，信息论提供了另一种衡量信息量的方式，如互信息、熵等。将信息论的度量引入降维过程，可以让我们关注那些更能揭示数据背后生成机制或统计依赖性的信息。例如，最大化降维后数据与原始数据之间的互信息，或者最小化降维过程中的信息损失。 图模型与结构化数据： 许多数据天生就具有图结构，例如社交网络、知识图谱、分子结构等。传统的PCA方法难以直接处理这些图结构数据。广义的降维框架需要能够有效地从图结构中提取信息，并将其映射到低维空间。这可能涉及到图嵌入技术，将图的节点映射到向量空间，同时保留图的连接信息和节点的属性信息。 条件降维与特定任务导向： 在许多监督学习场景下，我们降维的目的并非仅仅是描述数据的整体变化，而是为了更好地服务于一个特定的下游任务，如分类或回归。因此，一种更“广义”的降维方法，应该是能够根据任务目标来指导降维过程，使得降维后的特征对目标变量具有更强的预测能力。这可能涉及到在降维过程中融入任务相关的损失函数或约束条件。 构建广义降维的理论框架与实践路径 本书将从理论层面探讨构建广义降维方法的可能性。我们将审视如何扩展PCA的数学表达，使其能够处理非线性映射、学习度量，以及整合信息论的度量。这可能涉及到核方法（Kernel Methods）的应用，将数据映射到高维特征空间，然后在該空间进行线性 PCA，从而间接实现非线性降维。或者，我们也将探讨基于优化理论的方法，通过定义合适的损失函数和约束条件，直接在高维数据空间中寻找最优的低维表示。 在实践层面，本书将为读者提供一些探索性的思路和潜在的实现方向。虽然不会直接给出具体算法的实现代码，但会引导读者思考如何将上述的“广义”内涵转化为可操作的算法设计。例如，如何选择合适的核函数来捕捉数据的非线性结构？如何设计能够保持局部邻域关系的损失函数？如何将图卷积网络（Graph Convolutional Networks, GCNs）等深度学习模型融入到降维框架中？ 超越“主成分”：探索新的降维视角 “广义主成分分析”这个术语本身也值得我们去反思。传统的“主成分”强调的是方差最大化。当我们走向“广义”时，我们是否应该继续沿用“主成分”这个概念？或许，我们可以将其视为“主要子空间”、“关键结构”、“最优表示”等更具包容性的术语。本书将鼓励读者打破思维定势，从更广泛的角度去理解降维的目标和方法。 总结与展望 总而言之，本书旨在提供一个关于数据降维的深度思考框架。它不是一个算法手册，而是一次对“广义”二字背后所蕴含的无限可能性的探索。我们将从理解数据、审视线性PCA的局限性出发，逐步拓展到对非线性结构、多样化信息度量、图模型以及任务导向降维的思考。本书的目的是激发读者对数据降维领域更深入的理解和创新，鼓励大家跳出固有的框架，去探索更强大、更普适的数据降维范式，从而在日益复杂的数据世界中，解锁更多的洞察与价值。它将是一次思维的启迪，引领读者走向更广阔的数据科学天地。
作者简介
René Vidal is a Professor of Biomedical Engineering and Director of the Vision Dynamics and Learning Lab at The Johns Hopkins University.
Yi Ma is Executive Dean and Professor at the School of Information Science and Technology at ShanghaiTech University.
S. Shankar Sastry is Dean of the College of Engineering, Professor of Electrical Engineering and Computer Science and Professor of Bioengineering at the University of California, Berkeley.
目录信息
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
· · · · · · (收起)
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
· · · · · · (收起)
读后感
用户评价
对于那些希望在方法论上建立起自己独特见解的资深研究人员来说，本书的贡献无法估量。它提供了一个坚实的理论基石，让我们可以站在巨人的肩膀上，去质疑、去拓展已有的范式。作者在论述中展现出的那种严谨的逻辑链条和对数理细节的精雕细琢，使得全书的论述几乎无懈可击。它成功地构建了一个“为什么（Why）”和“如何（How）”紧密结合的知识结构，而不是仅仅罗列出一堆“做什么（What）”。这种深层次的剖析，促使我重新审视了数据结构背后的生成过程假设，从而能够设计出更能适应真实世界噪声和非线性特性的分析模型。这本书不仅仅是一部参考资料，它更像是一本启发性的思想伙伴，它挑战了我固有的分析框架，迫使我以更开放、更具实验精神的态度去面对未来的数据挑战。我强烈推荐给那些已经掌握基础，正寻求突破性创新的专业人士。
这本书的广度与深度达到了一个近乎完美的平衡点，它没有满足于停留在表面对经典方法进行复述，而是大刀阔斧地探索了其应用边界与局限性，这一点让我印象尤为深刻。它不像许多同类书籍那样，只停留在欧几里得空间内打转，而是勇敢地将分析视角拓展到了更复杂的黎曼流形甚至是信息几何的范畴，这无疑将本书的层次提升到了研究前沿的高度。更令人称道的是，作者在讨论每一种广义化方法时，都会极其审慎地分析其计算复杂性和收敛稳定性，这对于准备将理论付诸大规模计算实践的读者来说，是至关重要的“避坑指南”。阅读过程中，我多次停下来，对比了书中提出的新颖优化策略与我惯常使用的经典算法的优劣，这种对比和反思的过程，极大地强化了我对算法选择的批判性思维。这本书无疑是为那些不满足于现状、渴望推动技术前沿的学者和工程师量身定制的。
坦白说，我拿到这本书时，原本预期会是一本略显枯燥的教科书，但阅读过程中的惊喜层出不穷。作者的叙事节奏掌握得极佳，那种行云流水的叙述方式，让人完全沉浸其中，仿佛不是在阅读一篇篇密集的文字，而是在聆听一位经验极其丰富的专家，娓娓道来他毕生积累的洞见。书中对“广义”这一概念的诠释尤其精彩，它巧妙地超越了传统的基于方差最大化的线性投影，引入了更具适应性和情境敏感性的处理视角。这种多角度的审视，极大地拓宽了我对“主成分”这一概念的传统认知边界。书中穿插的那些精心挑选的案例研究，虽然抽象，却有力地支撑了理论的有效性，它们如同精确的坐标点，帮助读者将抽象的数学模型锚定在实际问题场景中。总而言之，这是一部需要静下心来细细品味的著作，其价值在于其提供的不仅仅是工具，更是一种看待和解析世界复杂性的新视角。
这部作品的阅读体验简直是一场智力上的盛宴，它不仅仅是一本技术手册，更像是一次深入探索数据内在结构的哲学之旅。作者以一种令人信服的清晰度，构建了一个宏大而严谨的理论框架，将原本晦涩难懂的多元统计概念，抽丝剥茧地呈现在读者面前。我尤其欣赏它在方法论上的深度挖掘，书中对不同维度缩减技术背后的数学基础进行了淋漓尽致的阐述，那些在其他入门读物中常被一笔带过的假设条件和约束，在这里都被置于显微镜下进行审视。每一次公式的推导都仿佛在引领我逐步揭开隐藏在复杂数据背后的真相，让我对如何从高维空间中提取出最具信息量的低维表示有了全新的、更加深刻的理解。它成功地平衡了理论的深度与实践的可操作性，使得即便是初次接触该领域尖端模型的读者，也能逐步建立起坚实的知识体系。这本书无疑为我处理复杂数据集的策略提供了革命性的指导，其影响远远超出了单纯的算法应用层面，更多是思维模式的重塑。
这本书的排版和图示设计简直是业界典范。在一个充斥着密密麻麻公式和图表的专业领域，能够做到如此清晰、直观的呈现，实属不易。那些复杂的迭代过程和特征空间的几何解释，如果仅仅依靠文字描述，读者必然会在半途迷失方向，但作者巧妙地利用了高质量的示意图，将抽象的数学操作具象化。比如，在解释某些非正交投影的优化目标时，配图的维度感和空间关系处理得恰到好处，使得原本需要耗费大量时间在脑海中构建模型的步骤，被瞬间打通。这种对读者学习路径的体贴入微，使得本书的门槛看似高昂，实则更容易被有志于深入钻研的读者跨越。它体现了一种深刻的教育理念：真正的专业深度，也应伴随着极致的表达清晰度。对于任何希望将理论知识转化为实际工程能力的专业人士而言，这种视觉化的辅助是无价之宝。
