text:
\section{Introduction}

Principal Component Analysis (PCA) has been routinely used to reduce dimensionality by finding linear projections of high-dimensional data into lower dimensional subspaces. Such linear models are highly pertinent to a broad range of data analysis problems, including computer vision, image processing, machine learning and bioinformatics \cite{lamport44,lamport45,rahmani2015innovation}.

Given a data matrix $\mathbf{D} \in \mathbb{R}^{N_1 \times N_2}$, PCA finds an $r$-dimensional subspace by solving
\begin{eqnarray}
\underset{\hat{\mathbf{U}}}{\min} \| \mathbf{D} - \hat{\mathbf{U}} \hat{\mathbf{U}}^T \mathbf{D} \|_F \quad \text{subject to} \quad \hat{\mathbf{U}}^T \hat{\mathbf{U}} = \mathbf{I},
\label{eq1}
\end{eqnarray}
where $\hat{\mathbf{U}} \in \mathbb{R}^{N_1 \times r}$ is an orthonormal basis for the $r$-dimensional subspace, $\mathbf{I}$ denotes the identity matrix and $\| .
\|_F$ the Frobenius norm. While PCA is useful when the data has low intrinsic dimension, it is notoriously sensitive to outliers in the sense that the solution to
(\ref{eq1}) can arbitrarily deviate from the true underlying subspace if a small portion of the data is not contained in this low-dimensional subspace.

As outliers prevail much of the real data, a large body of research has focused on developing robust PCA algorithms that are not unduly affected by the presence of outliers. The corrupted data can be expressed as
\begin{eqnarray}
\mathbf{D} = \mathbf{L} + \mathbf{C} \: ,
\label{eq2}
\end{eqnarray}
where $\mathbf{L}$ is a low rank matrix whose columns lie in a low-dimensional subspace, and the matrix $\mathbf{C}$, called the outlier matrix, models the data corruption.
Two main models for data corruption that are in fact incomparable for the most part were considered in the literature, namely, element-wise and column-wise corruption. In the former model, $\mathbf{C}$ is an element-wise sparse matrix with arbitrary support, whose entries can have arbitrarily large magnitudes \cite{lamport1,lamport22}. In this model, all the columns of $\mathbf{L}$ may be affected by the non-zero elements of $\mathbf{C}$ given its arbitrary support pattern.
In the column-wise model, a portion of the columns of $\mathbf{C}$ are non-zero and these non-zero columns do not lie in the column space of $\mathbf{L}$ \cite{lamport10 , lamport24}. Thus, a portion of the columns of $\mathbf{L}$, the so-called inliers, are unaffected by $\mathbf{C}$. This paper focuses on the column-wise outlier model according to the following data model.
\begin{data model} The given data matrix $\mathbf{D}$ satisfies the following conditions.\\
1. The matrix $\mathbf{D}$ can be expressed as (\ref{eq2}).\\
2. $\rank(\mathbf{L}) = r$. \\
3. The matrix $\mathbf{C}$ has $K$ non-zero columns. The non-zero columns of $~\mathbf{C}$
do not lie in the column space of $~\mathbf{L}$. Hence, if $\mathcal{I}$ is the index set
of the non-zero columns of $\mathbf{C}$ and $\mathbf{U} \in \mathbb{R}^{N_1 \times r}$ an
orthonormal basis for the column space of $\mathbf{L}$, then,
\begin{eqnarray}
(\mathbf{I} - \mathbf{U} \mathbf{U}^T) \mathbf{C}_i \neq 0\quad \text{for} \quad i \in \mathcal{I},
\label{eq7}
\end{eqnarray}
where $ \mathbf{C}_i $ is the $i^{\text{th}}$ column of $\mathbf{C}$. \\
4. Without loss of generality, it is assumed  that $$\mathbf{L}_i = \mathbf{0} \quad
\text{for} \quad i \in \mathcal{I} \:,$$ where $\mathbf{L}_i$  is the
$i^{\text{th}}$ column of $\mathbf{L}$. Define $\mathbf{L}^{'} \in \mathbb{R}^{N_1 \times
N_2^{'}}$ as the matrix of non-zero columns of $\mathbf{L}$ (the inlier columns) and
$N_2^{'}$ as the number of inlier columns, i.e., $N_2 = K + N_2^{'}$.
\end{data model}

The problem of robust PCA has received considerable attention in recent years \cite{rahmani2015analysis,lamport2,lamport6,lamport10,lamport13,lamport21,lamport29,lamport47,lamport48,zhang2014novel,soltanolkotabi2012geometric}.
However, the state-of-the-art robust estimators and matrix decomposition techniques are mostly unscalable, which limits their usefulness in big data applications.
For instance, many of the existing approaches rely on iterative algorithms that involve computing a Singular Value Decomposition (SVD) of the $N_1\times N_2$ data matrix in each iteration, which is computationally prohibitive in high-dimensional settings. This motivates the work of this paper.

\subsection{Notation and definitions}
 Given a matrix $\mathbf{L}$, $\|\mathbf{L}\|$ denotes its spectral norm, $\| \mathbf{L} \|_{*}$ its nuclear norm which is the sum of the singular values, and $\| \mathbf{L} \|_1$ its $\ell_1$-norm given by $ \| \mathbf{L} \|_1 = \sum\limits_{i,j} \big | \mathbf{L} (i,j) \big |$, i.e. the sum of the absolute values of its entries.
The norm $\| \mathbf{L} \|_{1,2}$ is defined as
$\| \mathbf{L} \|_{1,2} = \sum\limits_{i}  \| \mathbf{L}_i \|_2, $
where $\| \mathbf{L}_i \|_2$ is the $\ell_2$-norm of the $i^{\text{th}}$ column of
$\mathbf{L}$. In an $N$-dimensional space, $\mathbf{e}_i$ is the $i^{\text{th}}$ vector of
the standard basis. For a given vector $\mathbf{a}$, $\| \mathbf{a} \|_p$ denotes its $\ell_p$-norm.
Two linear subspaces $\mathcal{S}_1$ and $\mathcal{S}_2$ are said to be independent if the dimension of their intersection $\mathcal{S}_1 \cap \mathcal{S}_2$ is equal to zero.
In the presented algorithms and analysis, we make use of the following definitions.
\begin{definition}
The row space of a matrix $\mathbf{L}$ with rank $r$ and $N_2^{'}$ non-zero columns is said to be incoherent with parameters $\mu_v$, $\eta_v$ and $\gamma$ if
\begin{eqnarray}
\begin{aligned}
&\quad \underset{i}{\max} \|\mathbf{V}^T \mathbf{e}_i\|_2^2 \leq \frac{r \mu_v}{N_2} \quad , \quad \eta_v \hspace{-0.5mm}= \hspace{-.5mm}\sqrt{N_2}
\max_{i,j} |\mathbf{V}(i,j)|  \: , \\
& \quad \quad \quad \quad \quad \quad \quad  \underset{i}{\max} \|\mathbf{V}^T \mathbf{e}_i\|_2^2 \leq \frac{r \gamma}{N_2^{'}}
\end{aligned}
\end{eqnarray}
where $\mathbf{V}$ is an orthonormal basis for the row space of  $\mathbf{L}$. Similarly, the column space of $\mathbf{L}$  is said to be incoherent with parameters $\mu_u$ and $\eta_u$ if
\begin{eqnarray}
 \underset{i}{\max} \|\mathbf{U}^T \mathbf{e}_i\|_2^2 \leq \frac{r \mu_u}{N_1}  \quad and \quad \eta_u \hspace{-0.5mm}= \hspace{-.5mm}\sqrt{N_1}
\max_{i,j} |\mathbf{U}(i,j)| \:.
\end{eqnarray}
\label{def: incoh}
\end{definition}

\begin{definition}
(Distributional Johnson-Lindenstrauss (JL) Property \cite{ lamport35 , lamport37 , lamport39}). An $m \times n$ matrix $\mathbf{\Phi}$ is said to satisfy the Distributional JL property if for any fixed $\mathbf{v} \in \mathbb{R}^{n}$ and any $\epsilon \in (0,1)$,
\label{def2}
\begin{eqnarray}
\mathbb{P} \left( \Big | \| \mathbf{\Phi} \mathbf{v} \|_2^2 - \| \mathbf{v} \|_2^2 \Big | \ge \epsilon  \| \mathbf{v} \|_2^2  \right) \leq 2 e^{- m f(\epsilon) },
\label{eq12}
\end{eqnarray}
where $f(\epsilon) > 0$ is a constant that is specific to the distribution of $\mathbf{\Phi}$ and depends only on $\epsilon$.
\label{def: embedd}
\end{definition}
We refer the reader to \cite{lamport49,candes2007sparsity} for further details concerning the properties of the incoherency parameters.
Also, similar to Definition \ref{def: incoh}, we define $\mu_v^{'}$ as the row space incoherency of $\mathbf{L}^{'}$, i.e., if $\mathbf{V}^{'} \in \mathbb{R}^{N_2^{'} \times r}$ is an orthonormal basis for the row space of $\mathbf{L}^{'}$, $\underset{i}{\max} \| \mathbf{e}_i^T \mathbf{V}^{'} \|_2^2 \leq \frac{r \mu_v^{'}}{N_2^{'}}$.

\subsection{Summary of contributions}
Motivated by the aforementioned limitation of existing approaches in big data settings, which is to be further elaborated in the related work section, this paper explores and analyzes a randomized approach to robust PCA using low-dimensional data sketching. Two randomized designs are considered.
The first design is the Random Embedding Design (RED) wherein a random subset of the data columns is selected then embedded into a random low-dimensional subspace. The second randomized design is a Random Row-sampling Design (RRD), in which a random subset of the data columns are sampled, then we select a random subset of the rows of the sampled columns. Unlike conventional robust PCA algorithms that use the full-scale data, robust subspace recovery is applied to the reduced data sketch.

We consider two distinct popular models for the outlier matrix. In the first model -- the independent outlier model -- it is assumed that any small subset of the non-zero columns of $\mathbf{C}$ is not linearly dependent. This model allows for a remarkable portion of the data to be outliers. In the second model -- the sparse outlier model -- it is assumed that $\mathbf{C}$ is column-sparse, i.e., a very small portion of the given data columns are outliers, but no assumption is made about the linear dependence of the outlying columns.
For  both outlier models, we prove that the randomized approach using either of the designs can recover the correct subspace with high probability (whp). Some of the key technical contributions of this paper are listed below. \\
1. To the best of our knowledge, RRD is used and analyzed here for the first time for robust PCA with column-wise corruption. We prove that RRD can recover the correct subspace using roughly $\mathcal{O} (r^2 \mu_u \mu_v)$ random linear data observations.
The complexity of subspace recovery in RRD is roughly $\mathcal{O} (r^3 \mu_u \mu_v)$.
 \\
2. For RED, it is shown here for the first time that the sufficient number of random linear data observations for correct subspace recovery is roughly $\mathcal{O} (r^2 \mu_v)$. \\
3. The proposed randomized approach based on the linear independence of the outlier columns is novel. We take advantage of random column sampling to substantially reduce the number of outlying columns. Thus, unlike conventional approaches that need to go through all the columns to identify the outliers, we only need to check $\mathcal{O} (r \mu_v)$ data points. \\
Table \ref{tabl 1} summarizes the derived order of sufficient number of linear random data observations for the randomized designs with both outlier models.

\begin{table}
\centering
\caption{Order of sufficient number of random linear data observations.}
\begin{tabular}{| c | c | c |}
\hline
Outlier Model/Design & RED & RRD \\
 \hline
 Column-sparsity & $r^2  \max (\mu_v , r \mu_v^2 \: {K}/{N_2} )$ & $r^2 \eta_u^2 \max (\mu_v , r \mu_v^2 \: {K}/{N_2} )$ \\
 \hline
 Independence & $r^2 \mu_v^{'} \max (1 , \mu_v^{'} \: K/N_2) $ & $r^2 \mu_v^{'} \max (\eta_u^2 , \mu_v^{'} \: K/N_2) $ \\
 \hline
\end{tabular}
\label{tabl 1}
\end{table}

\section{Related Work}
\subsection{Robust PCA}
Some of the earliest approaches to robust PCA relied on robust estimation of the data covariance matrix, such as S-estimators, the minimum covariance determinant,
the minimum volume ellipsoid, and the Stahel-Donoho estimator \cite{lamport47}. However, these approaches are not applicable in high-dimensional settings due to their computational complexity and memory requirements, and we are not aware of any scalable algorithms for implementing these methods with explicit performance guarantees.

Another popular approach replaces the Frobenius norm in (\ref{eq1}) with other norms to enhance robustness to outliers \cite{lamport18}. An instance of this approach is \cite{lamport29}, which uses an $\ell_1$-norm relaxation, commonly used for sparse vector estimation, yielding robustness to outliers \cite{decod,lamport25,lamport22}. \cite{lamport21} replaces the $\ell_1$-norm in \cite{lamport29} with the $\ell_{1,2}$-norm to promote column sparse solutions.
Recently, the idea of using a robust norm was revisited in \cite{lamport2, zhang2014novel}. Therein, the non-convex constraint set is relaxed to a larger convex set and exact subspace recovery is guaranteed under certain conditions.
Nevertheless, these approaches are not directly applicable to large matrices and high-dimensional data settings. For example, the iterative solver of \cite{lamport2} requires an eigen-decomposition operation in each iteration.

An interesting approach for outlier detection was recently proposed in \cite{lamport8,soltanolkotabi2012geometric} based on the idea that outliers do not typically follow low dimensional structures. Hence, few outliers cannot form a linearly dependent set.
Unlike most existing approaches, this approach can recover the correct subspace even if a remarkable portion of the data is outliers, albeit its computational complexity is roughly $\mathcal{O} (N_2^2)$ \cite{soltanolkotabi2012geometric}. Also, the number of samples in \cite{lamport8} scales linearly with the data dimension, which is quite restraining in high dimensional settings.

In this paper, we propose two randomized algorithms for two distinct outlier models. The first algorithm is a new randomized approach that exploits the linear independence of the outlying columns (cf. Section \ref{sec:algo1_ind_outliers}). It is shown that this randomized algorithm can recover the correct subspace with sample complexity that is almost independent of the size of the data (roughly $\mathcal{O} (r^2 \mu_v)$). It also imposes less stringent constraints on the distribution of outliers compared to prior work on the independent outlier model.

The second algorithm presented in Section \ref{sec:algo2_sparse_outliers} deals with the sparse column outlier model using convex rank minimization on reduced data sketches. Robust PCA using convex rank minimization \cite{lamport34} was first analyzed in
\cite{lamport1,lamport10}. It was shown in \cite{lamport10} that the optimal point of \begin{eqnarray}
\begin{aligned}
& \underset{\hat{\mathbf{L}},\hat{\mathbf{C}}}{\min}
& & \|\hat{\mathbf{L}} \|_* + \lambda\|\hat{\mathbf{C}}\|_{1,2} \\
& \text{subject to}
& & \hat{\mathbf{L}} + \hat{\mathbf{C}} = \mathbf{D} \:.
\end{aligned}
\label{eq6}
\end{eqnarray}
yields the exact subspace and the correct outliers identification provided that $\mathbf{C}$ is sufficiently column-sparse. The column-sparsity of $\mathbf{C}$ is the main requirement of (\ref{eq6}), i.e., a very small fraction of the columns of $\mathbf{C}$ can be non-zero. The computational complexity of (\ref{eq6}) is roughly $\mathcal{O} (r N_1 N_2)$ per iteration and the entire data needs to be saved in the working memory, which is prohibitive in big data applications. In this paper, we show that the complexity of subspace recovery reduces to $\mathcal{O} (r^3 \mu_v)$, which is  substantially less than $\mathcal{O} (r N_1 N_2)$ for high dimensional data, using a randomized approach that applies (\ref{eq6}) to reduced data sketches.

\subsection{Randomized approaches for Robust PCA}
The low rank component $\mathbf{L}$ has a low-dimensional structure, and so is $\mathbf{C}$ in the element-wise sparse or column-wise sparse models. These low-dimensional structures motivated the usage of randomized algorithms for robust PCA using small sketches constructed from random linear measurements of $\mathbf{D}$.

However, the  majority of such algorithms have focused on robust PCA with the element-wise outlier model \cite{lamport28,myp,liu2011solving,mackey2011divide,mu2011accelerated,zhou2011godec}.  For instance, two randomized methods were proposed in \cite{mackey2011divide} and \cite{myp} to recover $\mathbf{L}$ from small subsets of the columns and rows of $\mathbf{D}$. The randomized approach in \cite{myp} was shown to reduce complexity from $\mathcal{O} (N_1 N_2 r)$ to $\mathcal{O}(\max (N_1 , N_2) r^2)$ per iteration.

Randomized approaches for the column-wise outlier model were proposed in \cite{lamport9} and \cite{lamport8}. The algorithm in \cite{lamport8} is built on the assumption that any subset of outlying columns with cardinality less than $N_1$ is linearly independent. The algorithm repeatedly samples $N_1$ data points until a linearly dependent set is found, upon which those columns that do not depend linearly on the other ones are selected as outliers. Since the number of samples scales linearly with the data dimension and the algorithm requires $\mathcal{O}(N_1^2 N_2)$ iterations on average, it can be quite restraining in high dimensions, especially when a remarkable portion of the data is ouliers.
Another limitation of \cite{lamport8} emerges from the assumption that any subset of inliers with at least $r$ columns spans the column space of $\mathbf{L}$. This may not be true in general, especially with real world data which often exhibits clustering structures.

The work in \cite{lamport9} considers the column-sparse outlier model. The data is first embedded into a random low-dimensional subspace, then a subset of the columns of the compressed data is selected. The convex program in  (\ref{eq6}) is then used to locate the outlying columns of the compressed data. The analysis provided in \cite{lamport9} requires roughly $\mathcal{O}(r N_2)$ random linear observations for exact outlier detection. In this paper, we show that both the required number of sampled columns and the dimension of the subspace for random embedding are almost independent of the size of data and the required number of random linear measurements is shown to be roughly $\mathcal{O}(r^2 \mu_v)$.

\section{Proposed Approach}
\label{sec:prop_approach}
In this section, we propose two algorithms for two distinct models of the outlier matrix. In the first model, the independent outlier model, it is assumed that any small subset of outliers is not linearly dependent. The corresponding algorithm is easy to implement and can recover the correct subspace even if more than 90$\%$ of the data is outliers. The second model concerns the scenario in which $\mathbf{C}$ is column-sparse, yet allows for outliers to be linearly dependent. For both algorithms, we consider two randomized designs, one utilizing random embedding and the other using random row sampling. We provide a full analysis of the sample complexity for the two algorithms based on both randomized designs. The randomized algorithms can provably retrieve the correct subspace with computational and sample complexity that are almost independent of the size of $\mathbf{D}$. In this section, we present the algorithms and the key insights underlying the proposed approach along with the statement of the main theorems. A step-by-step analysis is deferred to Sections \ref{sec:analysis 1} and \ref{sec:analysis 2}.

\begin{algorithm}
\caption{Randomized Robust PCA based on outlier linear independence with both randomized designs}
{\footnotesize
\textbf{Input}: Data matrix $\mathbf{D} \in \mathbb{R}^{N_1 \times N_2} $

\smallbreak
\textbf{1. Data Sketching}\\
\textbf{1.1} {\it Column Sampling:}
 Matrix $\mathbf{S} \in \mathbb{R}^{N_2 \times m_1}$ samples $m_1$ columns of $\mathbf{D}$ randomly $\mathbf{D}_{s} = \mathbf{D} \mathbf{S}$. The columns of $\mathbf{S}$ are a set of standard basis vectors. Thus, $\mathbf{D}_s \in \mathbb{R}^{N_1 \times m_1}$.

\textbf{1.2} {\it Row Compression:}\\
\textcolor{blue}{\textbf{If we use RED:}} Matrix $\mathbf{\Phi} \in \mathbb{R}^{m_2 \times N_1}$ is drawn from any distribution satisfying (\ref{eq12}).
Matrix $\mathbf{\Phi}$ projects the sampled columns $\mathbf{D}_s$  into a random $m_2$-dimensional subspace $\mathbf{D}_s^{\phi}=\mathbf{\Phi} \mathbf{D}_s$. Thus, $\mathbf{D}_s^{\phi} \in \mathbb{R}^{m_2 \times m_1}$.\\
\textcolor{blue}{\textbf{If we use RRD:}} The rows of $\mathbf{\Phi} \in \mathbb{R}^{m_2 \times N_1}$ are a subset of standard basis. Matrix $\mathbf{\Phi}$ samples $m_2$ rows of sampled columns $\mathbf{D}_s^{\phi}=\mathbf{\Phi} \mathbf{D}_s$. Thus, $\mathbf{D}_s^{\phi} \in \mathbb{R}^{m_2 \times m_1}$.

\smallbreak
\textbf{2. Subspace Learning}\\
\textbf{2.1} {\it Sampled Outlier Columns Detection:} Define $\mathbf{d}_{\phi s}^i$ as the $i^{\text{th}}$ column of $\mathbf{D}_s^{\phi}$ and $\mathbf{Q}_i^{\phi}$ is equal to $\mathbf{D}_s^{\Phi}$ with the $i^{\text{th}}$ column removed.
Solve the optimization problem (\ref{eq13})
for $1 \leq i \leq m_1$ to identify the outlying columns of $\mathbf{D}_s^{\phi}$ (if the minimum value of (\ref{eq13}) is non-zero, the column is an outlier). \\
\textbf{2.2} Subspace Learning: Construct $\mathbf{T}$ as the set of columns of $\mathbf{D}_s$ corresponding to a set of linearly independent inlier columns of $\mathbf{D}_s^{\phi}$ spanning the subspace of the inlier columns of $\mathbf{D}_s^{\phi}$.
\smallbreak
\textbf{Output:} The matrix $\mathbf{T}$ is a basis for the column space of $\mathbf{L}$.
}
\end{algorithm}

\begin{algorithm}
\caption{ Randomized Robust PCA based on outlier matrix column-sparsity with both randomized designs}
{\footnotesize
\textbf{Input}: Data matrix $\mathbf{D} \in \mathbb{R}^{N_1 \times N_2} $

\smallbreak
\textbf{1. Data Sketching}\\
Perform steps 1.1 and 1.2 of Algorithm 1.

\smallbreak
\textbf{2. Subspace Learning}\\
\textbf{2.1} {\it Sampled Outlier Columns Detection:} Obtain $\hat{\mathbf{L}}_s^{\phi}$ and $\hat{\mathbf{C}}_s^{\phi}$ as the optimal solution of
\begin{eqnarray}
\begin{aligned}
& \underset{\dot{\mathbf{L}}^{\phi}_s,\dot{\mathbf{C}}^{\phi}_s}{\min}
& & \lambda\|\dot{\mathbf{C}}^{\phi}_s\|_{1,2}  + \|\dot{\mathbf{L}}^{\phi}_s \|_* \\
& \text{subject to}
& & \dot{\mathbf{L}}^{\phi}_s +\dot{\mathbf{C}}^{\phi}_s = \mathbf{D}^{\phi}_s \: .
\end{aligned}
\label{convex_in_alg}
\end{eqnarray}
The non-zero columns of $\hat{\mathbf{C}}_s^{\phi}$ indicate the location of the outlying columns.  \\
\textbf{2.2} Subspace Learning: Construct $\mathbf{T}$ as the set of columns of $\mathbf{D}_s$ corresponding to a set of linearly independent inliers of $\mathbf{D}_s^{\phi}$ spanning the subspace of the inlier columns of $\mathbf{D}_s^{\phi}$.
\smallbreak
\textbf{Output:} The matrix $\mathbf{T}$ is a basis for the column space of $\mathbf{L}$.
}
\end{algorithm}

\subsection{Algorithm 1: randomized approach for the independent outlier model}
\label{sec:algo1_ind_outliers}
Algorithm 1 hinges on the assumption that any small subset of outliers are linearly independent as stated next.
\begin{assumption}
Any subset of the non-zero columns of $\mathbf{C}$ with cardinality equal to $q$ spans a $q$-dimensional subspace that is independent of the column space of $\mathbf{L}$.
\label{asm1}
\end{assumption}
The requirement on $q$ will be formalized later in the section. The table of Algorithm 1 presents the algorithm with both randomized designs along with the definitions of the used symbols. The only difference is in step 1.2 as RED uses random embedding while RRD uses row sampling.

\noindent{\it Insight}: Suppose that $n_s$ columns sampled randomly from $\mathbf{L}^{'}$ span its column space whp.
We do not have direct access to $\mathbf{L}^{'}$ but assume that the number of sampled data columns, $m_1$, is large enough so that the number of inliers in $\mathbf{D}_s$ (the sampled data columns) is at least $(n_s+1)$ and the number of outliers is less than $q$ whp. In Section \ref{sec:analysis 1}, it is shown that the sufficient values for $n_s$, $m_1$ and the upper-bound $q$ are small and scale linearly with $r$.

According to Assumption \ref{asm1}, if ${\mathbf{d}}_s^i$ (the $i^{\text{th}}$ column of $\mathbf{D}_s$) is an inlier, then it must lie in the span of the other columns of $\mathbf{D}_s$ which contains at least $(n_s + 1)$ inliers. By contrast, if ${\mathbf{d}}_s^i$ is an outlier, it would not lie in the span of the other columns since the selected outliers are not linearly dependent.
This is the basis for locating the outlying columns of $\mathbf{D}_s$.

Algorithm 1 solves a low-dimensional outlier identification problem by projecting the sampled data $\mathbf{D}_s$ in a lower-dimensional subspace. Specifically, we form the compressed matrix \begin{eqnarray}
\mathbf{D}_s^{\phi} = \mathbf{\Phi} \mathbf{D}_s,
\label{eq11}
\end{eqnarray}
where $\mathbf{\Phi} \in \mathbb{R}^{m_2 \times N_1}$. The randomized designs differ in the choice of $\mathbf{\Phi}$ in (\ref{eq11}). Specifically, in RED the matrix $\mathbf{\Phi}$ embeds the sampled columns into a random low dimensional subspace, while in RRD $\mathbf{\Phi}$ samples a random subset of the rows of $\mathbf{D}_s$ (c.f. table 1).

In order to ensure that (\ref{eq11}) preserves the essential information, we derive sufficient conditions to satisfy the following requirement.
\begin{requirement}
The data sketching has to ensure that:\\
\textbf{1.} The rank of $ \mathbf{ \Phi} \mathbf{L}$ is equal to $r$.\\
\textbf{2.} The non-zero columns of $\mathbf{\Phi} \mathbf{C}_s$ are independent and they span a subspace independent from the column space of $ \mathbf{ \Phi} \mathbf{L}$.
\end{requirement}

 Define $\mathbf{d}_{\phi s}^i$ as the $i^{\text{th}}$ column of $\mathbf{D}_s^{\phi}$ and $\mathbf{Q}_i^{\phi}$ is equal to $\mathbf{D}_s^{\phi}$ with the $i^{\text{th}}$ column removed. In order to locate the outlying columns of $\mathbf{D}_s^{\phi}$, we solve
\begin{eqnarray}
\underset{\hat{\mathbf{z}}}{\min} \quad \| \mathbf{d}_{\phi s}^i -  \mathbf{Q}_i^{\phi} \hat{\mathbf{z}} \|_2 \:,
\label{eq13}
\end{eqnarray}
for $1 \leq i \leq m_1$. If the minimum of (\ref{eq13}) is zero (or close to zero for noisy data) for the $i^{\text{th}}$ column, it is concluded that the $i^{\text{th}}$ column is an inlier, otherwise it is identified as an outlier.
Once the outlying columns of $\mathbf{D}_s^{\phi}$ are detected, we can estimate the dimension of the subspace spanned by the inliers of $\mathbf{D}_s^{\phi}$. If the estimated dimension is equal to $\hat{r}$, we find $\hat{r}$ independent inlier columns of $\mathbf{D}_s^{\phi}$. Define $\mathbf{T}$ as the matrix formed from the $\hat{r}$ columns of $\mathbf{D}_s$ corresponding to these $\hat{r}$ independent inliers of $\mathbf{D}_s^{\phi}$. Thus, if the outlying columns of $\mathbf{D}_s^{\phi}$ are correctly located, $\mathbf{T}$ would be a basis for the column space of $\mathbf{L}$.

In many applications, we may also be interested in locating the outlying columns. If $\mathbf{T}$ spans the column space of $\mathbf{L}$, we can easily identify the non-zero columns of $\mathbf{C}$ as the non-zero columns of
$
(\mathbf{I} - \mathbf{T} (\mathbf{T}^T \mathbf{T})^{-1} \mathbf{T}^T)\mathbf{D} \:.
$
If outlier detection is intended, an alternative course for data sketching would be to start with row compression followed by column sampling. This is particularly useful in a distributed network setting, in which each agent sends a compressed version of its data vector to a central processor as opposed to centralizing the entire data. As such, the central unit would work with $\mathbf{D}^{\phi} = \mathbf{\Phi} \mathbf{D}$. A random subset of the columns of $\mathbf{D}^{\phi}$ is then sampled to form $\mathbf{D}_s^{\phi}$, and subspace learning is applied to $\mathbf{D}_s^{\phi}$ to learn the column space of $\mathbf{\Phi} \mathbf{L}$.
If $\hat{\mathbf{U}}^{\phi}$ denotes the obtained orthonormal basis for the column space of $\mathbf{\Phi} \mathbf{L}$, then the non-zero columns of $\mathbf{C}$ are identified as the non-zero columns of
\begin{eqnarray}
 \mathbf{H} =  (\mathbf{I} - \hat{\mathbf{U}}^{\phi} (\hat{\mathbf{U}}^{\phi})^T)\mathbf{D}^{\phi} \:.
\label{outlier_detect 1}
\end{eqnarray}
We can readily state the following theorems, which establish performance guarantees for Algorithm 1 with both randomized designs.

\begin{theorem}[Sufficient Condition-Algorithm 1 with RED]
Suppose $\mathbf{D}$ follows Data Model 1, Assumption 1 is satisfied,  $m_1$ columns are sampled randomly with replacement and any repeated columns are removed. If for fixed $c > 1$ and small $0 < \delta \ll 1/5$,
\begin{eqnarray}
\begin{aligned}
& m_1 \ge \beta \alpha \frac{N_2}{N_2^{'}} \:, \quad\beta \ge 2 + \frac{3}{\alpha} \log \frac{2}{\delta}\: , \quad q = \alpha \left( \frac{\beta K}{N_2^{'}} + \frac{1}{c} \right),\\
&m_2 \ge \max \bigg[ \frac{(r+q) \log (42 \sqrt{2}) + \log \frac{2}{\delta}}{f (\frac{1}{{2}})} \: ,\\
&\quad \quad \quad\quad \quad\frac{(r+1) \log (42 \sqrt{2}) + \log K + \log \frac{2}{\delta}}{f (\frac{1}{{2}})}  \bigg]
\end{aligned}
\label{suff thorem 1}
\end{eqnarray}
where the embedding $m_2\times N_1$ matrix $\mathbf{\Phi}$ is drawn from any
 distribution satisfying (\ref{eq12}) and
\begin{eqnarray}
\alpha = \max \Big \{ 20 \mu_v^{'} r  \log \frac{4 r}{\delta} , 3 c^2 \frac{K}{N_2^{'}} \log \frac{2}{\delta} \Big \},
\label{alpha eq}
\end{eqnarray}
then Algorithm 1 with RED yields the exact subspace and (\ref{outlier_detect 1}) identifies the non-zero columns of $\mathbf{C}$ correctly
with probability at least $1 - 5 \delta$.
\label{theorem 1}
\end{theorem}
The following theorem is the counterpart of Theorem \ref{theorem 1} with RRD.
In this paper, for the analysis of RRD we assume that the non-zero entries of $\mathbf{C}$ are sampled from a zero-mean normal distribution.

\begin{theorem}[Sufficient Condition- Algorithm 1 with RRD]
Suppose $\mathbf{D}$ follows Data Model 1, $m_1$ columns are sampled randomly with replacement and any repeated columns are removed, $m_2$ rows are sampled randomly without replacement and the non-zero elements of $\mathbf{C}$ are sampled independently from a zero-mean normal distribution.
If for fixed $c > 1$ and small $0 < \delta \ll 1/6$, $m_1$, $\beta$ and $q$ follow (\ref{suff thorem 1}), $\alpha$ is equal to (\ref{alpha eq}) and
\begin{eqnarray}
\begin{aligned}
 &  m_2 \ge \max \Bigg[ r \eta_u^2 \max \left( c_1 \log r , c_2 \log\left(\frac{3}{\delta}\right) \right) \: , \\
& \quad \quad \quad\quad \quad r+ q + 2 \log \frac{2}{\delta} + \sqrt{8 \: q \log \frac{2}{\delta} } \: , \\
& \quad \quad \quad\quad \quad r+ 1 +2 \log \frac{2 K}{\delta} + \sqrt{8 \: \log \frac{2 K}{\delta} }  \Bigg] \:,
\end{aligned}
\end{eqnarray}
where $c_1$ and $c_2$ are constant numbers, then Algorithm 1 with RRD yields the exact subspace and (\ref{outlier_detect 1}) identifies the non-zero columns of $\mathbf{C}$ correctly with probability at least $1 - 6\delta$.
\label{Theorem 2}
\end{theorem}

\begin{remark}
In practice, the number of outliers is smaller than the number of inliers. Therefore, $\frac{K}{N_2^{'}} \leq 1$ (albeit this is not necessary for  Algorithm 1). Suppose that $C \mu_v^{'} r  \log \frac{4 r}{\delta} \ge 3 c^2 \frac{K}{N_2^{'}} \log \frac{2}{\delta}$, where $C$ is a constant number. According to (\ref{suff thorem 1}), it is almost sufficient to choose $\beta = 2$. Therefore, the sufficient number of randomly sampled columns
$
m_1 \ge 4 C \mu_v^{'} r \log \frac{4r}{\delta} \:,
$
i.e., $m_1$ scales linearly with $r \mu_v^{'}  \log 4r $.
The number of sampled outliers is $\mathcal{O}(m_1  K/ N_2)$. Thus, the sufficient value for $m_2$ for  Algorithm 1 is $\mathcal{O}( \max (r , \frac{K}{N_2^{'}} r \mu_v^{'} ) )$ with RED  and $\mathcal{O} ( \max(r \eta_u^2 ,\frac{K}{N_2^{'}} r \mu_v^{'} ))$ with RRD.

\end{remark}

\subsection{Algorithm 2: randomized approach for the column-sparse outlier model}
\label{sec:algo2_sparse_outliers}
The table of Algorithm 2 details the randomized approach based on the column-sparsity of $\mathbf{C}$ with both randomized designs. Algorithm 2 differs from Algorithm 1 in the subspace learning step since we do not assume that the outliers are linearly independent. Instead, subspace learning relies on the column-sparsity of $\mathbf{C}$ and the convex algorithm (\ref{eq6}) is used in the subspace learning step. This implies a different requirement for the row compression step stated as follows.
 \begin{requirement}
The data sketching has to ensure that:\\
\textbf{1.} The rank of $\mathbf{\Phi} \mathbf{L}$ is equal to $r$.\\
\textbf{2.} The non-zero columns of $\mathbf{\Phi} \mathbf{C}_s$ do not lie in the column space of $\mathbf{\Phi} \mathbf{L}$.
\end{requirement}

It is worth noting that the randomized approach substantially reduces the complexity of (\ref{eq6}). If (\ref{eq6}) is applied directly to $\mathbf{D}$, the complexity would be $\mathcal{O}(N_1 N_2 r)$ per iteration \cite{lamport10}. With the randomized approach, we show that the complexity of the subspace learning step is almost independent of the size of the data. The following theorems establish performance guarantees for Algorithm 2 with both randomized designs.

\begin{theorem}[Sufficient Condition-Algorithm 2 with RED]
Suppose $\mathbf{D}$ follows Data model 1, the matrix $\mathbf{\Phi}$ is drawn from any distribution satisfying (\ref{eq12}), and the columns of $\mathbf{D}_s$ are sampled randomly with replacement. If for small $0 < \delta \ll 1/3$,
\begin{eqnarray}
\begin{aligned}
& m_1 \ge \frac{N_2}{N_2^{'}}\zeta \: , \quad g \ge \frac{N_2^{'}}{N_2} \left( 1 + 6 r \mu_v (121/9) \right),\\
& \frac{K}{N_2^{'}} \leq \frac{g \frac{N_2}{N_2^{'}} - (1 + 6 r \mu_v (121/9))}{g (1+6 r \mu_v (121/9))} ,\\
&m_2 \ge \frac{(r+1) \log (42 \sqrt{2}) + \log K + \log \frac{2}{\delta}}{f (\frac{1}{{2}})},
\label{suff_cond    theorem 3}
\end{aligned}
\end{eqnarray}
where
\begin{eqnarray}
\zeta = \max \left( 3 g^2 \frac{K}{N_2^{'}} \log \frac{2}{\delta} \: , \frac{N_2^{'}}{N_2} 10\: r \mu_v  \log \frac{2r}{\delta} \right) \: ,
\label{g meghdar}
\end{eqnarray}
then Algorithm 2 with RED recovers the exact subspace and (\ref{outlier_detect 1}) correctly identifies the non-zero columns of $\mathbf{C}$ with probability at least $1-3\delta$.
\label{Theorem 3}
\end{theorem}

\begin{theorem}[Sufficient Condition- Algorithm 2 with RRD]
Suppose $\mathbf{D}$ follows Data model 1, the columns of $\mathbf{D}_s$ are sampled randomly with replacement, and the rows are sampled randomly without replacement. In addition, it is assumed that the non-zero elements of $\mathbf{C}$ are sampled independently from a zero-mean normal distribution.  If  for $0 < \delta \ll 1/4$, $m_1$, $g$ and $K / N_2^{'}$ follow (\ref{suff_cond    theorem 3}), $\zeta$ is  equal to (\ref{g meghdar}) and
\begin{eqnarray}
\begin{aligned}
&m_2 \ge \max \Bigg[ r \eta_u^2 \max \left( c_1 \log r , c_2\log\left(\frac{3 }{\delta}\right) \right) \: , \\
& \: r + 1 + 2 \log 2K /\delta + \sqrt{8 \log 2K /\delta}  \Bigg]
\label{suff theorem 4}
\end{aligned}
\end{eqnarray}
then Algorithm 2 with RRD recovers the exact subspace and (\ref{outlier_detect 1}) correctly identifies the non-zero columns of $\mathbf{C}$ with probability at least $1-4\delta$.
\label{theorem 4}
\end{theorem}

\begin{remark}
If we choose
\begin{eqnarray}
 g = 2 \frac{N_2^{'}}{N_2} \big(1 + 6 r \mu_v (121/9)\big) \: ,
\end{eqnarray}
then the sufficient conditions (\ref{suff_cond    theorem 3}) can be rewritten as
\begin{eqnarray}
\begin{aligned}
& \frac{K}{N_2} \leq \frac{{N_2}/{2N_2^{'}}}{1+6 r \mu_v (121/9)}\\
&m_1 \hspace{-0.75mm}\ge \hspace{-0.75mm} \max \hspace{-0.75mm} \left(\hspace{-1mm}12 \frac{K}{N_2} \big(1 \hspace{-0.75mm}+ \hspace{-0.75mm} 6 r \mu_v (121/9)\big)^2 \hspace{-0.5mm} \hspace{-0.5mm} \log \frac{2}{\delta}\: , \: 10 r \mu_v  \log \hspace{-0.5mm}\frac{2r}{\delta} \hspace{-1mm}\right) \hspace{-0.5mm}\\
\end{aligned}
\end{eqnarray}
Thus, $m_1$ for Algorithm 2 is $\mathcal{O} (\max(r\mu_v , \frac{K}{N_2} r^2 \mu_v^2))$. According to (\ref{suff_cond    theorem 3}) and (\ref{suff theorem 4}), the sufficient value for $m_2$ is roughly $\mathcal{O}(r)$ with RED and $\mathcal{O}(r \eta_v^2)$ with RRD. In addition, the permissible number of outliers scales linearly with $N_2$, i.e., not restricted to a sublinear sparsity regime.
\end{remark}

\section{Analysis of Algorithm 1}
\label{sec:analysis 1}
In this section, we provide a setp-by-step analysis of Algorithm 1. The proofs of the main theorems, the lemmas and the intermediate results are deferred to the appendix. First, we establish a sufficient condition on the number of sampled columns $m_1$ to guarantee that each inlier of $\mathbf{D}_s$ lies in the span of the other inliers of $\mathbf{D}_s$. Based on the number of sampled columns, we readily obtain an upper bound on the number of outlying columns in $\mathbf{D}_s$. Then, we derive a sufficient condition for (\ref{eq11}) to satisfy Requirement 1.
\subsection{Random sampling from low rank matrices}
\label{sec sampling lw}
In the randomized approach, the column space of $\mathbf{L}$ is learned from a small random subset of the columns of $\mathbf{D}$. Therefore, we first have to ensure that the selected inliers span the column space of $\mathbf{L}$. Initially, let's assume that $\mathbf{L}^{'}\in \mathbb{R}^{N_1 \times N_2^{'}}$ is given.
Suppose that $\mathbf{L}^{'} = \mathbf{U}^{'} \mathbf{\Sigma}^{'} (\mathbf{V}^{'})^T$ is the compact SVD of $\mathbf{L}^{'}$, where $\mathbf{U}^{'} \in \mathbb{R}^{N_1 \times r}$, $\mathbf{V}^{'} \in \mathbb{R}^{N_2^{'} \times r}$ and $\mathbf{\Sigma}^{'} \in \mathbb{R}^{r \times r}$.
The following lemma establishes a sufficient condition for a random subset of the columns of a low rank matrix to span its column space.
\begin{lemma}
Suppose $n_s$ columns are sampled uniformly at random with replacement from the matrix $\mathbf{L}^{'}$ with rank $r$. If
\begin{eqnarray}
n_s \ge 10 \mu_v^{'} r  \log \frac{2 r}{\delta},
\label{eq22}
\end{eqnarray}
then the selected columns of the matrix $\mathbf{L}^{'}$ span the column space of $\mathbf{L}^{'}$ with probability at least $(1-\delta)$.
\label{lm4}
\end{lemma}
Hence, the column space of a low rank matrix $\mathbf{L}^{'}$ can be captured from a small random subset of its columns when its row space is incoherent with the standard basis.

\subsection{Random column sampling from data matrix D}
Let $\alpha =20 \mu_v^{'} r  \log \frac{4 r}{\delta}$. Based on Lemma \ref{lm4}, the inliers in $\mathbf{D}_s$ span the column space of $\mathbf{L}$ and each inlier of $\mathbf{D}_s$ lies in the span of the rest of the inliers of $\mathbf{D}_s$ whp if the number of inliers in $\mathbf{D}_s$ is at least $\alpha$.
Suppose we sample $m_1 = \beta \alpha { N_2}/{N_2^{'}}$ data columns randomly from $\mathbf{D}$, where $\beta > 1$. The following lemma provides a sufficient condition on $\beta$ to ensure that the number of selected inliers exceeds $\alpha$.
\begin{lemma}
Suppose that $ m_1 = \beta \alpha \frac{N_2}{N_2^{'}}$ columns of the given data matrix are sampled uniformly at random with replacement. If
\begin{eqnarray}
\beta \ge 2 + \frac{3}{\alpha} \log \frac{2}{\delta},
\label{eq34}
\end{eqnarray}
then the number of inlier columns of $\mathbf{D}_s$ is greater than or equal to $\alpha$ with probability at least $(1 - \delta)$.
\label{lm6}
\end{lemma}
According to (\ref{eq34}), it is almost sufficient to choose $\beta = 2$. In addition, in most applications, $\frac{N_2}{N_2^{'}} < 2$. Therefore, if $4\alpha$ columns are sampled at random, the sampled columns will contain at least $\alpha$ randomly sampled inliers.

\subsection{Selected outlying columns}
The advantage of column sampling in the randomized approach is two-fold. First, complexity is substantially reduced since we only need to process a small subset of the data. Second, the number of outliers in $\mathbf{D}_s$ is significantly smaller than the total number of outliers, which in turn relaxes the requirement on the spark of $\mathbf{C}$ considerably. To clarify, robust PCA algorithms built on the linear independence assumption of the outlier columns as \cite{lamport8} require every subset of outliers with cardinality less than $(N_1 + 1)$ to be independent. In contrast, Algorithm 1 only requires independence for significantly smaller subsets of selected outliers.
The following lemma establishes an upper-bound on the number of selected outliers.
\begin{lemma}
Suppose that $ m_1 = \beta \alpha \frac{N_2}{N_2^{'}}$ columns of the given data matrix are sampled uniformly at random with replacement. If
\begin{eqnarray}
\alpha \ge 3 c^2 \frac{K}{N_2^{'}} \log \frac{2}{\delta},
\label{eq37}
\end{eqnarray}
then the number of outliers selected is bounded from above by
\begin{eqnarray}
q = \alpha \left( \frac{\beta K}{N_2^{'}} + \frac{1}{c} \right)
\label{eq38}
\end{eqnarray}
with probability at least $(1 - \delta)$, where $c$ is any number greater than 1.
\label{lm7}
\end{lemma}

\subsection{Row compression}
In this section, we establish sufficient conditions on $m_2$ to satisfy Requirement 1. Suppose $\mathbf{D}_s$ contains $k$ outlying columns. Thus, given Assumption 1, the rank of $\mathbf{D}_s$ is equal to $r+k$. Requirement 1 is clearly satisfied if the rank of $\mathbf{\Phi} \mathbf{D}_s$ is equal to the rank of $\mathbf{D}_s$. The following lemmas provide sufficient conditions for $m_2$ with both randomized designs.
\begin{lemma}
Suppose $\mathbf{D}_s$ contains at most $q$ outlying columns and assume that $\mathbf{\Phi}$ is an $m_2 \times N_1$ matrix satisfying the distributional JL property with
\begin{eqnarray}
m_2 \ge \frac{ (r + q) \log (42 \sqrt{2} ) + \log \frac{2}{\delta}}{f (\frac{1}{{2}})}.
\label{eq:  suffi m_2 1}
\end{eqnarray}
Then, the rank of $\mathbf{\Phi} \mathbf{D}_s$ is equal to the rank of $\mathbf{D}_s$ with probability at least $(1-\delta)$.
\label{lemma: embd 1}
\end{lemma}

\begin{lemma}
Suppose $\mathbf{D}_s$ contains at most $q$ outlying columns, the rank of its low rank component $ \mathbf{L}_s$ is equal to $r$, the non-zero elements of $\mathbf{C}$ are sampled independently from a zero-mean normal distribution, and the rows of $\mathbf{D}_s^{\phi}$ are $m_2$ randomly sampled (without replacement) rows of
$\mathbf{D}_s$. If
\begin{eqnarray}
\begin{aligned}
&  m_2 \ge \max \Bigg[ r\eta_u^2 \max \left( c_1 \log r , c_2 \log\left(\frac{3}{\delta}\right) \right) \: , \\
& \quad \quad \quad \quad r+ q + 2 \log \frac{2}{\delta} + \sqrt{8 \: q \log \frac{2}{\delta} } \Bigg] \:,
\label{m_2 row 1}
\end{aligned}
\end{eqnarray}
where $c_1$ and $c_2$ are constant numbers,
then the rank of $\mathbf{D}_s$ is equal to the rank of $\mathbf{D}_s^{\phi}$ with probability at least $1 - 2\delta$.
\label{lemma row 1}
\end{lemma}

\section{Analysis of Algorithm 2}
\label{sec:analysis 2}
Similar to the analysis of Algorithm 1 in section \ref{sec:analysis 1}, we can make use of Lemma \ref{lm4} to derive a sufficient condition on $m_2$ to ensure that the rank of $\mathbf{L}_s$ is equal to the rank of $\mathbf{L}$. The number of selected outliers can also be bounded in a similar way.
The analysis in \cite{lamport10} established that (\ref{eq6}) yields exact outlier identification if $\mathbf{C}$ is sufficiently column-sparse. If $\mathbf{C}$ is sufficiently sparse, $\mathbf{C}_s$ is also a column-sparse matrix whp.
Thus, we just need to ensure that $\mathbf{D}_s^{\phi}$ is a representative data sketch with sufficient information. The following lemmas establish sufficient conditions on $m_2$ for the row compression step to satisfy Requirement 2 for both RED and RRD.

\begin{lemma}
Suppose $\mathbf{D}_s$ contains at most $q$ outlying columns and assume that $\mathbf{\Phi}$ is an $m_2 \times N_1$ matrix satisfying the distributional JL property with
\begin{eqnarray}
m_2 \ge \frac{ (r + 1) \log (42 \sqrt{2}) + \log q + \log \frac{2}{\delta}}{f (\frac{1}{{2}})}.
\label{eq:  suffi m_2 2}
\end{eqnarray}
Then,  Requirement 2 is satisfied with probability at least $1 - \delta$.
\label{lemma: embd 2}
\end{lemma}

\begin{lemma}
Suppose the rank of $\mathbf{L}_s$ is equal to $r$, $\mathbf{D}_s$ contains at most $q$ columns, the non-zero elements of $\mathbf{C}$ are sampled independently from a zero-mean normal distribution and the rows of $\mathbf{D}_s^{\phi}$ are $m_2$ randomly sampled (without replacement) rows of $\mathbf{D}_s$.
If
\begin{eqnarray}
\begin{aligned}
&  m_2 \ge \max \Bigg[ r\eta_u^2 \max \left( c_1 \log r , c_2 \log\left(\frac{3}{\delta}\right) \right) \: , \\
& \quad \quad  \quad r+ 1 +2 \log \frac{2 q}{\delta} + \sqrt{8 \: \log \frac{2 q}{\delta} } \Bigg] \:,
\label{m_2 row 2}
\end{aligned}
\end{eqnarray}
then Requirement 2 is satisfied with probability at least $1 - 2\delta$.
\label{lemma row 2}
\end{lemma}

\section{RED versus RRD and Complexity Analysis}
 \textcolor{black}{ While the row compression step for RED has computational complexity $\mathcal{O} (m_1 m_2 N_1)$ if we start data sketching with column sampling or  $\mathcal{O} (m_2 N_1 N_2)$ if we start data sketching with row compression}, this step incurs no computational complexity in RRD.
Hence, RRD may be more favorable for big data due to its reduced computational complexity. However, concerning sample complexity, random embedding is generally a more effective data sketching tool since the random projection matrix is not coherent with the data. To clarify, consider the extreme scenario where $r= 2$, $\mathbf{L} \in \mathbb{R}^{2000 \times 2000}$ and only two rows of $\mathbf{L}$ are non-zero. In this scenario, one needs to sample more or less the entire rows to ensure that the rank of $\mathbf{L}^{\phi} = \mathbf{\Phi} \mathbf{L}$ is equal to 2, i.e., $m_2$ has to be equal to 2000. In contrast, projecting the data into a random subspace with dimension equal to 2 is almost sufficient to ensure that the rank of $\mathbf{L}^{\phi}$ is equal to 2 whp, i.e., $m_2 = 2$ is nearly sufficient. As another example, consider a

matrix $\mathbf{G} \in \mathbb{R}^{2000 \times 3000}$ generated by concatenating the columns of matrices $\mathbf{G}_i, i = 1, \ldots, n$, as
$
\mathbf{G} = [ \mathbf{G}_1 \: \mathbf{G}_2 \: ... \: \mathbf{G}_n ]  \:
$ and assume that $\mathbf{L} = \mathbf{G}^T$. For $1 \leq i \leq \frac{n}{2}$, $\mathbf{G}_i = \mathbf{U}_i \mathbf{Q}_i\: ,$
where $\mathbf{U}_i \in \mathbb{R}^{2000 \times \frac{r}{n}}$, $\mathbf{Q}_i \in \mathbb{R}^{\frac{r}{n} \times \frac{100 r}{n}}$. For $n/2+1 \leq i \leq n$, $\mathbf{G}_i = \mathbf{U}_i \mathbf{Q}_i\: ,$
where $\mathbf{U}_i \in \mathbb{R}^{2000 \times \frac{r}{n}}$, $\mathbf{Q}_i \in \mathbb{R}^{\frac{r}{n} \times \frac{20 r}{n}}$.
The elements of $\mathbf{U}_i$ and $\mathbf{Q}_i$ are sampled independently from a normal $\mathcal{N}(0 , 1)$ distribution.
The parameter $r$ is set equal to 50, thus, the rank of $\mathbf{L}$ is equal to 50 whp. Accordingly, the rows of $\mathbf{L}$ lie in a union of low-dimensional subspaces and if $n > 1$, the distribution of the rows of $\mathbf{L}$ in the row space of $\mathbf{L}$ will be highly non-uniform. Fig. \ref{fig: RED_RRD} shows the rank of $\mathbf{\Phi} \mathbf{L}$ versus $m_2$.
When $n=1$, the rows of $\mathbf{L}$ are distributed uniformly at random in the row space of $\mathbf{L}$. Thus, $r$ rows sampled uniformly at random are enough to span the row space of $\mathbf{L}$. But, when $n=50$, we need to sample almost 500 rows at random to span the row space. On the other hand, embedding the data into a random subspace with dimension 50 is almost sufficient to preserve the rank of $\mathbf{L}$ even if $n = 50$.
\begin{figure}[t!]
    \includegraphics[width=0.30\textwidth]{RED_RRD.pdf}
    \centering
     \vspace{-0.2in}
    \caption{The rank of $\mathbf{\Phi}\mathbf{L}$ versus $m_2$.}
    \label{fig: RED_RRD}
\end{figure}

\subsection{Computational complexity analysis}
The randomized approach consists of three steps: data sketching, subspace recovery and outlier detection. The data sketching step for RED has computational complexity $\mathcal{O} (m_1 m_2 N_1)$ if data sketching starts with column sampling and $\mathcal{O} (m_2 N_1 N_2)$ if it starts with row compression. Yet, this step has little impact on the actual run-time of the algorithms as it only involves a basic matrix multiplication operation for data embedding. Data sketching incurs no computational complexity in RRD. The complexity of subspace recovery is roughly $\mathcal{O} (m_1^2 m_2)$ and $\mathcal{O} (r m_1 m_2)$ for Algorithms 1 and 2, respectively. The outlier detection step (\ref{outlier_detect 1}) has complexity $\mathcal{O} (m_2^2 N_2)$. As subspace learning and outlier detection (if intended) dominate the run-time of the algorithms, the randomized approach brings about substantial speedups in comparison to approaches that use the full-scale data. This is so given that the sufficient values for $m_1$ and $m_2$ are almost independent of the size of the data (cf. Section \ref{sec:prop_approach}), hence the randomized approach evades solving high-dimensional optimization problem. In contrast, solving (\ref{eq6}) for example has complexity $\mathcal{O}(r N_1 N_2)$ per iteration. Table \ref{tabl 2} compares the run time of Algorithm 2 to the corresponding non-randomized approach with outlier detection. In this example, $r = 20$, $m_1 = 400$ and $m_2 = 100$. The randomized approach (even using RED) is remarkably faster than the non-randomized approach.
\begin{table}
\centering
\caption{Running time of randomized Algorithm 2 with outlier detection and the Algorithm in \cite{lamport10}. }
\vspace{-0.25cm}
\begin{tabular}{| c | c | c | c |}
\hline
$N_1 = N_2$& Algorithm 2 RED & Algorithm 2 RRD & \cite{lamport10}\\
 & + outlier detection & + outlier detection & \\
 \hline
 1000 & 0.5 s & 0.5 s & 30 s \\
 \hline
  5000 & 0.6 s & 0.6 s & 450 s \\
 \hline
  10000 & 1 s & 0.6 s & 2500 s \\
 \hline
  20000 & 2 s & 0.7 s & 12000 s \\
 \hline
\end{tabular}
\label{tabl 2}
\vspace{-.5cm}
\end{table}

\section{Noisy data}
In practice, noisy data can be modeled as
\begin{eqnarray}
\mathbf{D} = \mathbf{L} + \mathbf{C} + \mathbf{N} \:,
\end{eqnarray}
where $\mathbf{N}$ is an additive noise component.
In \cite{lamport10}, it was shown that the optimal point of
\begin{eqnarray}
\begin{aligned}
& \underset{\hat{\mathbf{L}},\hat{\mathbf{C}}}{\min}
& & \lambda\|\hat{\mathbf{C}}\|_{1,2}  + \|\hat{\mathbf{L}} \|_* \\
& \text{subject to}
& & \big\| \hat{\mathbf{L}} + \hat{\mathbf{C}} - \mathbf{D} \big\|_F \leq \epsilon_n \:, \\
\end{aligned}
\label{eq2noisy}
\end{eqnarray}
is equal to the optimal point of (\ref{eq6}) with an error proportional to the noise level.
The parameter $\epsilon_n$ has to be chosen based on the noise level. This modified version can be used in Algorithm 2 to account for the presence of noise.

Recall that Algorithm 1 is built on the idea that outliers of $\mathbf{D}_s^{\phi}$ cannot be constructed from, or well-approximated by, linear combinations of the other columns of $\mathbf{D}_s^{\phi}$. In the presence of noise, we further need to ensure that an outlier cannot be obtained from linear combinations of the columns of $\mathbf{N}_s^{\phi} = \mathbf{\Phi} \mathbf{N} \mathbf{S}$. If an outlier lies in the span of the columns of $\mathbf{N}_s^{\phi}$, the coefficients in the linear combinations of the columns of $\mathbf{N}_s^{\phi}$ would have to be fairly large given that the columns of $\mathbf{N}$ have small Euclidean norm.
Thus, to make Algorithm 1 robust to noise, we add a constraint to (\ref{eq13}) as follows
\begin{eqnarray}
\underset{\hat{\mathbf{z}}}{\min} \quad \| \mathbf{d}_{\phi s}^i -  \mathbf{Q}_i^{\phi} \hat{\mathbf{z}} \|_2 \quad \text{s.t.} \quad \| \hat{\mathbf{z}} \|_p \leq \omega \:,
\end{eqnarray}
where $p \ge 1$ and $\omega$ is adjusted w.r.t. the noise level.

\section{Numerical Simulations}
In this section, we present some numerical experiments to study the requirements and performance of the randomized approach. The numerical results confirm that the sample complexity of the randomized methods is almost independent of the size of data. First, we investigate different scenarios using synthetic data. Then, the performance and requirements of the randomized algorithms are examined with real data.

\subsection{Phase transition plots with synthetic data}
In this section, The low rank matrix is generated as a product $\mathbf{L} = \mathbf{U}_r \mathbf{V}_r^T$, where $\mathbf{U}_r  \in \mathbb{R}^{N_1 \times r}$, $\mathbf{V}_r  \in \mathbb{R}^{N_2 \times r}$. The elements of $\mathbf{U}_r$ and $\mathbf{V}_r$ are sampled independently from a standard normal $\mathcal{N} (0,1)$ distribution. The columns of $\mathbf{C}$ are non-zero independently with probability $\rho$. Thus, the expected value of the number of outliers columns is $\rho N_2$. The non-zero entries of $\mathbf{C}$ are sampled independently from $\mathcal{N} (0 , 20^2)$. The phase transition plots show the probability of correct subspace recovery for the pairs of $(m_1 , m_2)$. White designates exact subspace recovery and black indicates incorrect recovery. In all experiments presented in this section the data is a $2000 \times 4000$ matrix except for the simulation in Fig. \ref{fig: 2000_50000}.

Fig. \ref{fig: frs_alg1_r} shows the phase transition of Algorithm 1 with RED for different values of $r$. When $r$ is increased, the required values of $m_1$ and $m_2$ increase as we need more samples to ensure that the selected columns span the column space of $\mathbf{L}$, as well as a higher dimension for the embedding subspace given that the column space of $\mathbf{L}$ has a higher dimension.
Fig. \ref{fig: srs_alg1_r} shows a similar plot with RRD. Since in this section the columns/rows of $\mathbf{L}$ are distributed uniformly at random in the column/row-space of $\mathbf{L}$, RED and RRD yield a similar performance. As such, for the remaining scenarios in this section we only provide phase transitions with RED (RRD yields the same performance).

Fig. \ref{fig: frs_alg1_rho} illustrates the phase transition for Algorithm 1 with RED  for different values of $\rho$. Increasing $\rho$ has only minimal effect on $m_1$ (which is almost around 25) because the required number of sampled columns depends linearly on $r \frac{1}{(1- \rho)}$. Therefore, when $\rho$ is increased from 0.2 to 0.7, $r \frac{1}{(1- \rho)}$ increases from $1.25 r$ to $3.3 r$. It is interesting to observe that when the number of sampled columns is increased, the required $m_2$ also increases. This is due to the fact that the number of sampled outlier columns increases as we sample more columns. Subsequently, the selected outliers span a subspace with a higher dimension, wherefore we need a random subspace with higher dimension for embedding the sampled columns because to ensure that the rank of $\mathbf{\Phi} \mathbf{D}_s$ is equal to the rank $\mathbf{D}_s$ in Algorithm 1.

The phase transition plots for Algorithm 2 with RED are shown in Fig. \ref{fig: convex_phase} for different values of $\rho$ and $r$. In the left plot, $r = 5$ and $\rho = 0.01$. With $m_1 > 100$ and $m_2 \ge 50$, the algorithm yield correct output whp. In the middle plot, the rank is increased to 10. Thus, the required values for $m_1$ and $m_2$ increase. In the right plot, $\rho = 0.2$ and Algorithm 2 cannot yield correct subspace recovery since (\ref{eq6}) requires $\mathbf{C}$ to be column-sparse (roughly requiring $\rho \leq 0.05$).

Fig. \ref{fig: 2000_50000}
shows the phase transition of Algorithm 1 with RED for data matrices with different dimensions. Although the size of the data is increased from $2000 \times 4000$ to $(5 \times 10^4) \times 10^5$, the required values for $m_1$ and $m_2$ remain unchanged confirming our analysis, which revealed that the sample complexity of the proposed approach is almost independent of the size of the data. In this simulation, since the columns/rows are distributed randomly, the column space and row space of $\mathbf{L}$ have small incoherence parameters \cite{lamport49}. Thus the factors dominating the sample complexity are $r$ and $\rho$.

\begin{figure}[t!]
    \includegraphics[width=0.50\textwidth]{frs_alg1_r.jpg}
    \centering
     \vspace{-0.3in}
    \caption{Phase transition plots of Algorithm 1 with RED}
    \label{fig: frs_alg1_r}
\end{figure}

\begin{figure}[t!]
    \includegraphics[width=0.50\textwidth]{srs_alg1_r.jpg}
    \centering
     \vspace{-0.3in}
    \caption{Phase transition plots of Algorithm 1 with RRD}
    \label{fig: srs_alg1_r}
\end{figure}

\begin{figure}[t!]
    \includegraphics[width=0.50\textwidth]{frs_alg1_rho.jpg}
    \centering
     \vspace{-0.3in}
    \caption{Phase transition plots of Algorithm 1 with RED}
    \label{fig: frs_alg1_rho}
\end{figure}

\begin{figure}[t!]
    \includegraphics[width=0.50\textwidth]{convex_phase.jpg}
    \centering
     \vspace{-0.3in}
    \caption{Phase transition plots of Algorithm 2 with RED.}
    \label{fig: convex_phase}
\end{figure}

\begin{figure}[t!]
    \includegraphics[width=0.50\textwidth]{2000_500000.jpg}
    \centering
     \vspace{-0.3in}
    \caption{Phase transition plots of Algorithm 1 with RED ($r = 20$ , $\rho = 0.2)$. }
    \label{fig: 2000_50000}
\end{figure}

\begin{figure}[t!]
    \includegraphics[width=0.40\textwidth]{motion.jpg}
    \centering
     \vspace{-0.1in}
    \caption{Phase transition plots of Algorithm 1 with both RED  and RRD applied to motion tracking data. }
    \label{fig: motion}
\end{figure}

\begin{figure}[t!]
    \includegraphics[width=0.40\textwidth]{faces_example.jpg}
    \centering
     \vspace{-0.1in}
    \caption{A set of random examples of the faces in Yale database. }
    \label{fig: yale example}
\end{figure}

\begin{figure}[t!]
    \includegraphics[width=0.40\textwidth]{random_pic.jpg}
    \centering
     \vspace{-0.1in}
    \caption{Random examples of the images in Caltech101 database. }
    \label{fig: caltech ex}
\end{figure}

\begin{figure}[t!]
    \includegraphics[width=0.40\textwidth]{face_sample.jpg}
    \centering
     \vspace{-0.1in}
    \caption{The dimension of $\mathbf{U}^{\phi}$ and $h$ versus the value of $m_2$. }
    \label{fig: dimension of face}
\end{figure}

\subsection{Phase transition with real data}
In this section, we study the requirements of the randomized approach with real data for motion tracking and segmentation. The  data  is  generated  by  extracting  and  tracking  a  set  of
points  throughout the frames \cite{tron2007benchmark}. The data is a low rank matrix, and the motion data points lie in a union of low-dimensional subspaces. We use one of the scenarios in Hopkins155 \cite{tron2007benchmark}. This data matrix is $62 \times 464$ and its rank is roughly equal to 4. We add 50 outlying data points. Thus, the final data is $62 \times 512$. Fig. \ref{fig: motion} is the phase transition of Algorithm 1 with RED and RRD showing the probability of correct outlier identification. When $m_1$ and $m_2$ are greater than 10, the algorithm yields exact outlier detection whp.

\subsection{Sufficient values for $m_2$ with face images}
Vectorized images are high dimensional data vectors. Thus, if they construct low dimensional subspaces, substantial reductions in computational complexity and memory requirements can be achieved through the row compression operation of the randomized approach. In this experiment, we use the face images in the Extended Yale Face Database B \cite{lee2005acquiring} as inlier data points. Fig. \ref{fig: yale example} displays a random subset of these faces. This database consists of face images from 38 human subjects, and the images of each subject lie in a low-dimensional subspace \cite{lee2005acquiring}. According to our investigations, the dimension of the face images (38 faces) is roughly equal to 33. We randomly sample 350 images of the Caltech101 database \cite{fei2007learning} as outlying data points. Fig. \ref{fig: caltech ex} displays a randomly chosen set of the images in the Caltech101 database.
 Define $\mathbf{U}$ as a basis for the subspace of the faces, $\mathbf{U}^{\phi} = \mathbf{\Phi}\mathbf{U}$ and ${\mathbf{C}^{\phi}}^{\perp}$ as
\begin{eqnarray}
{\mathbf{C}^{\phi}}^{\perp} = \bigg( \mathbf{I}  - \mathbf{U}^{\phi} ( {\mathbf{U}^{\phi}}^T \mathbf{U}^{\phi} )^{-1} {\mathbf{U}^{\phi}}^T \bigg) \mathbf{C}^{\phi} \:.
\end{eqnarray}
In addition, define
\begin{eqnarray}
h = \| {\mathbf{C}^{\phi}}^{\perp} \|_F / \| \mathbf{C}^{\phi} \|_F \:.
\end{eqnarray}
Thus, by measuring the dimension of the span of $\mathbf{U}^{\phi}$ and the value of $h$, we can observe if the row compression operation preserves the essential information since the dimension of $\mathbf{U}^{\phi}$ is the rank of of the low rank component and $h$ is proportional to the norm of the components of the outlying data points which do not lie in the column space of the low rank component. Fig. \ref{fig: dimension of face} shows the dimension of $\mathbf{U}^{\phi}$ and the values of $h$ versus $m_2$ for both random embedding and random row sampling. Although the dimension of the data vectors is 32256, it is shown that 300 random linear measurements of the data vectors are nearly sufficient to preserve the rank of $\mathbf{L}$ and the outlying component of $\mathbf{C}$.

\section{Appendix}
\noindent\textbf{Proof of lemma \ref{lm4}}\\
The matrix of sampled columns can be represented as
\begin{eqnarray}
\mathbf{L}_s^{'} = \mathbf{L}^{'} \mathbf{S}^{'}
\label{eq23}
\end{eqnarray}
where $\mathbf{S}^{'} \in \mathbb{R}^{N_2^{'} \times n_s}$ selects the columns to sample. Using the SVD of $\mathbf{L}^{'}$, (\ref{eq23}) can be rewritten as
\begin{eqnarray}
\mathbf{L}_s^{'} = \mathbf{U}^{'} \mathbf{\Sigma}^{'} (\mathbf{V}^{'})^T \mathbf{S}^{'} \quad.
\label{eq24}
\end{eqnarray}
Therefore, if the matrix $ (\mathbf{V}^{'})^T \mathbf{S}^{'}$ is full rank, the selected columns of $\mathbf{L}^{'}$ span its column space.

Define $\mathbf{s}_i^{'}$ as the $i^{\text{th}}$ column of $\mathbf{S}^{'}$. The vector $\mathbf{s}_i^{'}$ can be any of the vectors of the standard basis with equal probability since we are using random sampling with replacement. Therefore,
\begin{eqnarray}
\mathbb{E} \left[ (\mathbf{V}^{'})^T \mathbf{s}_i^{'} (\mathbf{s}_i^{'})^T \mathbf{V}^{'} - \frac{1}{N_2^{'}} \mathbf{I} \right] = 0 .
\label{es1}
\end{eqnarray}
The matrix $ (\mathbf{V}^{'})^T \mathbf{S}^{'} (\mathbf{S}^{'})^T \mathbf{V}^{'} $ can be written as
\begin{eqnarray}
 (\mathbf{V}^{'})^T \mathbf{S}^{'} (\mathbf{S}^{'})^T \mathbf{V}^{'} = \sum_{i=1}^{n_s}  (\mathbf{V}^{'})^T \mathbf{s}_i^{'} (\mathbf{s}_i^{'})^T \mathbf{V}^{'}.
\label{es2}
\end{eqnarray}
If $(\mathbf{V}^{'})^T \mathbf{S}^{'} (\mathbf{S}^{'})^T \mathbf{V}^{'}$ is a full rank matrix, then $(\mathbf{V}^{'})^T \mathbf{S}^{'}$ is also full rank. In addition, if we can show that
\begin{eqnarray}
\Big \|  (\mathbf{V}^{'})^T \mathbf{S}^{'} (\mathbf{S}^{'})^T \mathbf{V}^{'}  - \frac{n_s}{N_2^{'}} \mathbf{I} \Big \|
\label{es3}
\end{eqnarray}
is sufficiently small, we can conclude that $ (\mathbf{V}^{'})^T \mathbf{S}^{'} (\mathbf{S}^{'})^T \mathbf{V}^{'} $ is full rank. According to (\ref{es1}) and (\ref{es2}), the matrix
\begin{eqnarray}
 (\mathbf{V}^{'})^T \mathbf{S}^{'} (\mathbf{S}^{'})^T \mathbf{V}^{'} - \frac{n_s}{N_2^{'}} \mathbf{I}
\label{es4}
\end{eqnarray}
is a sum of $n_s$ independent zero-mean random matrices. Thus, we use the non-commutative Bernstein Inequality \cite{lamport11} to bound the spectral norm of (\ref{es4}).

\begin{lemma}[\text{Non-commutative Bernstein Inequality \cite{lamport11}}]
Let $\mathbf{X}_1 , \mathbf{X}_2 , ... , \mathbf{X}_L $ be independent zero-mean random matrices of dimension $d_1 \times d_2$. Suppose $\rho_k^2 = \max \{\| \mathbb{E} [ \mathbf{X}_k \mathbf{X}_k^T ] \| , \| \mathbb{E} [ \mathbf{X}_k^T \mathbf{X}_k ] \| \} $ and $\| \mathbf{X}_k \| \leq M$ almost surely for all k. Then for any $\tau > 0$
\begin{eqnarray}
\begin{aligned}
&\mathbb{P} \left[ \Bigg \| \sum_{k=1}^{L} \mathbf{X}_k \Bigg  \| > \tau \right] \leq \\
&(d_1 + d_2) \exp \left( \frac{-\tau^2 / 2}{\sum_{k=1}^L \rho_k^2  + M\tau/3} \right) .
\end{aligned}
\label{eq28}
\end{eqnarray}
\label{lm5}
\end{lemma}
 In our problem, $\mathbf{X}_i = (\mathbf{V}^{'})^T \mathbf{s}_i^{'} (\mathbf{s}_i^{'})^T \mathbf{V}^{'} - \frac{1}{N_2^{'}} \mathbf{I} $. If the matrices $\mathbf{A}$ and $\mathbf{B}$ are positive definite, then $\| \mathbf{A} - \mathbf{B} \| \leq \max \{ \| \mathbf{A} \|, \| \mathbf{B} \| \} $. Thus, we can derive $M$ as follows
\begin{eqnarray}
\begin{aligned}
\Big \| (\mathbf{V}^{'})^T &\mathbf{s}_i^{'} (\mathbf{s}_i^{'})^T \mathbf{V}^{'} - \frac{1}{N_2^{'}} \mathbf{I} \Big \| \\
&\leq  \max \{ \Big  \| (\mathbf{V}^{'})^T \mathbf{s}_i^{'} (\mathbf{s}_i^{'})^T \mathbf{V}^{'} \Big  \| , \Big \| \frac{1}{N_2^{'}} \mathbf{I} \Big \|  \} \leq \frac{r \mu_v^{'}}{N_2^{'}}.
\label{eq29}
\end{aligned}
\end{eqnarray}
 We also have
\begin{eqnarray}
\nonumber
\begin{aligned}
&\Bigg \| \mathbb{E} \left[ \left(  (\mathbf{V}^{'})^T \mathbf{s}_i^{'} (\mathbf{s}_i^{'})^T \mathbf{V}^{'} - \frac{1}{N_2^{'}} \mathbf{I}\right) \left(  (\mathbf{V}^{'})^T \mathbf{s}_i^{'} (\mathbf{s}_i^{'})^T \mathbf{V}^{'} - \frac{1}{N_2^{'}} \mathbf{I} \right) \right] \Bigg \| \\
& = \Bigg \| \mathbb{E} \left[ (\mathbf{V}^{'})^T \mathbf{s}_i^{'} (\mathbf{s}_i^{'})^T \mathbf{V}^{'} (\mathbf{V}^{'})^T \mathbf{s}_i^{'} (\mathbf{s}_i^{'})^T \mathbf{V}^{'}  - \frac{1}{(N_2^{'})^2}  \mathbf{I} \right] \Bigg \| \\
& \leq \max \Bigg \{ \Big \| \mathbb{E} \left[ (\mathbf{V}^{'})^T \mathbf{s}_i^{'} (\mathbf{s}_i^{'})^T \mathbf{V}^{'} (\mathbf{V}^{'})^T \mathbf{s}_i^{'} (\mathbf{s}_i^{'})^T \mathbf{V}^{'}  \right] \Big \| , \frac{1}{(N_2^{'})^2} \Bigg \} \\
& \leq \max \Bigg \{ \frac{r \mu_v^{'}}{N_2^{'}}  \Big \| \mathbb{E} \left[ (\mathbf{V}^{'})^T \mathbf{s}_i^{'} (\mathbf{s}_i^{'})^T \mathbf{V}^{'}  \right] \Big \| , \frac{1}{(N_2^{'})^2} \Bigg \} \leq  \frac{r \mu_v^{'}}{(N_2^{'})^2} \quad.
\end{aligned}
\label{eq30}
\end{eqnarray}
Therefore, according to Lemma \ref{lm5} if we set
\begin{eqnarray}
n_s \ge \frac{28}{3} r \mu_v^{'} \log \frac{2 r}{\delta}
\label{eq31}
\end{eqnarray}
then,
\begin{eqnarray}
\mathbb{P} \left[ \frac{N_2^{'}}{n_s} \Bigg \|  (\mathbf{V}^{'})^T \mathbf{S}^{'} (\mathbf{S}^{'})^T \mathbf{V}^{'}  - \frac{n_s}{N_2^{'}} \mathbf{I}  \Bigg  \| > \frac{1}{2} \right] \leq \delta \quad.
\label{eq32}
\end{eqnarray}
If $\sigma_1$ and $\sigma_r$ denote the largest and smallest singular values of $(\mathbf{S}^{'})^T \mathbf{V}^{'}$, respectively, then
\begin{eqnarray}
\frac{n_s}{2 N_2^{'}} \leq \sigma_1^2 \leq \sigma_r^2 \leq \frac{3 n_s}{2 N_2^{'}} \: .
\label{eq33}
\end{eqnarray}
 Accordingly, the matrix $(\mathbf{S}^{'})^T \mathbf{V}^{'}$ is a full rank matrix with probability at least $1- \delta$.
\smallbreak

\noindent\textbf{Proof of Lemma \ref{lm6}}\\
Since we use random sampling with replacement, the number of inliers in the selected columns follows a Binomial distribution. Suppose $n_i$ is the number of sampled inlier columns. Then, $n_i$ is a Binomial random variable with $m_1$ independent experiments, each with success probability $\frac{N_2^{'}}{N_2}$. Therefore, using Chernoff bound for Binomial distributions \cite{lamport42}, we have
\begin{align}
\mathbb{P} \left( \alpha \leq n_i  \leq  \alpha(2\beta -1)  \right)   \ge
 1 - 2 \exp \left( - \frac{\alpha^2 (\beta - 1)^2}{3 \alpha \beta}\right).
\label{eq35}
\end{align}
Thus, if
$\beta \ge 2 + \frac{3}{\alpha} \log \frac{2}{\delta}$,
 the RHS of (\ref{eq35}) is lower-bounded by $(1 - \delta)$.
\smallbreak

\noindent\textbf{Proof of Lemma \ref{lm7}}\\
Since we use random sampling with replacement, the number of outliers $n_o$ in the matrix $\mathbf{D}_s$ follows a Binomial distribution
with $m_1$ independent experiments, each having success probability $\frac{K}{N_2}$. Using Chernoff bound we have that
\begin{align}
&\mathbb{P} \left( \alpha \left( \frac{\beta K}{N_2^{'}} - \frac{1}{c} \right) \leq n_o  \leq  \alpha \left( \frac{\beta K}{N_2^{'}} + \frac{1}{c} \right)  \right) \\
& \ge 1 - 2 \exp \left( - \frac{\alpha^2}{3 c^2 \alpha \beta \frac{K}{N_2^{'}}} \right) \:.
\label{eq39}
\end{align}
Therefore, the RHS of (\ref{eq39}) is greater than $1 - \delta$ if (\ref{eq37}) is satisfied.
\\

\noindent\textbf{Proof of Lemma \ref{lemma: embd 1}}\\
To prove Lemma \ref{lemma: embd 1} and Lemma \ref{lemma: embd 2}, we make use of the following result from  \cite{lamport39} and \cite{lamport40}.
\begin{lemma}
Let $\cup_{i=1}^{n} \mathcal{L}_i$ denote a union of $n$ linear subspaces in $\mathbb{R}^{N_1}$, each of dimension at most $d$. For fixed $\delta \in (0,1)$ and $\epsilon \in (0,1)$, suppose $\mathbf{\Phi}$ is an $m_2 \times N_1$ matrix satisfying the distributional JL property with
\begin{eqnarray}
m_2 \ge \frac{d \log (42/\epsilon) + \log n + \log \frac{2}{\delta}}{f (\frac{\epsilon}{\sqrt{2}})}.
\label{eq48}
\end{eqnarray}
Then,
\begin{eqnarray}
(1 - \epsilon) \| \mathbf{v} \|_2^2 \leq  \| \mathbf{\Phi}\mathbf{v} \|_2^2 \leq (1 + \epsilon) \| \mathbf{v} \|_2^2
\label{eq49}
\end{eqnarray}
holds simultaneously for all $\mathbf{v} \in \cup_{i=1}^{K} \mathcal{L}_i$ with probability at least $(1-\delta)$.
\label{lm10}
\end{lemma}

According to Lemma \ref{lm10}, if $m_2$ satisfies (\ref{eq:  suffi m_2 1}), then (\ref{eq49}) holds with $\epsilon = 1/\sqrt{2}$ for all the vectors in the column space of $\mathbf{D}_s$ with probability at least $1-  \delta$. If (\ref{eq49}) holds for all $\mathbf{v} \in \spn(\mathbf{D}_s)$, then it is straightforward to show that the rank of $\mathbf{\Phi \mathbf{D}_s}$ is equal to the rank of $\mathbf{D}_s$.
\smallbreak

\noindent\textbf{Proof of Lemma \ref{lemma: embd 2}}\\
Suppose $\mathbf{D}_s$ contains $k$ outlying data points. Assume $\{ \cup \mathcal{T}_i \}_{i=1}^{k}$ represents a union of $k$ linear subspaces in $\mathbb{R}^{N_1}$, where each subspace is spanned by $\{ \mathbf{U}, \mathbf{C}_i \}$ and $\mathbf{C}_i$ is the $i^{\text{th}}$ non-zero column of $\mathbf{C}_s$. According to Data model 1, the subspace $\mathcal{T}_i$ is an $(r+1)$-dimensional subspace since $\mathbf{C}_i$  does not lie in the column space of $\mathbf{L}$. Suppose $\mathbf{\Phi}$ is a stable embedding of the union of subspaces $\{ \cup \mathcal{T}_i \}_{i=1}^{k}$. Then, the dimension of the subspaces $\{ \mathcal{T}_i \}_{i=1}^{k}$ is not changed during the embedding operation. Accordingly, the columns of $ \mathbf{\Phi} \mathbf{C}_s$ do not lie in the column space of $ \mathbf{\Phi} \mathbf{L}$. Note that $q \ge k$. Thus, according to Lemma \ref{lm10}, if
\begin{eqnarray}
m_2 \ge \frac{(r+1) \log (42 \sqrt{2}) + \log q + \log \frac{2}{\delta}}{f (\frac{1}{{2}})}.
\end{eqnarray}
then the rank of $\mathbf{\Phi} \mathbf{L}$ is equal to the rank of $\mathbf{L}$ and the non-zero columns of $\mathbf{\Phi} \mathbf{C}_s$ do not lie in the column space of $\mathbf{\Phi} \mathbf{L}$, with probability at least $1 - \delta$.
\smallbreak
\noindent\textbf{Proof of Lemma \ref{lemma row 1}}\\
Since the rank of $\mathbf{L}_s$ is equal to $r$, $\mathbf{L}$ and $\mathbf{L}_s$ have the same column space.
Suppose $\mathbf{C}_s$ contains $k$ outlying columns.
We break this proof into two steps. In the first step, it is shown that the rank of $\mathbf{L}_s$ is equal to the rank of $\mathbf{\Phi} \mathbf{L}_s$ whp.
Define ${\mathbf{U}_s^{\phi}}^\perp$ as an orthonormal basis for the complement of the column space of $\mathbf{L}_s^{\phi} = \mathbf{\Phi} \mathbf{L}_s$. If the rank of $\mathbf{L}_s^{\phi}$ is equal to $r$, then ${\mathbf{U}_s^{\phi}}^\perp \in \mathbb{R}^{m_2 \times (m_2 - r)}$.
 In the second step, it is proven that the rank of
\begin{eqnarray}
({\mathbf{U}_s^{\phi}}^\perp)^T\mathbf{C}_s^{\phi}
\label{eq proj}
\end{eqnarray}
is equal to $k$ whp. The matrix (\ref{eq proj}) is the projection of the columns of $\mathbf{C}_s^{\phi}$ onto the complement of the column space of $\mathbf{L}_s^{\phi}$. Lemma \ref{lemma row 1} follows if these two requirements are satisfied.
For the first part, we make use of the following Lemma from \cite{candes2007sparsity,myp}.
\begin{lemma}
Suppose $m_2$ rows are sampled uniformly at random (without replacement) from the matrix $\mathbf{L}$ with rank $r$. If
\begin{eqnarray}
m_2 \ge r\eta_u^2  \max \left( c_1 \log r , c_2 \log\left(\frac{3}{\delta}\right) \right),
\label{eq27}
\end{eqnarray}
then the selected rows of the matrix $\mathbf{L}$ span the row space of $\mathbf{L}$ with probability at least $(1-\delta)$, where $c_1$ and $c_2$ are numerical constants.
\label{lm on paper}
\end{lemma}
The matrices $\mathbf{L}_s$ and $\mathbf{L}$ have the same column space. Thus, if $m_2$ satisfies (\ref{eq27}), the rank of $\mathbf{\Phi}\mathbf{L}_s$ is equal to the rank of $\mathbf{L}_s$ with probability at least $1 - \delta$.
Now we prove the second part. Assume the first part is satisfied, i.e., the rank of $\mathbf{L}_s^{\phi}$ is equal to $r$. It is easy to show that since ${\mathbf{U}_s^{\phi}}^\perp$ is an orthonormal matrix, then the  elements of matrix (\ref{eq proj}) are zero-mean independent normal random variables with equal variance. In order to show that the rank of (\ref{eq proj}) is equal to $k$, we make use of the following lemma from \cite{lamport14,davidson2001local}.

\begin{lemma}
Let $\mathbf{A}$ be an $N \times n $ matrix whose entries are independent standard normal variables. Then for every $t \ge \sqrt{2 \log 2/\delta} $,
\begin{eqnarray}
\sqrt{N} - \sqrt{n} - t \leq \sigma_{min} (\mathbf{A}) \leq \sigma_{max} (\mathbf{A}) \leq \sqrt{N} + \sqrt{n} + t \:
\end{eqnarray}
with probability at least $1 - \delta$, where $\sigma_{min} (\mathbf{A})$ and $\sigma_{max} (\mathbf{A})$ are the minimum and maximum singular values of $\mathbf{A}$.
\label{lemma: singulars}
\end{lemma}

Define $\mathbf{Z}$ as the non-zero columns of the matrix in (\ref{eq proj}). Based on Lemma (\ref{lemma: singulars}), to prove that the rank of $\mathbf{Z}$ is equal to $k$ with probability at least $1 - \delta$, it suffices to have
$$\sqrt{m_2 - r} - \sqrt{q}  > \sqrt{2 \log 2/\delta}.$$
\smallbreak
\noindent\textbf{Proof of Lemma \ref{lemma row 2}}\\
Similar to the proof of Lemma \ref{lemma row 1}, we can guarantee that if $m_2$ satisfies inequality (\ref{m_2 row 2}), then the rank of  $\mathbf{\Phi}\mathbf{L}$ is equal to the rank of $\mathbf{L}$ with probability $1- \delta$.

Suppose $\mathbf{c}$ is a non-zero column of $\mathbf{C}_s$. Similar to the analysis provided in the proof of Lemma \ref{lemma row 1}, if
$$\sqrt{m_2 - r} - 1  > \sqrt{2 \log 2/\delta} \: , $$
then $\mathbf{\Phi} \mathbf{c}$ do not lie in the column space of $\mathbf{\Phi}\mathbf{L}$ with probability at least $1- \delta$. Thus, if
$$m_2 > r + 1 + 2 \log 2q /\delta + 2\sqrt{2 \log 2q /\delta} \: , $$
then the non-zero columns of $\mathbf{\Phi} \mathbf{C}_s$ do not lie in the column space of $\mathbf{\Phi} \mathbf{L}$ with probability at least $1 - \delta$.
\smallbreak

\noindent\textbf{ Proof of Theorem \ref{theorem 1}}\\
Algorithm 1 with RED recovers the exact subspace if: \\
\textbf{[I]} The inliers of $\mathbf{D}_s$ span the column space of $\mathbf{L}$, and each inlier of $\mathbf{D}_s$ lies in the span of the other inlier columns of $\mathbf{D}_s$. \\
\textbf{[II]} If $\mathbf{D}_s$ contains $k$ outlying columns, the rank of $\mathbf{\Phi} \mathbf{D}_s$ is equal to $r+k$.

Lemma \ref{lm4} and Lemma \ref{lm6} establish a sufficient condition for $m_1$ to guarantee \textbf{[I]} whp. Given Assumption 1, the rank of $\mathbf{D}_s$ is equal to $r+k$.  Lemma \ref{lemma: embd 1} provides a sufficient condition for $m_2$ to ensure that the rank of $\mathbf{\Phi}\mathbf{D}_s$ is equal to the rank of $\mathbf{D}_s$ whp, i.e., \textbf{[II]} is guaranteed whp.
 In addition, Lemma \ref{lm7} provides an upper-bound on the number of sampled outliers. Therefore, according to Lemma \ref{lm4}, Lemma \ref{lm6}, Lemma \ref{lemma: embd 1} and Lemma \ref{lm7}, if (\ref{suff thorem 1}) is satisfied, Algorithm 1 with RED recovers the correct subspace with probability at least $1 - 4 \delta$.

In addition, similar to the analysis provided in the proof of Lemma \ref{lemma: embd 2}, if
\begin{eqnarray}
\begin{aligned}
m_2 \ge \frac{(r+1) \log (42 \sqrt{2}) + \log K + \log \frac{2}{\delta}}{f (\frac{1}{{2}})}   \: ,
\end{aligned}
\end{eqnarray}
then the non-zero columns of $\mathbf{\Phi}\mathbf{C}$ do not lie in the column space of $\mathbf{\Phi}\mathbf{L}$ with probability at least $1 - \delta$. Thus, if the subspace is learned correctly, (\ref{outlier_detect 1}) identifies the outlying columns correctly with probability at least $1 - \delta$.
\smallbreak

\noindent\textbf{Proof of Theorem \ref{Theorem 2}}\\
The proof of Theorem \ref{Theorem 2} is similar to the proof of Theorem \ref{theorem 1} but we need to make use of Lemma \ref{lemma row 1} (instead of Lemma \ref{lemma: embd 1}) to guarantee \textbf{[II]} whp. Therefore, according to Lemma \ref{lm4}, Lemma \ref{lm6}, Lemma \ref{lemma row 1} and Lemma \ref{lm7}, if the requirements of Theorem \ref{Theorem 2} are satisfied, Algorithm 1 with RRD recovers the correct subspace with probability at least $1 - 5 \delta$.
In addition, similar to the analysis provided in the proof of Lemma \ref{lemma row 2}, if
\begin{eqnarray}
\begin{aligned}
   m_2 \ge
 r+ 1 +2 \log \frac{2 K}{\delta} + \sqrt{8 \: \log \frac{2 K}{\delta} }  \Bigg] \:,
\end{aligned}
\end{eqnarray}
then the non-zero columns of $\mathbf{\Phi}\mathbf{C}$ do not lie in the column space of $\mathbf{\Phi}\mathbf{L}$ with probability at least $1 - \delta$. Thus, if the subspace is learned correctly, (\ref{outlier_detect 1}) identifies the outlying columns correctly with probability at least $1 - \delta$.
\smallbreak

\noindent\textbf{Proof of Theorem \ref{Theorem 3}}\\
In order to guarantee that Algorithm 2  recovers the exact subspace, we have to ensure that\\
\textbf{(a)} The columns of $\mathbf{L}_s$ span the column space of $\mathbf{L}$. \\
\textbf{(b)} Requirement 2 is satisfied.\\
\textbf{(c)} The optimization problem (\ref{convex_in_alg}) yields correct decomposition, i.e., the column space of $\hat{\mathbf{L}}_s^{\phi}$ is equal to the column space of $\mathbf{\Phi}\mathbf{L}$ and the non-zero columns of  $\hat{\mathbf{C}}_s^{\phi}$ and $\mathbf{\Phi} \mathbf{C}_s$ are at the same locations.

\noindent\textbf{Guarantee for (a)}:\\
 It suffices to show that the rank of $\mathbf{V}^T \mathbf{S}$ is equal to $r$.
According to the proof of Lemma \ref{lm4}, if we set
\begin{eqnarray}
m_1 \ge 10 \: r \mu_v \log \frac{2 r}{\delta}
\label{eq31n}
\end{eqnarray}
then,
\begin{eqnarray}
\mathbb{P} \left[ \frac{N_2}{m_1} \Bigg \|  \mathbf{V}^T \mathbf{S} \mathbf{S}^T \mathbf{V}  - \frac{m_1}{N_2} \mathbf{I}  \Bigg  \| > \frac{1}{2} \right] \leq \delta \:.
\label{eq32n}
\end{eqnarray}
If $\sigma_1$ and $\sigma_r$ denote the largest and smallest singular values of $\mathbf{S}^T \mathbf{V}$, respectively, then
\begin{eqnarray}
\frac{m_1}{2 N_2} \leq \sigma_1^2 \leq \sigma_r^2 \leq \frac{3 m_1}{2 N_2}
\label{eq33n}
\end{eqnarray}
with probability at least $1- \delta$. Accordingly, the matrix $\mathbf{V}^T \mathbf{S}$ is a full rank matrix with probability at least $1- \delta$. In addition, we study the row space coherency of matrix $\mathbf{L}_s$ since it is used to derive the  guarantee for \textbf{(c)}. The projection of the standard basis onto the row space of $\mathbf{L}_{s}$ can be written as
\begin{eqnarray}
\begin{aligned}
&\underset{i}{\max} \| \textbf{P}_{\mathbf{S}^T \mathbf{V}} \mathbf{e}_i \|_2^2 = \underset{i}{\max} \| \mathbf{S}^T \mathbf{V} (\mathbf{V}^T \mathbf{S} \mathbf{S}^T \mathbf{V})^{-1} \mathbf{V}^T \mathbf{S} \mathbf{e}_i \|_2^2 \\
& \leq \underset{j}{\max} \| \mathbf{S}^T \mathbf{V} (\mathbf{V}^T \mathbf{S} \mathbf{S}^T \mathbf{V})^{-1} \mathbf{V}^T  \mathbf{e}_j \|_2^2\\
&\leq \| \mathbf{S}^T \mathbf{V} (\mathbf{V}^T \mathbf{S} \mathbf{S}^T \mathbf{V})^{-1} \|^2 \| \mathbf{V}^T  \mathbf{e}_j \|_2^2 \\
& \leq \frac{\mu_v r}{N_2} (\frac{\sigma_1^2}{\sigma_r^4})= \frac{\mu_v r}{N_2} \frac{6 N_2}{m_1}=\frac{6 \mu_v r}{m_1}
\end{aligned}
\label{eq46}
\end{eqnarray}
where $ (\mathbf{S}^T \mathbf{V} (\mathbf{V}^T \mathbf{S} \mathbf{S}^T \mathbf{V})^{-1} \mathbf{V}^T \mathbf{S})$ is the projection matrix onto the column space of $\mathbf{S}^T \mathbf{V}$. The first inequality follows from the fact that $\{ \mathbf{S} \mathbf{e}_i \}_{i=1}^{m_1}$ is a subset of $\{ \mathbf{e}_j \}_{j=1}^{N_2}$. The second inequality follows from Cauchy-Schwarz inequality and the third inequality follows from (\ref{eq33n}).

\smallbreak
\noindent\textbf{Guarantee for (b)}:\\
Suppose that \textbf{(a)} is true. If $\mathbf{q}$ is the number of outliers of $\mathbf{D}_s$, Lemma \ref{lemma: embd 2} provides a sufficient condition for $m_2$ (inequality (\ref{eq:  suffi m_2 2})) to guarantee that these requirements are satisfied.
\smallbreak

\noindent\textbf{Guarantee for (c)}:\\
Suppose \textbf{(a)} and \textbf{(b)} are satisfied.
First, let us review the theoretical result provided in \cite{lamport10} which supports the performance of the convex algorithm (\ref{eq6}).
\begin{lemma}
Suppose $\mathbf{D}$ follows Data model 1 and define $\mathbf{L}^{*}$ and $\mathbf{C}^{*}$ as the optimal point of (\ref{eq6}). If
\begin{eqnarray}
K \leq \left(  \frac{1}{1 + (121/9) r \gamma }    \right) N_2 \quad \text{and} \quad \lambda = \frac{3}{7 \sqrt{K}},
\label{eq47}
\end{eqnarray}
then the column space of $\mathbf{L}^{*}$ is equal to the column space of $\mathbf{L}$ and the location of non-zero columns of $\mathbf{C}^{*}$ indicate the location of non-zero columns of $\mathbf{C}$.
\label{lm9}
\end{lemma}
The matrix $\mathbf{D}^{\phi}_s$ can be expressed as $\mathbf{D}^{\phi}_s = \mathbf{L}^{\phi}_s + \mathbf{C}^{\phi}_s$, where $\mathbf{L}^{\phi}_s = \mathbf{\Phi}\mathbf{L} \mathbf{S}$ and $\mathbf{C}^{\phi}_s = \mathbf{\Phi}\mathbf{C} \mathbf{S}$. If the rank of $\mathbf{\Phi} \mathbf{L}$ is equal to $r$, then $\mathbf{L}_s$ and $\mathbf{L}_s^{\phi}$ have the same row space. Thus, if $\mathbf{V}_s^{\phi}$ is an orthonormal basis for the row space of $\mathbf{L}^{\phi}_s$, then from (\ref{eq46})
\begin{eqnarray}
\underset{i}{\max} \|(\mathbf{V}_s^{\phi})^T \mathbf{e}_i\|_2^2 \leq \frac{6 r \mu_v }{m_1}.
\label{eq54}
\end{eqnarray}
Define $n_{L^{\phi}_s}$ as the   number of non-zero columns of $\mathbf{L}^{\phi}_s$. Therefore,
\begin{eqnarray}
\underset{i}{\max} \|(\mathbf{V}^{\phi}_s)^T \mathbf{e}_i\|_2^2 \leq \frac{6 r \mu_v }{m_1} \leq  \frac{6 r \mu_v }{n_{L^{\phi}_s}} .
\label{eq55}
\end{eqnarray}
Suppose $m_1 = \zeta \frac{N_2}{N_2^{'}}$.
According to Lemma \ref{lm7}, if
$
\zeta \ge 3 g^2 \frac{K}{N_2^{'}} \log \frac{2}{\delta},
$
then the number of outlying columns of $\mathbf{D}^{\psi}_s$ is less than or equal to
\begin{eqnarray}
\zeta \left( \frac{K}{N_2^{'}} + \frac{1}{g} \right)
\label{eq57}
\end{eqnarray}
with probability at least $(1 - \delta)$ where $g$ can be any number greater than one. Therefore, if
$
m_1 \ge \frac{N_2}{N_2^{'}} \left( 3 g^2 \frac{K}{N_2} \log \frac{2}{\delta} \right)
$
 and
\begin{eqnarray}
g \ge \frac{N_2^{'}}{N_2} \left( 1 + 6 r \mu_v (121/9) \right) \: ,
\label{eq59}
\end{eqnarray}
then according to Lemma \ref{lm9}, the column space of $\hat{\mathbf{L}}_s^{\phi}$ is equal to the column space of $\mathbf{\Phi}\mathbf{L}$ and the non-zero columns of  $\hat{\mathbf{C}}_s^{\phi}$ and $\mathbf{\Phi} \mathbf{C}_s$ are at the same locations provided that
\begin{eqnarray}
\frac{K}{N_2^{'}} \leq \frac{g \frac{N_2}{N_2^{'}} - (1 + 6 r \mu_v (121/9))}{g (1+6 r \mu_v (121/9))} .
\label{eq60}
\end{eqnarray}

Therefore, if the requirements of Theorem \ref{Theorem 3} are satisfied, Algorithm 2 with RED extracts the exact subspace with probability at least $1 - 3 \delta$. In addition, according to the analysis provided in the proof of Lemma \ref{lemma: embd 2}, if $m_2$ satisfies the requirement of Theorem \ref{Theorem 3}, then the columns of $\mathbf{\Phi} \mathbf{C}_s$ do not lie in the column space of $\mathbf{\Phi} \mathbf{L}$, and the non-zero columns of $\mathbf{\Phi} \mathbf{C}$ do not lie in the column space of $\mathbf{\Phi} \mathbf{L}$ whp, i.e., if the exact subspace is retrieved, (\ref{outlier_detect 1}) identifies the outlying columns correctly whp.
\smallbreak

\noindent\textbf{Proof of Theorem \ref{theorem 4}}\\
The proof of Theorem \ref{theorem 4} is similar to the proof of Theorem \ref{Theorem 3}. But, we use Lemma \ref{lemma row 2} to establish a sufficient condition on $m_2$ to guarantee \textbf{(b)}. In addition, according to the analysis in the proof of Lemma \ref{lemma row 2}, if $m_2$ satisfies the requirement of Theorem \ref{theorem 4}, not only is Requirement 2 satisfied whp,
but also the non-zero columns of $\mathbf{\Phi} \mathbf{C}$ do not lie in the column space of $\mathbf{\Phi} \mathbf{L}$ whp, i.e., (\ref{outlier_detect 1}) identifies the outlying columns correctly whp in case of exact subspace recovery.

\bibliographystyle{IEEEtran}

redpajama_set_name: RedPajamaArXiv


text:
Public Opinion on 'Don't Ask, Don't Tell'
Nov. 30, 2010 , at 3:56 PM
By Brian J. McCabe
The Pentagon on Tuesday released its long-awaited report on "don't ask, don't tell," the policy that allows gay men and women to serve in the military as long as they keep their sexual orientation quiet. The report, the result of a nine-month study, said that repealing the law would present a low risk to military effectiveness. It also found that 70 percent of service members believe that the impact of repealing the law would be positive, mixed or of no consequence at all.
But how does the rest of America feel about the 17-year-old policy?
Public opinion on the service of gay men and lesbians in the military falls into three categories. The first holds that they should be allowed to serve openly. The second position — held by proponents of "don't ask, don't tell" – holds that gay men and lesbians should be allowed to serve in the military as long as they don't disclose their sexual orientation. And the final position holds that they should not be allowed to serve in the military at all. For shorthand, we can call these positions the permissive, the restrictive and the prohibitive.
To measure public opinion on the service of gay men and lesbians in the military, pollsters typically rely on one of two questions. One type of question asks about allowing gay men and lesbians to openly serve in the military (e.g., "Do you favor or oppose permitting people who are openly gay or lesbian to serve in the military?" CNN/Opinion Research Corporation Poll, November). This wording differentiates the permissive position from the other two. It tells us how many people support open service, but among nonsupporters, it doesn't tell us how many favor an outright ban or how many support service by gay men and lesbians who do not disclose their orientation.
The second type of question asks about allowing gay men and lesbians to serve without reference to doing so openly (e.g., "Do you favor or oppose allowing gay men and lesbians to serve in the military?" CBS News Poll, October). This wording differentiates the prohibitive position from the other two. Among those who favor allowing gay men and lesbians to serve, though, it doesn't tell use how many support allowing them to do so openly, and how many support allowing them to do so only if they do not disclose their sexual orientation.
Since the Clinton administration implemented "don't ask, don't tell" in 1993, a series of ABC News/Washington Post polls has asked these two questions simultaneously. By comparing results from the ABC News/Washington Post polls, we can evaluate the permissive, restrictive and prohibitive positions simultaneously. (Also, since the survey questions were asked simultaneously on two separate samples, they avoid potential bias from order effects.)
In the chart below, the red series plots results from the question about open service in the military. In 1993, 44 percent of Americans approved of service by gays and lesbians who publicly disclosed their sexual orientation; by 2008, the percentage had risen to 75 percent. This rise by more than 30 percentage points is remarkable, especially compared with trends on other civil rights issues for gay Americans. We can think of this as a trend in support of the permissive attitude of open service.
The blue series plots results from the question about service by gay men and lesbians who do not disclose their sexual orientation. Support for this position rose by 15 percentage points in the same period, to 78 percent, from 63 percent.
And the area above the blue line represents the percentage of Americans who believe gay men and lesbians should not be allowed to serve in the military. Since 1993, support for the prohibitive position has fallen. When "don't ask" was implemented, nearly 40 percent of Americans supported the prohibitive position, according to the ABC News/Washington Post poll; by 2008, support for the prohibitive position had dropped to 22 percent.
What's most interesting about this plot, though, is the narrowing of the gap between the permissive and restrictive position. This gap is the percentage of Americans who believe gay men and lesbians should only be allowed to serve if they don't reveal their sexual orientation. In other words, it's the percentage of Americans who support the status quo. The gap between the permissive and restrictive positions offers an unobtrusive measure of support for the policy position behind "don't ask, don't tell."
From 1993 to 2008, support for the idea that gay men and lesbians should only be allowed to serve if they conceal their identity shrank considerably. In 1993, 19 percent of Americans supported this position; by 2008, only 3 percent of Americans supported this position.
By 2010, support for this position rose slightly (to 8 percent). However, this shift was fueled entirely by Americans moving from the prohibitive position to the restrictive one. From 2008 to 2010, 5 percent of Americans moved from the position that gay men and lesbians should not be allowed to serve in the military to the position that gay men and lesbians should be allowed to serve if they conceal their sexual orientation.
Together, these trends reveal an important shift in attitudes on the service of gay men and lesbians in the military. When the policy was established, none of the three positions had majority support among Americans. Forty-four percent supported open service, 37 opposed any service, and 19 percent supported allowing gay men and lesbians to serve only if they did not reveal their sexual orientation. Today, one position has emerged as the clear preference of the majority of Americans. Seventy-five percent of Americans support open service, 17 oppose any service, and only 8 percent support the compromise position of "don't ask, don't tell."
In 1993, "don't ask, don't tell" offered a compromise for a public deeply divided on the issue of gay men and lesbians serving the military. Today, though, that compromise position – the status quo, enshrined in the policy of "don't ask, don't tell" – would seem to hold very little support among the American public.
[Related Article: Over Time, a Gay Marriage Groundswell]
Gay Rights (55 posts) LGBT (15) Military (8)

redpajama_set_name: RedPajamaCommonCrawl


In this revised and expanded edition of his best-selling book, grilling guru Jim Tarantino explains the art and science of marinades and presents more than 400 savory, sweet, and spicy recipes. Featuring 150 brand-new recipes and sections on brines, cures, and glazes, this marinating bible is chock-full of ideas for preparing moist and flavorful beef, poultry, vegetables, and more—both indoors and out—including:Apple Cider Brine • Zesty Jalapeño Lime Glaze • Tapenade Marinade • Ancho-Espresso Dry Rub • Grilled Iberian Pork Loin with Blood Orange–Sherry Sauce • Vietnamese Grilled Lobster Salad MARINADES, RUBS, BRINES, CURES & GLAZES provides home cooks with a diverse repertoire of mouthwatering recipes and fail-safe techniques, so you can grill, steam, sauté, roast, and broil with confidence.Hundreds of marinades, rubs, brines, cures, glazes, bastes, mops, sops, dipping sauces, spice mixes, caramels, and more.Delicious dishes. Recipes for marinated main courses and sides with a tantalizing array of global flavors, from the deep South to the South Pacific.In-depth info. The know-how you need to understand how marinades react with meats and vegetables, with detailed marinating charts.Indispensable ingredients. Lists of essential foodstuffs to stock your pantry for a full repertoire of recipes and endless culinary improvisation.Tips & tricks for the kitchen & the grill. How to cure and brine seafood, smoke meat to perfection, get creative with jerky, and tons of other useful techniques.


text:
/* ---- HTML5 CSS Reset Minified - Eric Meyer ---- */

html,body,div,span,object,iframe,h1,h2,h3,h4,h5,h6,p,blockquote,pre,abbr,address,cite,code,del,dfn,em,img,ins,kbd,q,samp,small,strong,sub,sup,var,b,i,dl,dt,dd,ol,ul,li,fieldset,form,label,legend,table,caption,tbody,tfoot,thead,tr,th,td,article,aside,canvas,details,figcaption,figure,footer,header,hgroup,menu,nav,section,summary,time,mark,audio,video{margin:0;padding:0;border:0;outline:0;font-size:100%;vertical-align:baseline;background:transparent}
body{line-height:1}
article,aside,details,figcaption,figure,footer,header,hgroup,menu,nav,section{display:block}
nav ul{list-style:none}
blockquote,q{quotes:none}
blockquote:before,blockquote:after,q:before,q:after{content:none}
a{margin:0;padding:0;font-size:100%;vertical-align:baseline;background:transparent;text-decoration:none; color:inherit;}
mark{background-color:#ff9;color:#000;font-style:italic;font-weight:bold}
del{text-decoration:line-through}
abbr[title],dfn[title]{border-bottom:1px dotted;cursor:help}
table{border-collapse:collapse;border-spacing:0}
hr{display:block;height:1px;border:0;border-top:1px solid #ccc;margin:1em 0;padding:0}
input,select{vertical-align:middle}
li{list-style:none}

/* ---- base ---- */

html,body{
    width:100%;
    height:100%;
    background:#111;
}

html{
  -webkit-tap-highlight-color: rgba(0, 0, 0, 0);
    font-family: 'Roboto', sans-serif;
}

canvas{
  display:block;
  vertical-align:bottom;
}

/* ---- Layout ---- */

/* ---- Module ---- */

.connectionContainer {
    position: absolute;
    right: 0;
    margin: 10px;
    color: #DDDDDD;
}

.titleWrapper{
    position: absolute;
    top: 100px;
    text-align: center;
    width: 100%;
}

    .title{
        color: #FFFFFF;
        font-size: 6em;
    }

    @media screen and (max-width: 700px) {
      .title {
        font-size: 4em;
        }
    }

    @media screen and (max-width: 500px) {
      .title {
        font-size: 2em;
        }
    }

    .sub-title{
        color: #B3B3B3;
        font-size: 2em;
        font-weight: 100;
    }

    @media screen and (max-width: 700px) {
      .sub-title {
        font-size: 1.5em;
        }
    }

    @media screen and (max-width: 500px) {
      .sub-title {
        font-size: 1em;
        }
    }

    .particles-js{
      width: 100%;
      height: 350px;
      background-size: cover;
      background-position: 50% 50%;
      background-repeat: no-repeat;
    }

    .mainPage {
      width: 100%;
        background-color: white;
        padding-top: 20px;
        padding-bottom: 50px;
    }
        .titleCourseTable {
            text-align: center;
            margin: 30px;
            font-size: 1.5em;
            color: #555555
        }
        .courseTable {
                background-color: #EEEEEE;
                margin: auto;
                width: 60%;
                text-align: center;
                font-size: 1.5em;
        }

            .courseTable a {
                color: #555555;
            }

            .courseTable a:hover {
                color: #777777;
            }

        .courseTable td {
                padding: 20px 0;
        }

        .footer {
          height: 50px;
          background-color: #212121;
          color: #eeeeee;
          line-height: 50px;
          margin-top: 15px;
          font-weight: lighter;
          /*position:absolute;
          bottom:0;*/
          width: 100%;
          text-align: center;
        }

/* ---- State ---- */

/* ---- Theme ---- */

redpajama_set_name: RedPajamaGithub


text:
Surfing Banned At World's Most Famous Big Wave Spot
"Failure to comply with this determination incurs in a criminal offence punished by law."
5 November 2020 by James Booth
In response to the massive gathering of voyeurs, officials have banned surfing at Nazaré, Portugal's premier big wave attraction, and one of the world's most iconic surf spots.
This follows last week's "century swell," which saw everything from potentially world-record-breaking rides, altercations between jetski drivers and terrifying wipeouts.
A post shared by Kai Lenny (@kai_lenny) on Nov 3, 2020 at 6:52am PST
Portugal's National Health Commission announced the ban on Wednesday, November 4th. It is to remain in place "until further notice."
Surfline reports, it's "understood that the Mayor of Nazaré is working to allow freesurfers access to the water, outside of 'events.'"
The ban has come at a poor time for those hoping to watch the Nazaré Tow Surfing Challenge, whose waiting period started on the 2nd of November.
A post shared by Lifestyle Photography (@jairodiazphoto) on Nov 1, 2020 at 12:26pm PST
A photo of a statement from the harbour HQ, obtained by Magic Seaweed, reads (translated from Portuguese):
"In the current context of the pandemic in Portugal, as determined by the regional health delegate and the regional health administration, Free Surf and Tow-in surfing are banned at Praia do Norte, due to the promotion of the public agglomeration, which constitutes an increased risk for the public health. Failure to comply with this determination incurs in a criminal offence punished by law."
"There were too many people on the beach [to watch last week's swell], 20-30k people on the beach man, so yeah, maybe it's the right decision," Portuguese big wave surfer Nic Von Rupp told Magic Seaweed.
Andrew Cotton, an English big wave surfer, told Magic Seaweed he had no plans to appeal the decision: "I understand their position and it's for the benefit and safety of others and the local community. It effects a lot more people that the surfers though, which is a great shame."
Nazaré regular Rafael Tapia, however, told Magic Seaweed: "I think it's a terrible decision."
Though Tapia recognises "the situation on the cliff was chaos," he told Magic Seaweed he believes there are smarter ways of solving the problem.
"Considering that it's so easy to block the entrances to Nazare, I hope this decision is reviewed. Feels like us, the surfers, will be paying for the irresponsible behaviours of spectators. It's our passion, our job and authorities can easily control that. Although the risk of getting injured in Nazare is quite high, it's very unlikely we will put pressure on the hospital system, but that is not a reason surfing should be banned."
If DMARGE had to guess, we'd say the closure is symbolic (perhaps like Manly and Bondi's temporary closures earlier this year), intended to deter visitors more so than surfers, and that a resolution to keep the professional sportspeople happy will soon be underway.
Australian Big Wave Surfer Mark Mathews Reveals The Secret To True Courage
I Surfed Australia's Scariest Wave & This Is What I Discovered
TOPICS: Portugal


All types of Civil work like Interlocking, Tiling, painting works.
Electrical, Plumbing and Air conditioning works.
Your find is more than expected, trust us you will get more value than your money.
It may please be noted that we have a team who will pick up responsibilities of above mentioned Jobs on your advice.


�]有留下�z�诘乃勒撸� 需要有�z�a管理人�兔ι暾��z�a委任��, 而�@���^程可能��花上好�啄瓴磐瓿桑� 若家人是依��@��a�^生活, 在�@段�r�g�如何�^日子呢?
Have you made a nomination regarding your EPF/Insurance, House(s), Cash/Savings, Unit Trust investments/Shares, car(s), etc ? If your answer is NO to any of the above, then you may be adding to the statistics.