# Spatial Data Reconstruction via ADMM and Spatial Spline Regression +
## 2 Problem Formulation  
In this section, we formally introduce the problem of spatial field reconstruction from coarse aggregations observed at sparse scattered points in that field. Our problem can be formulated as a new type of sparse recovery problems. To ease the presentation, we may use cell phone activity recovery as an example. Let \(\Omega\subset\mathbb{R}^{2}\) denote an irregularly bounded domain, which is the entire region of interest in our problem. Usually, it excludes the uninhabited areas such as hills, ocean coasts, rivers, and so on. Suppose \(f(\mathbf{p})\) is a real-valued function that represents certain spatial densities field (e.g., cell phone activities), where \(\mathbf{p}=(x,y)\in\Omega\) denotes different geographical positions in \(\Omega\). Let \(B=\{B_{1},\ldots,B_{m}\}\) denote \(m\) observation points (e.g., base stations) that scattered in \(\Omega\). Each point \(B_{i}\) is located in a position \(\mathbf{p}_{B_{i}}\in\Omega\) and in charge of a subregion \(\Omega_{B_{i}}\). In our problem, we are given the _aggregated volume_\(z_{i}\) in \(\Omega_{B_{i}}\) that \(B_{i}\) is in charge of. Our goal is to reconstruct the spatial field \(f(\mathbf{p})\) based on the observed aggregated volumes \(z_{i}\). To give an instance, consider the problem of recover cell phone activity distribution. In this case, each user will connect to a base station (cell tower) that is closest to his/her cell phone. Therefore, we can observe the aggregated volume for each base station  
\[z_{i}=\int_{\Omega_{B_{i}}}f(\mathbf{p})\;\mathrm{d}\mathbf{p},\quad i=1, \ldots,m,\]  
where \(\Omega_{B_{i}}\) denotes the subregion that \(B_{i}\) is in charge of, and is given by  
\[\Omega_{B_{i}}=\{\mathbf{p}\in\Omega:\|\mathbf{p}-\mathbf{p}_{B_{i}}\|<\| \mathbf{p}-\mathbf{p}_{B_{i}}\|,\forall B_{i^{\prime}}\in B,\;i^{\prime}\
eq i\}.\]  
Given the aggregated activity volumes \(z_{1},\ldots,z_{m}\) recorded on \(m\) base stations, our goal is to reconstruct the entire cell phone activity densities distribution \(f\), which is a spatial field in the domain \(\Omega\). We may call \(z_{1},\ldots,z_{m}\) base station volumes in this case. However, reconstructing a continuous spatial field is almost computationally infeasible as a personal computer can not handle the continuous nature of \(\Omega_{B_{i}}\). In reality, we only need to recover \(f\) to a certain granularity required by the operator (e.g., \(235\;\mathrm{m}\times 235\;\mathrm{m}\) squares in the dataset provided by Telecom Italia Mobile). To fix notations, suppose \(\Omega\) is discretized into \(n\) small grid squares \(\mathbf{p}_{1},\ldots,\mathbf{p}_{n}\), where \(\mathbf{p}_{j}=(x_{j},y_{j})\in\Omega\), \(j=1,\ldots,n\) are the center positions of each square \(j\) in \(\Omega\). We can assume the area of each square is \(\Delta=1\) without loss of generality. In addition, the number of aggregate observations is much smaller than the total number of squares to be reconstructed, therefore we have \(m\ll n\). After domain discretization, we can get the aggregate volume on each base station \(B_{i}\) by  
\[z_{i}=\sum_{\mathbf{p}_{j}\in\Omega_{B_{i}}}f(\mathbf{p}_{j})\cdot\Delta,\quad i =1,\ldots,m, \tag{1}\]  
where the subregion that \(B_{i}\) represents is given by  
\[\Omega_{B_{i}}=\{\mathbf{p}_{j}:1\leq j\leq n,\|\mathbf{p}_{j}-\mathbf{p}_{B_ {i}}\|<\|\mathbf{p}_{j}-\mathbf{p}_{B_{i^{\prime}}}\|,\;\forall i^{\prime}\
eq i\}. \tag{2}\]  
Therefore, our goal is to reconstruct the underlying spatial field \(f\), and especially the activity densities  
\[\mathbf{f}:=\left(f(\mathbf{p}_{1}),\ldots,f(\mathbf{p}_{n})\right)^{\mathsf{ T}}\]  
in all \(n\) grid squares if the desired granularity is on a per-square level, with only access to the aggregated observations \(z_{i}\) in Label (1).