Implicit Bias of Projected Subgradient Method Gives Provable Robust Recovery of Subspaces of Unknown Codimension
Authors: Paris Giampouras
Benjamin David Haeffele
Rene Vidal
Venue: ICLR 2022 Spotlight (2022)
Keywords: representation learning
robust subspace recovery
dual principals component pursuit
outliers
model selection

Abstract: Robust subspace recovery (RSR) is the problem of learning a subspace from sample data points corrupted by outliers. Dual Principal Component Pursuit (DPCP) is a robust subspace recovery method that aims to find a basis for the orthogonal complement of the subspace by minimizing the sum of the distances of the points to the subspaces subject to orthogonality constraints on the basis. 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. In this paper, we show that if the orthogonality constraints --adopted in previous DPCP formulations-- are relaxed and random initialization is used instead of spectral one, DPCP can provably recover a subspace of \emph{unknown dimension}. Specifically, 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 succeeds 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 the PSGM algorithm that allows us to perform RSR without knowing the subspace dimension

Published as a conference paper at ICLR 2022
IMPLICIT BIAS OF PROJECTED SUBGRADIENT METHOD GIVES PROVABLE ROBUST RECOVERY OF SUBSPACES OF UNKNOWN CODIMENSION
Paris Giampouras, Benjamin D. Haeffele and René Vidal Mathematical Institute for Data Science Johns Hopkins University
Baltimore, MD, USA
(parisg, bww. ffele, rvida widaall 1 fuuu.cc. edu
ABSTRACT
Robust subspace recovery (RSR) is the problem of learning subspace from sample data points corrupted by outliers. Dual Principal Component Pursuit (DPCP) is a robust subspace recovery method that aims to find basis for the orthogonal complement of the subspace by minimizing the of the distances of the points to the subspaces subject to orthogonality constraints on the basis. 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. In this paper, we show that if the orthogonality constraints -adopted in previous DPCP formulations- are relaxed and random initialization is used instead of spectral one, DPCP can provably recover subspace of unknown dimension. Specifically, we propose a very simple algorithm based on running multiple instances of projected sub- -ab-gradient descent method (PSGM), with each problem instance seeking find one vector the null space of the subspace. We theoretically prove that under mild conditions this approach succeeds with high probability. particular, we show that 1) the problem instances will converge and 2) the ensemble of problem instance solutions will be sufficiently diverse 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 the PSGM algorithm that allows us to perform RSR without knowing the subspace dimension.
vector in the nullspace of the subspace
INTRODUCTION
Robust subspace recovery (RSR) refers to the problem of identifying an underlying linear subspace (with dimension less than the ambient data dimension) from sample data points that are potentially corrupted with outliers (i.e., points that do not lie the linear subspace). Many methods for RSR have been proposed in the literature over the past several years (Xu et al. 2012 You al. 2017a Lerman & Maunu 2018). Formulations based on convex relaxations and decompositions of the data matrix into low-rank matrix plus matrix of sparse corruptions either entrywise-sparse corruptions in Candès et al. 2011) or columnwise-spars corruptions as in Xu et al. (2012); McCoy & Tropp (001 can, in certain situations, be shown provably recover the true subspace when the dimension 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 for the more challenging regime of subspaces of high relative dimension (i.c., when D R 1).
Dual Principal Component Pursuit. 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). As implied by its name, DPCP follows a dual perspective of RSR by aiming to recover basis for the orthogonal complement of the inliers' subspace. As shown in (Takiris & Vidal 2018). DPCP is provably robust recovering subspaces of high relative dimension. However, key limitation of DPCP is that it requires a priori knowledge of the true subspace dimension.

---

Published as a conference paper at ICLR 2022
DPCP for 1. Let X (DDx(N+M) denote the data matrix defined as X X OJT, where DDN
X E is a matrix containing N inliers as its columns, O E Rx is a matrix containing M outliers, and I is an unknown permutation matrix. DPCP was first formulated by Tsakiris & Vidal (2018) for handling subspaces of codimension c. = D - d equal to (i.e., the subspace a hyperplane with dimension d = D 1). In this case, DPCP is formulated the optimization problem
min BER
X
b|11 s.t. ||b||2 =
which is nonconvex due to the spherical constraint imposed on the normal vector b SD-1 of the D 1 dimensional hyperplane. Tsakiris & Vidal showed that the global minimizer of (I is normal vector of the underlying true hyperplane when 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, (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 datasets heavily corrupted by outliers. Moreover, the authors introduced a projected subgradient method which converges to a normal vector of the true subspace at linear rate.
Recursive DPCP for known e > Zhu et al. (2018) also proposed an extension to DPCP to subspaces with codimension > 1 via projected subgradient algorithm that tries to learn normal vectors to the subspace in a recursive manner. Specifically, after convergence to 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, knowledge of the true subspace codimension e becomes critical. Specifically, if an underestimate of the true codimension is assumed the recovered basis for the null space, B, will fail to span the whole null space, S1. On the other hand, an overestimate of will lead to columns of B corresponding vectors that lie in S.
Orthogonal DPCP for known c. Zhu et al. (019) proposed an alternative to T which attempts to solve for normal vectors to the subspace at once by minimizing the sum of the distances from the points to the subspace:
min
X Bl1,2 s.t. B
(2)
B
The authors also proposed an optimization algorithm based on the projected Riemannian subgradient method (RSGM), which builds on similar ideas the projected subgradient method of Zhuu et al.
(2018) and enjoys a linear converge rate when the step size is selected based on a geometrically diminishing rule. [Ding et al. (202T) provided a geometric analysis of 2 which shows the merits of DPCP in handling a) datasets highly contaminated by outliers (in the order of M O(N2)) and b) subspaces of high relative dimension. However, key shortcoming of this approach is that, because all minimizers of (2) are orthogonal matrices, a prerequisite for recovering the correct orthogonal complement of the inliers subspace is the a priori knowledge of the true codimension e (see Fig. D.
Contributions. In this work, we address this key limitation by proposing framework that allows us to perform robust subspace recovery in the high relative subspace dimension regime without requiring a priori knowledge of the true subspace dimension. In particular, our proposed approach based on the simple idea of solving multiple, parallel instances of the DPCP formulation for subspaces of codimension one,
EIXTbIl s.t. ||b:l12 =1 i= 1, BEROXE
min
(3)
where c' is assumed to be an upper bound of c, i.e., c' c. Contrary to 2 the objective function in 3 decouples over the columns b; of matrix B = [b, by ...b.) and thus can be solved in a parallel manner by independently applying a projected subgradient algorithm (referred to as PSGM) from df different random initializations. 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' < and thus can span S when = c. c' > e then PSGM will return é' - c redundant vectors that will still lie in S yet they will be linearly dependent (see Figure []. That being said, we show that this simple strategy permits to robustly recover the true subspace even without knowledge of the true codimension c.
As is detailed in Sections 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 follows:
2

---

Published as a conference paper at ICLR 2022
6.
6
(8))
Ph. (4)
K1. Fs.
(4)
Figure 1: Graphical illustration of the recovered normal vectors of S by (left) the proposed DPCP- PSGM approach and (right) methods that use spectral initialization and impose orthogonality con- straints. Initial vectors 6%. 62. by are randomly initialized and are non-orthogonal in (left) and spec- trally initialized (hence orthogonal) in (right). Note that in (left) rank (B*) (where B [bj, bū bg]) equals to the true codimension = 2 of S and span B*) S_ while in (right) B is orthogonal hence rank (*) 3 with bū
1. First, study continuous version of (3) where the inliers and outliers are drawn from continuous measures. We show that this induces benign landscape on the DPCP objective, which can be analyzed more easily. Specifically, a projected subgradient algorithm that implicitly biases solutions towards low-rank matrices B E Dxe' whose columns are the projections of the randomly initialized columns of B onto S1. As result, B almost surely spans S1 as long as it is randomly initialized with c' 2
prove that the DPCP problem in B can be solved via
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 matrix B This compelling feature of OPCP-PSGN allows to derive sufficient condition and probabilistic bound guarantecing when the matrix B Dxe' spans S1.
3. We provide empirical results both simulated and real datasets, corrobortting theory and showing the robustness of our approach even without knowledge of the true subspace codimension.
RELATED WORK
Learning underlying low-dimensional subspace representations of data has been 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, Dolliffe & Cadimal (2016). Albeit, it is originally formulated as nonconvex optimization problem, PCA can be easily solved in closed form using singular value decomposition (SVD) operation (see e.g. Vidal 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 & norm sense.
Subspace Recovery.
subspace,Dolliffe
Robust Subspace Recovery (RSR). To remedy this weakness of PCA robust subspace recovery (RSR) methods attempt identify the outliers in the dataset an recover the true underlying low- dimensional subspace of the inliers Lerman & Maunu (2018): Maunu et al. (2019). A classical approach this problem is RANSAC randomly chooses per iteration d points and then fits a d' 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 outliers high (as well as the fact that RANSAC also needs knowledge of the true subspace dimension, d). The need to tackle inherent shortcomings alternative convex formulations of RSR. Xu et al. (2012); You al. (2017b); Rahmani & Atia (2017); Zhang & Lerman (2014). In Xu et al. (2012) the authors decompose the data matrix as a sum of low-rank and column-span column-sparre component. However, theoretical guarantees obtained for convex
Bolles (1981) which is given time budget and
RANSAC pertaining to computational complexity issues inspired
3

---

Published as a conference paper at ICLR 2022
formulations only hold for subspaces of relatively low-dimensional subspaces i.e., for d < D where 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 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 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 [aij er al. (2019) proved that e Ocelog c) independent random initial vectors suffice in order to recover with high probability a dictionary of size D x c with high accuracy. In this paper we aim to recover basis of the orthogonal complement of 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 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 al. (2020) showed that Robust PCA can be suitably re- parametrized in such a way to favor low-rank and sparse solutions without using any explicit regularization. this work, we use the term implicit bias for describing the convergence of DPCP- PSGM 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., e' 2 c and c) PSGM randomly initialized.
DUAL PRINCIPAL COMPONENT PURSUIT AND THE PROJECTED SUBGRADIENT METHOD
We re-write the DPCP formulation given in as
min BER
|X
b11
T|xbb|1 + +110 60]l s.t. ||bl|2 = 1
(4)
In Zhu et al. (2018), the authors proposed a projected subgradient descent algorithm for addressing that consists of subgradient step followed by a projection onto the sphere i.e..
b |--1 1 8t - (XSgn(X b²) + OSgn(O TT*)) b²))
and k++
PsD- (go--(b (b)
(5)
where n² is the adaptively updated per iteration- step size and 6* is the unit b 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 __max that reflect the geometry of the problem and are defined as
Cx.min .inn 1 minggge-ins ins X bll2 and cx maa x maxtesp-irs ||X bl|1. Note that the more well distributed the inliers are in the subspace 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 vector b in the subspace S that is orthogonal to the inliers. Moreover, Cx auin and Cx max converge to the same value as N + Do provided the inliers are uniformly distributed in the subspace i.c.. ex.min min + Cd, CX max + Ca, where ea is given as the average height of the unit hemisphere on Rd,
(d 2)!! ca (d 1)!! 1, if is odd
(2. if is even,
le(k- 2) 4) .. 2, k is even. k(k (): 4) ... .. 1, k is odd
where k!!
(6)
Similarly Cx .uin: Cx max. 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 = mingg3o-1 x7 | b/] and cO.max = max 37 | bl] I- 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
4

---

Published as a conference paper at ICLR 2022
zero as M - oo. Further, if the outliers uniformly distributed on the sphere, then co max - cD and C0, - CD where ep defined as in (6). (Zhu et al. 2018).
Finally, we also define the quantities пo = 37 maxbes2 1 [I( - bb JOSgn(O b)ll2 and 7 = M maxbes (Ps bb To ) Sgn(X X b)]l2. As M oo and assuming outliers in O are well- distributed we get OO b) + cpb thus fl + (Tsakiris & Vidal 2018). Likewise, as N - DO provided that inliers are uniformly distributed 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 (T.
- 0
Theorem (Informal Theorem 3 of Thu et al. (2018) Let (b&) the sequence generated by the projected subgradient algorithm in Zhu al. (2018), with initialization by such that
Nex miin
80
arctan
and Ncx.um min 2 Nux + Mno
Nпx + Mno
where Oo denotes the principal angle of bd from Si. If the step size n²th is updated according piecewise geometrically diminishing rule given as
14" L 3111--K00/K111,
<< Ko
=
(8)
2 Ko
where B < [-] is the floor function, then the iterates bt converge to a normal vector of S,
4 DUAL PRINCIPAL COMPONENT PURSUIT IN SUBSPACES OF UNKNOWN CODIMENSION
Current theoretical results provide guarantees for recovering the true inlier subspace, when the pro- posed algorithms know priori of the subspace codimension which is 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 B, along with theoretical analysis that gives guarantees of recovering the true underlying subspace even when the true codimension e unknown. First we analyze continuous version of DPCP, which arises when the number of inliers and outliers are distributed according to continuous measures and their number tends to co. The continuous DPCP incurs optimization problem with benign landscape that allows to better illustrate the favorable properties of DPCP-PSGM when it comes to the convergence of its iterates. Then we extend the results the discrete case that deals with finite number of inliers and outliers yielding more challenging optimization landscape.
4.1 PSGM's ITERATES CONVERGENCE THE CONTINUOUS VERSION OF DPCP
The following lemma provides the continuous version of the discrete objective function given in 3
Lemma In the continuous case, the discrete DPCP problem given in is reformulated as,
min Be Σ (pEp [fb.] + (1 p) a nn (fo.)) = Σ |bbll22 (pcp + (1 p00cppcsssssh)
E
i=1
|bb1122 = 1, == s.t.
where fo DD RR fb(z) T2 b), 6, is the principal angle of b, from the inliers subspace S and p is the probability of occurrence of an outlier.
Note that p Ing are the continuous measures associated with the outliers and inliers, respectively. Evidently, (9) attains its global minimum for vectors b,s that orthogonal to the inliers' subspace. Based on (3) and due to Lemma we can now minimize the objective function of the "continuous version" of DPCP by employing projected subgradient methods (PSGM) that
5

---

Published as a conference paper at ICLR 2022
performs the following steps per iteration
b g++1
b. 1p + (1 - -))cas)) and 8 = (b,+1) ; 1,2, 1,2,...,,
(10)
Lemma A projected subgradient algorithm consisting of the steps described in (TC using a piece- wise geometrically diminishing step size rule (see (3) in Theorem 1) will almost surely asymptotically converge matrix B' T Dxe' whose columns b7 1,2,..., will be normal vectors of the inliers' subspace when randomly initialized with vectors by E ESP-1 1,2....5 uniformly distributed over the sphere SD-1
Lemma alllows to claim that we can always recover è' 2 normal vectors the inliers' subspace using a PSGM algorithm consisting of steps given in (TO). However, this does not tell the whole story yet, since our ultimate objective is to recover a matrix B that spans S1. Thus, it remains to show that the rank of B is equal to the true and unknown codimension of the inliers' subspace Next we prove that by initializing with Bg such that rank Bb) d' (i.e., Bo 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) = e thus getting span( B) = S (along with recovering the true subspace dimension). By projecting the PSGM iterates given in (TO) onto S have,
Ps. (b,+1) = (1 - PPs) (B(+) and Ps, (b:+t) = Pss (P&D (b,++1)
(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
Lemma The PSGM iterates b i= 1,-1,,, 1,2,...., initialized with bis, =
1,2.... given in 10 when randomly c' that are independently drawn from a spherical distribution with unit Eg norm converge almost surely to c' normal vectors of the inliers subspace denoted as
o;, 1,2..... that are given by b iPs (l))
Pss (b.)
1,2....,
Lemma shows that the initialization of PSGM plays a pivotal role since it determines the direction of the recovered normal vectors {bū Lemmas and pave the way for Theorem
Theorem Let B E Dxd where 2 with e denoting the true codimension of the inliers subspace S, consisting of unit lg norm column vectors b E SD-1, 3D-1,i- 1,2,.... ..,.....d that are indepen- dently drawn from uniform distribution over the sphere D-1, 1, PSGM algorithm initialized with BO will almost surely converge to a matrix B such that span B²) = S1.
From Theorem we observe that in the benign scenario where inliers and outliers distributed under continuous measures, we can recover the correct orthogonal complement of the inlier's s subspace when we oblivious its true codimension. Remarkably, this is achieved by exploiting the implicit bias induced by multiple random initializations the PSGM algorithm for solving the DPCP formulation given 33. which is free of orthogonality constraints.
4.2 PSGM's ' ITERATES CONVERGENCE THE DISCRETE VERSION OF DPCP
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, reformulate the DPCP objective as follows
Σ x b.
Σ
| bill + +10 b.ll M M
b ob. + N
Lb.
(12)
where Zb; and ob, are called as average inliers and average outliess terms, defined as ab; N E Syn(b, æ and Ob, = गे Σソ Sgn(b, 0,)o,,
In Algorithm M we give the projected subgradient method (DPCP-PSGM) applied on the DPCP problem given in (3)
Note that 2 a|lbla
T for b a and [b.ll2cos((b)) b, 6, where Ps(b.)
[Pa

---

Published as a conference paper at ICLR 2022
Algorithm 1: DPCP-PSGM algorithm for solving
Result: B [66, 6 ...... ... .,.....,,.. 6
Initialize: Randomly sample by. by.... bú from a uniform distribution on S SP11, for k = 1,,.... do
for i = 1,2, 1........ do Update the step-size according to specific rule;
b = 6 (M + +No
B = P30-111 (b,tt);
end
end
Note that the average outliers and inliers terms are discrete versions of the corresponding continuous average terms cDb, and caš; where s; (b(.,), respectively, Tsakiris & Vidal (2018) We now express the sub-gradient step of Algorithm Jas
b. by - 11 (M(enby + +e0 + N(nss + +ex) i.k)
(13)
i.k = og - enb - and e = Jtz cD& account for the error between the where the quantities e continuous and discrete versions of the average outliers and the average inliers terms, respectively, Following a similar path as continuous case we next project the iterates of (13 onto S..
Ps. (b++)) = Ps.(6)) uh (PDs + e + NN Ps - L.k
(14)
11- Ps - MPM
Remark. Eq. (14) reveals that DPCP-PSGM. applied on the discrete problem, gives rise to updates whose projections to S1 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.))
and we can rewrite the update of the 2nd iteration of DPCP-PSGM, | ||
(b'))
(1 1 Mcp) ((1 ((1 (1- McD)) (6.) - - MPs (e:0) - (MM
Ps, (b?)
|bll
(1 -/MMcp) 10 Mcp) Ps. (B.) (1 m1 Mcp)
1b / MPMPs (e:0) - MPM (e)
||||116666112
(15)
where we have assumed that ||b| 1. By repeatedly applying the same steps, reach to the following recursive expression for Ps. (b,),
K-1
p McD)
K-1
K
(1 McD)
Ps_(bb)
II K=0
Ps. (b:)
Σ
/ MPs i.k
|
|bbl
k=
j=k+1
(16)
where for > K 1 set K-
(2-4 McD)
1.
1 lla
By dividing 16 with II
K-1
(1-p) Men) and by projecting onto the sphere SD-1 we get [|b]
k=
i.k Pgo-i (b:k) Poo-1 (Ps_ (b.) Ps. (6%))
(17)
where 5, defined as 8.K = K-1 (II
|
1º M
(--(MMp)
Assumption 1.
We assume that the principal angles 0 for all bbs satisfy the inequality 0 < Nex.min Nox
arctan
Vi,i= 1=1,22 ....
7

---

Published as a conference paper at ICLR 2022
Assumption 1 essentially assumes that the sufficient condition given in eq. required by PSGM algorithm for converging to a normal vector is satisfied which is the same condition for success in Zhu et al. (2088). Under Assumption I we can invoke the convergence properties of PSGM given
in Theorem and get K + 00, Psp 1 (Ps (bk)) + b' E 81
SD-1, That being said, we
denote 6; Pgp (b.) Ps_ (6:) where d; lim 8
Following the same steps
as Section 4.1 and by defining matrices B [bj. b3 b0l B = [6 b9. bg Á
18,,6 82. ] we can express the matrix B as B = P30-1 (Ps
1 - where B will
now consist of normal vectors of the inliers' subspace. In order to guarantee that span S1 thus suffices to ensure that rank (B*) = Here we show that a sufficient condition for this to hold
is that the matrix A = B Å is full-rank.
Lemma 6 If de B
A
2 then matrix A = BD - P is full-rank.
From Lemma 6 we can see that the success of DPCP-PSGM hinges on how well-conditioned the matrix B 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 Let B E RDx with columns randomly sampled from a unit l2 norm spherical distribution where d 2 c with denoting the true codimension of the inliers subspace S that satisfies Assumption I. If
C
1 1-C
vD ven(no + co, ca)
(18)
gV/K then with probability at least 1-2 11-eex((-e(0) (where C1, C2 are absolute constants), Algorithm with a piece- wise geometrically diminishing step size rule will converge to a matrix B such that span (B*) Si.
where = max; 3Ka/K-(1-rz) and r, (xe
Mp.
m
1- Mep
Note that quantities B, K., Ko are used in the step-size update rule that is used as defined in 8 (See also full version of Theorem in Appendix)). Theorem shows that we can randomly initialize DPCP- PSGM, with a matrix 80 whose number of columns c' is an overestimate of the true codimension 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 O since no + 0 and Co max + c.) in the continuous case which incurs a benign geometry. Moreover, the less benign geometry would increase the value of (no + CO max ca)
thus requiring a smaller initial codimension c' that would lead to larger values the LHS of (8
5 NUMERICAL SIMULATIONS
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.c., DPCP-IRLS Takiiris & Vidal (011)) and the Riemannian Subgradient Method (RSGM) Zhu et al. 2019). Recall that both DPCP-IRLS and RSGM address DPCP problem by enforeing 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., 8d E IR Dxe' which contains the first d'
eigenvectors of matrix X as its columns, as proposed in Tsakiris & Vidal (018)).
Robustness to outliers in the unknown codimension regime. In this experiment we set the dimen- sion of the ambicnt space to D = 200. We randomly generate N inliers uniformly distributed with unit &g norm in a d = 195 dimensional subspace (hence for its codimension Following a similar process we generate M outliers that live in the ambient space and are sampled
have D d = 5).
For 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 of Lemma for further details.
8

---

Published as a conference paper at ICLR 2022
5000
5000
5000
4000
4000
4000
3000
2000
2000
2000
1000
1000
1000
800
1000
1200
1400
800
1000
1200
1400
1400
Figure 2: Distances of the recovered B from the true orthogonal complements S1 as recovered by the proposed DPCP-PSGM algorithm provided an overestimated of the true i.e. c' 10 (left), RSGM provided the true (middle) and RSGM provided c' = 10 (right). Darker colors reflect higher values of distances while lighter colors indicate successful recoveries of B.
N'
from a uniform distribution over the unit sphere. Fig. illustrates the distances (see Appendix) of the recovered matrix B as obtained by the proposed DPCP-PSGIE algorithm initialized with an overestimate
10 of the true codimension e codimension and two versions of RSGM i.e., RSGM when it is given as input true c = 5 and RSGM when being incognizant of and hence it initialized with a e' 10 of cAs 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 which is attributed spectral initialization and the imposed orthogonality constraints. On the contrary, DPCP-PSGN displays a remarkably robust behavior (Fig. 2 middle) even without knowing the true value of performing similarly to RSGM when the latter knows beforehand the correct codimension (Fig. (left)).
the recovery of the true codimen- sion of the inliers' subspace S. Again, we set D = 200 and generate N 1500 inliers as before. We vary the true codimension of S from
Recovery of the true codimension. Here test DPCP-PSGM
10 to 20 and consider two different outlier's ratios defined as r = M+N namely r = 0.6 and r = 0.7. In both cases, DPCP-PSGM is initialized with the same overestimate of с i.e. = 30. In Fig. 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 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 the cases that fails to exactly compute c. The results corroborate the theory showing that the DPCP-PSGM with random initialization biases the solutions of towards matrices with rank c.
M
CONCLUSIONS
We proposed a simple frame- work which allows us to per- form robust subspace recovery without requiring priori knowl- edge of the subspace codimen- sion. This is based on Dual Prin- cipal Component Pursuit (DPCP) and thus is amenable to han- dling subspaces of high relative dimensions. We observed that projected subgradient method (PSGM) induces implicit bias and converges to a matrix that spans a basis of the orthogonal comple- overestimate it codimension, b) lift orthogonality
codiieession
18
est. codiraetsion
18
16
14
14
12
14
16
16
18
true codimensionn
true rodimension
Figure 3: Estimated by OPCP-PSGM. codimensions for two dif-
ferent outliers' ratios M+N (right)
M (a) r 0.6 (left) and (b) 0.7
ment of the inliers subspace even long constraints enforced in previous DPCP formulations and c) use random initialization. Empirical results that corroborate the developed theory and showcase the merits of our approach.
9

---

Published as a conference paper at ICLR 2022
Ethics Statement This work focuses theoretical aspects of robust subspace recovery problem which a well-established topic in framework of this work raises ethical issues or any violations vis-a-vis the ICLR Code of Ethics.
machine learning research. The research conducted in the
ACKNOWLEDGMENTS
We would like to thank Christian Kümmerle for helpful discussions on the probabilistic theorem that is used in Theorem 7. This work is partially supported by by the European Union under the Horizon 2020 Marie-Sktodowska- Curie Global Fellowship program: HyPPOCRATES, H2020- MSCA-II- 20-18, Grant Agreement Number: 844290, and the NSF Grants 1704458, 2031985 and 1934979.
REFERENCES
Yu Bai, Qijia Jiang, and Ju Sun. Subgradient descent learns orthogonal dictionaries. In International Conference on Learning Representations, 2019. URL htK.:tttps::/peeeeeeee... wwr.eeeetfff??
Hd-
Emmanuel J Candès, Xiaodong Li, Yi Ma, and John Wright. Robust principal component analysis? Journal of the ACM (JACM), 58(3):1-37, 2011.
Tianyu Ding, Zhihui Zhu, Rene Vidal, and Daniel P Robinson. Dual principal component pursuit for robust subspace learning: Theory and algorithms for a holistic approach. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 2748- PMLR, 18-24 Jul 2021. URLhttppa httptttstpppceeeeeeeeeee http://pweeeeaae.....eeeeeeeeaa/ wtt.m/..peeeee/1//11a....222.2.
Martin A Fischler and Robert C Bolles. Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Communications of the ACM, 24 (6):381-395, 1981.
Paris V. Giampouras, Athanasios A. Rontogiannis, and Konstantinos D. Koutroumbas. Alternt-- ing iteratively reweighted least squares minimization for low-rank matrix factorization. IEEE Transactions on Signal Processing, 67(2):490-555 50390005,,,000 2019. doi: 10. 10.1109/TSP2201888888999
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 Proceedings of Machine Learning Research, pp. 1832-1841. PMLR, 10-15 Jul 2018. URL mlr.
ngs
lan Jolliffe and Jorge Cadima. Principal component analysis: a review and recent developments. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 374(2065):2015022,, 2016.
Gilad Lerman and Tyler Maunu. An overview of robust subspace recovery. Proceedings of the IEEE, 18066) 2018.
Gilad Lerman, Michael McCoy, Joel A Tropp. and Teng Zhang. Robust computation of linear models by convex relaxation. Foundations of Computational Mathematics, 15(2):363-410, 2015.
Tyler Maunu, Teng Zhang, and Gilad Lerman. A well-tempered landscape for non-convex robust subspace recovery. Journal of Machine Learning Research, 20(37), 2019.
Michael McCoy and Joel A Tropp. Two proposals for robust PCA using semidefinite programming. Electronic Journal of Statistics, 5:1123-1160. 2011.
Qing Qu, Zhihui Zhu, Xiao Li, Manolis Tsakiris, John Wright, and René Vidal. Finding the sparsest vectors in a subspace: Theory, algorithms, and applications. arXiv preprint MXX1:2001.06977 2020.
10

---

Published as a conference paper at ICLR 2022
Mostafa Rahmani and George Atia. Coherence pursuit: Fast, simple, and robust subspace recovery. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Ma- chine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 2864 2873. PMLR. 06-11 Aug 2017. https://// httpss://proceee /ttp///ooeeddeeeee ngs m www...m............ee......e..ee www.s/vessvvv.o. re0//aaamannn a. html
Manolis C. Tsakiris and René Vidal. Dual principal component pursuit. Journal of Machine Learning Research, 19(18):1-50, 2018.
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3027, 2010.
René Vidal, Yi Ma, and S Shankar Sastry. Generalized principal component analysis, volume 5. Springer, 2016.
Huan Xu, Constantine Caramanis, and Sujay Sanghavi. Robust PCA via outlier pursuit. IEEE Transactions on Information Theory, 384533304--3064, 2012.
C. You, D. Robinson, and R. Vidal. Provable self-representation based outlier detection union of subspaces. In IEFE Conference Computer Vision and Putlern Recognition, pp. 2017a.
Chong You, Daniel Robinson, and René Vidal. Provable relfsseerrsnnttttion based outlier detection in umion of subspaces. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 3395-3404, 2017b.
Chong You, Zhihui Zhu, Qing Qu, and Yi Ma. Robust recovery via implicit bias of discrepant learning rates for double wwe-pparameterization. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 17733-17744. Curran Associates, Inc., 2020. URL. utt.htttps://proceeedeie neur ps cC/ pdf.
Teng Zhang and Gilad Lerman. A novel m-estimator for robust PCA. The Journal of Machine Learning Research, 15(1):749-888 808, 2014.
Z. Zhu, T. Ding, M. C. Tsakiris, D. P. Robinson, and R. Vidal. A linearly convergent method for non-smooth non-convex optimization on the grassmannian with applications robust subspace and dictionary learning. In Neural Information Processing Systems (NIPS), 2019.
Zhihui Zhu, Yifan Wang, Daniel Robinson, Daniel Naiman, René Vidal, and Manolis Tsakiris. Dual principal component pursuit: Improved analysis and efficient algorithms. In Advances in Neural Information Processing Systems 2018, volume 31. Curran Asso-
ciates, Inc., 2018. URL hsttpa://procedding wtt.::/s.nnrrrs..coooooo http:///oooooro......oooooo./oas
af2 c4210000000222277355777085553330

---

Published as a conference paper at ICLR 2022
A APPENDIX
Theorem (Theorem 3 of Zhu al.
(2018)) Let {b&} the sequence generated by the projected
subgradient method in Zhu et al. 2018), with initialization be such that
Nex. min
0o < arctan
(19)
Nux + M
where Og denotes the principal angle of bD from S1, and
Nex.min 2 Nux Mno
(20)
Lef p == 4mxx Moo max piece-wise geometrically diminishing rule given
If nt S pl and the step size nhd is updated according to
41
Ko
(21)
z Ko
where B < 1, I-] is the floor function, and Ko, Kr E N are chosen such that
Kn 2 K (1²);
K, 2 (V28p' (Nex (Nux + Mnol))
where,
tan(On)
( =
(22)
p (Nex min max;1, (1 tan() (Nux + Mno))
then for the angle 02 between be and $1 it holds
tan(0.) s { max(tan 72 } Kn
(23)
V2n" 3 (l-6-Ko)// Ko)/K.)
z Ko
A.1 PROOF OF LEMMA 2
Lemma In the continuous case, the discrete DPCP problem given in is reformulated as,
- Σ (p [sb.] + (1 E - Ins (fb.]) = Σ |blll2 (pcp + (1 (1=p)ccco((5))
min BERDx
i=1
| = 1, i= 1,2...... s.t.
(24)
where fo DDD IR, fb(z) Tz,,,, b), 6i the principal angle of b, from the inliers subspace S and p is the probability of occurrence of an outlier.
Proof We define the discrete measures μax, 14o associated with the inliers and outliers, respectively as.
1 N M
1 Σ 8(z 0;), po(z)=
xx (z)
Σ 8(z xz))
(25)
where 5(-) is the Dirac function. Recall that,
[S5p_, g(z)8(z -o0ddgooooo---o g(20)
(26)
where g SD-1 Th and pan-1 is the uniform measure SD-1
12

---

Published as a conference paper at ICLR 2022
The DPCP objective for the discrete version of the problem divided by M N can be written as,
M
1
bill1
[1X bill1
+110
1
x
b;
Σ
10 bil
+
M
N
M
N
Σ
Σ
1 bilo(( 20)
Σ
z bblo0 0, 01)d(1z0-1
M N
/=1 EEED
ZESD
1
/ESoo-1
/
M
M+NN
Σ
bz] Σ 5(z xz 2dj)duo--1 +
Iz bi Σ 8(2 o5)ddego-1
Ld(z
M M+N2
2280-1
1=1
(pxxx [fb,] +
Note that pxx No arise by discretizing the continuous uniform measures Mgo-1 and pgo-ins respectively (Jgn-ing denotes the uniform measure on SD-1 S) and p the probability of occurrence of an outlier i.e., M+N - N + (1 corresponds to the probability of occurrence of an inlier). That being said, the continuous version of DPCP can be simply stated by replacing fxx po with uga-1 and Mga-ins equation 27 as follows,
M
min
(pE p [fb.] + (1 pg (fb.l)))
The RHS of (9) immediately shows up by invoking Proposition in Tsakiris & Vidal (0118.
A.2 PROOF OF LEMMA 3
Lemma 3: A projected subgradient algorithm consisting of the steps described in (0)) using a piece- wise geometrically diminishing step size rule (see (8) in Theorem 1) will almost surely asymptotically converge matrix 3" DDxx' whose columns b 1, 2, 2,...,e' c' will be normal vectors of the inliers' subspace when randomly initialized with vectors by SD-1, i= 1.2....,4 e' uniformly distributed over the sphere DD-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 Theorem becomes 0 in the continuous case (since 7x + O, no + 0, cx - ca >> 0) and b) the set of unit l2 no-norm vectors b,s, i 2.2.... c' sampled independently by uniform distribution over the sphere and whose principal angle 0 is I 7 form the inliers' subspace has measure 0.
A.3 PROOF OF THEBREM 5
Lemma 4 The PSGM iterates i i, initialized with 6.s, 1,2, .....' that are independently drawn from a spherical distribution with unit E norm converge almost surely to e' normal vectors of the inliers subspuce S denoted as b;, i= 1, 2. d' that are given by
k=
given in 10). when randomly
Ps, Ps, (6?)
6;
i= ....
(28)
[Pss, (b9))l2"
13

---

Published as a conference paper at ICLR 2022
Proof Let assume b, bß. The iterates of subgradients steps of PSGM can be written in the following form,
b = (1 - H.pen 68. p..(1 p)cd8
by (1 plpen) )b} p1((1 p)ca8
(29)
6y (1 pi pcp) k- - - 11:-1(111 p)cy$
By projecting each update of PSGM onto S_ and since Ps_ (b,)) ||6|1| (6)) we have,
Ps. (b. (b++1)= (1 (CDpp))) Ps_ (b.))
(30)
||6%/1
We can thus easily derive the following form for Ps_ (b.))
K K-1 II
1- -(ppDD) |1b/
Ps. (b,))
Ps. (6%)
(31)
We know from Theorem I and Lemma when DPCP-PSGM is initialized with B.. i= 1....... ds randomly drawn according according to a spherical distribution then it will almost surely converge
................................
as + oo to vectors 6" = 1,2.....ce c' i.e., 6KK + b; where B E S Hence Ps_ (b - b
as K + 0c. Note that from Theorem we have that 1 *
Ak = {1, 2,....... K} hence
[=== K-1 (eD)
* 0. From 31 and after projecting the unit sphere and thus have
6; Ps, (6.)
[[Pa (b.)
Theorem Let BO E Dxd where d' 2 with denoting the true codimension of the inliers subspace S, consisting of unit lg norm column vectors by E GD-1, 1,2,...... .....,,' that indepen- dently drawn from uniform distribution
the sphere DD-1 PSGM algorithm initialized with B will almost surely converge to matrix B such that span B²) S1.
Proof From Lemma we have that for each initial unit norm vector bf which corresponds to the ith Ps. (6%)
column of 8 will almost surely converge to b [|ss (b
We can thus write B = Pss (B")r
where I is full-rank diagonal matrix given be r diag
PSs, (6)) [Ps, (6
IPs, (6) l
Note that Ps, is a linear projection and thus we can write Ps, (B") = Bs B where Bs, RR Dxc orthonormal matrix which spans S Note that the probability of sampling low-rank matrix
Bo = [b. b9....,du bo) when columns bys are randomly and independently drawn from a spherical distribution is zero. We thus have B" = Bs BJ, B with rank = c.
Lemma 6 If (B))
|| then the rank of matrix B
equals d'
Proof Let A B Á. From singular value perturbation inequalities we have (ox(A) - oB,(B))
2, for i = 1, ...... c'. Hence it holds,
......
| 2 < o. (A) (
(32)
If of (B")
| then from equation 32 get
ar (A) 0
(33)
hence the matrix D will be full-rank.
14

---

Published as a conference paper at ICLR 2022
A.4 PROOF OF THEOREM 7
We first give the following Lemmas:
Lemma For the &g norm of e 3.k for any k 1,2, K and i= 2, d it holds,
1 S 110 + co max ca
(34)
Proof
1
| l|2 - -100 - cabll2
M OSgn(O'0 c2bl12
1 (I - bb O + bb T OSgi(O b) - ccbll2 (35)
1
M
M
1
< ||
M (I - bb JOSgn ( b)ll2 +
O T b/1 - ca)l|bl12
M
- no + CO m0. cd
where we have used the fact that ||ه||
Lemma 8 Let the step size of Algorithm (DPCP-PSGM) μ² being updated following the piecewise geometrically diminishing step size rule with
K.
1 M4 McD
B <
I+ HO (N + (xx
M no CO maxx
co, For the spectral norm of Å holds | S Ven(no co. max - ca) where n max; BRo/K=
M
(1+ + + Mmo co amax))) ))) gilk.
and r.
Proof We first bound the le norm vectors b/s. s. We have that Vi = 1,2...., and j 1.2,.... K
it holds
b.th bJ mn
XSgnn 82) + O b;))
(36)
We define the quantities
1
1 Il(ss T J' (T/62)l
7x
max bEgD
N
(37)
1 x bi
Cx.max
max BEED
(38)
[bb] ||2
hence
|
12 + (gll X (8)) + O l2
+ 1a (1XX x 6 1|2 OSgn b))
+ 1n (1l(Ps 6 T )x x b/)12 + [[ T ) J'S xx b/)l22
+ || 6.65 Oggn O b 1|2 bb. OSgn 6.)l22)
+ / (1)x + cx m_x) M(no + co. .mx)
Due to equation
39 and since nn follows a non-increasing path as j + k, the scalar term is bounded above as follows.
I (1- 14 Men)
bb ||
6 l2
(1 p4 (N + Cx .axx + M + co max)))
II J= (1 McD)
S
(39)
1 u McD
15

---

Published as a conference paper at ICLR 2022
We now focus the geometrically diminishing step size rule given in equation We have μ n (e_gl=KKo Ko. p_ (alk--K)/K., for k 2 Ko and plk Kol/K, pl for Ko. Hence can get the following upper bound
111l2
lim
1 M
(1 1 McD)
k=0
1 1+ 13 (N + cx max) ) + M (no + CO. (0.mmx))
M lim
Bik Kol/K.
K-+00
R-1 Σ k=0
(1+ (N + xx + M (no + co ((xm))))))) B1/K.
= lim
M
BkolK, ui
K-y00
μu McD
k
The series S Lk=0
K-1
(I+x][N(nx max ) + to co m)x))) I- McD
g2/k.) is geometric and if
1. McD
k.
B <
(40)
(1 po (N Cx mmax) + M (no + co (0,,max)))
it converges as K xo where (1+ + xex max t B1/K.
Mep
Let us now bound the & norms of the columns of Á, From Lemma CO mmax - Cd. We can easily thus derive that || l2 S k(no + Go max ca). For the spectral norm of Å we thus have
we have I ll2 I no
Ar 12
Σ i=1 8:wrll22
Σ -==1 |
||ل|
sup z
sup
I sup
|
x 12
|| x |2|12
z
2*0
(41)
x
max
1
< x(no + co. max ca)
||
x 2
#
Where the last incquality arises since ||0||1 S Vell [
We then give the Theorem.
Theorem (Theorem 5.58 of Vershynin (2010) Let B be a D d matrix (D 2 d) whose columns b, are independent sub-gaussian isotropic random vectors in RR. with |b; l2 VD almost surely. Then for every 2 0 the inequality
VD- - D-CvV-ts - minn B) S max (B) S DD +
(42)
with probability at least 1-11-2220 1x2expp- (exp(_ct?), where C C/ c dx depend only on the subgaussian norm = mmxx bill, of the columns.
The proof of Theorem 7 follows next.
Theorem Let B Dxx with columns randomly sampled from unit le norm spherical distribution where 2 c with e denoting the true codimension of the inliers subspace S that satisfies
Assumption If
1 _ Ver(no + CO max ca)
c -
(43)
VD
where max; 3ka/K- (1-r;) and r, (N (M g1/K. then with
2
1-
probability at least 1 - exp(-e"C2) (where Ci, O2 are absolute constants), Algorithm with geometrically diminishing step size rule will converge matrix B such that span B*) S1.
16

---

Published as a conference paper at ICLR 2022
Table I: Results Washinghton DC AVIRIS hyperspectral image Methods
F1-scores
I 80%
90%
DPCP-PSGM (unknown c)
0.994
0.993
RSGM (unknown
0
0
DPCP-IRLS (unknown c)
RSGM (c 5)
0.999
0.993
DPCP-IRIS c 5
0.995
Proof By Assumption we have that all columns of Bo will satisfy the sufficient condition for convergence DPCP-PSGM (Algorithm 1) to normal vector of S. From Lemma 6 and we use the inequality ae (Bo) > || Á l|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 matrix By. Note that columns of Bo are drawn independently and are uniformly distributed on the unit sphere. Hence, columns of Bo are sampled by subgaussian distribution and the LHS of the inequality of the theorem appears if we scale with v/D so that to create unit-norm columns and use LHS of the incquality of Theorem 7. The RHS
of the incquality is due to the upper bound of A ll2 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).
B EXPERIMENTAL DETAILS AND ADDITIONAL MATERIAL
All experiments were conducted on a MacBook Pro 2.6GhZ 6-Core Intel Core i7, memory 16GB 2667 Mhz DDR using Matlab201 9B. For computational purposes and in order to avoid fine-tuning of the piecewise geometrically diminishing (PGD) step size, the modified backtracking line-search (MBL.S) step-size rule adopted for DPCP-PSGM as proposed in Zhu et al. (2018). We define the distance between two subspaces spanned by matrices B and A as dist B, A) = mingeo(D.e) | AQ where O(D,c) denotes the Stiefel manifold of orthogonal matrices of rank c. Note that disl(B, =
0 > span(B) B) span(A) A) (see Zhu et al. (2019)).
B.1 OUTLIERS PURSUIT IN WASHINGTON DC MALL AVIRIS HSI
Hyperspectral images (HSIs) provide rich spectral information as compared to RGB images capturing wide range of the electromagnetic spectrum. Washington DC Mall AVIRIS HSI contains contiguous spectral bands captured at 0.4 to 2.4/um region of visible and infrared spectrum, Giampouras et al. (2019). In this experiments coherence in the both the spectral and the spatial domain, pixels of HSIs admit representations in low-dimensional subspaces. Here, use a 100 100 segment of the hyperspectral image selecting randomly 10 out of its
randomly choose 10 out of its 210 spectral bands. Due to high
210 spectral bands. We form matrix X' of size 10 x 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 & norm for two different outliers' ratios i.e., 0.8 and r 0.9. In the corrupted X, the remaining clear pixels are considered as the inliers. Table 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, á' = (recall c = D d) is close to the true codimension value while é' = 10 is an overestimate thereof. From Table D outliers' ratios regardless its unawareness of the true codimension value. On the other hand, DPCP. IRLS and RSGM fail when initialized with 10 and this is attributed to the restrictions induced
see that the proposed DPCP-PSGM succeeds in both
17

---

Published as a conference paper at ICLR 2022
(a)
(b)
(c)
(d)
(f)
Figure 4: (a) False RGB color image of the clean version of Washington Mall AVIRIS HSI, (b) corrupted by outliers depicted with red and inliers correpsonding the non-red pixels (c) annotated outliers as recoverd by the proposed DPCP-PSCH method initialized with = 10 (d) RSGM with 10, (e) RSGM with c' 5 and (f) DPCP-IRLS with c' 5.
due to the orthogonality constraints they both impose. In Fig. 4 we provide annotated versions the clean HSI, its corrupted by outliers version for outliers' ratio 90%, and the annotated outliers as recovered by the proposed DPCM-PSGM, RSGM, RSGM with c' and DPCP-IRLS with c'
18


Reviews:
[{"review_id": "s8FyU09_0WE", "reviewer": "Reviewer_MxBa", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The idea is interesting, and seems to be more of a statistical result than of optimization.  The numerical results are encouraging, and I can't directly find any issues with the proofs (though for time reasons, I did not look too closely).  \n\nThere are two assumptions I think should be elaborated, at least qualitatively: first, the condition (9) on the initialization of b's, and second, the overestimate of c' over c. These relationships would really give better intuition as to how powerful the random initialization is. Additionally, I am curious as to how much it matters that the data itself has isometry principles. I would suspect if the inlier dimensions have a very uneven contribution, this method should not work that well; how is this captured? ", "summary_of_the_paper": "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. \n\n", "summary_of_the_review": "Overall, I think the paper's idea is nice and looks sound; however, I am not an expert in this area. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "rxNghDR0Fxs", "reviewer": "Reviewer_Az9P", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The work proposed a new analysis framework for justifying the robust subspace recovery under the DPCP formulation without requiring apriori knowledge of the subspace co-dimension. The work analyzed both the gradient flow and its projected subgradient counterpart, showing convergence to the target solutions.\nThe paper is well-organized, and well-presented overall. The work tackles an important challenge to perform robust subspace recovery in a high relative subspace dimension regime without requiring a priori knowledge of the true subspace dimension. \nNonetheless, the reviewer is a little concerned over the novelty of the work. It seems to be borrowing/combining ideas from previous work on DPCP, and implicit bias for low-rank matrix factorization. \n", "summary_of_the_paper": "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.", "summary_of_the_review": "The work is well-presented, and tackles a challenge of unknown true subspace dimension via overparametrization and implicit bias of optimization method. The work combines ideas from previous work on DPCP and implicit bias for low-rank matrix recovery. The overall result is novel, while the approaches seem to be a combination of previous methods.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "60RkumkhT-u", "reviewer": "Reviewer_1qf1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper introduces a new algorithm for a significant problem, which is able to circumvent an important issue with previous work (no knowledge of the subspace needed). For this reason, I think that the paper has a lot of potential. However, I think that in its current state the paper is not yet ready for acceptance.\n\nMost importantly, I feel that Theorem 7, which is the main result of this paper, needs to be formulated much more cleanly. For example, it is totally unclear to me what is $\\beta$. What is $K_{\\star}$ and $K_{0}$? Has this been defined before? I feel that the authors should work on a version which is more digestible and more self-contained. Furthermore, I am not able to assess the strength of these results. It might be useful to derive some implications of this theorem in some simple settings to see how sharp the result is.\n\nFurthermore, I think that the paper needs to be really polished and proofread, before it gets submitted again to another conference (see comments below).\n\nFurther comments:\n\n1. Figure 1: I think it should be \"as opposed to b)\" instead of \"as opposed to a)\" \n2. Figure 3: In the caption below the Figure, it is written that both (a) and (b) use r=0.6. I think for (b) it should be r=0.7\n3. Is in equation (3) a transpose missing? Should it not be $Xtilde^T$ instead of $Xtilde$?!\n4. In equation (7) is $c_{O,min}$ correctly defined? Should it not be $O^T b$ rather than $X^Tb$?\n5. This might be a bit nitpicky, but in the related work section on subspace recovery, the authors refer to Joliffe&Cadima and Vidal et al. for PCA, respectively SVD. I feel that if the authors of the paper are doing this they should write \"see, e.g., Vidal et. al\" instead of just \"Vidal et. al\". (SVD is not due to Vidal...)\n6. I feel that in the related work section on robust subspace recovery some important work is missing. For example Candes, Wright et al. on Robust PCA at the end of page 6: \"outliers and inliers terms of (??)\n7. In the formulation of Theorem 1 it would be helpful for the reader if the authors would refer to (1). I think that this would clarify that this is the problem which gets solved.\n8. Typo in the formulation of Lemma 6: \"then (the) matrix\"\n9. Why do M and N not matter interested formulation of Theorem? Clarifying this might be helpful for the reader.", "summary_of_the_paper": "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. \n\nWhereas 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.\n\nThe contributions of this paper are threefold.\n1. It proposes a new algorithm, which does not need a-priori knowledge of the unknown subspace.\n2. Some theory for the new algorithm is developed.\n3. The algorithm is tested on both synthetic and real data.", "summary_of_the_review": "Due to the aforementioned reasons, I think that the paper is not yet ready for acceptance. However, I feel that the paper has a lot of potential and I hope that the authors keep working on the issues which have been raised in this report.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "1x-ZtGAKx1i", "reviewer": "Reviewer_euxB", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main result of this paper is rather surprising-- that random initialization can replace the need for explicit orthogonality constraint in DPCP. These proofs and theoretical results need more careful review, but if this is accurate, I believe it will have meaningful impact on many other problems in signal processing and machine learning.\n\nThis paper could be improved by addressing the following points:\n- Although the phrase \"implicit bias\" is in the title and repeated throughout the paper, it is not very well-defined. There should also be a mention on how this result connects to existing works on implicit bias, often mentioned in the context of non-convex optimization.\n- Figure 1 needs a lot more explanation in the text and/or the caption. What are the definition of these terms and what is the difference we're supposed to notice between them?\n- Sections 3 and 4 are very dense. Is there a way to provide more high level explanations or proof sketches?\n- Algorithm 1 is lacking, given the importance of initialization. There should be more explicit instructions on how to find $\\hat{B}_0$ inside the algorithm box.\n- Are there any computational analysis of the algorithm?\n\n\nMore minor points:\n- Should $\\tilde{X}$ equation (3) be transposed?\n- Notation in equation (6) is confusing. Is the left side claiming that $c_d$ evaluates to $2/\\pi$ for even $d$?\n- Broken link (??) in page 6 \n- Figure 2 needs a colorbar. Is this in log or linear scale?", "summary_of_the_paper": "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.", "summary_of_the_review": "The take-home message of the main theoretical result is very interesting, and could open a new way to think about many other optimization problems with explicit orthogonality contrainsts. However, I have only skimmed the proofs and have not carefully checked them.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper looks at subspace recovery in the presence of outliers, of which there have been many formulations. They study a recent formulation, DPCP, but relax the requirement that the dimension of the subspace is known -- obviously very important in practice. The approach is quite clever: they exploit the fact that for this non-convex problem, starting a simple algorithm at a randomly chosen starting point will converge to a local minimizer, and they can run an ensemble of these algorithms (each with different starting points) and be guaranteed the solutions will span an appropriate subspace. This idea alone is a nice contribution. The paper has theory and experiments.

Most reviewers were positive about the paper. The most critical review, by 1qf1, still acknowledged that this paper has a lot of potential, but in their opinion the paper was not in a state ready for acceptance, especially regarding the formulation of the main result, Theorem 7.  The other reviewers were OK with the state of the paper, and the authors made changes in the rebuttal. Hence, while acknowledging the paper could possibly still be improved (what paper couldn't be!), I think the paper is in a good enough state to accept it for ICLR. I don't think there would be enough benefit to the community (authors, readers and reviewers) to ask for this to go through one more round of submission/revision.
Decision: Accept (Spotlight)