Year: 2021

Abstract:
Robust subspace recovery (RSR) is a fundamental problem in robust representation learning. Here we focus on a recently proposed RSR method termed Dual Principal Component Pursuit (DPCP) approach, which aims to recover a basis of the orthogonal complement of the subspace and is amenable to handling subspaces of high relative dimension. Prior work has shown that DPCP can provably recover the correct subspace in the presence of outliers, as long as the true dimension of the subspace is known. We show that DPCP can provably solve RSR problems in the unknown subspace dimension regime, as long as orthogonality constraints -adopted in previous DPCP formulationsare relaxed and random initialization is used instead of spectral one. Namely, we propose a very simple algorithm based on running multiple instances of a projected sub-gradient descent method (PSGM), with each problem instance seeking to find one vector in the null space of the subspace. We theoretically prove that under mild conditions this approach will succeed with high probability. In particular, we show that 1) all of the problem instances will converge to a vector in the nullspace of the subspace and 2) the ensemble of problem instance solutions will be sufficiently diverse to fully span the nullspace of the subspace thus also revealing its true unknown codimension.We provide empirical results that corroborate our theoretical results and showcase the remarkable implicit rank regularization behavior of PSGM algorithm that allows us to perform RSR without being aware of the subspace dimension.

text: Robust subspace recovery (RSR) is a fundamental problem in robust representation learning. Here we focus on a recently proposed RSR method termed Dual Principal Component Pursuit (DPCP) approach, which aims to recover a basis of the orthogonal complement of the subspace and is amenable to handling subspaces of high relative dimension. Prior work has shown that DPCP can provably recover the correct subspace in the presence of outliers, as long as the true dimension of the subspace is known. We show that DPCP can provably solve RSR problems in the unknown subspace dimension regime, as long as orthogonality constraints -adopted in previous DPCP formulations- are relaxed and random initialization is used instead of spectral one. Namely, we propose a very simple algorithm based on running multiple instances of a projected sub-gradient descent method (PSGM), with each problem instance seeking to find one vector in the null space of the subspace. We theoretically prove that under mild conditions this approach will succeed with high probability. In particular, we show that 1) all of the problem instances will converge to a vector in the nullspace of the subspace and 2) the ensemble of problem instance solutions will be sufficiently diverse to fully span the nullspace of the subspace thus also revealing its true unknown codimension.We provide empirical results that corroborate our theoretical results and showcase the remarkable implicit rank regularization behavior of PSGM algorithm that allows us to perform RSR without being aware of the subspace dimension.

heading: 1 INTRODUCTION
text: Robust subspace recovery (RSR) refers to methods designed to identify an underlying linear subspace (with dimension less than the ambient data dimension) in a dataset which is potentially corrupted with outliers (i.e., points that do not lie in the linear subspace). Many methods for RSR have been proposed in the literature over the past several years Xu et al. (2012); You et al. (2017a); Lerman & Maunu (2018). Formulations based on convex relaxations and decompositions of the data matrices into a low-rank matrices plus sparse corruptions – either uniformly at random as in Robust PCA (RPCA) Candès et al. (2011) or column-sparse corruptions as in Xu et al. (2012); McCoy & Tropp (2011)1 – can, in certain situations, be shown to provably recover the true subspace when the dimension is unknown. However, these theoretical guarantees often require the dimension of the subspace, d, to be significantly less than the ambient dimension of the data, D, and these methods are not suitable to the more challenging high relative subspace dimension regime (i.e., when dD ≈ 1). The Dual Principal Component Pursuit approach for RSR. Recently, progress has been made towards solving the RSR problem in the high relative dimension regime by a formulation termed Dual Principal Component Pursuit (DPCP), which is provably robust in recovering subspaces of high relative dimension, Tsakiris & Vidal (2018). As implied by its name, DPCP follows a dual perspective of RSR aiming to recover a basis for the orthogonal complement of the inliers’ subspace. However, a key limitations of DPCP is that it requires a priori knowledge of the true subspace dimension.
1Note that RPCA is closely related but distinct from RSR. In RPCA the corruptions are assumed to be entry-wise in a data matrix, while in RSR the corruptions apply to an entire datapoint (i.e., column-wise).
DPCP for c = 1. Let X̃ ∈ RD×(N+M) denote the data matrix defined as X̃ = [X O]Γ where X ∈ RD×N is a matrix containing N inliers as its columns,O ∈ RD×M is a matrix containing M outliers, and Γ is an unknown permutation matrix. DPCP was first formulated in Tsakiris & Vidal (2018) for handling subspaces of codimension c = D−d equal to 1 (i.e., the subspace is a hyperplane with dimension d = D − 1) formulated as the following optimization problem:
min b∈RD
‖X̃>b‖1 s.t. ‖b‖2 = 1. (1)
Note that problem (1) is nonconvex due to the spherical constraint imposed on vector b ∈ SD−1 which is a normal vector of the D−1 dimensional hyperplane. In Tsakiris & Vidal (2018) the authors showed that the global minimizer of (1) will give a normal vector of the underlying true hyperplane as long as both inliers and outliers are well-distributed or the ratio between the number of inliers and number of outliers is sufficiently small. Following a probabilistic point of view, the authors in Zhu et al. (2018) presented an improved theoretical analysis of DPCP giving further insights on the remarkable robustness of DPCP in recovering the true underlying subspaces even in datasets heavily corrupted by outliers. Moreover, the authors introduced a projected subgradient method which converges to a normal vector of the true subspace at a linear rate.
Recursive DPCP for known c > 1. The authors of Zhu et al. (2018) also proposed an extension to DPCP which allows for subspaces with codimension c > 1 via a projected subgradient algorithm which attempted to learn c normal vectors to the subspace in a recursive manner. Specifically, after convergence to a normal vector, the projected subgradient algorithm is initialized with a vector orthogonal to the previously estimated normal vector. However, for that approach to be successful the knowledge of the true subspace codimension c becomes critical. Specifically, if an underestimate of the true codimension c is assumed the recovered basis for the null space, B̂, will fail to span the whole null space, S⊥. On the other hand, an overestimate of c will lead to columns of B̂ corresponding to vectors that lie in S. Orthogonal DPCP for known c. In Zhu et al. (2019), an alternative to (1) was proposed which attempts to solve for c normal vectors to the subspace at once via the formulation
min B∈RD×c
‖X̃>B‖1,2 s.t. B>B = I. (2)
The authors also propose an optimization algorithm based on the projected Riemannian subgradient method (RSGM), which builds on similar ideas as the projected subgradient method of Zhu et al. (2018) and enjoys a linear converge rate when the step size is selected based on a geometrically diminishing rule. In Ding et al. (2021) a theoretical analysis is provided on the geometric properties of 2 showing the merits of DPCP in handling datasets a) highly contaminated by outliers (in the order of M = O(N2)) and b) subspaces of high relative dimension. However again, it is critical to note that a key shortcoming of this approach is the fact that because all minimizers of problem (2) will be orthogonal matrices, a prerequisite for recovering the correct orthogonal complement of the inliers subspace is the a priori knowledge of the true codimension c (see Fig. 1).
Contributions. In this work, we address this key limitation by proposing a framework that allows us to perform robust subspace recovery in high relative subspace dimension regime without requiring a priori knowledge of the true subspace dimension. In particular, our proposed approach will be based on the simple approach of solving multiple, parallel instances of the DPCP formulation for solving for a single normal vector to the subspace,
min B∈RD×c′ c′∑ i=1 ‖X̃>bi‖1 s.t. ‖bi‖2 = 1, i = 1, 2, . . . , c′ (3)
where c′ is assumed to be a safe overestimate of c i.e., c′ ≥ c. Contrary to (2), the objective function in (3) decouples over the columns bi of matrixB = [b1 b2 · · · bc′ ] and thus can be can be solved in a parallel manner by independently applying a projected subgradient algorithm (referred to as PSGM) from c′ different random initialization. Moreover, we observe that with random initialization we can get vectors sufficiently spread on the sphere that lead PSGM (initialized with those vectors) to return normal vectors of S. These are all linearly independent when c′ ≤ c and thus can span S⊥ when c′ = c. If c′ > c then PSGM will return c′ − c redundant vectors that will still lie in S⊥ yet they will be linearly dependent (see Figure 1). That being said, we show that this simple strategy permits us to robustly recover the true subspace even without knowledge of the true codimension c.
As is detailed in Sections 3 and 4, this remarkable behavior of PSGM originates from the implicit bias that is induced in the optimization problem due to a) the relaxation of orthogonality constraints in (3) and b) the random initialization scheme that is adopted. Our specific contributions are as follows:
1. First, we focus on a continuous version of (3) i.e., in the case that inliers and outliers are distributed under continuous measures which induces a benign landscape in DPCP and hence is easier to be analyzed. We prove that DPCP problem formulated as in (3) can be solved via a projected subgradient algorithm that implicitly biases solutions towards low-rank matrices B̂ ∈ RD×c′
whose columns are the projections of the randomly initialized columns of B0 onto S⊥. As a result, B̂ almost surely spans S⊥ as long as it is randomly initialized with c′ ≥ c.
2. Second, we analyze the discrete version which is more challenging, yet of more practical interest, showing that iterates of DPCP-PSGM converge to a scaled and perturbed version of the initial matrixB0. This compelling feature of DPCP-PSGM allows to derive a sufficient condition and a probabilistic bound guaranteeing when the matrix B̂ ∈ RD×c′ spans S⊥.
3. We provide empirical results both on simulated and a real datasets, corroborating our theory and showing the robustness of our approach even without knowledge of the true subspace codimension.

heading: 2 RELATED WORK
text: Subspace Recovery. Learning underlying low-dimensional subspace representations of data has been a central topic of interest in machine learning research. Principal Component Analysis (PCA) has been the most celebrated method of this kind and is based on the minimization of the perpendicular distances of the data points from the estimates linear subspace, Jolliffe & Cadima (2016). Albeit, it is originally formulated as nonconvex optimization problem, PCA can be easily solved in closed form using a singular value decomposition (SVD) operation (see e.g. Vidal et al. (2016)). Despite its great success, PCA is prone to failure when handling datasets that contain outliers i.e., data points whose deviation from the inliers’ subspace is “large” in the `2 norm sense.
Robust Subspace Recovery (RSR). To remedy this weakness of PCA robust subspace recovery (RSR) methods attempt to identify the outliers in the dataset an recover the true underlying lowdimensional subspace of the inliers Lerman & Maunu (2018); Maunu et al. (2019). A classical approach to this problem is RANSAC Fischler & Bolles (1981), which is given a time budget and randomly chooses per iteration d points and then fits a d-dimensional subspace to those points and checks how the proposed subspace fits the remaining data points. RANSAC then outputs the subspace that agrees with the largest number of points. However, RANSAC’s reliance on randomly sampling points to propose subspaces can be highly inefficient when the number of outliers is high (as well as the fact that RANSAC also needs knowledge of the true subspace dimension, d). The need to
tackle inherent shortcomings of RANSAC pertaining to computational complexity issues inspired alternative convex formulations of RSR, Xu et al. (2012); You et al. (2017b); Rahmani & Atia (2017); Zhang & Lerman (2014). In Xu et al. (2012) the authors decompose the data matrix as a sum of a low-rank and a column-sparse component. However, theoretical guarantees obtained for convex formulations only hold for subspaces of relatively low-dimensional subspaces i.e., for d D where d and D denote the subspace and the ambient dimension, respectively. To the best of our knowledge, existing RSR algorithms rely heavily on one of two key assumptions. 1) The subspace is very low-dimensional relative to the ambient dimension (d D) or 2) The subspace dimension is a priori known. Undoubtedly, the second hypothesis is rather strong in real-world applications, and many applications also do not satisfy the first assumption. Moreover, heuristic strategies for selecting the dimension of the subspace are hard to be applied in the RSR setting since they incur computationally prohibitive procedures, Lerman & Maunu (2018). Relation to Orthogonal Dictionary Learning (ODL). Note that objective functions in the form of (3) show up beyond RSR problems i.e., in orthogonal dictionary learning (ODL), sparse blind deconvolution, etc., Qu et al. (2020). Specifically, based on a similar formulation the authors in Bai et al. (2019) proved that c′ = O(c log c) independent random initial vectors suffice in order to recover with high probability a dictionary of size D × c with high accuracy. In this paper we aim to recover a basis of the orthogonal complement of a subspace of unknown dimension instead of accurately estimating a dictionary hence our goal differs from that in Bai et al. (2019). Implicit bias in Robust Recovery Problems. The notions of implicit bias and implicit regularization have been used interchangeably in the nonconvex optimization literature for describing the tendency of optimization algorithms to converge to global minima of minimal complexity with favorable generalization properties in overparameterized models, Gunasekar et al. (2018). In the context of robust recovery, the authors in You et al. (2020) showed that Robust PCA can be suitably reparametrized in such a way to favor low-rank and sparse solutions without using any explicit regularization. In this work, we use the term implicit bias for describing the convergence of DPCPPSGM to low-rank solutions, which are not necessarily global minimizers, that span the orthogonal complement of the subspace when a) orthogonality constraints in DPCP formulation are relaxed b) DPCP is overparameterized i.e., c′ ≥ c and c) PSGM randomly initialized. To the best of our knowledge our work is the first that explores implicit bias in projected subgradient algorithms that minimize objective functions with sphere/orthogonality constraints.

heading: 3 DUAL PRINCIPAL COMPONENT PURSUIT AND THE PROJECTED SUBGRADIENT METHOD
text: We re-write the DPCP formulation given in (1) as
min B∈RD×c′
‖X̃>b‖1 = ‖X>b‖1 + ‖O>b‖1 s.t. ‖b‖2 = 1 (4)
In Zhu et al. (2018), the authors proposed a projected subgradient descent algorithm for addressing (4) that consists of a subgradient step followed by a projection onto the sphere i.e.,
bk+1 = b̂k − µk ( XSgn(X>bk) +OSgn(O>bk) ) and b̂k+1 = PSD−1(bk+1), (5)
where µk is the -adaptively updated per iteration- step size and b̂k is the unit `2 norm vector corresponding to the kth iteration.
The convergence properties of the projected subgradient algorithm described above depend on specific quantities denoted as cX,min and cX,max that reflect the geometry of the problem and are defined as cX,min = 1 N minb∈Sd−1∩S ‖X >b‖1 and cX,max = 1N maxb∈SD−1∩S ‖X >b‖1. Note that the more well distributed the inliers are in the subspace S the higher the value of the quantity cX,min (called as permeance statistic which first appeared in Lerman et al. (2015)) as it becomes harder to find a vector b in the subspace S that is orthogonal to the inliers. Moreover, cX,min and cX,max converge to the same value as N → ∞ provided the inliers are uniformly distributed in the subspace i.e., cX,min → cd, cX,max → cd, where cd is given as the average height of the unit hemisphere on Rd,
cd := (d− 2)!! (d− 1)!!
{ 2 π , if d is even,
1, if d is odd where k!! = { k(k − 2)(k − 4) · · · 4 · 2, k is even, k(k − 2)(k − 4) · · · 3 · 1, k is odd (6)
Similarly to cX,min, cX,max, we will also be interested in quantities cO,min, cO,max which indicate how well-distributed the outliers are in the ambient space. These quantities are defined as cO,min = minb∈SD−1 1 M ‖O >b‖1 and cO,max = maxb∈SD−1 1M ‖O >b‖1. cO,max can be viewed as the dual permeance statistic and is bounded away from small values while its difference from cO,min tends to zero as M →∞. Further, if the outliers are uniformly distributed on the sphere, then cO,max → cD and cO,min → cD where cD is defined as in (6), (Zhu et al., 2018).
Finally, we also define the quantities ηO = 1M maxb∈SD−1 ‖(I − bb >)OSgn(O>b)‖2 and ηX =
1 M maxb∈SD−1 ‖(PS − bb >)XSgn(X>b)‖2. As M → ∞ and assuming outliers in O are welldistributed we getOSgn(O>b)→ cDb thus ηO → 0 (Tsakiris & Vidal, 2018). Likewise, ηX → 0 as N → ∞ provided that inliers are uniformly distributed in the d-dimensional subspace. The following theorem (see full version in Appendix) provides convergence guarantees of the projected subgradient method that was proposed in Zhu et al. (2018) for addressing problem (1).
Theorem 1 (Informal Theorem 3 of Zhu et al. (2018)) Let {b̂k} the sequence generated by the projected subgradient algorithm in Zhu et al. (2018), with initialization b̂0 such that
θ0 < arctan
( NcX,min
NηX +MηO
) and NcX,min ≥ NηX +MηO (7)
where θ0 denotes the principal angle of b0 from S⊥. If the step size µk is updated according to a piecewise geometrically diminishing rule given as
µk = { µ0, k < K0 µ0βb(k−K0)/K∗c+1, k ≥ K0
(8)
where β < 1, b·c is the floor function, then the iterates bk converge to a normal vector of S.

heading: 4 DUAL PRINCIPAL COMPONENT PURSUIT IN SUBSPACES OF UNKNOWN CODIMENSION
text: Current theoretical results provide guarantees for recovering the true inlier subspace, when the proposed algorithms know a priori of the subspace codimension c, which is a rather strong requirement and is far from being true in real word applications. Here we describe our proposed approach, which consists of removing the orthogonality constraint onB, along with a theoretical analysis that gives guarantees of recovering the true underlying subspace even when the true codimension c is unknown. First we analyze a continuous version of DPCP, which arises when the number of inliers and outliers are distributed according to continuous measures and their number tends to ∞. The continuous DPCP incurs an optimization problem with a benign landscape that allows us to better illustrate the favorable properties of DPCP-PSGM when it comes to the convergence of its iterates. Then we extend the results to the discrete case that deals with a finite number of inliers and outliers yielding a more challenging optimization landscape.

heading: 4.1 PSGM’S ITERATES CONVERGENCE IN THE CONTINUOUS VERSION OF DPCP
text: The following lemma provides the continuous version of the discrete objective function given in (3).
Lemma 2 In the continuous case, the discrete DPCP problem given in (3) is reformulated as,
min B∈RD×c′ c′∑ i=1 ( pEµSD−1 [fbi ] + (1− p)EµSD−1∩S [fbi ] ) = c′∑ i=1 ‖bi‖2 (pcD + (1− p)cdcos(φi))
s.t. ‖bi‖2 = 1, i = 1, 2, . . . , c′ (9)
where fb : SD−1 → R, fb(z) = |z>b|, φi is the principal angle of bi from the inliers subspace S and p is the probability of occurrence of an outlier.
Note that µSD−1 ,µSD−1∩S are the continuous measures associated with the outliers and inliers, respectively. Evidently, (9) attains its global minimum for vectors bis that are orthogonal to the
inliers’ subspace. Based on (3) and due to Lemma 2, we can now minimize the objective function of the “continuous version” of DPCP by employing a projected subgradient methods (PSGM) that performs the following steps per iteration 2
bk+1i = b̂ k i − µki (pcDb̂ki + (1− p)cdŝki ) and b̂k+1i = PS⊥(b k+1 i ) , i = 1, 2, . . . , c ′ (10)
Lemma 3 A projected subgradient algorithm consisting of the steps described in (10) using a piecewise geometrically diminishing step size rule (see (8) in Theorem 1) will almost surely asymptotically converge to a matrix B̂∗ ∈ RD×c′ whose columns b̂∗i , i = 1, 2, . . . , c′ will be normal vectors of the inliers’ subspace when randomly initialized with vectors b0i ∈ SD−1, i = 1, 2, . . . , c′ uniformly distributed over the sphere SD−1.
Lemma 3 allows us to claim that we can always recover c′ ≥ c normal vectors to the inliers’ subspace using a PSGM algorithm consisting of steps given in (10). However, this does not tell the whole story yet, since our ultimate objective is to recover a matrix B̂ that spans S⊥. Thus, it remains to show that the rank of B̂ is equal to the true and unknown codimension of the inliers’ subspace c. Next we prove that by initializing with a B̂0 such that rank(B̂0) = c′ (i.e., B̂0 is initialized to be full-rank), we can guarantee that we can solve the continuous version of DPCP using PSGM and converge to a B̂ such that rank(B̂) = c thus getting span(B̂) ≡ S⊥ (along with recovering the true subspace dimension). By projecting the PSGM iterates given in (10) onto S⊥ we have,
PS⊥(b k+1 i ) = (1− µ k i pcD)PS⊥(b̂ki ) and PS⊥(b̂ k+1 i ) = PS⊥(PSD−1(b k+1 i )) (11)
We hence observe that the projections of successive iterates of PSGM are scaled versions of the corresponding projections of the previous iterates. We can now state Lemma 4.
Lemma 4 The PSGM iterates b̂ki , i = 1, 2, . . . , c′, k = 1, 2, . . . given in (10), when randomly initialized with b̂0i s, i = 1, 2, . . . , c
′ that are independently drawn from a spherical distribution with unit `2 norm converge almost surely to c′ normal vectors of the inliers subspace S denoted as b̂∗i , i = 1, 2, . . . , c ′ that are given by b̂∗i = PS⊥ (b̂ 0 i )
‖PS⊥ (b̂ 0 i )‖2
, i = 1, 2, . . . , c′.
Lemma 4 shows that the initialization of PSGM plays a pivotal role since it determines the direction of the recovered normal vectors {b̂∗i }c ′ i=1. Lemmas 3 and 4 pave the way for Theorem 5.
Theorem 5 Let B̂0 ∈ RD×c′ where c′ ≥ c with c denoting the true codimension of the inliers subspace S , consisting of unit `2 norm column vectors b̂0i ∈ SD−1, i = 1, 2, . . . , c′ that are independently drawn from uniform distribution over the sphere SD−1. A PSGM algorithm initialized with B̂0 will almost surely converge to a matrix B̂∗ such that span(B̂∗) ≡ S⊥.
From Theorem 5 we observe that in the benign scenario where inliers and outliers are distributed under continuous measures, we can recover the correct orthogonal complement of the inlier’s subspace even when we are oblivious to its true codimension. Remarkably, this is achieved by exploiting the implicit bias induced by multiple random initializations of the PSGM algorithm for solving the DPCP formulation given in (3), which is free of orthogonality constraints.

heading: 4.2 PSGM’S ITERATES CONVERGENCE IN THE DISCRETE VERSION OF DPCP
text: From this analysis of the continuous version of DPCP we now extend to the the discrete version, which is of more practical relevance for finite data, yet also presents more challenges. To begin, we reformulate the DPCP objective as follows
c′∑ i=1 ‖X̃>bi‖1 = c′∑ i=1 ‖X>bi‖1 + ‖O>bi‖1 =M c′∑ i=1 b>i obi +N c′∑ i=1 b>i x bi (12)
where x bi and obi are called as average inliers and average outliers terms, defined as x bi = 1 N ∑N j=1 Sgn(b > i x j)x j and obi = 1 M ∑M j=1 Sgn(b > i oj)oj .
2Note that ∂‖b‖2 = b‖b‖2 for b 6= 0 and ‖bi‖2cos(φi) = b > i ŝi where ŝi = PS(bi) ‖PS(bi)‖2 .
In Algorithm 1, we give the projected subgradient method (DPCP-PSGM) applied on the DPCP problem given in (3).
Algorithm 1: DPCP-PSGM algorithm for solving (3)
Result: B̂ = [b̂k1 , b̂k2 , . . . , b̂kc′ ] Initialize: Randomly sample b̂10, b̂20, . . . , b̂c ′
0 from a uniform distribution on SD−1 ; for k = 1, 2, . . . do
for i = 1, 2, . . . , c′ do Update the step-size according to a specific rule; bk+1i = b̂
k i − µki (Mokb̂i +Nx k b̂i );
b̂k+1i = PSD−1(b k+1 i );
end end
Note that the average outliers and inliers terms are discrete versions of the corresponding continuous average terms cDbi and cdŝi where ŝi = PS(bi), respectively, Tsakiris & Vidal (2018). We now express the sub-gradient step of Algorithm 1 as
bk+1i = b̂ k i − µki ( M(cDb̂ k i + e i,k O ) +N(cD ŝ k i + e i,k X ) )
(13)
where the quantities e i,kO = o b̂ki − cDb̂ k i− and e i,k X = x b̂ki − cD ŝki account for the error between the continuous and discrete versions of the average outliers and the average inliers terms, respectively. Following a similar path as in the continuous case we next project the iterates of (13) onto S⊥,
PS⊥(b k+1 i ) = PS⊥(b̂ k i )− µki MPS⊥(cDb̂ki + e i,kO ) +N : 0 PS⊥(cD ŝki + e i,k X )  = (1− µkiMcD)PS⊥(b̂ki )− µkiMPS⊥(e i,k O )
(14)
Remark. Eq. (14) reveals that DPCP-PSGM, applied on the discrete problem, gives rise to updates whose projections to S⊥ are scaled and perturbed versions of the previous estimates. The magnitude of perturbation depends on the discrepancy between the continuous and the discrete problem.
Recall that PS⊥(b̂ki ) = PS⊥ (b k i )
‖bki ‖2 , and we can rewrite the update of the 2nd iteration of DPCP-PSGM,
PS⊥(b2i ) = (1− µ1iMcD) ‖b1i ‖2
( (1− µ0iMcD)PS⊥(b̂0i )− µ0iMPS⊥(e i,0 O ) ) − µ1iMPS⊥(e i,1 O )
= (1− µ1iMcD)(1− µ0iMcD)
‖b1i ‖2‖b0i ‖2 PS⊥(b̂0i )− (1− µ1iMcD) ‖b1i ‖2 µ0iMPS⊥(e i,0 O )− µ 1 iMPS⊥(e i,1 O )
(15)
where we have assumed that ‖b0i ‖2 = 1. By repeatedly applying the same steps, we can reach to the following recursive expression for PS⊥(bKi ),
PS⊥(bKi ) = ( K−1∏ k=0 (1− µkiMcD) ‖bki ‖2 ) PS⊥(b0i )− K−1∑ k=0  K−1∏ j=k+1 (1− µjiMcD) ‖bji‖2 µkiMPS⊥(e i,kO ) (16)
where for j > K − 1 we set ∏K−1 j=k+1
(1−µjiMcD) ‖bji‖2 = 1.
By dividing (16) with ∏K−1 k=0 (1−µkiMcD) ‖bki ‖2 and by projecting onto the sphere SD−1 we get
PSD−1(PS⊥(bKi )) = PSD−1(PS⊥(b0i )− PS⊥(δKi )) (17)
where δi is defined as δKi = ∑K−1 k=0 (∏k j=0
‖bji‖2 (1−µjiMcD)
) µkiMe i,k O .
Assumption 1. We assume that the principal angles θi0 for all b0i s satisfy the inequality θi0 < arctan ( NcX,min
NηX+MηO
) ∀i, i = 1, 2, . . . , c′.
Assumption 1 essentially assumes that the sufficient condition given in eq. (7) required by PSGM algorithm for converging to a normal vector is satisfied which is the same condition for success in Zhu et al. (2018). Under Assumption 1 we can invoke the convergence properties of PSGM given in Theorem 1 and get as K → ∞,PSD−1(PS⊥(bK)) → b̂∗ ∈ S⊥ ∩ SD−1. That being said, we denote b̂∗i = PSD−1 ( PS⊥(b0i )− PS⊥(δ̂i) ) , where δ̂i = limK→∞ δKi 3. Following the same steps
as in Section 4.1 and by defining matrices B∗ = [b∗1, b ∗ 2, . . . , b ∗ c′ ],B 0 = [b01, b 0 2, . . . , b 0 c′ ], ∆̂ = [δ̂1, δ̂2, . . . , δ̂c′ ] we can express the matrixB∗ as B̂∗ = PSD−1 ( PS⊥ ( B0 − ∆̂ )) whereB∗ will now consist of normal vectors of the inliers’ subspace. In order to guarantee that span(B∗) ≡ S⊥ it thus suffices to ensure that rank (B∗) = c. Here we show that a sufficient condition for this to hold is that the matrixA = B0 − ∆̂ is full-rank.
Lemma 6 If σc′(B0) > ‖∆̂‖2 then matrixA = B0 − ∆̂ is full-rank.
From Lemma 6 we can see that the success of DPCP-PSGM hinges on how well-conditioned the matrix B0 is. Specifically, it says that if a lower-bound on the smallest singular is satisfied then DPCP-PSGM is guaranteed to converge to the correct complement of the inlier without knowledge of the correct codimension c. From this, we can prove the following Theorem.
Theorem 7 Let B0 ∈ RD×c′ with columns randomly sampled from a unit `2 norm spherical distribution where c′ ≥ c with c denoting the true codimension of the inliers subspace S that satisfies Assumption 1. If
1− C1
√ c′
D − √ D > √ c′κ(ηO + cO,max − cd) (18)
where κ = maxi Mµ0i
βK0/K∗ (1−ri) and ri = (1+µ0i (N(ηX+cX ,max)+M(ηO+cO,max))) 1−µ0iMcD β1/K∗ then with
probability at least 1−2 exp(− 2C2) (whereC1, C2 are absolute constants), Algorithm 1 with a piecewise geometrically diminishing step size rule will converge to a matrix B̂∗ such that span(B̂∗) ≡ S⊥.
Note that quantities β,K∗,K0 are used in the step-size update rule that is used as defined in (8) (See also full version of Theorem 1 in Appendix)). Theorem 7 shows that we can randomly initialize DPCPPSGM, with a matrix B̂0 whose number of columns c′ is an overestimate of the true codimension c of the inliers’ subspace and with columns sampled independently by a uniform distribution over the unit sphere and recover a matrix that will span the orthogonal complement of S . The probability of success depends on the geometry of the problem since condition (18) is trivially satisfied (RHS of (18) tends to 0 since ηO → 0 and cO,max → cd) in the continuous case which incurs a benign geometry. Moreover, the a less benign geometry would increase the value of (ηO + cO,max − cd) thus requiring a smaller initial codimension c′ that would lead to larger values the LHS of (18).

heading: 5 NUMERICAL SIMULATIONS
text: In this section we demonstrate the effectiveness of the proposed DPCP formulation and the derived DPCP-PSGM algorithm in recovering orthogonal complements of subspace of unknown codimension. We compare the proposed algorithm with previously developed methods i.e., DPCP-IRLS Tsakiris & Vidal (2018) and the Riemannian Subgradient Method (RSGM) Zhu et al. (2019). Recall that both DPCP-IRLS and RSGM address DPCP problem by enforcing orthogonality constraints, and thus both algorithms are quite sensitive if the true codimension of S is not known a priori. Further, they are both initialized using of spectral initialization i.e., B̂0 ∈ RD×c′ which contains the first c′ eigenvectors of matrix X̃ X̃ > as its columns, as proposed in Tsakiris & Vidal (2018); Zhu et al. (2019). 3For the sake of brevity we assume that the step size has been selected such that existence of the limit is guaranteed. We refer the reader to the proof Lemma 8 for further details.
Robustness to outliers in the unknown codimension regime. In this experiment we set the dimension of the ambient space to D = 200. We randomly generate N inliers uniformly distributed with unit `2 norm in a d = 195 dimensional subspace (hence for its codimension we have c = D− d = 5). Following a similar process we generate M outliers that live in the ambient space and are sampled from a uniform distribution over the unit sphere. Fig. 2, illustrates the distances (see Appendix) of the recovered matrix B̂ as obtained by the proposed DPCP-PSGM algorithm initialized with an overestimate c′ = 10 of the true codimension c codimension and two versions of RSGM i.e., RSGM when it is given as input true c = 5 and RSGM when being incognizant of c and hence it initialized with a c′ = 10 of cAs is shown in Fig. 2 (right), RSGM fails to recover the correct orthogonal complement of S when it is provided with an overestimate of the true c which is attributed to spectral initialization and the imposed orthogonality constraints. On the contrary, DPCP-PSGM displays a remarkably robust behavior (Fig. 2(middle)) even without knowing the true value of c, performing similarly to RSGM when the latter knows beforehand the correct codimension (Fig. 2(left)).
Recovery of the true codimension. Here we test DPCP-PSGM on the recovery of the true codimension c of the inliers’ subspace S. Again, we set D = 200 and follow the same process described above for generating N = 1500 inliers. We vary the true codimension of S from c = 10 to 20 and consider two different outlier’s ratios r, defined as r = MM+N , namely r = 0.6 and r = 0.7. In both cases, DPCP-PSGM is initialized with the same overestimate of c i.e., c′ = 30. In Fig. 3 we report the estimated codimensions obtained by DPCP-PSGM for 10 independent trials of the experiments. It can be observed that DPCP-PSGM achieves 100% for all different codimensions for r = 0.6. Moreover, it shows a remarkable performance in estimating the correct c’s even in the more challenging case corresponding to outliers’ ratios equal to 0.7. with the estimated codimensions being close to the true values even in the cases that it fails to exactly compute c. The results corroborate the theory showing that the DPCP-PSGM with random initialization biases the solutions of B̂ towards matrices with rank c.
A hyperspectral imaging experiment See Appendix B.1.

heading: 6 CONCLUSIONS
text: We proposed a simple framework which allows us to perform robust subspace recovery without requiring a priori knowledge of the subspace codimension. This is based on Dual Principal Component Pursuit (DPCP) and thus is amenable to handling
subspaces of high relative dimensions. We observed that a projected subgradient methods (PSGM) induces implicit bias and converges to a matrix that spans a basis of the orthogonal complement of the inliers subspace even as long as a) we overestimate it codimension, b) lift orthogonality constraints enforced in previous DPCP formulations and c) use random initialization. We provide empirical results that corroborate the developed theory and showcase the merits of our approach.
Ethics Statement This work focuses on theoretical aspects of robust subspace recovery problem which is a well-established topic in machine learning research. The research conducted in the framework of this work raises no ethical issues or any violations vis-a-vis the ICLR Code of Ethics.

heading: A APPENDIX
text: Theorem 1 (Theorem 3 of Zhu et al. (2018)) Let {b̂k} the sequence generated by the projected subgradient method in Zhu et al. (2018), with initialization b̂0 such that
θ0 < arctan
( NcX,min
NηX +MηO
) (19)
where θ0 denotes the principal angle of b0 from S⊥, and
NcX,min ≥ NηX +MηO (20)
Let µ′ := 14max{NcX,min,McO,max} . If µ 0 ≤ µ′ and the step size µk is updated according to a piece-wise geometrically diminishing rule given as
µk = { µ0, k < K0 µ0βb(k−K0)/K∗c+1, k ≥ K0
(21)
where β < 1, b·c is the floor function, and K0,K∗ ∈ N are chosen such that
K0 ≥ K♦(µ0), K∗ ≥ (√ 2βµ′ (NcX − (NηX +MηO)) )−1
where,
K♦(µ) := tan(θ0)
µ (NcX,min −max{1, tan(θ0} (NηX +MηO)) (22)
then for the angle θk between b̂k and S⊥ it holds
tan(θ0) ≤ { max{tan(θ0), µ0√2µ′ }, k < K0 µ0√ 2µ′ βb(k−K0)/K∗c, k ≥ K0
(23)

heading: A.1 PROOF OF LEMMA 2
text: Lemma 2 In the continuous case, the discrete DPCP problem given in (3) is reformulated as,
min B∈RD×c′ c′∑ i=1 ( pEµSD−1 [fbi ] + (1− p)EµSD−1∩S [fbi ] ) = c′∑ i=1 ‖bi‖2 (pcD + (1− p)cdcos(φi))
s.t. ‖bi‖2 = 1, i = 1, 2, . . . , c′ (24)
where fb : SD−1 → R, fb(z) = |z>b|, φi is the principal angle of bi from the inliers subspace S and p is the probability of occurrence of an outlier.
Proof We define the discrete measures µX ,µO associated with the inliers and outliers, respectively as,
µX (z) = 1
N N∑ j=1 δ(z− oj), µO(z) = 1 M N∑ j δ(z− x j) (25)
where δ(·) is the Dirac function. Recall that,∫ z∈SD−1 g(z)δ(z− z0)dµSD−1 = g(z0) (26)
where g : SD−1 → R and µSD−1 is the uniform measure on SD−1.
The DPCP objective for the discrete version of the problem divided by M +N can be written as,
1
M +N c′∑ i=1 ‖X̃ > bi‖1 = 1 M +N c′∑ i=1 ( ‖X>bi‖1 + ‖O>bi‖1 ) =
1
M +N c′∑ i  N∑ j=1 |x>j bi|+ M∑ j=1 |o>j bi|  = 1
M +N c′∑ i=1  N∑ j=1 ∫ z∈SD−1 |z>bi|δ(z− x j)dµSD−1 + M∑ j ∫ z∈SD−1 |z>bi|δ(z− oj)dµSD−1  = 1
M +N c′∑ i=1 ∫ z∈SD−1 |z>bi| N∑ j=1 δ(z− x j)dµSD−1 + ∫ z∈SD−1 |z>bi| M∑ j δ(z− oj)dµSD−1  =
c′∑ i=1 (pEµX [fbi ] + (1− p)EµO [fbi ])
Note that µX ,µO arise by discretizing the continuous uniform measures µSD−1 and µSD−1∩S respectively (µSD−1∩S denotes the uniform measure on SD−1 ∩ S) and p is the probability of occurrence of an outlier i.e., MM+N → p as M,N → ∞ ( 1 − p corresponds to the probability of occurrence of an inlier). That being said, the continuous version of DPCP can be simply stated by replacing µX ,µO with µSD−1 and µSD−1∩S in equation 27 as follows,
min B c′∑ i=1 ( pEµSD−1 [fbi ] + (1− p)EµSD−1∩S [fbi ] ) (27)
The RHS of (9) immediately shows up by invoking Proposition 4 in Tsakiris & Vidal (2018).

heading: A.2 PROOF OF LEMMA 3
text: Lemma 3: A projected subgradient algorithm consisting of the steps described in (10) using a piecewise geometrically diminishing step size rule (see (8) in Theorem 1) will almost surely asymptotically converge to a matrix B̂∗ ∈ RD×c′ whose columns b̂∗i , i = 1, 2, . . . , c′ will be normal vectors of the inliers’ subspace when randomly initialized with vectors b0i ∈ SD−1, i = 1, 2, . . . , c′ uniformly distributed over the sphere SD−1. Proof:
The proof can be trivially obtained by noticing a) that the condition for convergence i.e., inequality (7) of the projected subgradient algorithm given in Theorem 1 becomes θ0i < π 2 in the continuous case (since ηX → 0, ηO → 0, cX,min → cd > 0) and b) the set of unit `2-norm vectors b0i s, i = 1, 2, . . . , c′ sampled independently by a uniform distribution over the sphere and whose principal angle θ0i is π 2 form the inliers’ subspace has measure 0.

heading: A.3 PROOF OF THEOREM 5
text: Lemma 4 The PSGM iterates b̂ki , i = 1, 2, . . . , c′, k = 1, 2, . . . given in (10), when randomly initialized with b̂0i s, i = 1, 2, . . . , c
′ that are independently drawn from a spherical distribution with unit `2 norm converge almost surely to c′ normal vectors of the inliers subspace S denoted as b̂∗i , i = 1, 2, . . . , c ′ that are given by
b̂∗i = PS⊥(b̂0i ) ‖PS⊥(b̂0i )‖2 , i = 1, 2, . . . , c′ (28)
Proof Let us assume b0i = b̂0i . The iterates of subgradients steps of PSGM can be written in the following form,
b1i = (1− µ0i pcD)b̂0i − µ0i (1− p)cdŝ b2i = (1− µ1i pcD)b̂1i − µ1i (1− p)cdŝ ... = ...
bKi = (1− µK−1i pcD)b̂ K−1 i − µ K−1 i (1− p)cdŝ
(29)
By projecting each update of PSGM onto S⊥ and since PS⊥(bki ) = ‖bki ‖PS⊥(b̂ki ) we have,
PS⊥(b k+1 i ) = (1− µki pcD) ‖bki ‖ PS⊥(bki ) (30)
We can thus easily derive the following form for PS⊥(bKi ),
PS⊥(bKi ) = ( K−1∏ k=1 (1− µki pcD) ‖bki ‖2 ) PS⊥(b0i ) (31)
We know from Theorem 1 and Lemma 3 when DPCP-PSGM is initialized with b0i , i = 1, 2, . . . , c ′s randomly drawn according according to a spherical distribution then it will almost surely converge as K → ∞ to vectors b̂∗i , i = 1, 2, . . . , c′ i.e., b̂Ki → b̂∗i where b̂∗i ∈ S⊥. Hence PS⊥(b̂Ki ) → b̂∗i as K → ∞. Note that from Theorem 1 we have that µki 6= 1pcD ∀k = {1, 2, . . . ,K} hence∏K−1 k=1
(1−µki pcD) ‖b̂ki ‖2 6= 0. From 31 and after projecting on the unit sphere and we thus have
b̂∗i = PS⊥ (b̂ 0 i )
‖PS⊥ (b̂ 0 i )‖2
.
Theorem 5 Let B̂0 ∈ RD×c′ where c′ ≥ c with c denoting the true codimension of the inliers subspace S , consisting of unit `2 norm column vectors b̂0i ∈ SD−1, i = 1, 2, . . . , c′ that are independently drawn from uniform distribution over the sphere SD−1. A PSGM algorithm initialized with B̂0 will almost surely converge to a matrix B̂∗ such that span(B̂∗) ≡ S⊥.
Proof From Lemma 4 we have that for each initial unit norm vector b0i which corresponds to the ith column ofB0 will almost surely converge to b̂∗i = PS⊥ (b̂ 0 i )
‖PS⊥ (b̂ 0 i )‖2 . We can thus writeB∗ = PS⊥(B0)Γ where Γ is a full-rank diagonal matrix given be Γ = diag( 1
‖PS⊥ (b̂ 0 1)‖2 , 2 ‖PS⊥ (b̂ 0 2)‖2 , . . . , 1 ‖PS⊥ (b̂ 0 c′ )‖2 ).
Note that PS⊥ is a linear projection and thus we can write PS⊥(B0) = BS⊥B>S⊥ where BS⊥R D×c is an orthonormal matrix which spans S⊥. Note that the probability of sampling a low-rank matrix B0 = [b 0 1, b 0 2, . . . , b 0 c′ ] when columns b 0 i s are randomly and independently drawn from a spherical distribution is zero. We thus haveB∗ = BS⊥B > S⊥B 0Γ with rank(B∗) = c.
Lemma 6 If σc′(B0) > ‖∆̂‖2 then the rank of matrixB0 − ∆̂ equals c′.
Proof LetA = B0−∆̂. From singular value perturbation inequalities we have |σi(A)−σi(B0)| ≤ ‖∆̂‖2, for i = 1, 2, . . . , c′. Hence it holds,
− ‖∆̂‖2 ≤ σi(A)− σi(B0) (32)
If σc′(B0) > ‖∆̂‖2 then from equation 32 we get
σc′(A) > 0 (33)
hence the matrixB0 − ∆̂ will be full-rank.

heading: A.4 PROOF OF THEOREM 7
text: We first give the following Lemmas:
Lemma 7 For the `2 norm of e i,kO for any k = 1, 2, . . . ,K and i = 1, 2, . . . , c ′ it holds,
‖e i,kO ‖2 ≤ ηO + cO,max − cd (34)

heading: Proof
text: ‖e i,kO ‖2 = ‖ob − cdb‖2 = ‖ 1 M OSgn(O>b)− cdb‖2
= ‖ 1 M (I− bb>)OSgn(O>b) + 1 M bb>OSgn(O>b)− cdb‖2 ≤ ‖ 1 M (I− bb>)OSgn(O>b)‖2 + ( 1 M ‖O>b‖1 − cd)‖b‖2 ≤ ηO + cO,max − cd (35)
where we have used the fact that ‖b‖2 = 1.
Lemma 8 Let the step size of Algorithm 1 (DPCP-PSGM) µki being updated following the piecewise geometrically diminishing step size rule with
β <
( 1− µ0iMcD
1 + µ0i (N(ηX + cX ,max) +M(ηO + cO,max))
)K∗ .
For the spectral norm of ∆̂ it holds ‖∆̂‖2 < √ c′κ(ηO+cO,max−cd) where κ = maxi Mµ 0 i
βK0/K∗ (1−ri)
and ri = (1+µ0i (N(ηX+cX ,max)+M(ηO+cO,max)))
1−µ0iMcD β1/K∗ .
Proof We first bound the `2 norm of vectors bji s. We have that ∀i = 1, 2, . . . , c′ and j = 1, 2, . . . ,K it holds
bj+1i = b̂ j i − µ j i ( XSgn(X>b̂ji ) +OSgn(O >b̂ji ) )
(36)
We define the quantities
ηX := max b∈SD−1
1
N ‖(PS − b̂ji b̂ j,> i )XSgn(X >b̂ji )‖2 (37)
cX,max := max b∈SD−1
1
N ‖X>b̂ji‖1 (38)
‖b̂ji‖2 = 1 hence
‖bj+1i ‖2 ≤ 1 + µ j i‖XSgn(X >b̂ji ) +OSgn(O >b̂ji‖2 ≤ 1 + µji ( ‖XSgn(X>b̂ji )‖2 + ‖OSgn(O >b̂ji )‖2 )
≤ 1 + µji (‖(PS − b̂ j i b̂ j,> i )XSgn(X >b̂ji )‖2 + ‖(b̂ j i b̂ j,> i )XSgn(X >b̂ji )‖2 + ‖ ( 1− b̂ji b̂ j,> i ) OSgn(O>b̂ji )‖2 + ‖b̂ j i b̂ j,> i OSgn(O >b̂ji )‖2)
≤ 1 + µji (N(ηX + cX ,max) +M(ηO + cO,max))
Due to equation 39 and since µji follows a non-increasing path as j → k, the scalar term∏k j=0
‖bji‖2 (1−µjiMcD) is bounded above as follows,
k∏ j=0 ‖bji‖2 (1− µjiMcD) ≤
(( 1 + µ0i (N(ηX + cX ,max) +M(ηO + cO,max)) ) 1− µ0iMcD )k (39)
We now focus on the geometrically diminishing step size rule given in equation 8. We have µki = µ0iβ bk−K0/K∗c+1 < µ0iβ (k−K0)/K∗ for k ≥ K0 and µ0iβ(k−K0)/K∗ > µ0i for k < K0. Hence we can get the following upper bound
lim K→∞ K−1∑ k=0 k∏ j=0 ‖bji‖2 (1− µjiMcD) µkiM <
M lim K→∞ K−1∑ k=0
(( 1 + µ0i (N(ηX + cX ,max) +M(ηO + cO,max)) ) 1− µ0iMcD )k µ0iβ (k−K0)/K∗
≡ lim K→∞ K−1∑ k=0 M 1 βK0/K∗ µ0i
(( 1 + µ0i (N(ηX + cX ,max) +M(ηO + cO,max)) ) 1− µ0iMcD β1/K∗ )k
The series S = ∑K−1 k=0
( (1+µ0i (N(ηX+cX ,max)+M(ηO+cO,max)))
1−µ0iMcD β1/K∗
)k is geometric and if
β <
( 1− µ0iMcD
(1 + µ0i (N(ηX + cX ,max) +M(ηO + cO,max)))
)K∗ (40)
it converges as K →∞ to 11−ri where ri = (1+µ0i (N(ηX+cX ,max)+M(ηO+cO,max))) 1−µ0iMcD β1/K∗ .
Let us now bound the `2 norms of the columns of ∆̂. From Lemma 7 we have ‖e i,kO ‖2 ≤ ηO + cO,max − cd. We can easily thus derive that ‖δ̂i‖2 ≤ κ(ηO + cO,max − cd). For the spectral norm of ∆̂ we thus have
‖∆̂‖2 = sup x 6=0 ‖∆̂x‖2 ‖x‖2 = sup x 6=0 ‖ ∑c′ i=1 δ̂ixi‖2 ‖x‖2 ≤ sup x 6=0 ∑c′ i=1 ‖δ̂i‖2|xi| ‖x‖2
≤ max i ‖δ̂i‖2sup
x 6=0 ‖x‖1 ‖x‖2 ≤ κ(ηO + cO,max − cd) √ c′
(41)
Where the last inequality arises since ‖x‖1 ≤ √ c′‖x‖2.
We then give the Theorem.
Theorem 9 (Theorem 5.58 of Vershynin (2010)) LetB be a D × d matrix (D ≥ d) whose columns bi are independent sub-gaussian isotropic random vectors in RD with ‖bi‖2 = √ D almost surely. Then for every t ≥ 0 the inequality √ D − C √ d− t ≤ σmin(B) ≤ σmax(B) ≤ √ D + C √ d+ t (42)
with probability at least 1−2 exp(−ct2), whereC = C ′k, c = c′K > 0 depend only on the subgaussian norm K = maxj ‖bi‖ψ2 of the columns.
The proof of Theorem 7 follows next.
Theorem 7 Let B0 ∈ RD×c′ with columns randomly sampled from a unit `2 norm spherical distribution where c′ ≥ c with c denoting the true codimension of the inliers subspace S that satisfies Assumption 1. If
1− C1
√ c′
D − √ D > √ c′κ(ηO + cO,max − cd) (43)
where κ = maxi Mµ0i
βK0/K∗ (1−ri) and ri = (1+µ0i (N(ηX+cX ,max)+M(ηO+cO,max))) 1−µ0iMcD β1/K∗ then with
probability at least 1 − 2 exp(− 2C2) (where C1, C2 are absolute constants), Algorithm 1 with a geometrically diminishing step size rule will converge to a matrix B̂∗ such that span(B̂∗) ≡ S⊥.
Proof By Assumption 1 we have that all columns of B0 will satisfy the sufficient condition for convergence of DPCP-PSGM (Algorithm 1) to a normal vector of S . From Lemma 6 and we use the inequality σc′(B0) > ‖∆̂‖2 which ensures full-rankness of B̂∗, which is the key ingredient in order to prove that span(B̂∗) = S⊥. We can then Use Theorem 9 for matrixB0. Note that columns ofB0 are drawn independently and are uniformly distributed on the unit sphere. Hence, columns ofB0 are sampled by subgaussian distribution and the LHS of the inequality of the theorem appears if we scale with 1√
D so that to create unit-norm columns and use LHS of the inequality of Theorem 7. The RHS
of the inequality is due to the upper bound of ‖∆̂‖2 as stated in Lemma 8. The absolute constants C1, C2 depend only the subgaussian norm of the uniform distribution (they is no dependency on the dimensions of the problem).

heading: B EXPERIMENTAL DETAILS AND ADDITIONAL MATERIAL
text: All experiments were conducted on a MacBook Pro 2.6GhZ 6-Core Intel Core i7, memory 16GB 2667 Mhz DDR using Matlab2019B. For computational purposes and in order to avoid fine-tuning of the piecewise geometrically diminishing (PGD) step size, the modified backtracking line-search (MBLS) step-size rule was adopted for DPCP-PSGM as proposed in Zhu et al. (2018). We define the distance between two subspaces spanned by matricesB andA as dist(B,A) = minQ∈O(D,c) ‖B −AQ‖F where O(D, c) denotes the Stiefel manifold of orthogonal matrices of rank c. Note that dist(B,A) = 0 ⇐⇒ span(B) ≡ span(A) (see Zhu et al. (2019)).

heading: B.1 OUTLIERS PURSUIT IN WASHINGTON DC MALL AVIRIS HSI
text: Hyperspectral images (HSIs) provide rich spectral information as compared to RGB images capturing a wide range of the electromagnetic spectrum. Washington DC Mall AVIRIS HSI contains contiguous spectral bands captured at 0.4 to 2.4µm region of visible and infrared spectrum, Giampouras et al. (2019). In this experiments we randomly choose 10 out of its 210 spectral bands. Due to high coherence in the both the spectral and the spatial domain, pixels of HSIs admit representations in low-dimensional subspaces. Here, we use a 100×100 segment of the hyperspectral image selecting randomly 10 out of its D = 210 spectral bands. We form a matrix X̃ of size 10 × 10000 whose columns correspond to different points in the 10-dimensional ambient space. Then we corrupt columns of X̃ by replacing them with outliers that are generated uniformly at random with unit `2 norm for two different outliers’ ratios i.e., r = 0.8 and r = 0.9. In the corrupted X̃ , the remaining clear pixels are considered as the inliers. Table 1 displays the F1 scores obtained by DPCP-PSGM, RSGM and DPCP-IRLS algorithm. The latter two algorithms are evaluated in two scenarios: a) codimension is initialized c′ = 5 and b) c′ = 10. Given the singular value distribution of the initial image, we infer that the dimension d of the inliers’ subspace is less or equal than 5.
Hence, c′ = 5 (recall c = D − d) is close to the true codimension value while c′ = 10 is an overestimate thereof. From Table 1, we can see that the proposed DPCP-PSGM succeeds in both outliers’ ratios regardless its unawareness of the true codimension value. On the other hand, DPCPIRLS and RSGM fail when initialized with c = 10 and this is attributed to the restrictions induced
due to the orthogonality constraints they both impose. In Fig. 4 we provide annotated versions of the clean HSI, its corrupted by outliers version for outliers’ ratio r = 90%, and the annotated outliers as recovered by the proposed DPCP-PSGM, RSGM, RSGM with c′ = 5 and DPCP-IRLS with c′ = 5.

Review summaries:
This paper is concerned with the Robust Subspace Recovery (RSR) problem. That is, one tries to estimate an unknown subspace given some data, where some of the entries are corrupted. This paper studies the setting, where the subspace to be recovered has large dimension, i.e. the co-dimension of this subspace is small.   Whereas previous work tackles this question, it requires that the dimension of the subspace to be recovered is known a-priori. This work proposes a new algorithm, which is able to recover the subspace without knowing this dimension.  The contributions of this paper are threefold. 1. It proposes a new algorithm, which does not need a-priori knowledge of the unknown subspace. 2. Some theory for the new algorithm is developed. 3. The algorithm is tested on both synthetic and real data.

This paper studies robust sparse recovery when the dimension of the subspace is not known. It finds a basis of the orthogonal complement of the subspace via dual principal component pursuit (DPCP), but without explicitly imposing orthogonality between the columns. The authors propose a projected sub-gradient method with random initialization and overestimate of the dimension, and show theoretical results. Simulation experiments are provided.

The work proposed a simple framework that allows performing robust subspace recovery without requiring a priori knowledge of the subspace codimension. The proposed approach is based on Dual Principal Component Pursuit (DPCP), which is amenable to handling subspaces of high relative dimensions. Empirical results corroborate the developed theory and showcase the merits of the proposed optimization methods.

This paper discusses solving robust subspace recovery by solving parallel versions of $\min_b$ $\|X^Tb\|_1$ st $\| b\|_2=1$, for random initializations of $b$, using projected subgradient method. The argument is that using this  method, in the limit where the number of inliers greatly outnumber the outliers, that if the inlier dimension is c, then c random initializations will converge on identifying this dimension with probability 1. Experimental results and proofs are given to prove this idea.