# Spatial Data Reconstruction via ADMM and Spatial Spline Regression +
## 1 Introduction  
The problem of reconstructing fine-grained spatial data from its coarse-grained aggregate observations of each subregions lies in the core of many real world applications. For example, the reconstruction of fine-grained spatial distribution of cell phone activities is of particular interest to telecommunication and information technology companies, where the recovered data can be used for device installation, capacity planning, the study of urban ecology [1; 2; 3], population density estimation [4; 5; 6], and human mobility prediction [7; 8; 9; 10; 11]. However, the companies may only have access to the aggregate mobile traffic volumes on each base station, as either privacy issues or additional technical overhead is involved to get fine-grained spatial data of users. Similarly, it is also highly valuable if we can infer the spatial distribution of population (e.g., the population vote for a certain party) densities based on the total population recorded at polling stations that sparsely scatteredat different subregions. Internet media providers or retailers, such as Google, Tencent, Amazon, Facebook, etc., may want to recover a fine-grained geographical distribution of their users based on the aggregated user counts observed at different points of presence (PoPs) or data centers. Note that, in all the above-mentioned cases, it is impossible or not allowed to track the position of each individual due to either privacy concerns or technical overhead. Therefore, reconstructing the spatial data from coarse aggregation will be highly useful in such cases. In this paper, we study such spatial sparse recovery problem, that is, to infer the fine-grained distribution of certain spatial data in a region given the aggregate observations recorded for each of its subregions. However, it is an extremely challenging problem and has seldom been studied. A straightforward idea is assuming the density is uniformly distributed within each subregion. Based on the based on the obtained aggregate observation, we can calculate a patched piece-wise constant estimation for each subregion. However, the densities estimated by this method will jump between neighboring subregions and disregard the local continuity or similarity of the studied spatial distribution across subregion boundaries. In addition, the piece-wise constant spatial field given by this approach provides little value for applications such as hot spot discovery. Many spatial data presents local continuity, e.g., Internet activity or cell phone activity. This is because the data often highly depend on underlying factors which are usually smoothly changing, like area functionality, urban geographical features, population density and so on. To exploit the smoothness, we may utilize spatial smoothing techniques such as Thin Plate Splines [12], Soap film smoothing [13], Spline smoothing [14], Bivariate Spline Regression [15], or Spatial Spline Regression [16] developed in statistics to smoothen the patched estimation. However, nearly all existing spatial smoothing techniques [12; 13; 14; 15; 16] are designed to recover a spatial field of densities according to sampled observations, e.g., reconstruct a spatial field of temperatures based on the temperature records at some sample points. In contrast, our problem needs to recovery a spatial field based on coarse-grained aggregate observations. Therefore, existing spatial smoothing techniques are not directly applicable to our new problem. Without modification, these smoothing techniques will violate the necessary constraint that the estimated spatial data in each subregion must sum up to its corresponding aggregate observation in the first place, leading to systematic errors. To overcome the difficulties mentioned above, in this paper, we propose a new technique named Constrained Spatial Smoothing (CSS) for the problem of spatial data reconstruction. Specifically, given a region, we aim to reconstruct a spatial field of densities over that region based on observed aggregate values in patched subregions.