  The idea of Innovation Search was proposed as a data clustering method in
which the directions of innovation were utilized to compute the adjacency
matrix and it was shown that Innovation Pursuit can notably outperform the self
representation based subspace clustering methods. In this paper, we present a
new discovery that the directions of innovation can be used to design a
provable and strong robust (to outlier) PCA method. The proposed approach,
dubbed iSearch, uses the direction search optimization problem to compute an
optimal direction corresponding to each data point. iSearch utilizes the
directions of innovation to measure the innovation of the data points and it
identifies the outliers as the most innovative data points. Analytical
performance guarantees are derived for the proposed robust PCA method under
different models for the distribution of the outliers including randomly
distributed outliers, clustered outliers, and linearly dependent outliers. In
addition, we study the problem of outlier detection in a union of subspaces and
it is shown that iSearch provably recovers the span of the inliers when the
inliers lie in a union of subspaces. Moreover, we present theoretical studies
which show that the proposed measure of innovation remains stable in the
presence of noise and the performance of iSearch is robust to noisy data. In
the challenging scenarios in which the outliers are close to each other or they
are close to the span of the inliers, iSearch is shown to remarkably outperform
most of the existing methods. The presented method shows that the directions of
innovation are useful representation of the data which can be used to perform
both data clustering and outlier detection.
