Publications and research of Mikhail Belkin partially or fully supported by the NSF Early Career Award 0643916.

[Journal papers]  [Conference papers] [Technical Reports and preprints]

Journal Papers:

  1. Towards a Theoretical Foundation for Laplacian-Based Manifold Methods
    M. Belkin, P. Niyogi
    Journal of Computer and System Sciences, 2008. Invited, special issue on learning theory (to appear).


Refereed and Invited Conference Proceedings:
  1. The value of labeled and unlabeled examples when the model is imperfect [pdf, bib]
    K. Sinha, M. Belkin, NIPS 2007.
    + abstract
    Semi-supervised learning, i.e. learning from both labeled and unlabeled data has received signi.cant attention in the machine learning literature in recent years. Still our understanding of the theoretical foundations of the usefulness of unlabeled data remains somewhat limited. The simplest and the best understood situation is when the data is described by an identi.able mixture model, and where each class comes from a pure component. This natural setup and its implications ware analyzed in [11, 5]. One important result was that in certain regimes, labeled data becomes exponentially more valuable than unlabeled data. However, in most realistic situations, one would not expect that the data comes from a parametric mixture distribution with identifiable components. There have been recent efforts to analyze the non-parametric situation, for example, .cluster. and manifold assumptions have been suggested as a basis for analysis. Still, a satisfactory and fairly complete theoretical understanding of the nonparametric problem, similar to that in [11, 5] has not yet been developed. In this paper we investigate an intermediate situation, when the data comes from a probability distribution, which can be modeled, but not perfectly, by an identi.able mixture distribution. This seems applicable to many situation, when, for example, a mixture of Gaussians is used to model the data. the contribution of this paper is an analysis of the role of labeled and unlabeled data depending on the amount of imperfection in the model.

Technical Reports and Preprints:
  1. Discrete Laplace Operator for Meshed Surfaces
    M. Belkin, J. Sun, Y. Wang, 2007
    + abstract
    In recent years a considerable amount of work in graphics and geometric optimization used tools based on the Laplace-Beltrami operator on a surface. The applications of the Laplacian include mesh editing, surface smoothing, and shape interpolations among others. However, it has been shown [12, 23, 25] that the popular cotangent approximation schemes do not provide convergent point-wise (or even L2) estimates, while many applications rely on point-wise estimation. Existence of such schemes has been an open question [12]. In this paper we propose the first algorithm for approximating the Laplace operator of a surface from a mesh with point-wise convergence guarantees applicable to arbitrary meshed surfaces. We show that for a sufficiently fine mesh over an arbitrary surface, our mesh Laplacian is close to the Laplace-Beltrami operator on the surface at every point of the surface. Moreover, the proposed algorithm is simple and easily implementable. Experimental evidence shows that our algorithm exhibits convergence empirically and outperforms cotangent-based methods in providing accurate approximation of the Laplace operator for various meshes.