Variational splines and Paley-Wiener spaces on Combinatorial graphs (Q734052)

Let \(G\) be a combinatorial graph with vertices \(V\). Each vertex \(v\in V\) is given a degree \(d(v)\) (the number of its edges). \(L_2(V)\) is the space of functions square summable over the vertices weighted with \(d(v)\). Given a subset \(W\) of vertices and a corresponding set of complex values, a variational spline is the (unique) solution in \(L_2(G)\) that interpolates the data having a certain minimal Sobolev norm \(\|f\|_{t,\epsilon}=\|{\mathcal S}^{1/2}f\|\) where \({\mathcal S}=(\epsilon I-{\mathcal L})^{t}\), \(\epsilon\geq0\), \(t\) real and \({\mathcal L}\) is a discrete Laplace operator. If \({\mathcal L}\) is invertible, then \(\epsilon=0\), otherwise \(\epsilon\) needs to be positive. Every spline can be written as a linear combination of the fundamental solutions of the operator \({\mathcal S}\). The operator \({\mathcal L}\) is an essential tool in developing the results of this paper. It is bounded and selfadjoint and allows to define a generalization of the Fourier transform on \(G\). A Paley-Wiener space \(PW_\omega\) on graph \(G\), (\(\omega>0\) but in practice it belongs to the spectrum of \({\mathcal L}\)) contains functions from \(L_2(G)\) whose generalized Fourier transform has support in \([0,\omega]\). Some generalization of Shannon's sampling theorem is then solved: Can uniqueness sets \(U\subset V\) be found such that values in these vertices, will define the \(L_2(G)\)-function uniquely? It is shown that nontrivial uniqueness sets exist in \(PW_\omega\) if \(0<\omega<(1+1/d(G))^{1/2}\) where \(d(G)=\max_{v\in V} d(v)\). Several such sets are described. The main result of this paper shows how and when spline interpolation is able to recover any function in \(PW_\omega\). For \(t=2^l\) with \(l\) integer going to infinity, a sequence of interpolating splines is constructed that converges linearly to \(f\in FW_\omega\).