Subspace Clustering via Tangent Cones
Given samples lying on any of a number of subspaces, subspace clustering is the task of grouping the samples based on the their corresponding subspaces. Many subspace clustering methods operate by assigning a measure of affinity to each pair of points and feeding these affinities into a graph clustering algorithm. This paper proposes a new paradigm for subspace clustering that computes affinities based on the corresponding conic geometry. The proposed conic subspace clustering (CSC) approach considers the convex hull of a collection of normalized data points and the corresponding tangent cones. The union of subspaces underlying the data imposes a strong association between the tangent cone at a sample x and the original subspace containing x. In addition to describing this novel geometric perspective, this paper provides a practical algorithm for subspace clustering that leverages this perspective, where a tangent cone membership test is used to estimate the affinities. This algorithm is accompanied with deterministic and stochastic guarantees on the properties of the learned affinity matrix, on the true and false positive rates and spread, which directly translate into the overall clustering accuracy.
Summary: 
The paper describes a new geometric insight and a new algorithm for noiseless subspace clustering based on a geometric insight about the tangent cone.
The key idea (Proposition 2) is that if x and x’ are from the same subspace, then -x -\sign(< x,x’ >) \beta x’ should within a union of non-convex cones that comes directly from x and the underlying union of subspaces for all positive \beta, while if x and x’ are not from the same subspace, then when \beta is sufficiently large then the vector will not be on this union of non-convex cones.
The authors then propose an algorithm that tests every ordered pair of observed data points with a similar condition for a crude approximation of the ``union of non-convex cones’’ of interest ---- on the conic hull (therefore convex) of the observed data points.  The algorithm is parameterized by a tuning parameter \beta.  The authors then provide geometric conditions under which:  (1). if \beta is sufficiently large then there are no false positives. (2) if \beta is sufficiently small, then the true positive rate is at least a fixed fraction.  The geometric conditions are different for (1) and (2). For (1) the condition is reasonable, but for (2) it is quite restrictive, as I will explain later.
In addition, the authors analyzed the method under semi-random model (uniform observations on each subspace, or uniformly random subspaces themselves ) and described how to control the true positive rate. 
Evaluation:
The paper is well-written.
The technical results appear to be correct (didn’t have time to check the proofs in details). The idea of testing the “affinity” of pairs of data points using tangent cone is new as far as I know. The true positive rate control in Section 4 is new and useful. 
The result itself (in Section 4 and 5) seems quite preliminary are has a number of issues. 
In particular, it is not clear under what condition there exists a \beta that simultaneously satisfy conditions in Theorem 4 and Theorem 7. Or rather that the largest \rho one can hope to get when we require \beta > \beta_L, and how that number depends on parameters of the stochastic model.
On the other hand, the proposed approach does not seem to solve a larger class of problems than known before through using SSC.  Specifically, SSC allows the number of subspaces to be exponential in the ambient dimension, while the current approach seems to require the sum of dimensions of all subspaces to be smaller than the ambient dimension n. This is critical and not an artifact of the proof because in that case, the tangent cone would be R^n (or is it a half space?).  (For example, consider three 1D disjoint subspaces in 2D).
Part of the motivation of the work is to alleviate the ``graph connectivity’’ problem that SSC suffers. 
I believe the authors are not aware of the more recent discoveries on this front.  This issue is effectively solved the noiseless subspace clustering problem with great generality [a].  Now we know that if SSC provides no false discoveries then there is a post processing approach that provides the correct clustering despite potentially disconnected graph for data points in the subspace. The observation was also extended to noisy SSC. The implication of this to the current paper  (which also construct an affinity graph) is that as long as there are no false discoveries and at least d true discoveries (d is the subspace dimension) then the correct clustering can be obtained. Some discussions of the advantage of the proposed approach to the robust post-processing approach described in [a].
Lastly, since the proposed method is based on a seemingly very unstable geometric condition, I feel that it is much more important to analyze the robustness to stochastic noise as in [b,15] and adversarial perturbation as in [a,b]. 
Overall, I feel that this paper contains enough interesting new insights that should merit an accept to NIPS. 
Detailed comments/pointers and references:
1. Noiseless subspace clustering is, in great generality, a solved problem. 
-	For l1 SSC, there is a postprocessing approach that provides perfect clustering under only identifiability condition as long as there is no false positives. 
-	In other word, on noiseless subspace clustering problem, SSC does not suffer from the graph connectivity problem at all.  
-	As a result, the authors should explicitly compare the geometric condition used in this paper to the condition for SSC to yield no-false discoveries [14].
2. Even those geometric conditions in [14] can be removed if we allow algorithms exponential in subspace dimension d (and polynomial in everything else). In fact, L0 verson of SSC can already achieve that solve all subspace clustering problems that are identifiable [a].
3. The noisy subspace clustering and missing data subspace clustering problems are where many of the remaining open problems are. So it will be great if the authors can continue to pursue the new tangent cone idea and figure out how they can solve the noisy/missing data problems in comparison to those approaches existing in the literature.
[a] Wang, Yining, Yu-Xiang Wang, and Aarti Singh. "Graph connectivity in noisy sparse subspace clustering." Artificial Intelligence and Statistics. 2016.
[b] Wang, Yu-Xiang, and Huan Xu. "Noisy Sparse Subspace Clustering." Proceedings of the 30th International Conference on Machine Learning (ICML-13). 2013.