Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2016 | Book

Introduction Read chapter Read first chapter

Generalized Principal Component Analysis

Authors: René Vidal, Yi Ma, S.S. Sastry

Publisher: Springer New York

Book Series : Interdisciplinary Applied Mathematics

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access
insite
SEARCH

About this book

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.

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.

Table of Contents

Frontmatter
Chapter 1. Introduction
Abstract
The sciences do not try to explain, they hardly even try to interpret, they mainly make models. By a model is meant a mathematical construct which, with the addition of certain verbal interpretations, describes observed phenomena. The justification of such a mathematical construct is solely and precisely that it is expected to work.
René Vidal, Yi Ma, S. Shankar Sastry

Modeling Data with a Single Subspace

Frontmatter
Chapter 2. Principal Component Analysis
Abstract
Principal component analysis (PCA) is the problem of fitting a low-dimensional affine subspace to a set of data points in a high-dimensional space. PCA is, by now, well established in the literature, and has become one of the most useful tools for data modeling, compression, and visualization.
René Vidal, Yi Ma, S. Shankar Sastry
Chapter 3. Robust Principal Component Analysis
Abstract
In the previous chapter, we considered the PCA problem under the assumption that all the sample points are drawn from the same statistical or geometric model: a low-dimensional subspace.
René Vidal, Yi Ma, S. Shankar Sastry
Chapter 4. Nonlinear and Nonparametric Extensions
Abstract
In the previous chapters, we studied the problem of fitting a low-dimensional linear or affine subspace to a collection of points. In practical applications, however, a linear or affine subspace may not be able to capture nonlinear structures in the data. For instance, consider the set of all images of a face obtained by rotating it about its main axis of symmetry. While all such images live in a high-dimensional space whose dimension is the number of pixels, there is only one degree of freedom in the data, namely the angle of rotation. In fact, the space of all such images is a one-dimensional circle embedded in a high-dimensional space, whose structure is not well captured by a one-dimensional line. More generally, a collection of face images observed from different viewpoints is not well approximated by a single linear or affine subspace, as illustrated in the following example.
René Vidal, Yi Ma, S. Shankar Sastry

Modeling Data with Multiple Subspaces

Frontmatter
Chapter 5. Algebraic-Geometric Methods
Abstract
In this chapter, we consider a generalization of PCA in which the given sample points are drawn from an unknown arrangement of subspaces of unknown and possibly different dimensions.
René Vidal, Yi Ma, S. Shankar Sastry
Chapter 6. Statistical Methods
Abstract
The algebraic-geometric approach to subspace clustering described in the previous chapter provides a fairly complete characterization of the algebra and geometry of multiple subspaces, which leads to simple and elegant subspace clustering algorithms. However, while these methods can handle some noise in the data, they do not make explicit assumptions about the distribution of the noise or the data inside the subspaces. Therefore, the estimated subspaces need not be optimal from a statistical perspective, e.g., in a maximum likelihood (ML) sense.
René Vidal, Yi Ma, S. Shankar Sastry
Chapter 7. Spectral Methods
Abstract
The preceding two chapters studied the subspace clustering problem using algebraic-geometric and statistical techniques, respectively. Under the assumption that the data are not corrupted, we saw in Chapter 5 that algebraic-geometric methods are able to solve the subspace clustering problem in full generality, allowing for an arbitrary union of different subspaces of any dimensions and in any orientations, as long as sufficiently many data points in general configuration are drawn from the union of subspaces. However, while algebraic-geometric methods are able to deal with moderate amounts of noise, they are unable to deal with outliers. Moreover, even in the noise-free setting, the computational complexity of linear-algebraic methods for fitting polynomials grows exponentially with the number of subspaces and their dimensions. As a consequence, algebraic-geometric methods are most effective for low-dimensional problems with moderate amounts of noise.
René Vidal, Yi Ma, S. Shankar Sastry
Chapter 8. Sparse and Low-Rank Methods
Abstract
The previous chapter studies a family of subspace clustering methods based on spectral clustering. In particular, we have studied both local and global methods for defining a subspace clustering affinity, and have noticed that we seem to be facing an important dilemma. On the one hand, local methods compute an affinity that depends only on the data points in a local neighborhood of each data point. Local methods can be rather efficient and somewhat robust to outliers, but they cannot deal well with intersecting subspaces. On the other hand, global methods utilize geometric information derived from the entire data set (or a large portion of it) to construct the affinity. Global methods might be immune to local mistakes, but they come with a big price: their computational complexity is often exponential in the dimension and number of subspaces. Moreover, none of the methods comes with a theoretical analysis that guarantees the correctness of clustering. Therefore, a natural question that arises is whether we can construct a subspace clustering affinity that utilizes global geometric relationships among all the data points, is computationally tractable when the dimension and number of subspaces are large, and is guaranteed to provide the correct clustering under certain conditions.
René Vidal, Yi Ma, S. Shankar Sastry

Applications

Frontmatter
Chapter 9. Image Representation
Abstract
In this and the following chapters, we demonstrate why multiple subspaces can be a very useful class of models for image processing and how the subspace clustering techniques may facilitate many important image processing tasks, such as image representation, compression, image segmentation, and video segmentation.
René Vidal, Yi Ma, S. Shankar Sastry
Chapter 10. Image Segmentation
Abstract
Image segmentation is the task of partitioning a natural image into multiple contiguous regions, also known as segments, whereby adjacent regions are separated by salient edges or contours, and each region consists of pixels with homogeneous color or texture. In computer vision, this is widely accepted as a crucial step for any high-level vision tasks such as object recognition and understanding image semantics.
René Vidal, Yi Ma, S. Shankar Sastry
Chapter 11. Motion Segmentation
Abstract
The previous two chapters have shown how to use a mixture of subspaces to represent and segment static images. In those cases, different subspaces were used to account for multiple characteristics of natural images, e.g., different textures. In this chapter, we will show how to use a mixture of subspaces to represent and segment time series, e.g., video and motion capture data. In particular, we will use different subspaces to account for multiple characteristics of the dynamics of a time series, such as multiple moving objects or multiple temporal events.
René Vidal, Yi Ma, S. Shankar Sastry
Chapter 12. Hybrid System Identification
Abstract
Hybrid systems are mathematical models that are used to describe continuous processes that occasionally exhibit discontinuous behaviors due to sudden changes of dynamics. For instance, the continuous trajectory of a bouncing ball results from alternating between free fall and elastic contact with the ground. However, hybrid systems can also be used to describe a complex process or time series that does not itself exhibit discontinuous behaviors, by approximating the process or series with a simpler class of dynamical models. For example, a nonlinear dynamical system can be approximated by switching among a set of linear systems, each approximating the nonlinear system in a subset of its state space. As another example, a video sequence can be segmented to different scenes by fitting a piecewise linear dynamical model to the entire sequence.
René Vidal, Yi Ma, S. Shankar Sastry
Chapter 13. Final Words
Abstract
As we have stated from the very beginning of this book, the ultimate goal of our quest is to be able to effectively and efficiently extract low-dimensional structures in high-dimensional data. Our intention is for this book to serve as an introductory textbook for readers who are interested in modern data science and engineering, including both its mathematical and computational foundations as well as its applications. By using what is arguably the most basic and useful class of structures, i.e., linear subspaces, this book introduces some of the most fundamental geometrical, statistical, and optimization principles for data analysis. While these mathematical models and principles are classical and timeless, the problems and results presented in this book are rather modern and timely. Compared with classical methods for learning low-dimensional subspaces (such as PCA (Jolliffe 1986), the methods discussed in this book significantly enrich our data analysis arsenal with modern methods that are robust to imperfect data (due to uncontrolled data acquisition processes) and can handle mixed heterogenous structures in the data.
René Vidal, Yi Ma, S. Shankar Sastry
Backmatter
Metadata
Title
Generalized Principal Component Analysis
Authors
René Vidal
Yi Ma
S.S. Sastry
Copyright Year
2016
Publisher
Springer New York
Electronic ISBN
978-0-387-87811-9
Print ISBN
978-0-387-87810-2
DOI
https://doi.org/10.1007/978-0-387-87811-9