We consider point clouds obtained as random samples of a measure on a Euclidean domain. A graph representing the point cloud is obtained by assigning weights to edges based on the distance between the points they connect. Our goal is to develop mathematical tools needed to study the consistency, as the number of available data points increases, of graph-based machine learning algorithms for tasks such as clustering. In particular, we study when the cut capacity, and more generally total variation, on these graphs is a good approximation of the perimeter (total variation) in the continuum setting. We address this question in the setting of Γ-convergence. We obtain almost optimal conditions on the scaling, as the number of points increases, of the size of the neighborhood over which the points are connected by an edge for the Γ-convergence to hold. Taking of the limit is enabled by a transportation based metric which allows us to suitably compare functionals defined on different point clouds.
In the discrete setting, works related to the @math -convergence of functionals to continuous functionals involving perimeter include @cite_44 , @cite_55 and @cite_36 . The results by Braides and Yip @cite_44 , can be interpreted as the analogous results in a discrete setting to the ones obtained by Modica and Mortola. They give the description of the limiting functional (in the sense of @math -convergence) after appropriately rescaling the energies. In the discretized version considered, they work on a regular grid and the gradient term gets replaced by a finite-difference approximation that depends on the mesh size @math . Van Gennip and Bertozzi @cite_55 consider a similar problem and obtain analogous results. In @cite_36 , Chambolle, Giacomini and Lussardi consider a very general class of anisotropic perimeters defined on discrete subsets of a finite lattice of the form @math . They prove the @math -convergence of the functionals as @math to an anisotropic perimeter defined on a given domain in @math .
@cite_44 @cite_55 @cite_36
2086002908 2963833097 2129572061
We investigate the minimization of Newton's functional for the problem of the body of minimal resistance with maximal height @math cite butt in the class of convex developable functions defined in a disc. This class is a natural candidate to find a (non-radial) minimizer in accordance with the results of cite lrp2. We prove that the minimizer in this class has a minimal set in the form of a regular polygon with @math sides centered in the disc, and numerical experiments indicate that the natural number @math is a non-decreasing function of @math . The corresponding functions all achieve a lower value of the functional than the optimal radially symmetric function with the same height @math . We investigate the limiting description for a finite-difference approximation of a singularly perturbed Allen--Cahn type energy functional. The key issue is to understand the interaction between two small length-scales: the interfacial thickness @math and the mesh size of spatial discretization @math . Depending on their relative sizes, we obtain results in the framework of @math -convergence for the (i) subcritical ( @math ), (ii) critical ( @math ), and (iii) supercritical ( @math ) cases. The first case leads to the same area functional as the spatially continuous case while the third gives the same result as that coming from a ferromagnetic spin energy. The critical case can be regarded as an interpolation between the two. This is the second article of a series of papers on stochastic homogenization of discrete elliptic equations. We consider a discrete elliptic equation on the @math -dimensional lattice @math with random coefficients @math of the simplest type: They are identically distributed and independent from edge to edge. On scales large w. r. t. the lattice spacing (i. e. unity), the solution operator is known to behave like the solution operator of a (continuous) elliptic equation with constant deterministic coefficients. This symmetric ''homogenized'' matrix @math is characterized by @math for any direction @math , where the random field @math (the ''corrector'') is the unique solution of @math in @math such that @math , @math is stationary and @math , @math denoting the ensemble average (or expectation). In order to approximate the homogenized coefficients @math , the corrector problem is usually solved in a box @math of size @math with periodic boundary conditions, and the space averaged energy on @math defines an approximation @math of @math . Although the statistics is modified (independence is replaced by periodic correlations) and the ensemble average is replaced by a space average, the approximation @math converges almost surely to @math as @math . In this paper, we give estimates on both errors. To be more precise, we do not consider periodic boundary conditions on a box of size @math , but replace the elliptic operator by @math with (typically) @math , as standard in the homogenization literature. We then replace the ensemble average by a space average on @math , and estimate the overall error on the homogenized coefficients in terms of @math and @math . We investigate a family of regression problems in a semi-supervised setting. The task is to assign real-valued labels to a set of @math sample points, provided a small training subset of @math labeled points. A goal of semi-supervised learning is to take advantage of the (geometric) structure provided by the large number of unlabeled data when assigning labels. We consider random geometric graphs, with connection radius @math , to represent the geometry of the data set. Functionals which model the task reward the regularity of the estimator function and impose or reward the agreement with the training data. Here we consider the discrete @math -Laplacian regularization. We investigate asymptotic behavior when the number of unlabeled points increases, while the number of training points remains fixed. We uncover a delicate interplay between the regularizing nature of the functionals considered and the nonlocality inherent to the graph constructions. We rigorously obtain almost optimal ranges on the scaling of @math for the asymptotic consistency to hold. We prove that the minimizers of the discrete functionals in random setting converge uniformly to the desired continuum limit. Furthermore we discover that for the standard model used there is a restrictive upper bound on how quickly @math must converge to zero as @math . We introduce a new model which is as simple as the original model, but overcomes this restriction.