# Spatial Data Reconstruction via ADMM and Spatial Spline Regression +
## 2 Problem Formulation
The problem defined above is broadly applicable to characterize a variety of applications other than the recovery of cell phone activity density distribution, e.g., inferring a fine-grained geographical user distribution for a certain app or website based on aggregated user counts collected at sparsely distributed Presence of Points (PoPs) or data centers, and recovering the voter distribution for a certain party based on aggregate voting statistics at different polling stations. The nonessential difference is that the definition of subregion \(\Omega_{B_{i}}\), from which volume \(z_{i}\) is aggregated, is different for each specific application. Constrained Spatial Smoothing Problem  
Denote \(\mathbf{z}=\left(z_{1},\ldots,z_{m}\right)^{\mathsf{T}}\). Since all \(\Omega_{B_{i}}\) are predetermined, e.g., from Label (2) for the problem of cell phone activity distribution recovery, and \(z_{i}\) are known, reconstructing spatial field \(\mathbf{f}\) from (1) is essentially solving a linear system of equations for \(\mathbf{f}\), i.e.,  
\[\mathbf{z}=\mathbf{A}\mathbf{f},\]  
where the matrix \(\mathbf{A}\in\mathbb{R}^{m\times n}\) is given by  
\[A_{ij}=\left\{ \begin{array}{ll}1,&\quad\text{if }\mathbf{p}_{j}\in\Omega_{B_{i }},\\ 0,&\quad\text{otherwise}.\end{array} \right. \tag{3}\]  
Since \(m\ll n\), i.e., the number of equations is far smaller than the number of the unknowns, reconstructing \(f(\mathbf{p}_{1}),\ldots,f(\mathbf{p}_{n})\) from \(z_{1},\ldots,z_{m}\) is essentially a sparse recovery problem. Directly solving the linear system of Equation (1) is infeasible, as it is an underdetermined system which has an infinite number of solutions. However, the spatial property of \(f\) can be utilized as constraints to make the sparse recovery problem feasible and has a unique solution. We observe that spatial data usually exhibit local continuity or correlation within domain \(\Omega\). For example, in the problem of cell phone activity density recovery, the activity density of a certain location highly depends on the population and activity at that place, e.g., the downtown has more population and cell phone activity than suburban residential areas. In addition, the underlying area functionality and the spatial distributions of human activity density are often slowly changing over the domain \(\Omega\) rather than suddenly jumping between different subregions. Therefore, we can formulate our constrained spatial sparse recovery problem as the following:  
\[\underset{f}{\text{minimize}} \int_{\Omega}(\
abla^{2}f)^{2}\,\mathrm{d}\mathbf{p},\] (4) subject to \[\mathbf{z}=\mathbf{A}\mathbf{f},\] \[\mathbf{f}\geq 0,\]  
by taking into account the non-negative property and the local spatial continuity (smoothness) of \(f\). \(\
abla^{2}f=\frac{\partial^{2}f}{\partial x^{2}}+\frac{\partial^{2}f}{ \partial y^{2}}\) is the Laplacian of \(f\), and is utilized to encourage local similarity and penalize the roughness of the spatial field \(f\). It is worth noting that once \(f\) is reconstructed, we have not only recovered the densities \(\mathbf{f}\) at the square centers \(\mathbf{p}_{1},\ldots,\mathbf{p}_{n}\), but can also recover the density \(f(\mathbf{p})\) of any point \(\mathbf{p}\in\Omega\), e.g., between the centers of two neighboring grid squares, although such a fine-grained recovery may not be needed in every application. To further improve the recovery performance, we can utilize additional external demographic or social features at each location. In the problem of cell phone activity density reconstruction, cell phone activities are often correlated with the underlying population density and social functionalities (e.g., the percentage of green area, the number of schools, the number of businesses/restaurants, the number of sport facilities, and the number of bus stops, etc.) of the considered regions. Specifically, suppose \(\mathbf{w}_{j}=(w_{j1},\ldots,w_{jq})^{\mathsf{T}}\) represents the feature vector consisting of \(q\) external feature values of square \(j\).