# Spatial Data Reconstruction via ADMM and Spatial Spline Regression +
## 3 Patched Estimation and Spatial Spline Regression
### Spatial Spline Regression  
Given the above observation, we can naturally come up with a second idea, which is learning a smooth estimation of \(\tilde{f}(\mathbf{p}_{j})\) by spatial smoothing techniques. In the following, we introduce the powerful smoothing technique named Spatial Spline Regression (SSR) proposed in [PERSON] et al. [16]. We will show how it can be applied to our particular spatial data reconstruction problem, as well as point out its limitations in solving the problem. Given \(l\) data points in \(\Omega\), which contains the following information: (1) their positions \(\{\mathbf{p}_{j}\}_{j=1}^{l}\); (2) the values of these \(l\) points: \(\{h_{j}\}_{j=1}^{l}\); and (3) their feature vectors \(\{\mathbf{w}_{j}\}_{j=1}^{l}\), SSR is able to fit a smooth spatial field \(f\) by minimizing the following equation [14; 16], i.e.,  
\[\underset{\mathbf{\beta},f}{\text{minimize}}\sum_{j=1}^{l}\left(h_{j}-\mathbf{w}_ {j}^{\mathsf{T}}\mathbf{\beta}-f(\mathbf{p}_{j})\right)^{2}+\lambda\int_{\Omega} \left(\
abla^{2}f\right)^{2}\mathrm{d}\mathbf{p}, \tag{8}\]  
where \(f\) is assumed to be twice-differentiable over \(\Omega\), and \(\
abla^{2}f=\frac{\partial^{2}f}{\partial x^{2}}+\frac{\partial^{2}f}{\partial y ^{2}}\) denotes the _Laplacian_ of \(f\) to penalize the roughness of \(f\). The hyper parameter \(\lambda\) is used to trade the smoothness of \(f\) off for a better approximation to data value \(h_{j}\). However, the challenge to solving problem (8) is that it involves searching for a functional \(f\) over a possibly non-convex domain \(\Omega\) that may have strong concavities, complicated boundaries, and even interior holes. Although kernel-based methods [26] are also a commonly used smoothing technique, their major drawback is that, by using uniformly damping weights in distance-based kernels, they tend to link data points across unrelated or weakly related subregions in an irregularly shaped non-convex domain. We now briefly describe how spatial spline regression [16] can solve problem (8) via finite element analysis for any irregularly shaped domain \(\Omega\). SSR splits a domain \(\Omega\) by transforming it into a triangular mesh with triangulation methods (e.g., Delaunay triangulation [27]). After triangulation, it defines a polynomial function on each triangle, such that the summation of these polynomial functions defined on different pieces closely approximates the desired spatial field \(f\). Specifically, let \(\zeta_{1},\ldots,\zeta_{K}\) denote the vertices of all the small triangles, which are called control points and can be adaptively selected by available data points. Define a piecewise linear or quadratic basis function \(\psi_{k}(x,y)\) called _Lagrangian finite element_ with \((x,y)\in\Omega\), associated with each control point \(\zeta_{k}\) such that \(\psi_{k}\) evaluates to \(1\) at \(\zeta_{k}\) and is equal to \(0\) at all other control points. Therefore, according to the _Lagrangian property of the basis_, we can approximate \(f(x,y)\) for any \((x,y)\in\Omega\) only using the values of \(f\) on the \(K\) control points, i.e., \(\mathbf{f}_{K}:=(f(\zeta_{1}),\ldots,f(\zeta_{K}))^{\mathsf{T}}\). That is, if we let \(\psi(x,y):=(\psi_{1}(x,y),\ldots,\psi_{K}(x,y))^{\mathsf{T}}\) denote the \(K\) predefined basis functions, each corresponding to a control point, then we have  
\[f(x,y)=\sum_{k=1}^{K}f(\zeta_{k})\psi_{k}(x,y)=\mathbf{f}_{K}^{\mathsf{T}}\psi (x,y). \tag{9}\]Since \(\psi_{1}(x,y),\ldots,\psi_{K}(x,y)\) are predefined and known a priori, the variational estimation of \(f\) in problem (8) boils down to the estimation of only \(K\) scalar values, i.e., \(\mathbf{f}_{K}=(f(\zeta_{1}),\ldots,f(\zeta_{K}))^{\mathsf{T}}\). In fact, it is shown in [PERSON] et al. [16] that with the piece-wise approximation given by (9), solving (8) is simply solving a set of linear equations for \(\hat{f}(\zeta_{1}),\ldots,\hat{f}(\zeta_{K})\).