Closed-Form, Provable, and Robust PCA via Leverage Statistics and Innovation Search
The idea of Innovation Search, which was initially proposed for data clustering, was recently used for outlier detection. In the application of Innovation Search for outlier detection, the directions of innovation were utilized to measure the innovation of the data points. We study the Innovation Values computed by the Innovation Search algorithm under a quadratic cost function and it is proved that Innovation Values with the new cost function are equivalent to Leverage Scores. This interesting connection is utilized to establish several theoretical guarantees for a Leverage Score based robust PCA method and to design a new robust PCA method. The theoretical results include performance guarantees with different models for the distribution of outliers and the distribution of inliers. In addition, we demonstrate the robustness of the algorithms against the presence of noise. The numerical and theoretical studies indicate that while the presented approach is fast and closed-form, it can outperform most of the existing algorithms.
\section{Introduction}
Principal Component Analysis (PCA) has been extensively
used for linear dimensionality reduction.
While PCA is useful when the data has
low intrinsic dimension, its output is  sensitive to outliers
in the sense that the subspace found by  PCA can arbitrarily deviate from
the true underlying subspace even if a small portion of the data  is corrupted. In addition, locating the outlying components is of great interest in many applications.

There are two different robust PCA problems corresponding to two different models for the data corruption. The first problem, known as low rank plus sparse matrix decomposition, assumes that a random subset of the elements of data are corrupted and the corrupted elements are not concentrated in any column/row of the data~\cite{lamport22,lamport1}. In the second problem,  a subset of columns of the data  \textcolor{black}{are affected by the data corruption}~\cite{lamport10,zhang2014novel,lerman2014fast,fischler1981random,li1985projection,choulakian2006l1,feng2012robust,mccoy2011two,hardt2013algorithms,zhang2016robust,you2017provable,markopoulos2014optimal}.
This paper focuses on the column-wise model, i.e., it is assumed that
data matrix $\mathbf{D} \in \mathbb{R}^{M_1 \times M_2}$ can be expressed as
$$
\mathbf{D} = ( [\mathbf{B} \hspace{.2cm} \mathbf{A}] ) \: \mathbf{T} \:,
$$
where $\mathbf{A} \in \mathbb{R}^{M_1 \times n_i}$, $\mathbf{B} \in \mathbb{R}^{M_1 \times n_o}$,  $\mathbf{T}$ is an unknown permutation matrix, and $[\mathbf{B} \hspace{.2cm} \mathbf{A}]$ represents the concatenation of matrices $\mathbf{A}$ and $\mathbf{B}$.
 The columns of $\mathbf{A}$ lie in an $r$-dimensional subspace $\mathcal{U}$. The columns of $\mathbf{B}$ do not lie entirely in $\mathcal{U}$, i.e., the $n_i$ columns of $\mathbf{A}$ are the inliers and the $n_o$ columns of $\mathbf{B}$ are the outliers.  
The output of a robust PCA method is an estimate for $\mathcal{U}$.
If  $\mathcal{U}$ is estimated accurately, the outliers can be  located by projecting the data points on the complement of $\mathcal{U}$.






\subsection{Summary of Contributions}
Most of the existing robust PCA algorithms require a large number of iterations each with high computational complexity and most of them are not supported with thorough performance guarantees. We present  closed-form and provable robust PCA methods which  mostly outperform the existing methods.  The main contributions can be summarized as follows. 
\\
$\bullet$ It is proved that  Innovation Value introduced in~\cite{rahmani2019outlier2} is equivalent to Leverage Score if a quadratic cost function is used to find the optimal directions instead of the $\ell_1$-norm based cost function. This interesting connection is used to establish several  theoretical guarantees
\\
$\bullet$ Inspired by the explanation of Leverage Scores with  Innovation Search, a new robust PCA method, which uses a symmetric measure of similarity, is presented. The presented closed-form methods mostly outperform the existing methods while they only include one singular value decomposition plus one matrix multiplication.
\\
$\bullet$ Theoretical performance guarantees under several different models for the distribution of the outliers and inliers are presented. Furthermore, the robustness to the presence of noise is studied and it is shown that the  algorithm can provably distinguish the outliers when the data is noisy. 







\subsection{Notation} 
Given a matrix $\mathbf{A}$, $\| \mathbf{A} \|$ denotes its spectral norm, $\| \mathbf{A} \|_F$ denotes its Frobenius norm,  and $\mathbf{A}^T$ is the transpose of $\mathbf{A}$. For a vector $\mathbf{a}$, $\| \mathbf{a} \|_p$ denotes its $\ell_p$-norm and $\mathbf{a}(i)$ its $i^{\text{th}}$ element.  For a matrix $\mathbf{A}$, $\mathbf{a}_i$ denotes its $i^{\text{th}}$ column and  $\| \mathbf{A} \|_{1,2} = \sum_{i} \| \mathbf{a}_i \|_2$.
$\mathbb{S}^{M_1 - 1}$ indicates the unit $\ell_2$-norm sphere in $\mathbb{R}^{M_1}$. Matrix $\mathbf{D} = \mathbf{U}^{'} \Sigma \mathbf{V}$ where $\mathbf{U}^{'} \in \mathbb{R}^{M_1 \times r_d}$ is the matrix of left singular vectors, $\Sigma \in \mathbb{R}^{r_d \times r_d}$ is a diagonal matrix whose diagonal values are equal to the non-zero singular values of $\mathbf{D}$,  the rows of $\mathbf{V} \in \mathbb{R}^{r_d \times M_2}$ are equal to the right singular vectors, and $r_d$ is the rank of $\mathbf{D}$. The orthonormal matrix $\mathbf{U} \in \mathbb{R}^{M_1 \times r}$ is defined as a basis for $\mathcal{U}$. 
Note that $\mathbf{U}^{'}$ is a basis for the entire data, $\mathbf{U}$ is a basis for the inliers, $r_d$ is the rank of $\mathbf{D}$, and $r$ is the rank of $\mathbf{A}$. The subspace $\mathcal{U}^{\perp}$ is defined as the complement of $\mathcal{U}$. 


\section{Related Work}
\label{sec:related_work}
 Robust PCA is a well-known problem and many approaches were developed for this problem. In this section, we briefly review some of the previous works on robust PCA.
Some of the earliest approaches to robust PCA are based on 
robust estimation of the data covariance matrix, such as the minimum covariance determinant, the minimum volume ellipsoid, and the Stahel-Donoho estimator~\cite{lamport47,feng2012robust,xu2010principal}.
However, these methods mostly compute a full SVD
or eigenvalue decomposition in each iteration and their performance greatly degrades when $\frac{n_i}{n_o} < 0.5$. In addition, they lack performance guarantees with structured outliers. 
Another approach is to replace the Frobenius Norm in the cost function of PCA  with  $\ell_1$-norm~\cite{lamport18,lamport29}, as $\ell_1$-norm was shown to be robust to the presence of the outliers~\cite{decod,lamport29}. In order to leverage the column-wise structure of the outliers,  
the authors of~\cite{lamport21} replaced the $\ell_1$-norm minimization problem used in~\cite{lamport29}  with an $\ell_{1,2}$-norm minimization problem. In~\cite{lerman2015robustnn} and~\cite{zhang2014novel}, the optimization problem used in~\cite{lamport21} was relaxed to two different convex optimization problems. The authors of~\cite{lerman2015robustnn,zhang2014novel}  provided sufficient conditions \textcolor{black}{under which} the optimal points of the convex optimization problems proposed in~\cite{lerman2015robustnn,zhang2014novel} are guaranteed to yield an exact basis for  $\mathcal{U}$ . 
The approach presented in~\cite{tsakiris2015dual} focused on the scenario in which the data is predominantly unstructured outliers and the number of outliers is larger than $M_1$.
In~\cite{tsakiris2015dual}, it is essential to assume that the outliers are randomly distributed on $\mathbb{S}^{M_1 - 1}$ and the inliers are distributed randomly on the intersection of $\mathbb{S}^{M_1 - 1}$ and $\mathcal{U}$. 
The outlier detection method proposed in~\cite{soltanolkotabi2012geometric} assumes that the outliers are randomly distributed on $\mathbb{S}^{M_1 - 1}$ and a small number of them are not linearly dependent which means that~\cite{soltanolkotabi2012geometric} is not able to detect the linearly dependent outliers and the outliers which are close to each other. Another approach is based on decomposing the given $\mathbf{D}$ into a low rank matrix and a column sparse matrix where the column sparse matrix models the presence of the outliers \cite{cherapanamjeri2017thresholding,lamport10}. However, this approach requires the number of outliers to be significantly smaller than the number of the outliers and the solver algorithms that are used to decompose the data need to compute a SVD of the data in each iteration. 


The main shortcomings of the previous methods are sensitivity to structured outliers and the lack of comprehensive theoretical guarantees. The Coherence Pursuit method, proposed in~\cite{rahmani2017coherence}, was shown (theoretically and numerically) to be robust to different types of outliers. However, Coherence Pursuit can miss outliers which carry weak innovation with respect to the inliers. The iSearch algorithm, proposed in~\cite{rahmani2019outlier2}, was shown to notably outperform Coherence Pursuit in detecting outliers with weak innovation . Similar to Coherence Pursuit, the robustness of iSearch against different types of outliers were supported with several theoretical guarantees. However, in contrast to Coherence Pursuit which is a closed-form method, iSearch needs to run an iterative and computationally expensive solver to find the directions of innovation.
\textit{This paper presents  robust PCA methods which have the advantages of both (CoP and iSearch) algorithms: while they are closed-form algorithms, their ability in distinguishing outliers are on a par with iSearch. 
In the rest of this section, Coherence Pursuit and iSearch are reviewed in more details.}

\begin{comment}
In this section, some of the previous works on robust PCA are briefly reviewed. 
Since the presented approach is more related to  Coherence Pursuit ~\cite{rahmani2017coherence} and  iSearch ~\cite{rahmani2019outlier2}, these two methods are reviewed with more details. 
The earliest approaches to robust PCA were mostly based on a 
robust estimation of the data covariance matrix~\cite{lamport47}.
These methods compute a full SVD
or eigenvalue decomposition in each iteration and their performance greatly degrades when $\frac{n_i}{n_o} < 0.5$.
Another approach to enhance the robustness of PCA against outliers is to replace  the Frobenius Norm in the cost function of PCA  with  $\ell_1$-norm~\cite{lamport18,lamport29} because $\ell_1$-norm were shown to be robust to the presence of the outliers~\cite{decod,lamport29}. The authors of~\cite{lamport21} modified the $\ell_1$-norm minimization problem used in~\cite{lamport29} and replaced it with an $\ell_{1,2}$-norm minimization problem to leverage the column-wise structure of the outliers. In~\cite{lerman2015robustnn} and~\cite{zhang2014novel}, the optimization problem used in~\cite{lamport21} was relaxed to two different convex optimization problems. 
The approach presented in~\cite{tsakiris2015dual} assumes that the data is predominantly unstructured outliers and the outliers/inliers are randomly distributed in $\mathbb{S}^{M_1-1}$/$\mathbb{S}^{M_1-1}\cap \mathcal{U}$
In~\cite{lamport10}, a convex optimization problem was proposed which decomposes the data into a low rank component and a column sparse component. The approach presented in~\cite{lamport10} is provable but it requires $n_o$ to be significantly smaller than $n_i$.
The outlier detection method proposed in~\cite{soltanolkotabi2012geometric} utilizes sparse self representation and it assumes that the outliers are randomly distributed on $\mathbb{S}^{M_1 - 1}$ and a small number of them are not linearly dependent.
\end{comment}

\vspace{0.05in}
\noindent
\textbf{Coherence Pursuit (CoP):}
CoP  ~\cite{rahmani2017coherence} assigns a value, termed Coherence Value, to each data point and $\mathcal{U}$ is recovered using the span of the data points with the highest Coherence Values. The Coherence Value corresponding to data point $\mathbf{d}_i$ represents the similarity between $\mathbf{d}_i$ and the rest of the data points. CoP uses inner-product to measure the similarity between data points and it distinguishes the outliers based on the fact that an inlier bears more resemblance to the rest of the data than an outlier.


\vspace{0.05in}
\noindent
\textbf{Innovation Search (iSearch)~\cite{rahmani2019outlier2}:}
Innovation Pursuit was initially proposed as a data clustering algorithm~\cite{rahmani2017subspacedi,rahmani2015innovation}.  The authors of~\cite{rahmani2017subspacedi,rahmani2015innovation} showed that Innovation Pursuit can notably outperform the self-representation based clustering methods (e.g. Sparse Subspace Clustering~\cite{lamport7}) specifically when the clusters are close to each other. 
Innovation Pursuit computes an optimal direction corresponding to each data point $\mathbf{d}_i$ which can be written as the optimal point of 
\begin{eqnarray}
\underset{ \mathbf{c}}{\min} \: \:  \| \mathbf{c}^T \mathbf{D} \|_1 \quad \text{subject to} \quad \mathbf{c}^T \mathbf{d}_i = 1 \:.
\label{eq:el1_innov}
\end{eqnarray}
If $\mathbf{C}^{*} \in \mathbb{R}^{M_1 \times M_2}$ contains all the optimal directions, Innovation Pursuit builds the adjacency matrix as $\mathbf{Q} + \mathbf{Q}^T  $ where $\mathbf{Q} = |\mathbf{D}^T \mathbf{C}^{*}|$. In~\cite{rahmani2019outlier2}, it was shown that the optimal directions  can be utilized for outlier detection too. The approach proposed in~\cite{rahmani2019outlier2}, termed iSearch, assigns an Innovation Value to each data point and it distinguishes the outliers as the data points with the higher Innovation Values. The Innovation Value assigned to $\mathbf{d}_i$ is computed as 
$$
\frac{1}{\| \mathbf{D}^T \mathbf{c}_i^{*} \|_1}
$$
where $\mathbf{c}_i^{*}$ is the optimal point of (\ref{eq:el1_innov}).  iSearch needs to run an iterative solver to find the optimal directions. In contrast, the  methods presented in this paper are closed-form and they can be hundreds of time faster. 

\vspace{0.05in}
\noindent
\textbf{Leverage Statistics:}
In regression, Leverage Scores are defined as the diagonal values  of the hat matrix $\mathbf{X}^T (\mathbf{X} \mathbf{X}^T)^{-1} \mathbf{X} $ where $\mathbf{X} \in \mathbb{R}^{m_1 \times m_2}$ is the design matrix~\cite{everitt2002cambridge}. Assuming that the rank of $\mathbf{X}$ is equal to $m_1$, then the $i^{\text{th}}$ leverage score is equal to $\| {\mathbf{v}_x}_i \|_2^2$ where the rows of $\mathbf{V}_x \in \mathbb{R}^{m_1 \times m_2}$ are equal to the right singular vectors of $\mathbf{X}$ and ${\mathbf{v}_x}_i$ is the $i^{\text{th}}$  column of $\mathbf{V}_x$. 
Leverage   has been typically  used  in the regression framework and there are few  works which focused on  using it for the robust PCA problem~\cite{mejia2017pca,naes1989leverage}. For instance,
\cite{mejia2017pca} utilized leverage to reject the  outlying time points in an functional magnetic resonance images (fMRI) run.
However, there is not still an analysis and full understating of Leverage in the robust PCA setting. We show that  Innovation Value introduced in~\cite{rahmani2019outlier2} is equivalent to Leverage Score if a quadratic cost function is used to find the optimal directions. This interesting connection is used to establish several  theoretical guarantees and to design a new robust PCA method. 



\begin{algorithm}
        \caption{Asymmetric Normalized Coherence Pursuit (ANCP) for Robust PCA }
{
\textbf{Input.} The inputs are the data matrix $\mathbf{D} \in \mathbb{R}^{M_1 \times M_2}$ and $r$ which is the dimension of the recovered subspace.

\smallbreak
\textbf{1.} Normalize the $\ell_2$-norm of the columns of $\mathbf{D}$, i.e., set $\mathbf{d}_i$ equal to $\mathbf{d}_i / \| \mathbf{d}_i \|_2$ for all $1 \le i \le M_2$.

\smallbreak
\textbf{2.} Rows of $\mathbf{V} \in \mathbb{R}^{r_d \times M_2  }$ are equal to the first $r_d$ right singular vectors of $\mathbf{D}$ where $r_d$ is the rank of $\mathbf{D}$.

\smallbreak
\textbf{3.} Define $\mathbf{x} \in \mathbb{R}^{M_2}$,  vector of Normalized Coherence Values, as  
\begin{eqnarray}
\mathbf{x}(i) = \frac{1}{\| \mathbf{v}_i \|_2^2} \: . 
\label{eq:ANCP}
\end{eqnarray}

\smallbreak
\textbf{4. } Construct matrix $\mathbf{Y}$ from the
columns of $\mathbf{D}$ corresponding to the largest elements of $\mathbf{x}$ such that they span an r-dimensional subspace.

\smallbreak
\textbf{ Output:} The column-space of $\mathbf{Y}$ is the identified subspace.
 }
\end{algorithm}

\section{Robust PCA with Leverage and Innovation Search}
\label{sec:proposed}
The table of Algorithm 1 and the table of Algorithm 2 show the presented methods along with the used definitions. Algorithm 1  utilizes Leverage Scores  to rank the data points and the data points with the minimum Leverage Scores are used to build a basis for $\mathcal{U}$. 
In this section, we show the underlying connection between Algorithm 1 and iSearch  and 
the motivation for naming Algorithm 1 ``Asymmetric Normalized Coherence Pursuit'' is explained.
In addition, we explain the motivations behind the design of Algorithm 2 based on the connection between Algorithm 1 and iSearch.  
Both algorithms are closed-form and they are  faster than most of the existing methods. The computation complexity of ANCP is $\mathcal{O}( r_d M_1 M_2)$  and the computation complexity of SNCP is $\mathcal{O}( r_d M_1 M_2 + r_d M_2^2)$. 



The presented robust PCA algorithms use the data points corresponding to the largest  Normalized Coherence Values   to form the basis matrix $\mathbf{Y}$. If the inliers are distributed uniformly at random in $\mathcal{U}$, then $r$ data points corresponding to the $r$ largest Normalized Coherence Values span $\mathcal{U}$ with high probability. 
However, in real data, the inliers form some clustering structure and the algorithm should continue adding new columns to $\mathbf{Y}$ until the columns of  $\mathbf{Y}$ span an $r$-dimensional subspace. It means that we need to check the singular values of $\mathbf{Y}$  multiple times. Two techniques can be utilized to  \textcolor{black}{avoid these extra steps}~\cite{rahmani2019outlier2,rahmani2017coherence22f}. The first approach is based on leveraging side information that we mostly have about the population of the outliers.  In most of the applications, we can have an upper-bound on $n_o/M_2$ because outliers are mostly associated with rare events. If we know that the number of outliers is less than $y$ $\%$ of the data,  matrix $\mathbf{Y}$ can be constructed using $(1 - y)$ $\%$ of the data columns which are corresponding to the largest Normalized Coherence Values. The second technique is to use the adaptive column sampling method proposed in~\cite{rahmani2017coherence22f} which uses subspace projection to avoid sampling redundant columns.



\begin{algorithm}
        \caption{Symmetric Normalized Coherence Pursuit (SNCP) for Robust PCA}

\textbf{Input.} The inputs are the data matrix $\mathbf{D} \in \mathbb{R}^{M_1 \times M_2}$ and $r$ which is the dimension of the recovered subspace.

\smallbreak
\textbf{1.}   Similar to Step 1 in Algorithm 1.

\smallbreak
\textbf{2.} Define $\mathbf{V} \in \mathbb{R}^{r_d \times M_2  }$ as in Algorithm 1.

\smallbreak
\textbf{3.} The vector of Normalized Coherence Values is defined as
$$\mathbf{x}(i) = \sum_{j=1}^{M_2} \frac{({\mathbf{v}_i}^T \mathbf{v}_{j})^2}{ \|\mathbf{v}_i\|_2^2 \|\mathbf{v}_j\|_2^2 }\:.$$

\smallbreak
\textbf{4. } Construct matrix $\mathbf{Y}$ as in Algorithm 1. 

\smallbreak
\textbf{ Output:} The column-space of $\mathbf{Y}$ is the identified subspace.
 }
\end{algorithm}



\subsection{Explaining Leverage Score for Robust PCA Using Innovation Search}\label{sec:expl}

Algorithm 1 ranks the data points based on the inverse of their leverage scores. The following lemma shows that Leverage Score is directly related to Innovation Value. 
\begin{lemma}
Suppose rows of $\mathbf{V} \in \mathbb{R}^{r_d \times M_2  }$ are equal to the first $r_d$ right singular vectors of $\mathbf{D}$ where $r_d$ is the rank of $\mathbf{D}$. Define $\mathbf{c}_i^{*}$ as the optimal point of 
\begin{eqnarray}
\underset{ \mathbf{c}}{\min} \: \:  \| \mathbf{c}^T \mathbf{D} \|_2 \quad \text{subject to} \quad \mathbf{c}^T \mathbf{d}_i = 1  \:.
\label{eq:el_2_inno}
\end{eqnarray}
Then,
$
\| \mathbf{D}^T \mathbf{c}_i^{*} \|_2^2 = \frac{1}{\| \mathbf{v}_i \|_2^2} \:.
$

\label{lem:equi}
\end{lemma}
\noindent
Lemma~\ref{lem:equi} indicates that if a quadratic cost function  is used to compute the optimal directions in iSearch, Innovation Values are equivalent to Leverage Scores. Accordingly, we can use the idea of Innovation Search to explain the Leverage Score based robust PCA method. 
First suppose that  $\mathbf{d}_i$ is an outlier which means that $\mathbf{d}_i$ has a non-zero projection on $\mathcal{U}^{\perp}$. Since most of the data points are inliers, the optimization problem utilizes the projection of $\mathbf{d}$ in $\mathcal{U}^{\perp}$ and finds the optimal direction near $\mathcal{U}^{\perp}$ to minimize $\| \mathbf{A}^T \mathbf{c}_i\|_2^2$.
In sharp contrast, when $\mathbf{d}_i$ is an inlier, the linear constraint strongly discourages the optimal direction to be close to $\mathcal{U}^{\perp}$. Thus, $\| \mathbf{A}^T \mathbf{c}_i^{*}\|_2^2$ is notably larger when $\mathbf{d}_i$ is an inlier comparing to $\| \mathbf{A}^T \mathbf{c}_i^{*}\|_2$  when $\mathbf{d}_i$ is an outlier.
Accordingly, since $\frac{1}{\| \mathbf{v}_i \|_2^2} = \| \mathbf{D}^T \mathbf{c}_i^{*}\|_2^2 = \|\mathbf{A}^T \mathbf{c}_i^{*} \|_2^2 + \|\mathbf{B}^T \mathbf{c}_i^{*} \|_2^2$, $1/\| \mathbf{v}_i \|_2^2$
is much larger when $\mathbf{d}_i$ is an inlier comparing to the same value when $\mathbf{d}_i$ is an outlier because $\|\mathbf{A}^T \mathbf{c}_i^* \|_2^2$ is much larger when $\mathbf{d}_i$ is an inlier. 

The following Lemma indicates that $\| \mathbf{D}^T \mathbf{c}_i^{*} \|_2^2$ can be written as the sum of the similarities between the columns of $\mathbf{V} \in \mathbb{R}^{r_d \times M_2}$. 
\begin{lemma}
Define $\mathbf{c}_i^{*}$ and $\mathbf{V}$ as in Lemma~\ref{lem:equi}. Then,
\begin{eqnarray}
\| \mathbf{D}^T \mathbf{c}_i^{*} \|_2^2 = \sum_{j=1}^{M_2} \left(\frac{ \mathbf{v}_i^T \mathbf{v}_j }{ \|\mathbf{v}_i\|_2 \|\mathbf{v}_i\|_2 }\right)^2 \:. 
\label{eq:sum_asymmm}
\end{eqnarray}
\label{lm:secondlm} 
\end{lemma}
Thus,  Algorithm 1 is inherently similar to  CoP  but Algorithm 1 utilizes the coherency between the columns of  $\mathbf{V}$. In other word, the functionality of Algorithm 1 is similar to that of a CoP algorithm which is applied to a data matrix whose non-zero singular values are normalized to 1.   This is the motivation  to name the  presented algorithms Normalized Coherence~Pursuit.

\subsection{Symmetric Normalized Coherence Pursuit}
The measure of similarity used in (\ref{eq:sum_asymmm}) is not symmetric. In other word, the similarity between $\mathbf{d}_i$ and $\mathbf{d}_j$ which is computed as $\left(\frac{ \mathbf{v}_i^T \mathbf{v}_j }{ \|\mathbf{v}_i\|_2 \|\mathbf{v}_i\|_2 }\right)^2 $ is not equal to the similarity between $\mathbf{d}_j$ and $\mathbf{d}_i$ which can be written as $\left(\frac{ \mathbf{v}_i^T \mathbf{v}_j }{ \|\mathbf{v}_j\|_2 \|\mathbf{v}_j\|_2 }\right)^2$. Accordingly, we modify the measure of similarity used in (\ref{eq:sum_asymmm}) into a symmetric measure of similarity. The Normalized Coherence Value corresponding to $\mathbf{d}_i$ using the symmetric measure of similarity is defined as 
$
\mathbf{x}(i) = \sum_{j=1}^{M_2} \left(\frac{ \mathbf{v}_i^T \mathbf{v}_j }{ \|\mathbf{v}_i\|_2 \|\mathbf{v}_j\|_2 }\right)^2 \:. 
$
Algorithm 2 uses the symmetric measure of similarity to compute the Normalized Coherence Values. The numerical experiments show that utilizing the symmetric function can notably improve the performance in most of the cases. 







\begin{comment}

\begin{figure}[h!]
\begin{center}
\mbox{\hspace{-0.15in}
\includegraphics[width=1.55in]{figs/noise_values.eps}\hspace{-0.15in}
\includegraphics[width=1.55in]{figs/noise_values2.eps}
}
\end{center}
\vspace{-0.15in}
           \caption{ In both plots, $n_i=100$, $n_o=500$, $r= 4$, $M_1 = 50$,   the last 100 columns are the inliers, and the outliers are sampled uniformly at random from $\mathbb{S}^{M_1-1}$. In the left plot the data is not noisy and in the right plot $\mathbf{D} = [\mathbf{B} \:\:(\mathbf{A} + \mathbf{E})]$ where $\mathbf{E}$ represents the presence of noise and $\text{SNR} = \frac{\|\mathbf{A}\|_F^2}{\| \mathbf{E} \|_F^2} = 4$.
           }
           \label{fig:example_noise}
\end{figure}

\end{comment}


\section{Theoretical Studies}
In this section, we present analytical performance guarantees for Normalize Coherence Pursuit under different models for the distribution of the outliers.  
The connection between Innovation Values and Leverage Scores is utilized to analyze the ANCP method and we leave the analysis of SNCP to future works. In the following subsections, the performance guarantees  with unstructured outliers, linearly dependant outliers, noisy inliers, and clustered outliers is provided. Moreover, in contrast to most of the previous methods whose guarantees are limited to randomly distributed inliers, Normalized Coherence Pursuit  is supported with theoretical guarantees even when the inliers are clustered. 
The following sections provide the theoretical results and each theorem is followed by a short  discussion
which highlights the important aspects of that theorem.





To simplify the exposition and notation, in the presented results,  it is assumed without loss of generality that $\mathbf{T}$  is equal to the identity matrix, i.e, $\mathbf{D} = [\mathbf{B} \hspace{.2cm} \mathbf{A}]$.
The subspace $\mathcal{U}$ is recovered using the span of the data points with the largest Normalized Coherence Values. A sufficient condition which guarantees exact recovery of $\mathcal{U}$ is that the minimum of the Normalized Coherence Values corresponding to the inliers is larger than the maximum of the Normalized Coherence Values corresponding to the outliers, i.e., 
\begin{eqnarray}
\begin{aligned}
&\min \left(  \{  \mathbf{x}(i) \}_{i=n_o+1}^{M_2}  \right) >  \max \left(  \{ \mathbf{x}(i) \}_{i=1}^{n_o}  \right) \:. 
\end{aligned}
\label{cond:main_cond}
\end{eqnarray}
\noindent
This
is not a necessary condition but it is easier to guarantee. 
In addition, we define $$\psi =  \max  \left( \left\{ \frac{1}{\| \mathbf{b}_i^T \mathbf{R}\|_2^2}  \right\}_{i=1}^{n_o} \right)$$ where $\mathbf{R}$ is an orthonormal basis for $\mathcal{U}^{\perp}$ and $\mathbf{b}_i$ is the $i^{\text{th}}$ column of $\mathbf{B}$. The parameter $\psi$ indicates how close the outliers are to $\mathcal{U}$.


\vspace{0.05in}
\noindent
\textbf{Proof Strategy:} Although the presented theorems consider different scenarios for the distribution of the inliers/outliers and different techniques are required to guarantee (\ref{cond:main_cond}) in each case, but a similar strategy is used in the proofs of all the results.  In contrast to Cop which analyzed $\{ |\mathbf{d}_i^T \mathbf{d}_j|\}_{i,j}$ based on the distribution of the data, it is not straightforward to directly bound $\{ |\mathbf{v}_i^T \mathbf{v}_j|\}_{i,j}$. In addition, in contrast to iSearch which leveraged the fact that the optimal direction of (\ref{eq:el1_innov}) is mostly orthogonal to $\mathcal{U}$ when $\mathbf{d}_i$ is an outlier, the optimal direction obtained by (\ref{eq:el_2_inno}) is not necessarily orthogonal to $\mathcal{U}$ when $\mathbf{d}_i$ is an outlier. In the proofs of the presented results, we utilized the geometry of the problem in which the optimal direction of (\ref{eq:el_2_inno}) is not  close to $\mathcal{U}$ when $\mathbf{d}_i$ is an outlier. Specifically, corresponding to outlier $\mathbf{d}_i$, we define $\mathbf{d}_i^{\perp} = \frac{\mathbf{R} \mathbf{R}^T \mathbf{d}_i}{\| \mathbf{d}_i^T \mathbf{R} \|_2^2}$ and by definition $\mathbf{d}_i^T \mathbf{d}_i^{\perp} = 1$. According to the definition of $\mathbf{c}_i^{*}$ as the optimal point of (\ref{eq:el_2_inno}) and according to Lemma~\ref{lem:equi}, $\frac{1}{\| \mathbf{v}_i \|_2^2} \le \| \mathbf{D}^T \mathbf{d}_i^{\perp} \|_2^2 $. We utilized this inequality  to derive the sufficient conditions which prove that (\ref{cond:main_cond}) holds with high probability. The detailed proofs of all the results are provided in the appendix. 


\subsection{Outliers Distributed on $\mathbb{S}^{M_1 -1}$}
\label{sec:uns}
In most of the previous works on the robust PCA problem, the performance of the outlier detection method is analyzed under the assumption that the outliers are randomly distributed on $\mathbb{S}^{M_1 - 1}$. This is a simple scenario because the outliers are unstructured and the projection of each outlier on $\mathcal{U}$ is not strong with high probability given that $r$ is sufficiently small because when the outliers are randomly distributed as in Assumption \ref{assum_DistUni}, then $\mathbb{E} [\| \mathbf{U}^T \mathbf{b} \|_2^2] = \frac{r}{M}$ ( $\mathbf{b}$ is an outlying data point). The following assumption specifies the presumed model for the distribution of the inliers/outliers. 

\begin{assumption}

The columns of $\mathbf{A}$ are drawn  uniformly at random from $\mathcal{U} \cap \mathbb{S}^{M_1 -1}$ and the columns of $\mathbf{B}$ are drawn  uniformly at random from $\mathbb{S}^{M_1 - 1}$. 
\label{assum_DistUni}
\end{assumption}

The following theorem provides the sufficient conditions to guarantee the exact recovery of $\mathcal{U}$.


\begin{theorem}
\label{theo:randomrandom}
Suppose $\mathbf{D}$ follows Assumption 1.  If $\mathbf{x}$ is defined as in  (\ref{eq:ANCP}) and
\begin{eqnarray} 
\begin{aligned}
& \frac{n_i}{r} - \max \left( \frac{4}{3} \log \frac{2r}{\delta} , \sqrt{4 \frac{n_i}{r} \log \frac{2 r}{\delta}} \right) > \frac{(\psi - 1)n_o}{M_1} + \\
& \quad \max \left( \frac{8}{3} \log \frac{2M_1}{\delta} , \sqrt{16 \frac{n_o}{M_1} \log \frac{2 M_1}{\delta}} \right) \:,
\end{aligned}
\label{eq:suff_1}
\end{eqnarray}
then (\ref{cond:main_cond}) holds and   $\mathcal{U}$ is recovered exactly with probability at least $1 - 3 \delta$.
\label{theo:random}
\end{theorem}

Since the outliers are randomly distributed, the expected value of $\| \mathbf{b}_i^T \mathbf{R} \|_2^2$ is equal to $\frac{M_1- r}{M_1}$  which is nearly equal to~1 when $r/M_1$ is small~\cite{rahmani2017coherence,park2014greedy}.
Thus, Theorem~\ref{theo:random} roughly indicates that if ${n_i}/{r}$ is sufficiently larger than $n_o/M_1$, Normalized Coherence Values can successfully distinguish the outliers. It is important to note that $n_i$ is scaled with $r$ while $n_o$ is scaled with $M_1$. It means that if $r$ is sufficiently small and if the outliers are unstructured,   $\mathcal{U}$ can be recovered exactly even if $n_o$ is much larger than $n_i$. 
In addition, one can observe that when the outliers are unstructured, the requirements of Normalized Coherence Pursuit are similar with those of CoP~\cite{rahmani2017coherence}.  In the next subsection, we observe a clear difference between their requirements when the outliers are close to $\mathcal{U}$.


\subsection{Outliers in an Outlying Subspace}
\label{sec:outlier_sub}
Although Assumption~\ref{assum_DistUni} is a popular data model in the literature of robust PCA, it is not a realistic assumption in the practical scenarios. In practice, outliers can be structured and  they are not completely independent from each other as it is assumed in Assumption~\ref{assum_DistUni}.  
For instance, in anomaly event detection, the outlying video frames are highly correlated or in misclassified data points identification, they can belong to the same cluster~\cite{gitlin2018improving}. In this section, we study the robustness against linearly dependant outliers. The following assumption specifies the presumed model for the outliers. 


\begin{assumption}
Define
subspace $\mathcal{U}_o$ with dimension $r_o$ such that $\mathcal{U}_o \notin \mathcal{U}$ and $\mathcal{U} \notin \mathcal{U}_o$.
The columns of $\mathbf{A}$ are randomly distributed on  $\mathcal{U} \cap \mathbb{S}^{M_1 -1}$  and the columns of  $\mathbf{B}$ are randomly distributed on   $\mathcal{U}_o \cap \mathbb{S}^{M_1 - 1} $
\label{asm:out}
\end{assumption}
The following theorem provides the sufficient condition to guarantee that (\ref{cond:main_cond}) holds. 
\begin{theorem}
\label{theo:Linearly_dependant}
Suppose  $\mathbf{D}$ follows Assumption~\ref{asm:out}.  If $\mathbf{x}$ is defined as in (\ref{eq:ANCP}) and
\begin{eqnarray*}
\begin{aligned}
&\frac{n_i}{r} - \max \left( \frac{4}{3} \log \frac{2r}{\delta} , \sqrt{4 \frac{n_i}{r} \log \frac{2 r}{\delta}} \right) >   \\
& \| \mathbf{U}_{o}^T \mathbf{U}^{\perp} \|\left( \frac{\psi n_o}{r_o} + \psi \max \left( \frac{4}{3} \log  \frac{2r_o}{\delta} , \sqrt{\frac{n_o}{r_o} \log \frac{2 r_o}{\delta}} \right)\right)
\end{aligned}
\end{eqnarray*}
then (\ref{cond:main_cond}) is satisfied  and $\mathcal{U}$ is recovered exactly with probability at least $1 - 2 \delta$.
\end{theorem}

Theorem~\ref{theo:Linearly_dependant} roughly states that if $n_i/r$ is sufficiently larger than $n_o/r_o$, the exact recovery is guaranteed with high probability. If $r_o$ is comparable to $r$, then the number of inliers should be sufficiently larger than the number of outliers. This confirms our intuition about the outliers because if $r_o$ is comparable to $r$  and $n_o$ is also large, we cannot label the columns of $\mathbf{B}$ as outliers. 
It is informative to compare the requirements of  Normalized Coherence Pursuit with that of CoP. The following theorem provides the sufficient conditions to guarantee that  CoP successfully distinguishes the outliers. 
\begin{theorem}
\label{theo:Linearly_dependant_CP}
Suppose $\mathbf{D}$ follows  Assumption~\ref{asm:out}. If 
\begin{eqnarray*}
\begin{aligned}
& \frac{n_i}{r} - \max \left( \frac{4}{3} \log \frac{2r}{\delta} , \sqrt{4 \frac{n_i}{r} \log \frac{2 r}{\delta}} \right) > \\
 & \|\mathbf{U}^T \mathbf{U}_o \|^2 \left( \frac{n_i}{r} + \max \left( \frac{4}{3} \log \frac{2r}{\delta} , \sqrt{4 \frac{n_i}{r} \log \frac{2 r}{\delta}} \right) \right) + \\
 & \frac{n_o}{r_o} + \max \left( \frac{4}{3} \log \frac{2r_o}{\delta} , \sqrt{4 \frac{n_o}{r_o} \log \frac{2 r_o}{\delta}} \right) \: ,
\end{aligned}
\label{eq:cop_reqq}
\end{eqnarray*}
then the CoP method proposed in~\cite{rahmani2017coherence} recovers $\mathcal{U}$ exactly with probability at least $1- 3\delta$.

\end{theorem}

One can observe that the requirement  of Theorem~\ref{theo:Linearly_dependant_CP} is much stronger than that of Theorem~\ref{theo:Linearly_dependant} because $n_i/r$ appears on the right hand side of the sufficient condition of Theorem~\ref{theo:Linearly_dependant_CP}.
 Theorem~\ref{theo:Linearly_dependant_CP} predicts that when $\mathcal{U}_o$ is close $\mathcal{U}$, the CoP Algorithm is more likely to fail. This is a correct prediction because when $\mathcal{U}$ and $\mathcal{U}_o$ are close, the inliers and the outliers are close to each other and their inner-product values are large. 
 In addition, by comparing the sufficient conditions of Normalized Coherence Pursuit with that of iSearch~\cite{rahmani2019outlier2} with linearly dependant outliers, we can observe that the nature of the sufficient conditions are similar. In the presented experiments, it is shown that Normalized Coherence Pursuit is on a par with iSearch in identifying outliers with weak innovation while it is a closed-from algorithm and its running time is much faster. 



















\begin{comment}
\subsection{Clustered Outliers}
In this section, we consider a different structure for the outliers. It is assumed that the outliers form a cluster outside  the span of the inliers. Structured outliers are mostly associated with important rare events  such as malignant tissues~\cite{karrila2011comparison} or web attacks~\cite{kruegel2003anomaly}. The following assumption specifies the presumed model for $\mathbf{B}$.



\begin{assumption}
Each column of $\mathbf{B}$ is formed as $\mathbf{b}_i = \frac{1}{\sqrt{1 + \eta^2}} ( \mathbf{q} + \eta \mathbf{f}_i)$. The unit $\ell_2$-norm vector $\mathbf{q}$ does not lie in $\mathcal{U}$, $\{\mathbf{f}_i \}_{i=1}^{n_o}$ are drawn uniformly at
random from $\mathbb{S}^{M_1 - 1}$, and $\eta$ is a positive number.
\label{asm:clus}
\end{assumption}

\noindent
In Assumption~\ref{asm:clus}, the outliers form a cluster around vector $\mathbf{q}$ which does not lie in $\mathcal{U}$ and $\eta$ determines how close they are to each other. The following theorem provides the sufficient conditions to guarantee that Normalized Coherence Values distinguish the cluster of  outliers. 

\begin{theorem}
\label{theo:clustered_outliers}
Suppose that the distribution of  inliers/outliers follows Assumption-\ref{assum_DistUni}/Assumption-\ref{asm:clus}. If If $\mathbf{x}$ is defined as  in (\ref{eq:ANCP}) and
$\frac{n_i}{r} - \max \left( \frac{4}{3} \log \frac{2r}{\delta} , \sqrt{4 \frac{n_i}{r} \log \frac{2 r}{\delta}} \right) > n_o \frac{\psi  \| \mathbf{q}^T \mathbf{U}^{\perp} \|_2^2}{1 + \eta^2} +  \frac{\psi \eta^2  n_o}{(1 + \eta^2 )M_1} + \frac{\eta^2  \psi}{1 + \eta^2} \max \left( \frac{4}{3} \log \frac{2M_1}{\delta} , \sqrt{\frac{n_o}{M_1} \log \frac{2 M_1}{\delta}} \right) + \frac{ \eta \sqrt{\psi}}{1+ \eta^2} \| \mathbf{q}^T \mathbf{U}^{\perp} \|_2 \left( \frac{n_o}{\sqrt{M_1}} + 2\sqrt{n_o} + \sqrt{\frac{2 n_o \log \frac{1}{\delta}}{M_1 -1 }} \right) \:,
$
then (\ref{cond:main_cond}) is satisfied and   $\mathcal{U}$ is recovered exactly with probability at least $1 - 4 \delta$.
\end{theorem}

In sharp contrast to Theorem~\ref{theo:randomrandom},  $n_o$ is not scaled with $M_1$. This means that when $\eta$ is small (the outliers are close to each other), $n_i/r$ should be sufficiently larger than $n_o$.  When  $\eta$ goes to infinity, the distribution of  outliers converges to the distribution of outliers  in Assumption~\ref{assum_DistUni} and one can observe that the sufficient condition in Theorem~\ref{theo:clustered_outliers} converges to the sufficient condition in Theorem~\ref{theo:randomrandom}.
\end{comment}




















\subsection{Noisy Inliers}
\label{sec:nooooise}
Although exact recovery of $\mathcal{U}$ is not feasible when the inliers are noisy but the Normalized Coherence Values can distinguish the outliers even in the strong presence of noise. 
In this section , we present a theorem which guarantees that (\ref{cond:main_cond}) holds with high probability if $n_i/r$ and Signal to Noise Ratio (SNR) are sufficiently large. The following assumption specifies the presumed model.

\begin{assumption}
The matrix $\mathbf{D}$ can be expressed as
$$
\mathbf{D} =  [\mathbf{B} \hspace{.2cm} \frac{1}{\sqrt{1+\sigma_n^2}}(\mathbf{A}+\mathbf{E})] \: \mathbf{T} \:.
$$
The matrix $\mathbf{E} \in \mathbb{R}^{M_1 \times n_i}$ represents the presence of noise and it can be written as $\mathbf{E} = \sigma_n \mathbf{N}$ where the columns of $\mathbf{N} \in \mathbb{R}^{M_1 \times n_i}$  are drawn  uniformly at random from $\mathbb{S}^{M_1 - 1}$ and $\sigma_n$ is a positive number which controls the power of the added noise.
\label{asm:noiss}
\end{assumption}

Before we state the theorem, let us define vectors $\{ \mathbf{t}_i \}_{i=1}^{M_2}$ where $\mathbf{t}_i = \Sigma \mathbf{v}_i$ and the diagonal matrix $\Sigma$ contains the non-zero singular values of $\mathbf{D}$. Note that $\mathbf{d}_i = \mathbf{U}^{'} \mathbf{t}_i$ and $\| \mathbf{t}_i \|_2 = \| \mathbf{d}_i \|_2$.
In addition,  define 
$
 t_{\min} = \min_i \left( \left\{ \frac{\| \Sigma^{-2} \mathbf{t}_i \|_2}{\mathbf{t}_i^T \Sigma^{-2} \mathbf{t}_i}  \right\}_{i=n_o + 1}^{M_2} \right)$  and $ t_{\max} = \max_i \left( \left\{ \frac{\| \Sigma^{-2} \mathbf{t}_i \|_2}{\mathbf{t}_i^T \Sigma^{-2} \mathbf{t}_i}  \right\}_{i=n_o + 1}^{M_2} \right) \:.
$
 



\begin{theorem}
\label{theo:noise}
Suppose $\mathbf{A}$ and $\mathbf{B}$ follow Assumption~\ref{assum_DistUni} and  $\mathbf{D}$ is formed according to Assumption~\ref{asm:noiss}.
If  $\mathbf{x}$ is defined as in  (\ref{eq:ANCP}) and
\begin{eqnarray*} 
\begin{aligned}
& \frac{(\sqrt{1 + \sigma_n^2}  - t_{\max} \sigma_n)^2}{1 + \sigma_n^2} \\
&  \Bigg( \frac{n_i}{r} -  \max \left( \frac{4}{3} \log \frac{2r}{\delta} , \sqrt{4 \frac{n_i}{r} \log \frac{2 r}{\delta}} \right) \Bigg) >  2 \sigma_n n_i t_{\max}^2 +   \\
& \psi \left( \frac{n_o}{M_1} + \max \left( \frac{4}{3} \log \frac{2 M_1}{\delta} , \sqrt{4 \frac{n_o}{M_1} \log \frac{2 M_1}{\delta}}  \right) \right) + \\
& \frac{\sigma_n^2 \psi}{1+\sigma_n^2 } \Bigg( \frac{n_i}{M_1} +  \max \left( \frac{4}{3} \log \frac{2 M_1}{\delta} , \sqrt{4 \frac{n_i}{M_1} \log \frac{2 M_1}{\delta}} \right) \Bigg)
\end{aligned}
 \end{eqnarray*} 
then (\ref{cond:main_cond}) holds  with probability at least $1 - 3 \delta$.
\end{theorem}


In this section, we considered the unstructured outliers whose number can be much larger than $M_1$ and $n_i$. Consider the challenging scenario that the unstructured outliers dominate the data, thus the values of all the singular values are close to each other which indicates that the values of $t_{\min}$ and $t_{\max}$ are close to one. Thus, the sufficient condition of Theorem~\ref{theo:noise}  roughly states that $\frac{(1- \sigma_n)^2}{1+ \sigma_n^2} \frac{n_i}{r}$ should be sufficiently larger than $n_i \sigma_n + \frac{n_o}{M_1}$. In practise, the algorithm works  better than what the sufficient condition implies
because  the proof is based on considering  the worst case scenarios.  
















\begin{comment}
\vspace{-0.1in}
\begin{figure}[h!]
\begin{center}
\mbox{
\includegraphics[width=0.5\textwidth]{figs/phase.eps}
}
\end{center}
\vspace{-0.15in}
           \caption{The  phase transitions in presence of the unstructured outliers versus $n_i$ and $n_o$. White indicates correct
subspace recovery and black designates incorrect recovery. In this experiment, the data follows Assumption~\ref{assum_DistUni} with $M_1=50$ and $r=4$. }
\label{fig:phase}

\end{figure}
\end{comment}














\subsection{Clustered Outliers}
In this section, we consider a different structure for the outliers. It is assumed that the outliers form a cluster outside of the span of the inliers. Structured outliers are mostly associated with important rare events  such as malignant tissues~\cite{karrila2011comparison} or web attacks~\cite{kruegel2003anomaly}. The following assumption specifies the presumed model for $\mathbf{B}$.



\begin{assumption}
Each column of $\mathbf{B}$ is formed as $\mathbf{b}_i = \frac{1}{\sqrt{1 + \eta^2}} ( \mathbf{q} + \eta \mathbf{f}_i)$. The unit $\ell_2$-norm vector $\mathbf{q}$ does not lie in $\mathcal{U}$, $\{\mathbf{f}_i \}_{i=1}^{n_o}$ are drawn uniformly at
random from $\mathbb{S}^{M_1 - 1}$, and $\eta$ is a positive number.
\label{asm:clus}
\end{assumption}

\noindent
In Assumption~\ref{asm:clus}, the outliers form a cluster around vector $\mathbf{q}$ which does not lie in $\mathcal{U}$ and $\eta$ determines how close they are to each other. The following theorem provides the sufficient conditions to guarantee that Normalized Coherence Values distinguish the cluster of  outliers. 

\begin{theorem}
\label{theo:clustered_outliers}
Suppose that the distribution of  inliers follows Assumption ~\ref{assum_DistUni} and  the distribution of  outliers follows Assumption~\ref{asm:clus}. If $\mathbf{x}$ is defined as  in (\ref{eq:ANCP}) and
\begin{eqnarray*} 
\begin{aligned}
& \frac{n_i}{r} - \max \left( \frac{4}{3} \log \frac{2r}{\delta} , \sqrt{4 \frac{n_i}{r} \log \frac{2 r}{\delta}} \right) > 
n_o \frac{\psi  \| \mathbf{q}^T \mathbf{U}^{\perp} \|_2^2}{1 + \eta^2} +  \\
& \frac{\psi \eta^2  n_o}{(1 + \eta^2 )M_1} +  \frac{\eta^2  \psi}{1 + \eta^2} \max \left( \frac{4}{3} \log \frac{2M_1}{\delta} , \sqrt{\frac{n_o}{M_1} \log \frac{2 M_1}{\delta}} \right) + \\
&\frac{ \eta \sqrt{\psi}}{1+ \eta^2} \| \mathbf{q}^T \mathbf{U}^{\perp} \|_2 \left( \frac{n_o}{\sqrt{M_1}} + 2\sqrt{n_o} + \sqrt{\frac{2 n_o \log \frac{1}{\delta}}{M_1 -1 }} \right) \:,
\end{aligned}
\end{eqnarray*} 
then (\ref{cond:main_cond}) is satisfied and   $\mathcal{U}$ is recovered exactly with probability at least $1 - 4 \delta$.
\end{theorem}

In sharp contrast to Theorem~\ref{theo:randomrandom},  $n_o$ is not scaled with $M_1$. This means that when $\eta$ is small (the outliers are close to each other), $n_i/r$ should be sufficiently larger than $n_o$.  When  $\eta$ goes to infinity, the distribution of  outliers converges to the distribution of outliers  in Assumption~\ref{assum_DistUni} and one can observe that the sufficient condition in Theorem~\ref{theo:clustered_outliers} converges to the sufficient condition in Theorem~\ref{theo:randomrandom}.

\subsection{Outlier Detection in a Union of Subspaces}
In practice, the inliers are not randomly distributed in a subspace and they mostly form some structures. In this section, we assume that the inliers are clustered. It is assumed that the columns of $\mathbf{A}$ form $m$ clusters and the data points in each cluster span a $d$-dimensional subspace. The following assumption provides the details. 
 
\begin{assumption}
The matrix of inliers can be written as $\mathbf{A} = [\mathbf{A}_1 \: ... \: \mathbf{A}_m] \mathbf{T}_A$ where $\mathbf{A}_k \in \mathbb{R}^{M_1 \times {n_i}_k}$, $\sum_{k=1}^{m}  {n_i}_k = n_i$, and $\mathbf{T}_A$ is an arbitrary permutation matrix.
The columns of $\mathbf{A}_k$  are drawn uniformly at random from the
intersection of  subspace $\mathcal{U}_k$ and $\mathbb{S}^{M_1-1}$ where $\mathcal{U}_k$ is a $d$-dimensional subspace. In other word, the columns of $\mathbf{A}$ lie in a union of subspaces $\{ \mathcal{U}_k \}_{k=1}^m$ and $\left(\mathcal{U}_1 \oplus \: ... \oplus \mathcal{U}_m \right)= \mathcal{U}$ where $\oplus$ denotes the direct sum operator.
\label{asm:union_of_sunb}
\end{assumption}

\noindent
The following theorem provides the sufficient conditions to guarantee that the computed Normalized Coherence Values satisfy (\ref{cond:main_cond}) with high probability.

\begin{theorem}
\label{theo:Linearly_dependant_inliers}
Suppose that the distribution of the inliers follows Assumption~\ref{asm:union_of_sunb} and the distribution of outliers follows Assumption~\ref{assum_DistUni}. If  $\mathbf{x}$ is defined as in  (\ref{eq:ANCP}) and
\begin{eqnarray*}
\begin{aligned}
\vartheta \mathcal{A} >  (\psi - 1)\frac{n_o}{M_1} +  2 \max \left( \frac{4}{3} \log \frac{2M_1}{\delta} , \sqrt{4 \frac{n_o}{M_1} \log \frac{2 M_1}{\delta}} \right)
\end{aligned}
\end{eqnarray*} 
where $ \vartheta = \underset{\mathbf{a} \in \mathcal{U}  \atop \| \mathbf{a} \| = 1}{\inf} \sum_{k=1}^{m} \| \mathbf{a}^T \mathbf{U}_k \|_2^2$ and
$
 \mathcal{A} = \min_i \Bigg\{ \frac{ {n_i}_k }{d} - \max \left( \frac{4}{3} \log \frac{2 m d}{\delta} , \sqrt{4 \frac{{n_i}_k}{d} \log \frac{2 m d}{\delta}} \right)  \Bigg\}_{i=1}^m, 
$
then (\ref{cond:main_cond}) is satisfied and  $\mathcal{U}$ is recovered exactly with probability at least $1 - 3 \delta$.
\end{theorem}

Theorem~\ref{theo:Linearly_dependant_inliers} reveals an interesting property of the Normalized Coherence Values. 
According to the definition of $\mathcal{A}$, $\mathcal{A}$ is roughly equal to ${\min \{{n_i}_k \}_{k=1}^m}/{d}$. 
Thus, Theorem~\ref{theo:Linearly_dependant_inliers} states that when the inliers are clustered, the population of the cluster with the minimum population is the key factor. 
This property matches with our intuition about outlier detection because if there is a cluster with few number of data points, we could label them as outliers similar to the outliers modeled in Assumption~\ref{asm:out}.
The parameter $\vartheta = \underset{\mathbf{a} \in \mathcal{U}  \atop \| \mathbf{a} \| = 1}{\inf} \sum_{k=1}^{m} \| \mathbf{a}^T \mathbf{U}_k \|_2^2$  shows  how well the inliers are diffused in $\mathcal{U}$. Clearly, if the inliers are present in all or most of the directions inside $\mathcal{U}$,
 a robust PCA algorithm is more likely to recover $\mathcal{U}$ correctly. However, the presented methods do not require the inliers to occupy all the directions in $\mathcal{U}$. The reason that
 $\vartheta$ appeared in the sufficient conditions is that the theorem guarantees  the performance in the worst case scenarios.  





\section{Numerical Experiments}
In this section, SNCP and ANCP are compared with the existing robust PCA approaches, including FMS~\cite{lerman2014fast}, GMS~\cite{zhang2014novel}, CoP~\cite{rahmani2017coherence}, iSearch~\cite{rahmani2019outlier2}, and R1-PCA~\cite{lamport21},
and their robustness against different types of outliers   is examined with both real and synthetic data.

\begin{remark}
In the presented theoretical results, it was assumed that $r_d$ is known. When the data is noisy, one can utilize any rank estimation algorithm and the performance of the algorithms is not sensitive to the chosen rank as long as $r_d$ is sufficiently larger than $r$.  In the presented experiments, we set $r_d$ equal to the number of singular values of $\mathbf{D}$ which are greater than $s_1/20$ where $s_1$ is the first singular value of $\mathbf{D}$.
\end{remark}

\subsection{Comparing Different Scores}
In this experiment, 
we simulate a scenario in which the outliers  are close to $\mathcal{U}$.
Suppose $r=8$, $n_i = 180$, and $n_o = 40$. The outliers are generated as $[\mathbf{U} \:\: \mathbf{H}]\: \mathbf{G}$ where $\mathbf{H} \in \mathbb{R}^{M_1 \times 4}$ spans a random 4-dimensional subspace and the elements of $\mathbf{G} \in \mathbb{R}^{12 \times 20} $ are sampled independently from $\mathcal{N}(0,1)$.  Fig.~\ref{fig:compare_scores} demonstrates  Innovation Values, Coherence Values, and Normalized Coherence Values computed by ANCP and SNCP (the first 40 columns are outliers). In this figure, we show the  inverse of Coherence Values and the inverse of Normalized Coherence Values to make them comparable to Innovation Values. One can  observe that the scores computed by iSearch, ANCP, and SNCP can be reliably used to form a basis for $\mathcal{U}$ but the scores computed by CoP do not distinguish the outliers well enough.
As it was predicted by Theorem~\ref{theo:Linearly_dependant_CP},  CoP  can fail to distinguish the outliers when they are close to $\mathcal{U}$. The main reason is that CoP measures the similarity between the data points via a simple inner-product while iSearch and ANCP  utilize the directions of innovation to measure the similarity between a data point and the rest of  data.   The functionality of SNCP is similar to that of ANCP while it uses a symmetric measure of similarity and the plots show that it distinguishes the outliers in a more clear way. 



\begin{comment}
\vspace{-0.1in}
\subsection{Abundance of Unstructured Outliers}
\vspace{-0.1in}
Theorem~\ref{theo:random} predicted that when the outliers are randomly distributed, the number of outliers can be much larger than the number of inliers provided that $n_i/r$ is sufficiently large. Suppose the data follows Assumption~\ref{assum_DistUni} with $M_1=50$ and $r=4$.
Define $\hat{\mathbf{U}}$ as an orthonormal basis for the recovered subspace. A trial is considered successful if
$
\frac{\| (\mathbf{I} - \mathbf{U} \mathbf{U}^T) \hat{\mathbf{U}} \|_F}{ \|\mathbf{U} \|_F } < 10^{-3} \: .
$
Fig.~\ref{fig:phase} shows the phase transitions 
in which white means correct subspace recover and black  designates  incorrect  recovery (the number of evaluation runs was 20). The phase transitions indicate that  when $n_i/r$ is larger than 5, the  algorithms can successfully recover $\mathcal{U}$ even if $n_o = 2000$. In addition, SNCP shows more robustness against the outliers when $n_i$ is small.
\end{comment}



\begin{figure}[t]
\begin{center}
\mbox{
\includegraphics[width=1.78in]{figs/vs1.eps}\hspace{-0.1in}
\includegraphics[width=1.78in]{figs/vs2.eps}}
\mbox{
\includegraphics[width=1.78in]{figs/vs3.eps}\hspace{-0.1in}
\includegraphics[width=1.78in]{figs/vs4.eps}
}
\end{center}
\vspace{-0.15in}
           \caption{The plots  show the inverse of Normalized Coherence Values computed by SNCP and ANCP, the Innovation Values, and the inverse of Coherence  Values. In this experiment, the first 40 columns are the outliers. }
    \label{fig:compare_scores}
\end{figure}















\subsection{Noisy Data}

In this section, we examine the robustness of the robust PCA methods against noise. Suppose $\mathbf{B}$ follows Assumption~\ref{asm:out}, $r=5$, $r_o=10$, $M_1 = 200$, $n_i=100$, and $n_o=100$
where $\mathcal{U}_o$ is a random 10-dimensional subspace. We consider two models for the distribution of the inliers. The first model is random distribution on $\mathcal{U} \cap \mathbb{S}^{N-1}$ as described in Assumption~\ref{assum_DistUni}. In the second model, it is assumed that the inliers form a cluster in $\mathcal{U}$. The following assumption describes the second model. 

 \begin{assumption}
Each column of matrix $\mathbf{A}$ is formed as $\mathbf{a}_i = \frac{ \mathbf{U} \mathbf{s}_i}{\|  \mathbf{U} \mathbf{s}_i \|_2} $ where $\mathbf{s}_i =  \mathbf{w} + \gamma \mathbf{z}_i$, $\mathbf{w} \in \mathbb{R}^{r }$ is a unit $\ell_2$-norm vector, and $\{\mathbf{z}_i \}_{i=1}^{n_i}$ are sampled randomly  from $\mathbb{S}^{r - 1}$.
\label{asm:inliers_clus}
\end{assumption}

\noindent
Since the data is noisy, exact subspace recovery is not feasible. Instead, we examine the probability that an algorithm distinguishes  all the outliers correctly. Define vector $\mathbf{f} \in \mathbb{R}^{M_2 }$ such that $\mathbf{f}(k) = \| (\mathbf{I} - \hat{\mathbf{U}} \hat{\mathbf{U}}^T) \mathbf{d}_k \|_2$ where $\hat{\mathbf{U}}$ is the identified subspace. A trial is considered successful if
\begin{eqnarray}
\label{eq:out_conddi}
\max \bigg( \{\mathbf{f}(k) \: \: : \: \: k > n_o \} \bigg) < \min \bigg( \{\mathbf{f}(k) \: \: : \: \: k \le n_o \} \bigg),
\end{eqnarray} 
which means that the norm of projection of all the inliers on $\hat{\mathcal{U}}^{\perp}$ should be smaller than the corresponding values for the outliers.  Define  $\text{SNR} = \frac{\| \mathbf{A} \|_F^2}{\| \mathbf{E} \|_F^2 }$ where $\mathbf{E}$ is the noise component which is added to the inliers. Fig.~\ref{fig:lin_dep_out} shows the probability that (\ref{eq:out_conddi}) is valid versus SNR (the number of evaluation runs was 200). In the left plot, the distribution of inliers follows Assumption~\ref{assum_DistUni} and in the right plot it follows Assumption~\ref{asm:inliers_clus} with $\gamma = 0.2$. 
 One can observe that SNCP outperforms most of the existing methods on both cases and the performance of iSearch and ANCP are close. 
 In addition, by comparing the two plots, it can be observed that the performance of some of the robust PCA methods is sensitive to the distribution of the inliers. For instance, FMS outperforms most of the other methods when the inliers are randomly distributed but its performance degrades significantly when the inliers form a cluster in $\mathcal{U}$.
 

\begin{figure}[h!]
\begin{center}
\mbox{
\includegraphics[width=1.8in]{figs/1000.eps}\hspace{-0.1in}
\includegraphics[width=1.8in]{figs/210n.eps}}
\end{center}
\vspace{-0.15in}
           \caption{The outliers are linearly dependant and they lie in a 10-dimensional subspace. In the left plot, the inliers are randomly distributed in $\mathcal{U}$ (Assumption~\ref{assum_DistUni}) and in the right plot, the inliers form a cluster (Assumption~\ref{asm:inliers_clus} with $ \gamma = 0.2)$. }

\label{fig:lin_dep_out}
\end{figure}
\subsection{ Identifying the Permuted Columns  }

The problem of  regression with  unknown permutation
is similar to the conventional  regression but the correspondence between input variables and labels is missing or erroneous. Suppose $\mathbf{X} \in \mathbb{R}^{d \times n}$ is the measurement matrix where $n$ is the number of measurements. Define $\mathbf{Y} \in \mathbb{R}^{m \times n}$ as the observation matrix which can be written as $\mathbf{Y} = \Theta \mathbf{X}$ where $\Theta \in \mathbb{R}^{m \times d}$ is the unknown matrix which is estimated by the regression algorithm. 
In the regression problem with  unknown permutation, the observation matrix $\mathbf{Y}$ is affected by an unknown permutation matrix $\Pi$, i.e., matrix $\mathbf{Y}$ can be written as $\mathbf{Y} = \Theta \mathbf{X} \Pi$ where $\Pi \in \mathbb{R}^{n \times n}$. In this problem, it is assumed that $\Pi$ does not displace all the columns of $\Theta \mathbf{X}$ and only an unknown fraction of the columns are displaced. The authors of~\cite{slawski2019sparse} showed that this special regression problem can be translated into a robust PCA problem. Define matrix $\mathbf{Z} \in \mathbb{R}^{(d+m) \times n}$ as $\mathbf{Z} = ([\mathbf{X}^T \:\: \mathbf{Y}^T])^T$, i.e., each column of $\mathbf{Z}$ is equal to the concatenation of the corresponding columns of $\mathbf{X}$ and $\mathbf{Y}$. 
Suppose $n > d$ and assume that the rank of $\mathbf{X}$ is equal to $d$. 
If $\Pi$ is equal to the identity matrix, the rank of $\mathbf{Z}$ is equal to $d$. In contrast, when the columns of $\mathbf{Y}$ are displaced, the corresponding columns of $\mathbf{Z}$ do not lie in the $d$-dimensional subspace which the other columns of $\mathbf{Z}$ lie in. Therefore,  the columns of $\mathbf{Z}$ which are corresponding to the displaced columns can be considered as outliers and a robust PCA method can be utilized to locate them. Once they are located and removed, the regression problem can be solved using the remaining measurements. 

In this experiment, the elements of $\mathbf{X}$ and $\Theta$ are sampled from $\mathcal{N} (0,1)$, $d = 10$, and $m = 10$. Define $n_i$ as the number of columns of $\mathbf{Y}$ which are not affected by the permutation matrix and define $n_o$ as the number of displaced columns. The robust PCA methods are applied to $\mathbf{Z}$ to find a basis for the $d$-dimensional subspace which is spanned by the columns of $\mathbf{Z}$ corresponding to the inliers. If this subspace is estimated accurately, all the displaced columns can be exactly located~\cite{slawski2019sparse}.  Define Log-Recovery Error   as
           $
\log_{10} \left( \frac{\| (\mathbf{I} - \mathbf{U} \mathbf{U}^T) \hat{\mathbf{U}} \|_F}{ \|\mathbf{U} \|_F } \right)
$, where $\hat{\mathbf{U}}$ is an orthonormal basis for the recovered subspace. 
Fig.~\ref{fig:lin_dep_out2} shows Log-Recovery Error versus $n_o$ where $n_i$ is fixed equal to 200 (the number of evaluation runs was 400). 
This is a challenging subspace recovery task because the outliers can be close to the span of inliers and this is the main reason that CoP did not perform well. One can observe that SNCP and FMS yielded the best performance.  


\begin{figure}[h!]
\begin{center}
\mbox{
\includegraphics[width=2.1in]{figs/reg.eps}
    }
\end{center}
\vspace{-0.15in}
           \caption{This plot shows subspace recovery error versus the number of displaced measurements. The number of measurements which are not displaced are equal to $n_i=200$ and the total number of measurements are equal to $n_i + n_o$.}

\label{fig:lin_dep_out2}
\end{figure}

\subsection{Unstructured Outliers}
Theorem~\ref{theo:random} predicted that when the outliers are randomly distributed, the number of outliers can be much larger than the number of inliers provided that $n_i/r$ is sufficiently large. Suppose the data follows Assumption~\ref{assum_DistUni} with $M_1=50$ and $r=4$.
Define $\hat{\mathbf{U}}$ as an orthonormal basis for the recovered subspace. A trial is considered successful if
$
\frac{\| (\mathbf{I} - \mathbf{U} \mathbf{U}^T) \hat{\mathbf{U}} \|_F}{ \|\mathbf{U} \|_F } < 10^{-3} \: .
$
Fig.~\ref{fig:phase} shows the phase transitions 
in which white means correct subspace recover and black  designates  incorrect  recovery (the number of evaluation runs was 20). The phase transitions indicate that  when $n_i/r$ is larger than 5, the  algorithms can successfully recover $\mathcal{U}$ even if $n_o = 2000$. In addition, SNCP shows more robustness against the outliers when $n_i$ is small.



\begin{figure}[h!]
\begin{center}
\mbox{
\includegraphics[width=0.5\textwidth]{figs/phase.eps}
}
\end{center}
\vspace{-0.15in}
           \caption{ The  phase transitions in presence of the unstructured outliers versus $n_i$ and $n_o$. White indicates correct
subspace recovery and black designates incorrect recovery. In this experiment, the data follows Assumption~\ref{assum_DistUni} with $M_1=50$ and $r=4$. }
\label{fig:phase}
\end{figure}

\subsection{Structured Outlier Detection in Real Data}
The authors of~\cite{gitlin2018improving,rahmani2017coherence} proposed to use robust PCA to improve the accuracy of the clustering algorithms. The robust PCA method is applied to each identified cluster to find the miss-classified data points as outliers. We refer the reader to~\cite{gitlin2018improving,rahmani2017coherence}  for further details. Similar to corresponding experiment in~\cite{rahmani2017coherence}, we use Hopkins155 dataset which makes the outlier detection problem challenging. In this dataset, the data points are linearly dependent and the clusters are  close to each other. Therefore, the outliers are  structured and they are close to the inliers. The clustering error of the clustering algorithm is $30 \%$ and we compute the final clustering error after applying the robust PCA methods and updating the clusters. Table~\ref{tab:accuracy} shows the clustering error after applying different robust PCA methods. One can observe that iSearch, ANCP, SNCP, and CoP yielded better performance and the main reason is that they leverage the clustering structure of the inliers and they are robust against structured outliers. 














\begin{comment}
\vspace{-0.1in}
\subsection{Running Time}
\vspace{-0.1in}
In this section, we study the running time of the robust PCA methods. For ANCP, SNCP, CoP, and iSearch, we used 50 data points to build the basis matrix (matrix $\mathbf{Y}$). Table
\ref{tab:runnig_M2} shows the running times versus $M_2$ while $M_1 = 200$. Table~\ref{tab:runnig_M1} shows the  running times versus $M_1$ while $M_2 = 1500$. In all the runs, $r = 5$ and $n_i = 200$. One can observe that CoP, SNCP, and ANCP are notably fast since they are single step algorithms. The running time of CoP and SNCP is longer than ANCP when $M_2$ is large because their computation complexity scale with $M_2^2$. GMS is also  a fast algorithm when $M_1$ is small but its running time can be long when $M_1$ is large because its computation complexity scale with $M_1^3$. 
\end{comment}










\begin{table}[h!]
\centering
\caption{Clustering error after using the robust PCA methods to detect the misclassified data points. }
\begin{tabular}{| c | c | c  | c |c|c|c|c|}
\hline
 CoP & FMS  & R1-PCA & GMS &     iSearch  & PCA  & ANCP & SNCP \\
 \hline
 6.93 & 28.5  & 22.56 & 17.25 &     3.72  & 12.01  & 6.64 & 3.65 \\
 \hline
\end{tabular}
\label{tab:accuracy}
\end{table}

\begin{figure*}[t]
\begin{center}
\mbox{
\includegraphics[width=1.22in]{figs/Ancp.eps}\hspace{-0.12in}
\includegraphics[width=1.22in]{figs/sncp.eps}\hspace{-0.12in}
\includegraphics[width=1.22in]{figs/svd.eps}\hspace{-0.12in}
\includegraphics[width=1.22in]{figs/r1.eps}\hspace{-0.12in}
\includegraphics[width=1.22in]{figs/isearch.eps}\hspace{-0.12in}
\includegraphics[width=1.22in]{figs/FMS.eps}
}
\end{center}
\vspace{-0.15in}
           \caption{\textcolor{black}{This figure shows the residual} values computed by different methods. Each element represents a frame of the video file and frames 65 to 80 are the outlying frames.  }
    \label{fig:activity}
\end{figure*}









\subsection{Event Detection in Video}
In this experiment, we utilize the robust PCA methods to identify an activity in a video files, i.e., the outlier detection methods identify the frames which contain the activity as the outlying frames/data-points. 
We use the Waving Tree video file~\cite{li2004statistical} where in this video
 a tree is smoothly waving and in
the middle of the video, a person crosses the frame. The frames which only contain the background (the tree and the environment) are inliers and the few frames corresponding to the event (the presence of the person) are the outliers.
The tree is smoothly waving and we use $r=3$ as the rank of inliers for all the methods.  We use 100 frames where frames 65 to 80 are the outlying frames. In this interval (65 to 80), the person enters the frame from left, stay in the middle, and leaves from right. In this experiment, we vectorize each frame and form data matrix $\mathbf{D}$ by the vectorized frames. In addition, we reduce the dimensionality of $\mathbf{D}$ by projecting each column of $\mathbf{D}$ into the span of the first 50 left singular vectors. Thus, $\mathbf{D} \in \mathbb{R}^{50 \times 100}$.
Define $\hat{\mathbf{U}}$ as the estimated subspace and define the residual value corresponding to data point $\mathbf{d}_i$ as ${\| \mathbf{d}_i - \hat{\mathbf{U}}\hat{\mathbf{U}}^T \mathbf{d}_i\|_2}$. The outliers are detected as the data points with the larger residual values.
Fig.~\ref{fig:activity} shows the residual values computed by different methods. An important observation is that FMS, PCA (SVD), and R1-PCA clearly distinguished the first and the last outlying frames but they hardly distinguish the middle outliers (frames 69 to 74). The main reason is that in these frames the person does not move which means that these outlying frames are very similar to each other. Fig.~\ref{fig:activity} shows that the ANCP, SNCP, and iSearch successfully distinguish all the outlying frames since they are robust to structured and linearly dependant outliers.



\subsection{Running Time}
In this section, we study the running time of the robust PCA methods. For ANCP, SNCP, CoP, and iSearch, we used 50 data points to build the basis matrix (matrix $\mathbf{Y}$). Table
\ref{tab:runnig_M2} shows the running times versus $M_2$ while $M_1 = 200$. Table~\ref{tab:runnig_M1} shows the  running times versus $M_1$ while $M_2 = 1500$. In all the runs, $r = 5$ and $n_i = 200$. One can observe that CoP, SNCP, and ANCP are notably fast since they are single step algorithms. The running time of CoP and SNCP is longer than ANCP when $M_2$ is large because their computation complexity scale with $M_2^2$. GMS is also  a fast algorithm when $M_1$ is small but its running time can be long when $M_1$ is large because its computation complexity scale with $M_1^3$. 



\begin{table}[h!]
\centering
\caption{Running time of the algorithms versus $M_2$ ($M_1 = 200$).}
\begin{tabular}{| c | c | c  | c |c|c|c|}
\hline
$M_2 $& SNCP & ANCP & iSearch & CoP & FMS & GMS \\
 \hline
500 & 0.0228 & 0.0120 & 0.2660 & 0.016 & 0.1130 &  0.0872\\
 \hline
 1000 & 0.0427 & 0.0160 & 0.8983 & 0.0325 & 0.2440 & 0.1265\\
 \hline
  5000 & 0.2622 & 0.0428 & 19.4080 & 0.3930 & 0.6635  & 0.2926\\
 \hline
\end{tabular}
\label{tab:runnig_M2}
\end{table}



\begin{table}[h!]
\centering
\caption{Running time of the algorithms versus $M_1$ ($M_2 = 1500$).}
\begin{tabular}{| c | c | c  | c |c|c|c|}
\hline
$M_1 $& SNCP & ANCP & iSearch & CoP & FMS & GMS \\
 \hline
200 & 0.0614 & 0.0187 & 1.7279 & 0.0576 & 0.2978 &  0.1458 \\
 \hline
 500 & 0.1456  & 0.0727  & 2.1261  & 0.0710  & 0.9574 & 0.6399\\
 \hline
  1000 & 0.3145 & 0.2527  & 2.7695  & 0.0900  & 2.7731  & 2.5590 \\
 \hline
\end{tabular}
\label{tab:runnig_M1}
\end{table}












\section{Conclusion}
It was shown that  Innovation Value under the quadratic cost function is equivalent to  Leverage Score. Two closed-form robust PCA methods were presented where the first one was based on Leverage Score and the second one was inspired by the connection between Leverage Score and Innovation Value. Several theoretical performance guarantees for the robust PCA method under different models for the distribution of the outliers and the distribution of the inliers were presented. In addition, it was shown with both theoretical and numerical investigations that the algorithms are robust to the strong presence of noise. Although the presented methods are fast  closed-form algorithms, it was shown that they often outperform most of the existing methods. 


\vspace{0.4in}

 

2021-06-24T02:12:16.000
2106
2106.12190
en
https://arxiv.org/abs/2106.12190
The idea of Innovation Search, which was initially proposed for data clustering, was recently used for outlier detection. In the application of Innovation Search for outlier detection, the directions of innovation were utilized to measure the innovation of the data points. We study the Innovation Values computed by the Innovation Search algorithm under a quadratic cost function and it is proved that Innovation Values with the new cost function are equivalent to Leverage Scores. This interesting connection is utilized to establish several theoretical guarantees for a Leverage Score based robust PCA method and to design a new robust PCA method. The theoretical results include performance guarantees with different models for the distribution of outliers and the distribution of inliers. In addition, we demonstrate the robustness of the algorithms against the presence of noise. The numerical and theoretical studies indicate that while the presented approach is fast and closed-form, it can outperform most of the existing algorithms.
Machine Learning (stat.ML); Machine Learning (cs.LG)
Closed-Form, Provable, and Robust PCA via Leverage Statistics and Innovation Search
Qwen/Qwen-72B
1. YES
2. YES

