# Spatial Data Reconstruction via ADMM and Spatial Spline Regression +
## 4 An ADMM Algorithm for Constrained Spatial Smoothing  
Our spatial sparse recovery problem (4) is different from (8) from two aspects: the additional constraints and the loss function. As a consequence, we can not directly apply the previous SSR method to solve it. A new approach is needed to handle our new loss function with constraints. In this section, we propose to utilize the Alternating Direction Method of Multipliers (ADMM) [28], to decompose our constrained optimization problem into two sub-problems that can be solved effectively by SSR and Quadratic Programming (QP), respectively. Algorithm 1 presents the proposed ADMM algorithm to learn our model parameters. ```
Input: The \(m\) observed volume of base stations \(\mathbf{z}=(z_{1},...,z_{m})^{\mathsf{T}}\), smoothing parameter \(\lambda\),  penalty parameter \(\beta\), initialize \(\mathbf{\alpha}=\mathbf{\alpha}^{0}\), \(\mathbf{f}=\mathbf{f}^{0}\). Output: Spatial field and parameters \(\hat{f}\), \(\hat{\mathbf{\beta}}\). Estimation values on \(n\) locations \(\hat{f}=\big{(}\hat{f}(\mathbf{p}_{1}),\ldots,\hat{f}(\mathbf{p}_{n})\big{)}\). 1:for\(iter=1,\ldots,\text{maxIter}\)do
2: Update \(\mathbf{f}\) by solving (18) using Quadratic Programming. 3: Update \(\mathbf{g}\) by solving (19) using Spatial Spline Regression. 4: Update \(\mathbf{\alpha}\) according to (17). 5:endfor
```  
**Algorithm 1**Constrained Spatial Smoothing by ADMM  
First, we introduce the following indicator function \(\mathds{1}_{\mathbf{\mathrm{f}}}\),  
\[\mathds{1}_{\mathbf{\mathrm{f}}}=\left\{ \begin{array}{ll}0,&\quad\text{if $\mathbf{ \mathrm{f}}\geq 0$ and $\mathbf{\mathrm{z}}=\mathbf{Af}$,}\\ \infty,&\quad\text{otherwise.}\end{array} \right. \tag{10}\]  
With the indicator function, the original problem (4) is equivalent to  
\[\underset{f}{\text{minimize}}\quad\lambda\int_{\Omega}(\
abla^{2}f)^{2}\, \mathrm{d}\mathbf{\mathrm{p}}+\mathds{1}_{\mathbf{\mathrm{f}}}, \tag{11}\]  
where \(\lambda\) is a hyper parameter that controls the smoothness of \(f\). Second, we introduce an auxiliary variable \(\mathbf{g}\) that is defined as  
\[\mathbf{g}:=\left(g(\mathbf{p}_{1}),\ldots,g(\mathbf{p}_{n})\right)^{\mathsf{T}}. \tag{12}\]  
This variable is utilized to split the convex optimization problem into two sub-convex problems. With \(\mathbf{g}\), we can formulate the problem as the standard ADMM format,  
\[\underset{f}{\text{minimize}} \lambda\int_{\Omega}(\
abla^{2}f)^{2}\,\mathrm{d}\mathbf{p}+ \mathds{1}_{\mathbf{g}},\] (13) subject to \[\mathbf{f}=\mathbf{g}.\]  
The _augmented Lagrangian_ for (13) is  
\[ \begin{split}\text{minimize}\quad\mathcal{L}_{\rho}(\mathbf{f},\mathbf{g},\boldsymbol{\alpha})=&\lambda\int_{\Omega}(\
abla^{ 2}f)^{2}\,\mathrm{d}\mathbf{p}+\mathds{1}_{\mathbf{g}}\\ &+\boldsymbol{\alpha}^{\mathsf{T}}(\mathbf{g}-\mathbf{f})+\frac{ \rho}{2}\|\mathbf{g}-\mathbf{f}\|_{2}^{2},\end{split}  \tag{14}\]  
where \(\boldsymbol{\alpha}=(\alpha_{1},...,\alpha_{n})^{\mathsf{T}}\) is the dual variable, and \(\rho>0\) is the penalty parameter in ADMM. Then, the ADMM consists of the following iterations:  
\[\mathbf{g}^{k+1} :=\underset{\mathbf{g}}{\text{argmin}}\ \mathcal{L}_{\rho}( \mathbf{f}^{k},\mathbf{g},\boldsymbol{\alpha}^{k}), \tag{15}\] \[\mathbf{f}^{k+1} :=\underset{\mathbf{f}}{\text{argmin}}\ \mathcal{L}_{\rho}( \mathbf{f},\mathbf{g}^{k+1},\boldsymbol{\alpha}^{k}),\] (16) \[\boldsymbol{\alpha}^{k+1} :=\boldsymbol{\alpha}^{k}+\rho(\mathbf{f}-\mathbf{g}). \tag{17}\]  
For the \(\mathbf{g}\)-update step in each iteration, Label (16) is equivalent to  
\[ \begin{split}\underset{\mathbf{g}}{\text{minimize}}& \frac{\rho}{2}\|\mathbf{g}\|_{2}^{2}+(\boldsymbol{\alpha}^{\mathsf{T}}- \rho\mathbf{f}^{\mathsf{T}})\mathbf{g},\\ \text{subject to}&\mathbf{g}\geq 0,\\ &\mathbf{z}=\mathbf{Ag}.\end{split}  \tag{18}\]  
We can solve this convex problem efficiently by Quadratic Programming (QP).