Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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.

The 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.

Major concerns:

* 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.

* 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. 

* 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.

Minor concerns:

* 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.
* 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?
* 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.
* The paper could use further review to avoid typos and missing references.
* The paper doesn’t follow the citation convention: authors’ last names and year.

review_title: Mixed-Features Vectors and Subspace Splitting

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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.

Comments:

My 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.
review_title: interesting new setting but with limitations

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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. 

Strengths: 
- The problem statement is novel. I did not see previous formulations of this problem. 
- The paper is generally well-written. 
- The paper has a good balance of theory and algorithm development. 

Weaknesses: 
- The experimental results section is rather weak. It would be good to include some realistic examples from some concrete applications.
- 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. 
- 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.
- 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.   
- Reproducibility: the authors did not include code for their developed algorithms in the supplementary material. 
 
Impact: 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.   

Overall 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. 

review_title: Anonymous review of subspace splitting paper

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)