Mixed-Features Vectors and Subspace Splitting
Authors: Alejandro Pimentel-Alarcón
Daniel L. Pimentel-Alarcón
Venue: ICLR 2021 Poster (2021)

Abstract: Motivated by metagenomics, recommender systems, dictionary learning, and related problems, this paper introduces subspace splitting(SS): the task of clustering the entries of what we call amixed-features vector, that is, a vector whose subsets of coordinates agree with a collection of subspaces. We derive precise identifiability conditions under which SS is well-posed, thus providing the first fundamental theory for this problem. We also propose the first three practical SS algorithms, each with advantages and disadvantages: a random sampling method , a projection-based greedy heuristic , and an alternating Lloyd-type algorithm ; all allow noise, outliers, and missing data. Our extensive experiments outline the performance of our algorithms, and in lack of other SS algorithms, for reference we compare against methods for tightly related problems, like robust matched subspace detection and maximum feasible subsystem, which are special simpler cases of SS.

Published as a conference paper at ICLR 2021
MIXED-FEATURES VECTORS & SUBSPACE SPLITTING
Alejandro Pimentel-Alarcón
Daniel Pimentel-Alaree
IMMAS, Universidad Nacional
Department of Biostatistics
Autónoma de México, UNAM
Wisconsin Institute for Discovery
Mexico City, Mexico
UW-Madison, WI, 53715
unam. mX
pimentelalar@vin edu
ABSTRACT
Motivated by metagenomics, recommender systems, dictionary learning, and re- lated problems, this paper introduces subspace splitting (Ss): the task of clustering the entries of what we call a mixed-features vector, that is, a vector whose subsets of coordinates agree with a collection of subspaces. We derive precise identifiability conditions under which Ss is well- well-posed, thus providing the first fundamental the- ory for this problem. We also propose the first three practical Ss algorithms, each with advantages and disadvantages: a random sampling method, projection-basee based greedy heuristic, and an alternating Lloyd-type algorithm all allow noise, out- liers, and missing data. Our extensive experiments outline the performance of our algorithms, and in lack of other Ss algorithms, for reference we compare against methods for tightly related problems, like robust matched subspace detection and maximum feasible subsystem, which are special simpler cases of Ss.
INTRODUCTION
As the reach of data science expands, and as we continuously improve our sensing, storage and computing capabilities, data in virtually all fields of science keeps becoming increasingly high- dimensional. For example, the CERN Large Hadron Collider currently "generates so much data that scientists must discard the overwhelming majority of it, hoping that they' 've not thrown away anything useful" [1], and the upcoming Square Kilometer Array is expected to produce 100 times that [2]. Fortunately, high-dimensional data often has an underlying low-dimensional structure. Inferring such structure not only cuts memory and computational burdens, but also reduces noise and improves learning and prediction. However, higher dimensionality not only increases computational requirements; it also augments data's structure complexity. In light of this, several research lines have explored new cow-dimensional models that best summarize data, going from principal component analysis (PCA) [3-1]] and single subspaces [12-21] unions of subspaces [22-405 22-40]. and algebraic varieties [41].
This paper introduces mixed-features vectors (MFV's): s): new model that describes the underlying structure of data arising from several modern applications that is not captured by existing low- dimensional models. The main idea is that each entry of a MFV comes from one out of several classes, and that the entries of the same class lie in an underlying subspace. In particular, MrV's are motivated by megatenomics [42-46] and recommender systems [47-59]: in metagenomics each gene segment comes from one of the several taxa present in microbiome; in recommender systems each rating may come from one of several users sharing the same account. However, MPV's also have applications in robust estimation (e.g., robust PCA [3-11] and robust dictionary learning [60-67]), matrix completion [48-59], subspace clustering [22-39], and more.
This paper also introduces subspace splitring (Ss): the task of clustering the entries of a MFV according to its underlying subspaces. Ss is tightly related to other machine learning problems. In particular, SS can be thought as generalization of robust matched subspace detection (RMSD) [12-17], and maximum feasible subsystem (MAxFS) (68-74]. However, the added complexity of Ss renders existing approaches for these problems inapplicable, which calls the attention for specialized Ss theory and methods. In these regards, (i) we derive precise identifiability conditions under which Ss is well-posed, and (ii) propose the first three Ss algorithms.

---

Published as a conference paper at ICLR 2021
2 PROBLEM STATEMENT AND FUNDAMENTAL THEORY
Let U' U'...., Uk be subspaces of R and let Ry .t,,..,, Sk denote a partition of [d] := fl....,de d]. For any subspace, matrix or vector that is compatible with set of indices Q C [c], we will use the subscript f2 to denote its restriction to the coordinates/rows f2. For example, U2 c CR (g denotes the restriction of U to the coordinates in Ωgg. Define x E I as the mixed-featunee vector (MFv) such that Xo UK, for each k = I,.... K. and the entries of Xn. are outliers. Let e E R denote noise vector with variance o², Given U2, the goal of subspace splitring (Ss) is to determine the subsets Q2 n ........ .2k n indicating the observed coordinates of y that match with each subspace.
UK and an incomplete observation Yς Xg eQ.
Example 1. Consider the following setup, with 1 1-dimensional subspaces U U2 spanned by U' U?
0.1
0.551
2
1/2
0.1
0.49
U
U
3
6
0.1
5.9
4
8
0.1
Yn
8.1
5
-0.1
8.9
10
0.1
It is easy to see that Q2 = (1, 022 = (3,4), Ro {5), because Xp,
U st, and Xn, 20
The keen reader will immediately wonder: there another partition (St....., Rkk} different from { Ox} } such that X Ub for every k? In other words, this problem well-posed, and so, under what conditions? Our main theoretical result answers this question, showing that under the next assumptions, S2y can be recovered if and only if has more elements than the dimension of Tk
A1 Each T is drawn independently with respect to the uniform measure over the Grassmannian.
A2 Each Xº2 drawn independently according an absolutely continuous distribution with respect to the Lebesgue measure on UK
In words, A1 essentially requires that U U..... JK are in general position with no particular relation with another. Similarly, A2 requires that each piece of x is in general position its corre- sponding piece of subspace. This type of genericity assumptions are becoming increasingly common in compressed sensing, matrix completion, subspace clustering, tensor theory, and related problems [10, 21, 30, 31, 33-38, 41, 56-59]. All our statements hold with probability with respect to the measures in A1 and A2. We point out that A1 and A2 do imply coherence or affinity (other typical assumptions in related theory that quantify alignment with the canonical axes or between subspaces [3, 6, 11, 23, 26, 27, 48-50, 54, 55)) nor vice-versa. For example, bounded coherence and affinity assumptions indeed allow subspaces perfectly aligned on some coordinates. However, they rule-out cases that our assumptions allow, for example the non-zero measure set of highly coherent or affine subspaces that are somewhat aligned with the canonical axes or with one another. To sum up, these assumptions are different, not stronger nor weaker than the usual coherence and affinity assumptions. With this, possible if and only if contains more than dim (U)) entries of each subspace U
ready to state our main theorem, showing that subspace splitting is
Theorem 1. Suppose Al and A2 hold. Given x and U ,..,. U one can identify Pi...., OK if and only [Ox] > dim(Uk) for every
Example shows a case where the conditions of Theorem 1 are met ([2] 1021 = 2 dim(U')
dim(U*) = 1), and consequently subspace splitting is well-posed (there exist no partition other than the true {Ω,, that splits x into U and U²). Conversely, the following Example shows a case where the conditions of Theorem are not satisfied, and at least some Pg is unidentifiable.
2

---

Published as a conference paper at ICLR 2021
Example 2. Consider the following setting:
1/22
1/2
U
U2
3
U
4
x
Now [021 = [92g| = 1- dim(U = ) As Theorem I shows, there exist multiple ways to split x into U². U22 and U Here the partitions could be {Ω1, 92, = {{1, 2), (3), {4}} or {{1,2], [4]. {3 and there is no way of telling which is the true partition from U', U², U². and x. In other words, 522 and Q2 are unidentifiable
Remark 1. We point out that the constructions in our examples are not generic (i.e., they were not constructed according to Al and A2). We chose them for their simplicity to build intuition and make a point. However, our results still apply to these constructions, showing that in addition to all generic cases, our theory also holds for some non mon-generic ones. An exact characterization of all the non-generic cases that our theory covers requires careful study of notions of sketching and partial coordinate discrepancy [31]. which are out of the scope of this paper.
The proof of Theorem follows by the next two lemmas. Lemma I shows that any subset of or fewer entries of any vector will always match with any r-dimensional subspace in general position. Lemma 2 shows that r entries of vector won't match with random r-dimensional subspace by chance. Said in other words, r + entries of vector will match with an r-dimensional subspace if and only if such entries truly come from that r-dimensional subspace. Lemma towards Theorem 1, as it allows us to try all combinations of + 1 entries that fit in an r-dimensional subspace, knowing that we will never get a false match. All proofs are in Appendix A.
effectively the key
Lemma 1, Suppose AI holds. Let S2 C [d]. If [2] S dim(T*), then Xa E Uh, for every x E Rdd
Lemma 2. Suppose Al and A2 hold. Let Ω be arbitrary subset of [d] with exactly dim(U*) + elements. Then X Ug if and only if Q 94.
Corollary extends these results to account for noise and missing data, replacing A1 and A2 with:
A1' The coherence of Uk is upper bounded by μa, and the geodesic distance over the Grassman- nian between U and U lower bounded by yp, for every k, = I,...,,.. K.
A2' The coherence of xn, is upper bounded by v. and its norm is lower bounded by vb, for every k I....... K.
Corollary 1. Suppose AI' and A2' hold with μ4, v < Co, and (. v > co for some constants C and c. Let Yn and U ...., UK be given. Suppose [S2x n > dim d for every k. Then with probability decreasing in C and increasing in c, can identify Ωt n 12 .2.....93 Ωg 0
To guarantee identifiability, Corollary I requires that subspaces and samples are sufficiently incoherent and separated to overcome the noise level a. Notice that since now there missing data (we observe Yn. instead of x as in Theorem 1), Corollary requires that there are enough observed entries per subspace, i.e., that [22 S2] are sufficiently large (rather than Ω4)). Similarly, only the observed entires can be classified, so only the intersections 22 O Ω are identifiable (rather than 222).
3 RELATED WORK
Arguably, the closest link that subspace splitting has with other popular machine learning problems, through robust matched subspace detection (RMSD) [12-17] and maximal feasible subsystem (MAXFS) [68-74]. In RMSD one observes a vector x E Rd of the form x = UO + where z IRd a sparse vector of outlier entries, and 0 E Rº is the coefficient of the entries the subspace spanned by U E Rdd Given x and U, the goal is to equivalently find 0, or the support of z. which in turn determine the coordinates where x matches U. Subspace splitting can be thought the generalization of RMSD the case where there multiple subspaces, and want to find the entries that match each one. Similarly, in MAXFS one has an inconsistent system of equations of the form U0, and wants to determine the solution 0 that produces the largest.
that match with
3

---

Published as a conference paper at ICLR 2021
subset Ω of consistent equations. Subspace splitting can be thought the generalization of MAXFS to the case where there are multiple consistent subsystems (one per subspace), and we want to find each of them. The three prevalent venues to solve these problems can be classified into three groups: (i) & minimization, (ii) mixed integer programs, and (iii) random sampling.
The first group essentially encompasses variants of minimizing |x U0ll1 over O E R,, which is tightly related to the Lasso [91]. The intuition is that the & -n-orrm will favor solutions that produce a sparse vector z x UO whose zero entries reveal Q. While formulations like this work great for just one subspace (or subsystem), if there are two or more, then for each subspace, the entries of all other subspaces are outliers, in which case z" := x U will no longer be sparse, and the solution to the f--nrrm minimization will no longer reveal S2g. The second group aims to directly recover S2 with variants of the mixed integer formulation that minimizes ||z|| subject to |x UØ| S Mz over z E {o, 1] and 0 E R', where M a tuning parameter. Here the main idea is to maximize the number of zero entries in (which reveal Ω2, where we are forcing to match span { (U, because the constraint guarantees that |x: U0] S z; = O. Unfortunately, because of the combinatorial nature of this approach, this method becomes exponentially slow as the fraction of outtiers/inconsistenciess increases, rendering it prohibitive in practice for even small values of K. The third group essentially uses the same principle random sampling consensus (RANSAC) [92-98]. That is, one iteratively selects a candidate subset of entries at random, until it finds one where x agrees with span (pan(U), (U}. This is in fact the approach that we used in the proof of Theorem 1, and the main idea behind our first SS algorithm, which we present in Section 5.1, and study in Section 6.
Remark 2. We point out that SS is also related to subspace clustering (22-40]. The main difference that in subspace clustering all entries of each column come from the same subspace.
4 MOTIVATING APPLICATIONS
This section details the main motivations behind Ss, namely, metagenomics, recommender systems, and robust estimation, relevant for dictionary learning, matrix completion, and related problems.
Metagenomics Microbial communities affect the balance of entire ecosystems, and play a crucial role in the planet's health [42]. Consequently, understanding microbiome compositions, interactions, and evolutions holds the key to the knowledge of the deep interconnectivity factors that play a role on Earth's 's biodiversity, our agricultural sustainability, and adaptation global threats like climate change. One cornerstone tool towards microbiome understanding lies in genomic analysis. In practice, to obtain an organism's 's genome (e.g., a person's genome), biologists feed a DNA sample (e.g.. blood or hair) to a sequencer machine that produces a series of reads, which are short genomic sequences that can later be assembled and aligned to recover the entire genome. The challenge arises when the sequencer is provided a sample with DNA from multiple organisms, as is the case in any microbiome (e.g., the human gut microbiome), where any sample will contain a mixture of DNA from multiple taxa that cannot be trivially classified [43]. In this case, each read produced by the sequencer may correspond to a different taxa, resulting in a DNA sample with a mixture of genes. Existing approaches depend on the correct classification of taxonomic units, which in turn relies on the existence of reference tables, and often require human intervention [44]. However, reference sequences remain unknown for vast majority of microbial biodiversity, which in turn precludes holistic metagenomic analyses, as scientists often have to discard unidentified data that cannot be currently categorized with existing reference tables [45]. In contrast, our work pioneers the theoretical foundations of a novel model tailored to automatically classify taxonomic units without any human intervention. Moreover, our model will naturally allow for missing data, and hence it will be robust to taxa with length-varying sequences, and fast-occurrigg mutations, which are in fact quite common in several microorganisms such as certain types of bacteria [46].
Recommender Systems and Image Inpainting In recommender systems like Amazon or Netflix, one aims to infer users' preferences in order to make good recommendations [47]. Arguably the most renowned model for this task is low-rank matrix completion [48-58], which assumes that each user's preferences vector can be explained as a linear combination of a few others. Said in other words, preferences lie in a lincar subspace. However, often multiple types of users share the same account. In this case the vector of preferences will contain a mixture of entries from multiple subspaces. is easy (details in the proof of Theorem in Appendix A) that the coefficient corresponding to the entries in the k subspace are given by 0 (U%: -xy where 2. is any subset of Sn with
4

---

Published as a conference paper at ICLR 2021
more than dim(U") elements. This insight can be used to estimate the values corresponding to the tthh subspace that would appear in the locations where there observations from other subspaces, or where data is missing, In For example, in recommender systems, this would allow to infer the preferences of all users sharing an account. In image inpainting this would allow to estimate the missing, corrupted, or occluded pixels in an image [60-67].
Robust Learning In Section we showed that Ss is generalization of RMSD and MAXFS, both of which are crucial subtasks in many importaniproblems, including robust PCA [3-11], dictionary learning [60-67], matrix completion [48-58], and more. For example, in subspace tracking one needs to identify outliers in each new vector (meaning performing RMSD or MAXFS) before updating the underlying subspace [18-20]. Or in subspace clustering one needs to identify outliers in each vector before finding sparse representations [26, 28, 29, 32, 39]. These in turn are core techniques in target localization [76], medical imaging [79], communications [80], anomaly detection [81, 82], hyperspectral imaging [16], and networks estimation [84? -89], among many others [78]. Being generalization of RMSD and MAXFS, subspace splitting is also applicable in these broader problems, cerformance.Moreoverr,
bringing possibilities for improved performance. Moreover, as these problems evolve into more
sophisticated models that allow mixeddfeature vectors (such as mixture matrix completion [59]), subspace splitting will gain importance and become crucial subroutine of these emerging problems.
SUBSPACE SPLITTING ALGORIHTM
We now present our three subspace splitting algorithms: random sampling method, iterative projection-base greedy heuristic, and an alternating approach inspired by Lloyd's algorithm [75].
5.1 RANDOM SAMPLING SPLITTING
Like Theorem I suggests, for each we can iteratively try sets S2 with din) + entries selected randomly until we find one such set where Ysg, lies close Uhy (within the noise level σr). At that
point we can estimate g ) ) "'y'', and subsequently Gg as the entries in Yę U el that are within a. We call this approach random sampling splitting (RANSAS). The main advantage of RANSAS that as consequence of Theorem 1, it is guaranteed to work after enough iterations. To see this, observe that if entries in x are uniformly distributed across subspaces and outliers, then the probability of randomly selecting + 1 entries from the khh subspace is 1/(K+1)=1 Consequently, simple
the probability that r + 1 random entries come from the same subspace is K/(K+1)=+1 Chernoff bound shows that the expected number of iterations before this happens is O(K*). Since we want this to happen K times, we conclude that the expected number of iterations is upper bounded by 0(K+)1). We summarize this the next theorem.
Theorem 2. Let Al and A2 hold. Suppose [021 > (im for every k. Suppose Pi E 24x 1/(K+) independently for everyi, k. Then the expected number of iterations before RANSAS identifies 2r...., Pg is lower and upper bounded by (K dim(U*)+1] and O )+1).
We point out that a scenario where all entries are equally distributed is in fact the most difficult setting. Otherwise, identifying any subspace with probability py > 1/(K+1) will take 0(1/rx < 0(1/(K+))**)) iterations to find. The main downside of this approach is that its computational complexity scales exponentially. So if K and r are small, or there is one dominant subspace, RANSAS may be a good idea. However, as we see in our experiments, this approach quickly becomes computationally prohibitive as K and r grow.
5.2 GREEDY SPLITTING
The main idea of our greedy splitting (GREEDYS) heuristic is to iteratively remove the most disruptive entry from each subspace. More precisely, for each k we will start with 2 [d]. and for each t > 0 we will define 2% := 2% - 11'-1 1 where 1 is the entry whose removal from 2 minimizes the difference between Yog and its projection onto U The intuition is that removing it- gets Yng closer to U/s We repeat this procedure for each k until Yng is close to Ukg (within the noise level r). We know from Lemma 1 that this procedure will terminate some point, because any subset of
5

---

Published as a conference paper at ICLR 2021
or fewer entries of any vector will always match with any r-dimensional subspace in general position. If for some k this procedure terminates with set Si with more than rg dim (U*) entries, Theorem I suggests that Yog truly lies in Uhg that Di Ω that can estimate 0 (Ung -'y and identify Sg as the entries in Ys U that are within At this point can prune all the entries corresponding to this subspace, and repeat the greedy procedure from the start without these entries. If at some point none of the remaining sets 2 has more than n. entries, that we cannot determine whether Yag truly lies in Uh with these entries alone, then we stop and consider this failure. Notice that for each k, GREEDY'S removes the most disruptive entry among all d entries, then the next most disruptive among the remaining d - 1, until either all the remaining entries lie in the same subspace, or there remain no more than I& entries. This requires no more than d+ (d- 1) +)+ (d - + + (nı + 1) = (dd)) iterations. After identifying the entries a subspace, potentially need to repeat the iterative removal process for the remaining K - 1 subspaces, and so on. In total, we potentially need to repeat the iterative removal process K (K - 1) + (K - 2) +..... = OK²2) times. Putting these two observations together, we obtain the following theorem, showing that GREEDYSS has polynomial computational complexity. Theorem 3. GREEDYS will terminate after no more than O (Kd)² iterations.
know by Lemma
if pruning is necessary,
The main caveat of this greedy approach, as the next Example shows, is that even in noiseless setting, the most disruptive entry for U (that is, the entry whose removal minimizes the distance between yog and its projection onto u may in fact correspond to U*
Example 3. Consider the following construction where the first two entries of x correspond to U the last two correspond to U², there are no outliers, i.e., Gl 0, there is no noise, i.e,, e 0, and there is no missing data, i.e., Ω = [d], so that we observe all entries of
2
2
3 1 y
U
U
3
2
4
Pay special atlention to U and y. Let Ω: [d]]i denote the of all except the ith entry, and
let Vo_, U (UkT Uk
- - 1
denote the projection of Ya., onto Uk U For example,
here:
1.572
U
0_1
3 [
Yn-
2 2
FR_
2.2759
33.0355
Proceeding according to our greedy heuristic, we can compute the projection residuals when removing each entry:
lya x/1 -
Ilya - -x1 , 2.7038,
ly =
Il =1 = 2.7440.
=
Here we see that removing any of the first two entries makes appear closer to U², even though the first two entries in fact correspond to WJ. We thus conclude that our greedy heuristic, while it works well in practice, it has no theoretical guarantee of working.
5.3 K-SPLITS
As the name suggests, our last algorithm, K-SPLITS, is inspired by the K-means algorithm. The main idea is to initialize partitioning randomly the entries of yn into Ω, Ωt,.... 22k. and then alternate until convergence between (i) estimating coefficients Ô1 ..... σk in light of the assignment of entries, and (ii) reassigning entries according to these coefficients. More precisely, at each step after pruning when possible we:
(i) Estimate coefficients 0h (Uk) -
iii Compute 3* ;= U and assign entries as Ω {1 [d]
ly, s S T(O)), where 7(a) is tuning thresholding parameter that depends the noise level.

---

Published as a conference paper at ICLR 2021
The assignment step is done a cyclic manner, that is, in every iteration, each cluster is assigned the entry that agrees the most with it, and receives no new entries until the next iteration. This changes the isotropic assumption of K-means with the assumption that each cluster has the same number of entries, as mentioned in Section 5.1, this is the most difficult setting for this problem, and whenever the assumption is not fulfilled, the algorithm will still be able to complete at least the most dominant subspace even if entries of that subspace contaminate other subspaces; for the next iteration that won't it be the case any more. Thanks to this, the assumption of every subspace having the same number of entries does not affect the effectiveness of the algorithm.
As we will see in our experiments, this method outperforms the rest. Its main downside, however, is that like most alternating methods, it suffers from local minima, and depends heavily on initialization. To mitigate the former, in our experiments we run several independent random initializations, We observe that in practice this has excellent performance. We conjecture that it is because this strategy will at some point spread the centers 0³ enough, in light of the subspaces. This sort of spread is crucial other related clustering algorithms, such as K-means [75]. Our future work will further investigate this, convergence, complexity, and initialization strategies, such as parallels of K-means++ [99], which require careful analysis and are out of the scope of this paper.
EXPERIMENTS
In this section we study the performance of our three methods above, as function of the number of subspaces K, the number of entries per subspace |Stx] (which in turn is a proxy of the ambient dimension d) and the subspaces dimensions r. We measure error as the fraction of misclassified entries. In lack of other existing subspace splitting methods, for reference we compare them against the & minimization described in Section 3. Our results show that our SS methods perform as well as existing methods in the single subspace case, and succeed in the presence of multiple subspaces, where existing methods fail dramatically. In the interest of reproducibility, all our code is available here [100].
In our experiments we first generate matrices U U UK E Rd with i.i.d. N(0, 1) entries, to use as bases of U²_ U....., UK with d = (K + 1)][k] Similarly, we generate ,',..., 0 E R", also with i.i.d. N(0, 1) entries, to use coefficient vectors. Next we create the partition of entries {Ωo. .t...., 92k} } where each 2g has the exact same number of clements. As discussed in Section 5.1, this is in fact the most difficult setting; otherwise the dominant subspace is easier to find, and one can simply prune its corresponding entries to simplify the problem. Then we create x as the vector such that Xn, =Uk, 6 for each k, and X2, are i.i.d. N(0, 1) entries representing outliers. Finally, we generate E ndd with i.i.d. N(0, o²) entries and Q C d with fraction p of observed entries, to construct our observed data Yn = Xq + en.
In our first experiment we study the behavior of our algorithms as a function of K, with 5. |02g| = 40, p = 1/2 (so that on average 20 observed entries correspond to each subspace), and o = O. i.e., noise. Figure 1 (a) shows that even for K = 2 (the smallest value of K), existing methodology is unable to split y. This is not surprising, as existing methods are meant for settings where most of the entries in y agree with a single subspace, and there are only a few outliers. In our setting, for each subspace, the entries of all other subspaces are outliers. Consequently, a fraction 1 - -1/K of the entries (at least half with K = and a dominant majority as K increases) are outliers for each subspace, which is well-documented to make existing methods fail (see the discussion in Section 3 for details). In contrast, GREEDYSS is better with K = 6 (which amounts 83.3% outliers) than L is with K = 2, while K-SPLITS and RANSAS maintain a 100% success rate for every K we tried. Nonetheless, increasing in K comes at a price (time), as seen in Figure 1 (a'), which shows how the number of iterations of each algorithm grows with K, relative to the simplest case (K = 2). Notice that the speed of K-SPLITS decays nicely with K. For instance, with K = 6, K-SPLITS degrades an order of magnitude slower than RANSAS, while still maintaining the same 100% success rate.
In our second experiment we study the behavior of our algorithms as a function of [Px], with r = 5. p 1/2, = 0, and K = 2 fixed. Figures 1 (b) and (b') show that as [[al grows, the performance of all methods improves: L and GREEDYS S achieve higher success rates, while RANSAS and K-SPLITS increase their speed and maintain the same 100% success rate.
7

---

Published as a conference paper at ICLR 2021
0. PM]- 0)
30
80
Naxthe of salepuos (8)
Suhppcc Discraee))
Subparo Dinccaee
- [N]
drok 2 rm mn
=2 SA DDa
( 2:
DOX 2. BA
Namber of lehipars (K)
Zasion OIL,)
Subppeci
Figure I: Average success rate and iteration growth over 100 trials, function of the number of subspaces K, the number of entries per subspace [52x| (which in turn is proxy of the ambient dimension d), the subspaces dimensions r, the gap y = [0a (r 1), and the noise level a.
In our third experiment we study performance as a function of r, with p = 1/2, o = O, and K = fixed. Recall from Lemma 1 that increases, does the number of entries per subspace required for identifiability (r + 1). Hence to allow a wide range of r, we fixed [2g]] = 40. Figures (c) and (c'), show that (conversely our previous experiment) the performance of all methods declines as r grows: & and GREEDYS achieve lower success rates, while RANSAS and K-SPLITS increase their time (though they maintain the same 100% success rate).
Our next two experiments are consistent with the intuition that cases with fewer data (small [9&g) relative to the problem's 's complexity (the dimension r) are harder. We verify this our next experiments, where we study performance
function of r, fixing p 1/2, 0, and K = 2 and (r + 1]) = 20. This setting represents the case where we always have a few more (20) entries per subspace than the strictly required (r - 1) for splitting. This is arguably a better experiment to test the effect the subspaces dimensions isolated from the sampling rate. Figures (d) and (d') now show that r slightly affects GREEDYS and K-SPLITS and K-SPLITS in terms of time), but dramatically affects RANSAS, causing an increase of iterations four orders of magnitude higher than the rest. This is consistent with our discussion in Section 5.1, showing that RANSAC will always succeed given enough time, which grows exponentially in Interestingly, K-SPLITS achieves the same 100% performance, but orders of magnitude faster, suggesting that K-SPLITS is in general the most promising SS algorithm.
the gap Y := p([
in terms of accuracy,
In our last experiment we study the accuracy of our algorithms function of the noise level a, with r r= 5, p = 1/2, [h = 40, and K = 2 fixed. Consistent with Corollary 1, Figure (e) shows that the performance of our algorithms decays nicely with noise, with K-SPLITS allowing up to a 10-3 The price, however, can be seen in execution time (Figure (c')), which grows up to the point where algorithms start decay, which case their execution time also starts decreasing. We point out that the fraction of missing data and outliers only affect results and performance in the sense that they reduce the number of available observed entries per subspace, so their effects are also captured the experiments [S& For example, case where there are [S& 40 samples per subspace, but only half of the entries are observed (p = 1/2) is equivalent to observing [S2x| = 20 samples per subspace with missing data (p 1). Appendix B shows additional results with K 4, where methods show even more dramatic improvements.
BROADER IMPACT
This paper introduces a new dimensionality reduction model, and a series of methods to infer such model, with broad applicability ranging from metagenomics to recommender systems. From a pragmatic standpoint, practitioners can use this research to better predict drug-target interactions, analyze the composition and dynamics soil or human microbiomes, and more. Ultimately, this can impact the well-being of society at many levels, improving drugs, medical diagnoses, treatments, agricultural sustainability, etc. From a learning perspective, we hope this work spurs discussions and insights, and motivates the data science community explore new directions that stem from this initial work (for example near- optimal initialization strategies on our K-SPLITS algorithm, similar to K <-menns++,, and that leads to better methods and understanding of subspace splitting.
8

---

Published as a conference paper at ICLR 2021
REFERENCES
[1] Edd Wilder-James, What is big data? An introduction to the big data landscape, available at:
attps://www.co wwwpwwwwwwwwww..w...wtwwpwwwwwwp wtw.llly.coomaa.. ideas/ watps//wwwtttisiiieeee
2018
[2] SKA Signs Big Data Cooperation Agreement With CERN, available at: https:
/ // www. www.skaaeeeeccop...
siiin--biggene cooperationocn
a agreement-cern/
[3] X. Yuan and J. Yang, Sparse and low-rank matrix decomposition via alternating direction methods, available http:/ //ww://wwwwwww/ www.oppptiiiioo..... oowoonnni........... www.l/.n..gg.........////// 11/2447. html, 2009.
[4] Z. Lin. A. Ganesh, J. Wright, L. Wu, M. Chen and Y. Ma, Fast convex optimization algorithms for exact recovery of a corrupted low-rank matrix, Computational Advances in Aulti-Sensor Adaptive Processing, 2009.
[5] X. Ding, L.. He and I.. Carin, Bayesian robust principal component analysis, IEER Transactions on Image Processing, 2011.
[6] E. Candès, X. Li, Y. Ma and J. Wright, Robust principal component analysis?, Journal of the ACM, 2011.
[7] T. Bouwmans and E. Zahzah, Robust PCA via principal component pursuit: review for comparative evaluation in video surveillance, Computer Vision and Image Understanding. 2014.
[8] Y. Ma. Low-rank matrix recovery and completion via convex optimization, avaiable at http: perception. csl.illinoi....i........oc....ie
aedu/matris rawkhhoomonnoeeeeee.oeoo html..
[9] T. Bouwmans, A. Sobral, S. Javed, S. Jung and E. Zahzah, Decomposition into low-rank plus additive matrices for backgroundforegroondd separation: A review for comparative evaluation with a large-scale dataset, Computer Science Review, 2016.
[10] D. Pimentel-Alareón and R. Nowak, Random consensus robust PCA, Electronic Journal of Statistics, 2017.
[11] M. C. Tsakiris and R. Vidal, Dual principal component pursuit, Journal of Machine Learning Research, 2018
[12] L. Scharf and B. Friedlander, Matched subspace detectors, IEEE Transactions on Signal Processing, 1994.
[13] Kraut, L. Schaft, L. McWhorter, Adaptive Subspace Detectors, IEEE Transactions on Signal Processing, 2001.
[14] M. Desai and R. Mangoubi, Robust gaussian and non-gaussian matched subspace detection, IEEE Transactions on Signal Processing, 2003.
[15] O. Besson, L. Scharf and F. Vincent, Matched direction detectors and estimators for array processing with subspace steering vector uncertainties, IEEE Transactions on Signal Processing, 2005.
[16] H. Kwon and N. Nasrabadi, Kernel matched subspace detectors for hyperspectral target detection, IEEE Transactions Pattern Analysis and Machine Intelligence, 2006.
[17] I.. Balzano, B. Recht and R. Nowak, High-dimensional matched subspace detection when data are missing, IEEE International Symposium on Information Theory, 2010.
[18] L. Balzano, R. Nowak and B. Recht, Online identification and tracking of subspaces from highly incomplete information, Allerton Conference Communication, Control and Computing, 2010.
[19] He, L. Balzano and Szlam, Incremental gradient on the Grassmannian for online fore- ground and background separation in subsampled video, Conference on Computer Vision and Pattern Recognition, 2012.
[20] H. Mansour, X. Jiang, robust online subspace estimation and tracking algorithm, IEEE International Conference Acoustics, Speech, and Signal Processing, 2015.
[21] D. Pimentel-Alareón N. Boston and R. Nowak, Deterministic conditions for subspace iden- tifiability from incomplete sampling, IEEE International Symposium on Information Theory, 2015.

---

Published as a conference paper at ICLR 2021
[22] K. Kanatani, Motion segmentation by subspace separation and model selection, IEEE Interna- tional Conference in Computer Vision, 2001.
[23] B. Eriksson, L. Balzano and R. Nowak, High-rank matrix completion and subspace clustering with missing data, Artificial Intelligence and Statistics, 2012.
[24] L. Balzano, A. Szlam, B. Recht, and R. Nowak, K-subspaces with missing data, IEEE Statistical
Signal Processing, 2012.
[25] G. Liu, Z. Lin, S. Yan, J. Sun, Y. Yu, and Y. Ma, Robust recovery of subspace structures by low-rank representation, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012.
[26] E. Elhamifar and R. Vidal, Sparse subspace clustering: algorithm, theory, and applications, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013.
[27] D. Pimentel-Alarcón, L. Balzano and R. Nowak, On the sample complexity of subspace cluster- ing with missing data, IEEE Statistical Signal Processing, 2014.
[28] C. Yang, D. Robinson and R. Vidal, Sparse subspace clustering with missing entries, Interna- tional Conference on Machine Learning, 2015.
[29] D. Fimentel-Alarcónn L. Balzano, R. Marcia, R. Nowak and R. Willett Group-sparse subspace clustering with missing data, IEEE Statistical Signal Processing, 2016.
[30] D. Pimentel- -llaróón and R. Nowak, The iifoommttion-hhoreetii requirements of subspace clus- tering with missing data, International Conference on Machine Learning. 2016.
[31] D. Pimentel-Alareee L. Balzano and R. NowakNecessary and sufficient conditions for sketched subspace clustering, Allerton Conference on Communication, Control and Computing, 2016.
[32] Y. Chong. D. Robinson and R. Vidal, Provable self representation based outlier detection in a union of subspaces, IEEE Conference on Computer Vision and Pattern Recognition, 2017.
[33] M. Ashraphijuo, X. Wang and V. Aggarwal, A characterization of sampling patterns for low- rank multi-view data completion problem, IEEE International Symposium on Information Theory, 2017.
[34] M. Ashraphijuo, V. Aggarwal and X. Wang, A characterization of sampling patterns for low- tucker-rank tensor completion problem, IEEE International Symposium on Information Theory, 2017.
[35] M. Ashraphijuo and X. Wang, Fundamental conditions for Now-CP-ranke tensor completion. Journal of Machine Learning Research, 2017.
[36] M. Ashraphijuo, V. Aggarwal and X. Wang, Deterministic and probabilistic conditions for finite completability of cow-tucker-rank tensor, IEEE Transactions on Information Theory, 2019.
[37] M. Ashraphijuo and X. Wang, Clustering a union of low-rank subspaces of different dimensions with missing data, Pattern Recognition Letters 2019.
[38] M. Ashraphijuo, X. Wang, Fundamental conditions on the sampling patlern for union of low-rank subspaces retrieval, Annals of Mathematics and Artificial Intelligence, 2019.
[39] E. Elhamifar, High-rank mairix completion and clustering under self-expressive models, Ad- vances in Neural Information Processing Systems, 2016.
[40] G. Ongie, R. Willett, R. Nowak and L. Balzano, Algebraic variety models for high-rank matrix completion, International Conference on Machine Learning. 2017.
[41] G. Ongie, D. Pimentel, L. Balzano, R. Willett and R. Nowak, Low algebraic dimension matrix completion, Allerton Conference Communication, Control and Computing, 2017.
[42] S. Highlander, High throughput sequencing methods for microbiome profiling: application to food animal systems, Animal Health Research Reviews, 2012.
[43] S. Mande, M. Mohammed and T. Ghosh, Classification of metagenomic sequences: methods
and challenges, Briefings in Bioinformatics, 2012.
[44] R. Ranjan, A. Rani, A. Metwally, H. McGee and D. Perkins, Analysis of the microbiome: Advan- tages of whole genome shotgun versus 16S amplicon sequencing, Biochemical and Biophysical Research Communications, 2016.
[45] N. Nguyen, T. Warnow, M. Pop and B. White, A perspective on 16S rRNA operational taxonomic unit clustering using sequence similarity, Biofilms and Microbiomes, 2016.
10

---

Published as a conference paper at ICLR 2021
[46] G. Marçais, A. Delcher, A. Phillippy, R. Coston, S. Salzberg and A. Zimin, MUMmer4: A fast and versatile genome alignment system, PLoS Computational Biology, 2018.
[47] Netflix, Inc. The Netflix prize, http: /wwwwwww....oom/o..o/ wwweeeiiiriiiii com.
[48] E. Candès and B. Recht, Exact matrix completion via convex optimization, Foundations of Computational Mathematics, 2009.
[49] E. Candès and T. Tao, The power of convex relaxation: near-optimal matrix completion, IEEE Transactions on Information Theory, 2010.
[50] B. Recht, simpler approach to matrix completion, Journal of Machine Learning Research, 2011.
[51] Z.. Lin, R. Liu and Su, Linearized alternating direction method with adaptive penalty for low rank representation, Advances in Neural Information Processing Systems, 2011.
[52] Z.. Wen, W. Yin and Y. Zhang, Solving a low-rank factorization model for matrix completion by non-linear successive over-relaxation algorithm, Mathematical Programming Computation, 2012.
[53] Jain, Netrapalli and Sanghavi, Low-rank matrix completion using alternating minimiza- tion, ACM symposium on Theory of computing, 2013.
[54] Y. Chen, S. Bhojanapalli, S. Sanghavi and R. Ward, Coherent matrix completion, International Conference on Machine Learning, 2014.
[55] Y. Chen, Incoherent-optineee optimal matrix completion, IEEE Transactions on Information Theory, 2015.
[56] F. Király, L. Theran and R. Tomioka, The algebraic combinatorial approach for low-rank matrix completion, Journal Machine Learning Research, 2015.
[57] D. Aomentel-Alarcón N. Boston and R. Nowak, A characterization of deterministic sampling patterns for low-rank matrix completion, IEEE Journal of Selected Topics in Signal Processing, 2016.
[58] D. Pimentel-Alarche and R. Nowak, A converse to low-rank matrix completion, IEEE Interna- tional Symposium on Information Theory, 2016.
[59] D. Pimentel-A -llaróó,,, Mixture Matrix Completion, Advances in Neural Information Processing Systems, 2018.
[60] M. Aharon, M. Elad and A. Bruckstein, K-SVD: An algorithm for designing overcomplete dictionaries for sparse representation, IEEE Transactions on Signal Processing, 2006.
[61] J. Mairal, F. Bach, J. Ponce and G. Sapiro, Online dictionary learning for sparse coding, International Conference on Machine Learning, 2009.
[62] C. Zhao, X. Wang and W. Cham, Background subtraction via robust dictionary learning, EURASIP Journal on Image and Video Processing, 2011
[63] C. Lu, J. Shi and J. Jia, Online robust dictionary learning, IEEE Conference on Computer Vision and Pattern Recognition, 2013.
[64] A. Iqbal and A. Seghouane, An a- -iivergence-based based approach for robust dictionary learning, IEEE Transactions on Image Processing, 2019.
[65] Y. Xu, Z. Li, C. Tian and J. Yang. Multiple vector representations of images and robust dictionary learning, Pattern Recognition Letters, 2019.
[66] S. Mahdiradehaghdam, A. Panahi, H. Krim and L. Dai, Deep dictionary learning: A parametric network approuch, IEEE Transactions on Image Processing. 2019.
[67] J. Ren. Z. Zhang, S. Li, Y. Wang, G. Liu, S. Yan, and M. Wang, Learning Hybrid Representation by Robust Dictionary Learning Factorized Compressed Space IEEE Transactions on Image Processing, 2020.
[68] Y. Zheng, S. Sugimoto, and M. Okutomi, Deterministically maximizing feasible subsystem for robust model fitting with unit norm construint, IEEE Conference on Computer Vision and Pattern Recognition, 2011.
[69] P. Purkait, C. Zach, and A. Eriksson, Maximum Consensus Parameter Estimation by Reweighted
E Methods, International Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition. Springer, Cham, 2017.
11

---

Published as a conference paper at ICLR 2021
[70] T.J. Chin, P. Purkait, A. Eriksson and D. Suter, Efficient globally optimal consensus maximi- sation with tree search, Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2015.
[71] T.JJ. Chin, Y. Heng Kee, A. Eriksson and F. Neumann, Guaranteed outlier removal with mixed integer linear programs, Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2016.
[72] P. Speciale, D. Pani, M. Oswald, T. Kroeger, L. Van Gool and M. Pollefeys, Consensus Maximization with Linear Matrix Inequality Constraints, IEEE Conference on Computer Vision and Pattern Recognition. 2017.
[73] Z. Cai, T, Chin, Le and D. Suter, Deterministic consensus maximization with biconvex programming, arXiv preprint, 2018.
[74] C. Yu and D.Y. Ju, A maximum feasible subsystem for globally optimal 3D point cloud registra- tion, Sensors, 2018.
[75] T. Kanungo, D. Mount, N. Netanyahu, C. Piatko, R. Silverman and A. Wu, An efficient k-means
clustering algorithm: Analysis and implementation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002.
[76] S. Shahbazpanahi, S. Valaee and M. Bastani, Distributed source localization using ESPRIT algorithm, IEEE Transactions Signal Processing, 2001.
[77) M. Rangaswamy, F. Lin and K. Gerlach, Robust adaptive signal processing methods for heterogeneous radar clutter scenarios, Signal Processing, 2004.
[78] H. Krim and M. Viberg, Two decades of array signal processing research: the parametric approach, Signal Processing Magazine, 1996.
[79] B. Ardekani, J. Kershaw, K. Kashikura and Kanno, Activation detection in functional MRI using subspace modeling and maximum likelihood estimation, IEEE Transactions on Medical Imaging, 1999.
[80] M. McCloud and L. Scharf, Interference estimation with applications to blind multiple-access communication over fuding channels, IEEE Transactions on Information Theory, 2000.
[81] D. Stein, S. Beaven, L. Hoff, E. Winter, A. Schaum and A. Stocker, Anomaly detection from hyperspectral imagery, IEEE Signal Processing Magazine, 2002.
[82] T. Ahmed, M. Coates and A. Lakhina, Multivariate online anomaly detection using kernel recursive least squares, INFOCOM. 2007.
[83] B. Eriksson, P. Barford, J. Sommers and R. Nowak, Domainlmpute: inferring unseen compo-
nents in the Internet, IEEE INFOCOM, 2011.
[84] R. Govindan and H. Tangmunarunkit, Heuristics for Internet Map Discovery, IEEE INFOCOM 2000.
[85] Barford, A. Bestavros, J. Byers and M. Crovella, On the marginal utility of network topology measurements, Proceedings of ACM Internet Measurement Workshop, 2001.
[86] N. Spring, R. Mahajan, D. Wetherall and T. Anderson, Measuring ISP topologies with rocketfuel, IEEE/ACM Transactions Networking, 2004.
[87] D. Alderson, I., Li, W. Willinger and J. Doyle, Understanding internet topology: Principles,
models and validation, IEEE/ACM Transactions on Networking, 2005.
[88] R. Sherwood, A. Bender and N. Spring, DisCarte: SIGCOMM, 2008
disjunctive Internet cartographer, ACM
[89] B. Eriksson, P. Barford and R. Nowak, Network Discovery from Passive Measurements, ACM SIGCOMM, 2008
[90] E. Leaaned--Miiii M. Narayana and A. Hanson, Coherent motion segmentation in moving camera videos using optical flow orientations, International Conference on Computer Vision, 2013.
[91] R. Tibshirani, Regression Shrinkage and Selection via the Lasso, Journal of the Royal Statistical Society, 1996.
[92] M.A. Fischler, R.C. Bolles, Random sample consensus: a paradigm for model fitting with applications image analysis and automated cartography, Communications of the ACM, 1981.
12

---

Published as a conference paper at ICLR 2021
[93] R. Raguram, J.M. Frahm, M. Pollefeys: A comparative analysis of ransac techniques leading to adaptive real-time random sample consensus, European Conference Computer Vision, 2008.
[94] R. Raguram, O. Chum, M. Pollefeys, Matas, J.M. Frahm, Usac: a universal framework for random sample consersus, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013.
[95] M. Feigin, B.J. Ranger, and Anthony, Statistical consensus framewook for image registration, International Conference on Pattern Recognition, 2016.
[96] H. Le, T.J. Chin, and D. Suter, An exacl penalty method for locally convergent maximum consensus, IEEE Conference Computer Vision and Pattern Recognition, 2017.
[97] R. Li, J. Sun, D. Gong, Y. Zhu, H. Li and Y. Zhang, ARSAC: Efficient Model Estimation via Adaptively Ranked Sample Consensus, Neurocomputing. 2018.
[98] K.H. Lee, C. Yu, and S.W. Lee, Deterministic Hypothesis Generation for Robust Fitting of Multiple Structures, arXiv preprint arXiv: .09408 (2018).
[99] D. Arthur and S. Vassilvitskii, k-means++: The advantages of careful seeding, Annual ACM- SIAM Symposium on Discrete Algorithms, 2007.
[100] https: / dani/aniiieeeee e pimeenell...eemmmmmmmm.e.mme.mee github..h....... / publ/ iicaiiinnnn........ html
13

---

Published as a conference paper at ICLR 2021
A
PROOFS
In this section we present the proofs of all statements. We begin with the proof of Lemmas and 2, which are required for the proof of Theorem
Proof. (Lemma 1) Since U is in general position, if [S2] I dim(U*), then U/ -R RR0 In other words, Uh is the entire / 121msiimesiionl space.
Proof. (Lemma 2) If C Q2 then x trivially lies in Up by A2. To see the reverse implication, let r: dim(U*). We know that X Uh if and only if there exists a coefficient vector 0 E R" such that
X 0
where U E Rdxx denotes basis of UK Since r by assumption, equation 1 defines system of r + equations (the rows of xn) and unknowns (the entries of 0). Assume without loss of generality that Ω {1, 21,2..... , + 1] (otherwise simply permute the rows accordingly), and let rewrite equation 1
Ω = (1,2......)) be the subset of Q with the first elements. Then
r
X
N
0.
Xr++1
U r+1
Notice that Uh R invertible because A1 guarantees that U in general position with probability 1. Hence we can use the top block obtain = ( and we can plug this in the last row obtain:
x++1 = U (U X2'
Let kj indicate the subspace corresponding to the jth entry of x. Then by A2 there exist coefficients
@² 0 such that x; = U gh. In light of this we can rewrite the last equation
Uk gki U
Ulit (Uk))
U 0%.
At this point equation 2 has no variables left (all U and e are fixed), which means that equation is consistency condition. Notice that if I2 S2 then k; k, and equation 2 transforms into
UK 0 Uk r+ - UU
which further simplifies to Uk _ 0 equation is met. On the other hand, if 52 & S4. equation does not simplify any further. Recall from A1 that U' ...., T are drawn independently. This implies that the entries in U K keep no relation with one another. Similarly, from A2 we know that Xo, is drawn independently. Equivalently, 0¹ ,..., 0k keep no relation with one another. Intuitively, we can think of the entries in Uh's 's and 0k', 's as independent random numbers drawn from distribution with full measure. We thus conclude that & Qg. with probability the consistency condition equation would not hold.
Uk r- g In other words, if f2 C Ω4, the consistency condition
To summarize, we know that xn E Uh if and only if there is vector 0 that satisfies equation 1. We showed that this will be the case if and only if equation 2 holds, which in turn will happen if and only C Og claimed.
Notice that if Ω has dim( entries, equation becomes system with dim(U*) & equations, which result in consistency conditions similar to equation By the same arguments as in the proof of Lemma 2, Xa will agree with U if and only if these consistency conditions hold, which will happen if and only if Ω Sr. We thus obtain the following corollary
14

---

Published as a conference paper at ICLR 2021
Corollary 2. Suppose A1 and A2 hold. Let Q be arbitrary subset of [d] with more than dim (U*)
elements. Then Xn Dg if and only i 94.
With this, we are ready to give proof of Theorem
Proof. (Theorem 1) Let Iv dim(U"). To identify 2 S2 we will exhaustively search for combinations of Ik entries in that match with U By Lemma 2 know that x will match with U if and only if S4. By assumption there is least one k for which [S2g] > rk. 80 we know that some point we will find such subset Q2 Once we do, we can recover 0 (Uk₂ xy'- where S2 can be any subset of Ω with exactly Fı entries (recall that A1 guarantees that Ug is invertible). Finally, we can compute x == U* and recover Qg by inspection (the set zero entries in x x), where Corollary 2 guarantees that there will be no additional false matching entries. Repeating this procedure for every k we can recover Q,...., Skg, as claimed.
To obtain the converse, suppose that ri or fewer entries of x correspond U for some k. By Lemma 1, any subset S2' of Q2 U 2g with [S2'| I ræ satisfies X E U.y Hence we can split the entries of x corresponding to Ω and Ωg non-unique manner, and still have them agree with U which makes f4 unidentifiable.
We now use the same strategy to prove Corollary 1, which extend these ideas noisy settings.
Proof. (Corollary 1) Let Pky denote the projection operator onto Uh. Under the assumptions of the corollary, if S2 E Qu. then with high probability (decreasing in C' and increasing in c). ||x0- - Pk 1o
[2 (see Theorem in [17]). In other words, the residual of projecting X onto Uh will be too large if the entries of Ω2' do not come from the k/h subspace. Hence, instead of
searching for a set 52' where X perfectly fits in Upy (as in the proof of Theorem 1), we can search for subsets S C S4 where the residual is within the noise level, i.e., ||x0' Ph < |o
The rest of the proof follows by the same arguments as the proof of Theorem
B ADDITIONAL EXPERIMENTS
04 -44
12 20,
(6 - 2.
Bii
0.
RusbAS
1277
12T1
10.7
persshepace
Suhppces Dirresson ())
Schapoon Dimaddo (0)
Noke Lovetoo 60)
[M)
4) aid
(ey 4,
r.r
Donbee gowd
110
12a
87
39
113
117
Emiess schepooe (50)
Sclapeens Dirressorrt
Schepaco Dimmdde (n)
Nokoa
1017
1970
Figure 2: Complementary results to Figure 1 with 4. Average success rate and iteration growth over 100
trials, as a function of the number of entries per subspace [2a, (which in turn is a proxy of the ambient dimension d). the subspaces dimensions r, the gap := [S&] (r + 1). and the noise level a.
15


Reviews:
[{"review_id": "k_j47-8k-BD", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper introduced a new setting in which variables in feature vector are divided into different groups and in each group, variables are generated by sampling within linear subspace. They characterized the sufficient and necessary condition for the system to be identifiable. Three algorithms are provided to cluster the variables into their generative subspace. They also provide motivating applications for this new setting in metagenomics, recommender systems, and robust learning. I think the new setting is potentially interesting and the proposed algorithms are good. However, compared with, for example, subspace clustering, the generative subspace {U_i} is known to the users a prior and the goal is to classify variables of a single data point, which might be rarely the case in practice.\n\nComments:\n\nMy main concern is on the proof of Theorem 1, which seems a little bit sloppy and not convincing enough to me. For example, on page 14, in the mid of Eq.(1) and Eq.(2), the authors argue U_\\Omega^k is invertible as subspace U^k is in so-called general space. Please elaborate on that. I am confused as if we set U_\\Omega^k any full rank r-by-r matrix and let U_{r+1}^k be a copy of any row in U_\\Omega^k. And, do a row swap between r+1 and any row in [r]. Then, the new r-by-r U_\\Omega^k cannot be invertible as it is not full rank in row. It is not clear to me the set of this type of subspace a zero-measure set on the uniform distribution of (d,r)-Grassmannian. Please consider rewriting the proof in a more rigorous way.", "extra_scores": {}, "extra_text": {}}, {"review_id": "jpcy1bdF9Sn", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose a method to perform subspace splitting. That is, the task of clustering the entries of an input vector into sets of coherent subspaces. The contribution of the work is two-fold: (1) the theoretical characterization of the problem, and its well-posedness, and (2) the presentation of three algorithms for tackling the problem of subspace splitting. Quantitative analysis of the performance of the three algorithms is provided by means of synthetic experiments.\n\nThe paper is well written, with sound mathematical formulation. The contributions proposed by the authors seem to have enough novelty and relevance for the community, and both theoretical and practical contributions are thoroughly motivated and discussed.\n\nMajor concerns:\n\n* I find the structure and content of the paper somehow unbalanced. A fairly large portion is dedicated to motivational applications, which feels like an extension of the related work section, but are not experimentally explored. In Section 5 most discussion is devoted to approaches with clear drawbacks (RanSaS, GreedyS), while the final proposal (K-splits) is hardly discussed.\n\n* While it is true that a large contribution of the work is strictly theoretical, the practical aspect of the paper could be further backed by experimental validation. The experiments section show limited results regarding the choice of the number of clusters (only 2 or 4). The performance of RanSaS and K-Splits is saturated in all noise-free experiments which makes them hard to compare or identify failure cases. \n\n* Given the attention paid in the paper to motivating applications (a full section) I miss a section in the Experiments where the proposed approach is validated with real data from any of the mentioned applications. I feel this would tremendously increase the value of the work and would legitimize the claim of practical importance that the authors make in introduction and conclusions.\n\nMinor concerns:\n\n* At the end of the first paragraph of related work, the authors claim that random sampling is not applicable to subspace splitting, with no further explanation of why this is the case. At the same time the algorithm presented (RansaS) is based on random sampling which seems contradictory.\n* As I mentioned earlier, I miss more discussion regarding the K-splits approach. Did the authors find any clear drawbacks besides initialization? What about the K-means assumption of isotropic clusters?\n* The choice of just l1 as a baseline for comparison is a bit arbitrary. I wonder why the other mentioned approaches (mixed-integer programming or random sampling) were not added to the evaluation.\n* The paper could use further review to avoid typos and missing references.\n* The paper doesn’t follow the citation convention: authors’ last names and year.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "U21z4qScv2-", "reviewer": "AnonReviewer2", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: The paper introduces the problem of subspace spitting, in which an observed mixed-features vector is to be partitioned such that the identified partitions match with given subspaces. The main results of the paper lie in deriving sufficient and necessary conditions for identifiability of these partitions when the subspaces and the entries of the features are randomly positioned in the ambient dimension and the subspaces, respectively. The conditions simply require that there are more entries associated with each subspace than the dimension of the subspace. The paper also presents algorithms to perform the splitting. \n\nStrengths: \n- The problem statement is novel. I did not see previous formulations of this problem. \n- The paper is generally well-written. \n- The paper has a good balance of theory and algorithm development. \n\nWeaknesses: \n- The experimental results section is rather weak. It would be good to include some realistic examples from some concrete applications.\n- While the paper has a dedicated section on motivating applications, they are not that convincing. The metagenomics application is more plausible, but I do not think this model applies well to recommender systems. The examples provided seem to be included to justify the proposed model. Perhaps there are meaningful relevant applications, but for the current version the problem setup is not sufficiently justified and seems somewhat contrived. \n- The assumptions about the subspaces need to be more explicit, especially when discussing the algorithms. For example, the random sampling algorithm seems to require full knowledge of the dimensions of these subspaces which may be impractical.\n- I have not fully verified this argument, but I am under the impression that the result of the main theorem is trivial. Isn't it obvious that the span of the restriction of a subspace to a given partition of size m, the whole R^m? I believe the main result can just follow from this simple observation.   \n- Reproducibility: the authors did not include code for their developed algorithms in the supplementary material. \n \nImpact: Provided that the problem setup and model are better justified, I believe this work could open up new research questions in machine learning and data analysis, including (mixture) variants of well-studied problems on matrix completion and robust learning.   \n\nOverall I like the paper, especially that the problem setup itself seems novel. However, the model is not sufficiently justified, the assumptions are somewhat questionable, and the experimental section is lacking. As such I would rate this as a marginal acceptance. \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers a new linear-algebraic problem motivated by applications such as metagenomics which requires the algorithm to partition the coordinates of a long noisy vector according to a few known subspaces. A number of theoretical questions were asked (e.g., identifiability;  efficient algorithms and their error bounds; etc).  

The reviewers generally liked the paper for what it does. Specific suggestions were raised by the reviewers, including how the paper went into length about the motivating applications but did not end up evaluating the proposed algorithms on any motivating applications; and that the main theoretical results were not technically challenging / nor surprising (although the authors provided a fair justification in their rebuttal).

The AC finds the paper an outlier in terms of the topics among papers typically received by ICLR, but liked the paper precisely because it is different.  The authors are encouraged to discuss the connections of the specific problem to the context of representation learning and machine learning in general.

Overall, I believe the paper is a solid borderline accept.  


Decision: Accept (Poster)