Generalized Robust Principal Component Analysis

Principal component analysis (PCA) is a widely used technique for estimating low-dimensional subspace from high-dimensional observations. PCA can be applied for dimension reduction, feature extraction, lossy compression, etc.

A major limitation of PCA is its sensitivity to the presence of outliers, where outliers are typically random data samples that deviate from the low-dimensional subspace with arbitrarily large distance. The outlier contaminated data can be regarded as the composition of a low-dimensional component and a sparse component. Techniques to robustify PCA against the presence of outliers are known as robust principal component analysis (RPCA). RPCA seeks separation of the sparse outlier component from the observation.

In certain applications the composite data are not directly observed but undergo a linear transformation. For example, in backbone networks the flow traffic among network nodes can be modeled as a composition of low-dimensional normal component and sparse abnormal component. The abnormal component may be due to external attacks or network failures, etc. The inter-nodal flows of traffic aggregate along the various physical links in the network. The observations made at the links are therefore a linear transformation of the underlying flow traffic. Another example is the separation of sparse foreground and low-dimensional background from distorted video sequences, where the distortion is modeled as a linear transformation.

The problem to decompose the low-dimensional component and the sparse component given transformed observations is known as the generalized robust PCA. Note the conventional robust PCA approaches can not be directly applied to solve these problems. In addition, naive inversion of the linear transformation may not work due the possible compression effect involved in the transformation.

The approaches to solve the generalized robust PCA problem generally fall into two categories: regularization-based approaches and statistical inference based approaches. Regularization-based approaches fit the the observation in the least-squares sense with the constraint that the underlying data components satisfy the low-rank and sparse properties. A major difficulty in applying the regularization-based approaches is the selection of the weighting parameters, which have significant impact on the algorithmic performance.

As an alternative, statistical models can be employed to characterize the properties of the underlying data components as well as the data generation process. Bayesian inference can then be applied to solve the inverse problem, where the posterior distributions of the unknowns are sought given the observations. By assigning priors, the unknown variables and model parameters can be automatically estimated, thus eliminating the need for parameter tuning.