Cluster Trees on Manifolds
In this paper we investigate the problem of estimating the cluster tree for a density f supported on or near a smooth
We analyze a modified version of a k-nearest neighbor based algorithm recently proposed by Chaudhuri and Dasgupta (2010). The main results of this paper show that under mild assumptions on f and M , we obtain rates of convergence that depend on d only but not on the ambient dimension D. Finally, we sketch a construction of a sample complexity lower bound instance for a natural class of manifold oblivious clustering algorithms.
The paper discusses the estimation of the cluster tree 
      when the probability density function is supported on a d dimension 
      manifold in a D dimensional space. They show that the algorithm RSL 
      proposed in (1) is consistent and the convergence rate, very roughly, 
      depends on d-the dimension of the manifold and not on D - the dimension of 
      the ambient space (but then the convergence rate also depends on tau-the 
      conditional number and an epsilon^{d+2} factor instead of an epsilon^2 
      factor). The main result is achieved by repeating the technique in 
      (1). To do that, the authors had to show: First,a bound on a size of an 
      s-net in the manifold setting. Second, bounds on the deformation of the 
      volume (i.e. that B(x,r)cap M has roughly the volume of a d-dimensional 
      ball of radius r where d is the dimension of M). The authors are able to 
      show both under the assumption of small conditional number. I 
      think it is interesting to know how convergence rate changes under this 
      assumption (i.e. manifold assumption) and the paper give both lower bounds 
      and upper bounds that are not trivial. So even though the convergence rate 
      depends on sizes that are not available (the dimension of the manifold and 
      the conditional number), still the results are interesting. I 
      found the writing very unclear and certain definitions are even confusing: 
      ******************************* 1) The statement in thm.4 is 
      wrong. A much stronger statement is proved in thm.6 of [1] than 
      def.3-consistency. (see also, remark after thm.6 in [1]). Theorem 
      6 states that with high probability: uniformly, every A A' that satisfy 
      (\sigma,\epsilon)-separation: we get separation and conectedness. 
      Theorem 4 states that for every A A' that satisfy (\sigma, 
      \epsilon)-seperation, with high probability we get separation and 
      connectedness. These are not equivalent statements. Please correct 
      this. ***************************** 2) Still in definition 3: what 
      is n? who is C_n (is it a random variable? how is it defined? is it 
      different than hat{C}) I had to rely on the definition in (1) to 
      understand what is meant here. 3) When using Lemma 16: It is worth 
      indexing and mentioning which inequality is used and how at each step. Not 
      all steps are clear, it seems that at last step you use 
      (1+4r/t(1+4r/t))(1+4r/t) < (1+6r/t) but that's not even hinted. The 
      steps should be clearer. 4) Lemma 18: I think a 1/2 is missing 
      from the definition of v_cap. Worth mentioning that 
      Gamma(1/2)=sqrt(pi) otherwise it's not clear where it went. 
      Further suggestions: The lower bound you produce 
      depends on the conditional number, it might be worth mentioning the lower 
      bound you produce are not an improvement over the lower bound in (1), but 
      are different (e.g. in a linear subspace that has 1/tau=0 your lower bound 
      is meaningless while (1) gives a sensible lower bound). Regarding 
      the parameter \rho, does it really make sense to choose salience parameter 
      2\sigma > tau? won't it be easier to simply assume (3\sigma/16) < 
      (\tau/16)?