Quadrature formulas on combinatorial graphs.

The goal of the paper is to establish quadrature formulas on combinatorial graphs. Three types of quadrature formulas are developed. Quadrature formulas of the first type are obtained through interpolation by variational splines. This set of formulas is exact on spaces of variational splines on graphs. Since bandlimited functions can be obtained as limits of variational splines we obtain quadrature formulas which are approximately exact on spaces of bandlimited functions. Accuracy of this type of quadrature formulas is given in terms of geometry of the set of nodes of splines and in terms of smoothness of functions which is measured by means of the combinatorial Laplace operator. Quadrature formulas of the second type are obtained through point-wise sampling for bandlimited functions and based on existence of certain frames in appropriate subspaces of bandlimited functions. The third type quadrature formulas are based on the average sampling over subgraphs. Our quadrature formulas which are based on sampling are exact on a relevant subspaces of bandlimited functions. The results of the paper have potential applications to problems that arise in data mining. [ABSTRACT FROM AUTHOR]