{'fraction_non_alphanumeric': 0.055346166493815296, 'fraction_numerical': 0.011661143854501302, 'mean_word_length': 3.921449022781028, 'pattern_counts': {'":': 0, '<': 24, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Dictionary-Based Generalization of Robust PCA Part I: Study of Theoretical Properties

We consider the decomposition of a data matrix assumed to be a superposition of a low-rank matrix and a component which is sparse in a known dictionary, using a convex demixing method. We consider two sparsity structures for the sparse factor of the dictionary sparse component, namely entry-wise and column-wise sparsity, and provide a unified analysis, encompassing both undercomplete and the overcomplete dictionary cases, to show that the constituent matrices can be successfully recovered under some relatively mild conditions on incoherence, sparsity, and rank. We corroborate our theoretical results by presenting empirical evaluations in terms of phase transitions in rank and sparsity, in comparison to related techniques. Investigation of a specific application in hyperspectral imaging is included in an accompanying paper.


I. INTRODUCTION
Leveraging structure of a given dataset is at the heart of all machine learning and data analysis tasks. A priori knowledge about the structure often makes the problem well-posed, leading to improvements in the solutions. Perhaps the most common of these, one that is often encountered in practice, is approximate low-rankness of the dataset, which is exploited by the popular principal component analysis (PCA) [1]. The low-rank structure encapsulates the model assumption that the data in fact spans a lower dimensional subspace than the ambient dimension of the data. However, in a number of applications, the data may not be inherently low-rank, but may be decomposed as a superposition of a low-rank component, and a component which has a sparse representation in a known dictionary. This scenario is particularly interesting in target identification applications [2], [3], where the a priori knowledge of the target signatures (dictionary), can be leveraged for localization.
In this work, we analyze a matrix demixing problem where a data matrix M ∈ R n×m is formed via a superposition of a low-rank component L ∈ R n×m of rank-r for r < min(n, m), and a dictionary sparse part DS ∈ R n×m . Here, the matrix D ∈ R n×d is an a priori known dictionary, and S ∈ R d×m is an unknown sparse coefficient matrix. Specifically, we will study the following model for M: and identify the conditions under which the components L and S can be successfully recovered given M and D by solving appropriate convex formulations. We consider the demixing problem described above for two different sparsity models on the matrix S. First, we consider a case where S has at most s e total non-zero entries (entry-wise sparse case), and second where S has s c non-zero columns (column-wise sparse case). To this end, we develop the conditions under which solving for the column-wise sparse case, will recover L and S for regularization parameters λ e ≥ 0 and λ c ≥ 0, respectively, given the data M and the dictionary D. Here, the known dictionary D can be overcomplete (fat, i.e., d > n) or undercomplete (thin, i.e., d ≤ n).
Here, "D-RPCA" refers to "Dictionary based Robust Principal Component Analysis", while the qualifiers "E" and "C" indicate the entry-wise and column-wise sparsity patterns, respectively. In addition, . * , . 1 , and . 1,2 refer to the nuclear norm, 1 -norm of the vectorized matrix, and 1,2 norm (sum of the 2 norm of the columns), respectively, which serve as convex relaxations of rank, sparsity, and column-wise sparsity inducing optimization, respectively.
These two types of sparsity patterns capture different structural properties of the dictionary sparse component. The entry-wise sparsity model allows individual data points to span low-dimensional subspaces, still allowing the dataset to span the entire space. In case of the column-wise sparse coefficient matrix S, the component DS is also column-wise sparse. Therefore, this model effectively captures the structured (which depend upon the dictionary D) corruptions in the otherwise low-rank structured columns of data matrix M. Note that the non-zero columns of S are not restricted to be sparse in the column-wise sparsity model.

A. Background
A wide range of problems can be expressed in the form described in (1). Perhaps the most celebrated of these is principal component analysis (PCA) [1], which can be viewed as a special case of (1), with the matrix D set to zero. Next, in the absence of the component L, the problem reduces to that of sparse recovery [4]- [6]; See [7] and references therein for an overview of related works. Further, the popular framework of Robust PCA tackles a case when the dictionary D is an identity matrix [8], [9]; variants include [10]- [13].
The model described in (1) is also closely related to the one considered in [14], which explores the overcomplete dictionary setting with applications to detection of network traffic anomalies. However, the analysis therein applies to a case where the dictionary D is overcomplete with orthogonal rows, and the coefficient matrix S has a small number of nonzero elements per row and column, which may be restrictive assumptions in some applications.
In particular, for the entry-wise case, the model shown in (1) is propitious in a number of applications. For example, it can be used for target identification in hyperspectral imaging [2], [3], and in topic modeling applications to identify documents with certain properties, on similar lines as [15]. We analyze and demonstrate the application of this model for a hyperspectral demixing task in an application extension of this work [16]. Further, in source separation tasks, a variant of this model was used in singing voice separation in [17], [18]. In addition, we can also envision source separation tasks where L is not low-rank, but can in turn be modeled as being sparse in a known [19] or unknown [20] dictionary.
For the column-wise setting, model (1) is also closely related to outlier identification [21]- [24], which is motivated by a number of contemporary "big data" applications. Here, the sparse matrix S, also called outliers in this regime, may be of interest and can be used in identifying malicious responses in collaborative filtering applications [25], finding anomalous patterns in network traffic [26] or estimating visually salient regions of images [27]- [29].

B. Our Contributions
As described above, we propose and analyze a dictionary based generalization of robust PCA as shown in (1). Here, we consider two distinct sparsity patterns of S, i.e., entry-wise and column-wise sparse S, arising from different structural assumptions on the dictionary sparse component. Our specific contributions for each sparsity pattern are summarized below. Entry-wise case: We make the following contributions towards guaranteeing the recovery of L and S via the convex optimization problem in D-RPCA(E). First, we analyze the thin case (i.e. d ≤ n), where we assume that the matrix S has at most s e = O( m r ) non-zero elements globally, i.e., S 0 ≤ s e Next, for the fat case, we first extend the analysis presented in [14] to eliminate the orthogonality constraint on the rows of the dictionary D. Further, we relax the sparsity constraints required by [14] on rows and columns of the sparse coefficient matrix S, to study the case when S 0 ≤ s e with at most k = O(d/ log(n)) non-zero elements per column [30]. Hence, we provide a unified analysis for both the thin and the fat case, making the model (1) amenable to a wide range of applications. Column-wise case: We propose and analyze a dictionary based generalization of robust PCA, specifically Outlier Pursuit (OP) [21], wherein the coefficient matrix S admits a column sparse structure which can be viewed as "outliers"; see also [3].
Note that, in this case there is an inherent ambiguity regarding the recovery of the true component pair (L, S) corresponding to the low-rank part and the dictionary sparse component, respectively. Specifically, any pair (L 0 , S 0 ) satisfying M = L 0 + DS 0 = L + DS, where L 0 and L have the same column space, and S 0 and S have the identical column support, is a solution of D-RPCA(C). To this end, we develop the sufficient conditions under which solving the convex optimization in D-RPCA(C) recovers the column space of the low-rank component L, while identifying the outlier columns of S. Here, the difference between D-RPCA(C) and OP being the inclusion of the known dictionary [21].
Next, we demonstrate how the a priori knowledge of the dictionary D helps us identify the corrupted columns via phase transitions in rank and sparsity for recovery of the outlier columns. Specifically, we show that in comparison to OP, D-RPCA(C) works for potentially higher ranks of L, when s c is a fixed proportion of m.
The thin dictionary case -an interesting result: As suggested by [14], when the dictionary is thin, i.e., d < n, one can envision a pseudo-inversed based technique, wherein we pre-multiply both sides in (1) with the Moore-Penrose pseudoinverse D † ∈ R d×n , i.e., D † D = I (this is not applicable for the fat case due to the non-trivial null space of the pseudoinverse). This operation leads to a formulation which resembles the robust PCA (RPCA) [8], [9] model for the entry-wise case and Outlier Pursuit (OP) [21] for the column-wise case, i.e., An interesting finding of our work is that although this transformation algebraically reduces the entry-wise and columnwise sparsity cases to Robust PCA and OP settings, respectively, the specific model assumptions of Robust PCA and OP may not hold for all choices of dictionary size d and rank r. Specifically, we find that in cases where d < r, this pre-multiplication may not lead to a "low-rank" D † L. This suggests that the notion of "low" or "high" rank is relative to the maximum possible rank of D † L, which in this case is min(d, r). Therefore, if d < r, D † L can be full-rank, and the low-rank assumptions of RPCA and OP may no longer hold. As a result, these two models (the pseudo inversed case and the current work) cannot be used interchangeably for the thin dictionary case. We corroborate these via experimental evaluations presented in Section V 1 The rest of the paper is organized as follows. We formalize the problem, introduce the notation, and describe various considerations on the structure of the component matrices in Section II. In Section III, we present our main theorems for the entry-wise and column-wise cases along with discussion on the implication of the results, followed by an outline of the analysis in Section IV. Numerical evaluations are provided in Section V. Finally, we summarize our contributions and conclude this discussion in Section VI with insights on future work.
Notation: Given a matrix X, we use X := σ max (X) for the spectral norm, where σ max (X) denotes the maximum singular value of the matrix, X ∞ := max i, j |X ij |, X ∞,∞ := max i e i X 1 , and X ∞,2 := max i Xe i . Here, X i,j denotes the (i, j) element of X and e i denotes the cannonical basis vector with 1 at the i-th location.

II. PRELIMINARIES
We start formalizing the problem set-up and introduce model parameters pertinent to our analysis. We begin our discussion with our notion of optimality for the two sparsity modalities; we also summarize the notation in Table I in the appendix.

A. Optimality of the Solution Pair
For the entry-wise case, we recover the low-rank component L, and the sparse coefficient matrix S, given the dictionary D, and data M generated according to the model described in (1). Recall that s e is the global sparsity, k denotes the number of non-zero entries in a column of S when the dictionary is fat.
In the the column-wise sparsity setting, due to the inherent ambiguity in the model (1), as discussed in Section I-B, we can only hope to recover the column-space for the low-rank matrix and the identities of the non-zero columns for the sparse matrix. Therefore, in this case any solution in the Oracle Model (defined below) is deemed to be optimal.

B. Conditions on the Dictionary
We require that the dictionary D follows the generalized frame property (GFP) as defined as follows.
Definition D.2. A matrix D satisfies the generalized frame property (GFP), on vectors v ∈ R, if for any fixed vector v ∈ R where v = 0, we have , where α and α u are the lower and upper generalized frame bounds with 0 < α ≤ α u < ∞.
The GFP shown above is met as long as the vectors v are not in the null-space of the matrix D, and D has a finite D . Therefore, for the thin dictionary setting d ≤ n for both entry-wise and column-wise cases R can be the entire space, and GFP is satisfied as long as D has full column rank. For example, D being a frame [31] suffices; see [32] for a brief overview of frames.
On the other hand, for the fat dictionary setting, we need the space R to be structured such that the GFP is met for both the entry-wise and column-wise sparsity cases. Specifically, for the entry-wise sparsity case, we also require that the frame bounds α u and α be close to each other. To this end, we assume that D satisfies the restricted isomtery property (RIP) of order k = O(d/ log(n)) with a restricted isometric constant (RIC) of δ in this case, and that α u = (1 + δ) and α = (1 − δ).

C. Relevant Subspaces
We now define the subspaces relevant for our discussion. For the following discussion, let the pair (L 0 , S 0 ) denote the solution to D-RPCA(E) in the entry-wise sparse case. Further, for the column-wise sparse setting, let (L 0 , S 0 ) denote a solution pair in the oracle model {M, U, I Sc } as defined in D.1, obtained by solving D-RPCA(C).
For the low-rank matrix L, let the compact singular value decomposition (SVD) be defined as where U ∈ R n×r and V ∈ R m×r are the left and right singular vectors of L , respectively, and Σ is the diagonal matrix with singular values on the diagonal. Here, matrices U and V each have orthogonal columns, and the non-negative entries Σ ii = σ i are arranged in descending order. We define L as the linear subspace consisting of matrices spanning the same row or column space as L, i.e., Next, let S e (S c for the column-wise sparsity setting) be the space spanned by d × m matrices with the same non-zero support (column support, denoted as csupp(·)) as S, and let the space D denote the space spanned by the dictionary sparse component under our model be defined as H ∈ S e for entry-wise case, csupp(H) ⊆ I Sc for column-wise case.
Here, I Sc denotes the index set containing the non-zero column index set of S for the column-wise case. Also, we denote the corresponding complements of the spaces described above by appending '⊥'. In addition, we use calligraphic 'P G (·)' to denote the projection operator onto a subspace G, and 'P G ' to denote the corresponding projection matrix. For instance, we define P U (·) and P V (·) as the projection operators corresponding to the column space U and row space V of the low-rank component L. Therefore, for a given matrix X ∈ R n×m , where P U = UU and P V = VV . With this, the projection operators onto, and orthogonal to the subspace L are respectively defined as

D. Incoherence Measures and Other Parameters
We employ various notions of incoherence to identify the conditions under which our procedures succeed. To this end, we first define the incoherence parameter µ, that characterizes the relationship between the low-rank part, L, and the dictionary sparse part DS as, The parameter µ ∈ [0, 1] is the measure of degree of similarity between the low-rank part and the dictionary sparse component.
Here, a larger µ implies that the dictionary sparse component is close to the low-rank part, while a small µ indicates otherwise.
In addition, we also define the parameter β U as which measures the similarity between the orthogonal complement of the column-space U and the dictionary D.
The next two measures of incoherence can be interpreted as a way to identify the cases where for L with SVD as L = UΣV : (a) U resembles the dictionary D, and/or (b) V resembles the sparse coefficient matrix S. In these cases, the low-rank part may mimic the dictionary sparse component. To this end, similar to [14], we define the following to measure these properties respectively as Here, γ U ≤ 1, and achieves the upper bound when a dictionary element is exactly aligned with the column space U of L. Moreover, γ V ∈ [r/nm, 1] achieves the upper bound when the row-space of L is "spiky", i.e., a certain row of V is 1-sparse, meaning that a column of L is supported by (can be expressed as a linear combination of) a column of U. The lower bound here is attained when it is "spread-out", i.e., each column of L is a linear combination of all columns of U. In general, our recovery of the two components is easier when the incoherence parameters γ U and γ V are closer to their lower bounds. Further, for notational convenience, we define constants

III. MAIN RESULTS
We present the main results corresponding to each sparsity structure of S in this section.

A. Exact Recovery for Entry-wise Sparsity Case
Our main result establishes the existence of a regularization parameter λ e , for which solving the optimization problem D-RPCA(E) will recover the components L and S exactly. To this end, we will show that such a λ e belongs to a non-empty interval where 0 ≤ C e < 1 is a constant that captures the relationship between different model parameters, and is defined as and c is defined as Given these definitions, we formalize the theorem for the entry-wise case as following, and its corresponding analysis is provided in Section IV-A.
in (6), the dictionary D ∈ R n×d obeys the generalized frame property D.2 with frame bounds [α , α u ], solving D-RPCA(E) will recover matrices L and S if the following conditions hold: • For d ≤ n, R may contain the entire space and γ U follows • For d > n > C 1 k log(n) for a constant C 1 , R consists of all k sparse vectors, and γ U follows Theorem 1 establishes the sufficient conditions for the existence of λ e to guarantee recovery of (L, S) for both the thin and the fat cases. The conditions on γ U dictated by (7) and (8), for the thin and fat case, respectively, arise from ensuring that λ min e ≥ 0. Further, the condition λ min e < λ max e , translates to the following sufficient condition on rank r in terms of the sparsity s e , for the recovery of (L, S). This relationship matches with our empirical evaluations and will be revisited in Section V-A. We note that for both, thin and fat dictionary case, the conditions are closely related to the incoherence measures (µ, γ V , and γ U ) between the low-rank part, L, the dictionary, D, and the sparse component S. In general, smaller sparsity, rank, and incoherence parameters are sufficient for ensuring the recovery of the components for a particular problem. This is in line with our intuition -the more distinct the two components, the easier it should be to tease them apart. Moreover, we observe that the theorem imposes an an upper-bound on the global sparsity, i.e., s e ≤ s max e = O( m r ). This bound is similar to the result in [21], and is due to the deterministic nature of our analysis w.r.t. the locations of the non-zero elements of coefficients S.

B. Exact Recovery for Column-wise Sparsity Case
Recall that we consider the oracle model in this case as described in D.1 owing to the intrinsic ambiguity in recovery of (L, S); see our discussion in Section I-B. To demonstrate its recoverability, the following lemma establishes the sufficient conditions for the existence of an optimal pair (L 0 , S 0 ). The proof is provided in Appendix B.
Then, our main result for the column-wise case is as follows, and its analysis is provided in Section IV-B.  (5), and any (10), solving D-RPCA(C) will recover a pair of components (L 0 , S 0 ) ∈ {M, U, I Sc }, if the space R is structured such that the dictionary D ∈ R n×d obeys the generalized frame property D.2 with frame bounds [α , α u ], for α > 0.
Moreover, suppose that 1 α l ≤ α u 1, which can be easily met by a tight frame when d < n, or a RIP type condition when . This is of the same order with the upper bound of s c in the Outlier Pursuit (OP) [21].
Our numerical results in Section V further show that D-RPCA(C) can be much more robust than OP, and may recover {U, I Sc } even when the rank of L is high and the number of outliers s c is a constant proportion of m.

A. Proof of Theorem 1
We use dual certificate construction procedure to prove the main result in Theorem. 1; the proofs of all lemmata used here are listed in Appendix A. To this end, we start by constructing a dual certificate for the convex problem shown in D-RPCA(E). Here, we first show the conditions the dual certificate needs to satisfy via the following lemma.
We will now proceed with the construction of the dual certificate which satisfies the conditions outlined by (C1)-(C4) by Lemma 4. Using the analysis similar to [14] (Section V. B.), we construct the dual certificate as for arbitrary X ∈ R n×m . The condition (C1) is readily satisfied by our choice of Γ. For (C2), we substitute the expression for Γ to arrive at = λ e sign(S 0 ). (12) Letting Z := D (I − P U )X(I − P V ) and we can write (12) as P Se (Z) = B Se . Further, we can vectorize the equation above as P Se (vec(Z)) = vec(B Se ). Let b Se be a length s e vector containing elements of B Se corresponding to the support of S 0 . Now, note that vec(Z) can be represented in terms of a Kronecker product as follows, On defining A := (I − P V ) ⊗ D (I − P U ) ∈ R md×mn , we have vec(Z) = Avec(X). Further, let A Se ∈ R s×nm denote the rows of A that correspond to support of S 0 , and let A S ⊥ e correspond to the remaining rows of A. Using these definitions and results, we have A Se vec(X) = b Se . Thus, for conditions (C1) and (C2) to be satisfied, we need Here, the following result ensures the existence of the inverse.
Now, we look at the condition (C3) P L ⊥ (Γ) < 1. This is where our analysis departs from [14]; we write where we have used the fact that (I − P U ) ≤ 1 and The following lemma establishes an upper bound on b Se 2 .
Combining (14), Lemma 5, and Lemma 6, we have Now, combining (15) and the upper bound on λ e defined in (6), we have that (C3) holds. Now, we move onto finding conditions under which (C4) is satisfied by our dual certificate. For this we will bound P Se ⊥ (D Γ) ∞ . Our analysis follows the similar procedure as employed in deriving (16) in [14], reproduced here for completeness. First, by the definition of Γ and properties of the . ∞ norm, we have We now focus on simplifying the term P Se ⊥ (Z) ∞ . By definition of A, and using the fact that vec(Z) = Avec(X), we have P Se ⊥ (Z) = A Se ⊥ vec(X), which implies where we have used the result on vec(X) shown in (13). Now, since b Se ∞ can be written as Now, using the following upper bound on b Se ∞ , and on defining where we have the following bound for Q ∞,∞ .
where 0 ≤ C e < 1 and c is defined as for d > n.
Combining this with (16) and Lemma 8, we have By simplifying (18), we arrive at the lower bound λ min e for λ e as in (6) Conditions for thin D: To simplify the analysis we assume, without loss of generality, that d < m. Specifically, we will assume that d ≤ m αr , where α > 1 is a constant. With this assumption in mind, we will analyze the following cases for the global sparsity, when s e ≤ d and d < s e ≤ m. Case 1: s e ≤ d. For this case c t is given by As per the GFP of D.2, we also require that α u /α ≥ 1. Therefore we arrive at . Further, since γ U ≥ 0, we require the numerator to be positive, and since the lower bound on γ V ≥ r m , we have which also implies s e ≤ m. Now, the condition c t ≥ 0 implies Since, the R.H.S. of this inequality is upper bounded by 1 (achieved when γ U and γ V are zero). This condition on c t is satisfied by our assumption that α u /α ≥ 1. Case 2: d < s e ≤ m. For this case, we have Again, due to the requirement that α u /α ≥ 1, following a similar argument as in the previous case we conclude that and s e ≤ (1−µ) 2 2 m r . As in the previous case the c t ≥ 0 is met by our due to our assumption on the frame bounds.

Conditions for fat D:
To simplify the analysis, we suppose that k < m. Note that in this case, we require that the coefficient matrix S has k-sparse columns. Now, c = c f is given by As for the thin case, we substitute the expression for c f in (19) as follows Again, by GFP we require that α u /α ≥ 1, therefore we have and s e ≤ (1−µ) 2 2 m r , Also, the condition that c f ≥ 0 is met by the assumption that D obeys GFP.
The following lemma states the optimality conditions for the optimal solution pair (L, S). We first propose Γ as the dual certificate, where Hence, the condition (C1) is readily satisfied by our choice of Γ. Now, the condition (C2), defined as P Sc (D Γ) = λ cS , whereS :,j = S:,j S:,j 2 for all j ∈ I Sc ; 0, otherwise. Substrituting the expression for Γ, we need the following condition to hold where b Sc := vec(B Sc ). Next, by letting A := (I − P V ) ⊗ D (I − P U ), using the definition of Z and the properties of the Kronecker product we have vec(Z) = Avec(X). Now, let A Sc denote the rows of A corresponding to the non-zero rows of vec(S) and A S ⊥ c denote the remaining rows, then P Sc (vec(Z)) = A Sc vec(X).
From (25) and (26), we have A Sc vec(X) = b Sc . Therefore, we need the following which corresponds to the least norm solution i.e., X = argmin X X F , s.t. A Sc vec(X) = b Sc ). For this choice of X (24) is satisfied and consequently the condition (C2). Here, the existence of the inverse is ensured by the following lemma.
Lemma 10. If µ < 1 and α > 0, the minimum singular values of A Sc is bounded away from 0 and is given by Upon the existence of such X as defined in (27), (C3) is satisfied if the following condition holds

From (27), this condition translates to
Now, since A Sc (A Sc A Sc ) −1 = 1/σ min (A Sc ) (see the analogous analysis for the entry-wise case), we need σmin(A Sc ) < 1. Now, using Lemma 10 and the following bound on b Sc 2 , Lemma 11. b Sc 2 is upper bounded by λ c √ s c + √ rα u µ.
we have that the condition (C3) holds if  which is satisfied by our choice of λ max c (10). Now, for the condition (C4) we need the following condition to hold true: Note that, here P Sc (D T UV T ) ∞,2 ≤ ξ c . Therefore, using the following result, Lemma 12. An upper bound on P S ⊥ c (Z) ∞,2 is given by the condition (C4) implies that, To this end, if we let C c := αu α (1−µ) 2 γ V β U , (C4) is satisfied by λ min c defined in (10). This completes the proof.
Characterizing λ min c : From (10), we need λ min , and using the fact that s c C c < 1, we arrive at (11).
V. NUMERICAL SIMULATIONS In this section, we empirically evaluate the properties of D-RPCA(E) and D-RPCA(C) via phase transition in rank and sparsity, and compare its performance to related techniques, and to the behavior predicted by Theorem 1 and Theorem 3 in (9) and (11), respectively.

A. Entry-Wise Sparsity Case
Experimental Set-up: We employ the accelerated proximal gradient (APG) algorithm outlined in Algorithm 1 of [14] Recovery of L  and Algorithm 1 of [16] to solve the optimization problem D-RPCA(E). For these evaluations, we fix n = m = 100, and generate the low-rank part L by outer product of two column normalized random matrices of sizes n × r and m × r, with entries drawn from the standard normal distribution. In addition, we draw s e non-zero entries of the sparse component S from the Rademacher distribution, and the dictionary D from the standard normal distribution with normalized columns. We then run 10 Monte-Carlo trials for each pair of rank and sparsity, and for each of these, we scan across 100 values of λ e s in the range of [λ min e , λ max e ] to find the best pair of (L 0 , S 0 ) to compile the results. 2 Discussion: Phase transition in rank and sparsity averaged over 10 trials for dictionaries of sizes d = 5 (thin) and d = 150 (fat), are shown in Fig. 1 and Fig. 2, respectively. We note from Fig. 1 that indeed the empirical relationship between rank and sparsity for the recovery of (L 0 , S 0 ) has the same trend as predicted by as shown in (9) in Section III for s e ≤ s max e . Here, the parameters corresponding to the predicted trend (shown in red) have been hand-tuned for best fit.
In fact, as shown in Fig. 2, this trend continues for sparsity levels much greater than s max e . This can be potentially attributed to the limitations of the deterministic analysis (on the locations of the non-zero elements of S) presented here.
Further, Fig. 3 shows the results of RPCA † (in green, shows the area where at least one of the 10 Monte-Carlo simulations succeeds) in comparision to the results obtained by D-RPCA(E) for d = 5 and d = 50. We observe that D-RPCA(E) outperforms RPCA † across the board. In fact, we notice that the RPCA † technique only succeeds when r < d. We believe that this is because when d < r the component D † L is not low-rank (full-rank in this case) w.r.t. the maximum potential rank of D † L. As a result, the model 2 For ease of computation we run on modest values of n and m. assumptions of the robust PCA problem do not apply; see Section I-B. In contrast, the proposed framework of D-RPCA(E) can handle these cases effectively (see Fig. 3) since L is low-rank irrespective of the dictionary size. This phenomenon highlights the applicability of the proposed approach to cases where d < r, and simultaneous recovery of the low-rank component in one-shot.

B. Column-wise Sparsity Case
We now present phase transition in rank r and number of outlierss c to evaluate the performance of D-RPCA(C). In particular, we compare with Outlier Pursuit (OP) [21] that solves D-RPCA(C) with D = I, and OP † to demonstrate that the a priori knowledge of the dictionary provides superior recovery properties.
Experimental Set-up: Again, we employ a variant of the APG algorithm outlined in Algorithm 1 of [14] specialized for the column-wise sparsity case to solve the optimization problem D-RPCA(C); see Algorithm 1 of [16]. We set n = 100, m = 1000, and for each pair of r and s c we run 10 Monte-Carlo trials for r ∈ {5, 10, 15 . . . , 100} and s c ∈ {50, 100, 150, . . . , 900}. For our experiments, we form L = [UV 0 n×sc ] ∈ R n×m , where U ∈ R n×r , V ∈ R (m−sc)×r have i.i.d. N (0, 1) entries, which are then column normalized. Next, we generate S = [0 d×(m−sc) W] ∈ R d×m where each entry of W ∈ R d×sc is i.i. d. N (0, 1). Also, the known dictionary D ∈ R n×d is formed by normalizing the columns of a random matrix with i.i.d. N (0, 1) entries. For each method, we scan through 100 values of the regularization parameter λ c ∈ [λ min c , λ max c ] to find a solution pair (L 0 , S 0 ) with the best precision, i.e., best detection of the outliers and rejection of false positives. We declare an experiment successful if it acheives a precision i.e. (True Positives/(True Positives + False Positives)) of 0.99 or higher. Here, we threshold the column norms at 2 × 10 −3 before we evaluate the precision. Discussion: Fig. 4 (a)-(c) shows the phase transition in rank r and column-sparsity s c for the outlier identification performance (in terms of precison) of OP for d = 50, D-RPCA(C) for d = 50 (and OP † in green, marking the region where precision is greater than 0), and D-RPCA(C) for d = 150, respectively. We observe that the a priori knowledge of the dictionary D significantly boosts the performance of D-RPCA(C) as compared to OP. This showcases the superior outlier identification properties of the proposed technique D-RPCA(C). Further, similar to the entry-wise case, we note that the pseudo-inversed based technique OP † (in green) fails when r > d. For the d = 150 case the proposed technique D-RPCA(C) is able to identify the outlier columns with high precision. This is interesting since our technique succeeds even when the outlier columns are not themselves sparse (we draw the entries of the outlier columns from N (0, 1)). This corroborates our theoretical assumption that R needs to be structured such that GFP is met.
Our empirical evaluations paves way to potential improvements via a probabilistic analysis of the model instead of the case considered here. Additionally, the recent results on non-convex low-rank matrix estimation formulations [33], [34] may potentially lead to computationally efficient algorithms by replacing the expensive SVD step in every iteration. Exploration of these extensions are left for future work.

VI. CONCLUSIONS AND FUTURE WORK
We analyze a dictionary based generalization of robust PCA. Here, we model the acquired data as a superposition of a lowrank component and a dictionary sparse component, considering two distinct sparsity patterns -entry-wise sparsity and columnwise sparsity, respectively. Specifically, for the entry-wise sparsity case, we extend the theoretical guarantees presented in [14] to a setting wherein the dictionary D may have arbitrary number of columns, and the coefficient matrix S has global sparsity of s e , i.e. S 0 = s e ≤ s max e , rendering the results useful for a potentially wide range of applications. Further, we propose a column-wise sparsity model, which can be viewed as a dictionary based generalization of Outlier Pursuit [21]. For this case, we analyze and develop the conditions under which solving a convex program will recover the correct column-space of the low-rank part while identifying the outlier columns in the dictionary sparse part. To corroborate our theoretical results, we provide empirical evaluations via phase transition plots in rank and sparsity.

APPENDIX
In the following appendices, we provide the proofs of the lemmata employed to establish our main results. We also summarize the notation in Table I. The data matrix L ∈ R n×m The low-rank matrix with rank-r and singular value decomposition L = UΣV D ∈ R n×d The known dictionary either thin (d ≤ n) or fat (d > n) S ∈ R d×m The sparse component with the following properties -(1) in case of entry-wise sparsity: se non-zero entries and when d > n has at most k non-zeros per column, and (2) in case of column-wise sparsity: sc non-zero columns Regularization Parameters λe ∈ R The regularization parameter for the entry-wise sparsity case λc ∈ R The regularization parameter for the column sparsity case Subspaces L The set of matrices which span the same column or row space as L, i.e., L : The set of matrices with the same support as S (for the entry-wise sparse case).

Sc
The set of matrices with the same column support as S (for the column-wise sparse case). D The set of matrices whose columns span the subspace spanned by columns of D, i.e. D := {Z = RH, H ∈ Se or H ∈ Sc} U The column space of L V The row space of L Index Sets I Se Support of matrix S (entry-wise case) I Sc Column support of matrix S (the outliers) I L Index set of the inliers (column-wise case) Projection P G (·) Projection operator corresponding to any subspace G P G Projection matrix corresponding to the operator P G (·) Parameters for analysis µ The incoherence parameter between the low-rank component and the dictionary, defined as µ := max Defined as ξe := D UV ∞ ξc Defined as ξc := D UV ∞,2 α Lower generalized frame bound αu Upper generalized frame bound

A. Proofs for Entry-wise Case
We present the details of the proofs in this section for the entry-wise case. We first start by deriving the optimality conditions.
Proof of Lemma 4. Let {L 0 , S 0 } be a solution of the problem posed above. Notice that this pair is not necessarily unique. For example, as shown in proof of Lemma 2 in [14], {L 0 + DH, S 0 − H}, with arbitrary H, is another feasible solution of the problem satisfying the optimality conditions (derived in this section).
We begin by writing the Lagrangian, F(L, S, Λ), for the given problem as follows.
where Λ ∈ R n×m are the Lagrange multipliers.
Let the singular value decomposition (SVD) of L 0 be represented as UΣV . Then the sub-differential set of L * can be represented as as shown in [35]. Also, the subdifferential set corresponding to S 1 is given by Using these results, we write the sub-differential of the Lagrangian with respect to L and S at {L 0 , S 0 } as Then optimality conditions are which implies that the dual solution Λ must obey the following, Our aim here is to find the conditions on W and F such that the pair {L 0 , S 0 } is a unique solution to the problem at hand.
Using these conditions, we see that P L (Λ) = UV and P Se (D Λ) = λ e sign(S 0 ); these correspond to conditions (C1) and (C2), respectively. Now consider a feasible solution {L 0 + DH, S 0 − H} for a non-zero H ∈ R d×m . Let W, with W = 1 and P L (W) = 0, then by duality of norms, Further, let F, with F ∞ = 1 and P Se (F) = 0, be such that where F ij denotes the (i, j) th element of F. Then, we arrive at the following simplification for F, H by duality of norms, We now simplify P L (Λ), DH − P Se (D Λ), H using Holder's inequality. 1 Finally, we simplify the optimality condition in shown in (28), Here, we note that if P L ⊥ (Λ) < 1 and P S ⊥ e (D Λ) ∞ < λ e , then the pair {L 0 , S 0 } is the unique solution of the problem. Consequently, these are the required necessary conditions (C3) and (C4), respectively.
Proof of Lemma 5. First, note that we need A Se to have full row rank, i.e, its smallest singular value should be greater than zero. To this end, we first derive a lower bound on the smallest singular value, σ min (A Se ) of A Se as follows: vec (H) . Now, using the definition of A and properties of Kronecker products namely, transpose and vectorization of product of three matrices, we have Using the GFP, we have the following lower bound: Further, simplifying using properties of the projection operator, the reverse triangle inequality and the definition of µ, Therefore, we note that if µ < 1 and α > 0, A Se has full row rank, and the lower bound on the smallest singular value is given by Now, since UV F = √ r and using the GFP we have P Se (D UV ) F ≤ µ √ rα u . Therefore, an upper bound for b Se 2 is given by b Se 2 ≤ λ e √ s e + √ rα u µ.
Proof of Lemma 7. Since b Se ∞ = B Se ∞ and B Se := λ e sign(S 0 ) − P Se (D UV ), we have the upper bound b Se ∞ ≤ λ e + P Se (D UV ) ∞ .
Proof of Lemma 8. We begin by simplifying the quantity of interest as follows: Now, we derive appropriate bounds on the numerator and the denominator of (29) separately. Consider the numerator A Se ⊥ A Se ∞,∞ . Here, we are interested in the maximum 1 -norm of the rows of A Se ⊥ A Se , i.e., Let I Se refer to the support of S 0 , andĪ Se to its complement. Then, the expression can be written in terms of I Se andĪ Se : Now, A is defined as (I − P V ) ⊗ D (I − P U ), therefore using the property of the product of two Kronecker products and product of projection matrices, AA can be written as We are interested in the { , j} entry of AA . Since, AA has a Kronecker product structure, an entry of AA is given by the product of elements of the matrices in the Kronecker product, therefore max j∈Ī Se ∈I Se |e l AA e j |= max j1,j2∈Ī Se 1, 2∈IS e g(j 1 , j 2 , 1 , 2 ), (30) where g(j 1 , j 2 , 1 , 2 ) is given by g(j 1 , j 2 , 1 , 2 ) = |Tr(e 2 e 1 D (I − P U )De j1 e j2 (I − P V ))|. Now, consider g(j 1 , j 2 , 1 , 2 ), which can be simplified as Now, the following upper bound on g(j 1 , j 2 , 1 , 2 ) can be evaluated by squaring both sides and simplifying g(j 1 , j 2 , 1 , 2 ) ≤ x 1 {j2= 2} + y 2 .