## 3 Distributed Estimation of Laplacian Spectrum
### Distributed Estimation of Non-Zero Laplacian Eigenvalues
#### 3.1.3 Implementation of an ADMM-Based Algorithm  
Now, the update steps (12) and (13) are executed. Since the achieved \(\hat{y}_{t,t}\) have to agree with the constraint (\(\mathcal{C}\)), we solve the following optimization problem:  
\[\min_{\mathbf{y}_{i}\in\mathbb{R}^{h\times 1}} \frac{1}{2}\sum_{i=1}^{N}\|\mathbf{y}_{i}-\hat{\mathbf{y}}_{i}\|^{2}\] subject to \[\mathbf{y}_{j}=\mathbf{y}_{i}\;\;i=1,\dots,N;j\in\mathcal{N}_{i}\] ( \[\mathcal{C}\] )  
To solve this optimization problem, an Alternating Direction Method of Multipliers (ADMM) in [16; 27] can be employed by introducing an augmented parameters \(\mathbf{z}_{ij}\). Hence, the optimization can be rewritten as follows:  
\[\min_{\mathbf{y}_{i}} \frac{1}{2}\sum_{i=1}^{N}\|\mathbf{y}_{i}-\hat{\mathbf{y}}_{i}\|^ {2}\] subject to \[\mathbf{y}_{i}=\mathbf{z}_{ij}\;\;i=1,\dots,N;j\in\mathcal{N}_{i} \tag{20}\] \[\mathbf{z}_{ji}=\mathbf{z}_{ij}\]  
The Augmented Lagrange Function is defined as follows:  
\[\mathbf{H}_{3}(\mathbf{y},\mathbf{z},\boldsymbol{\tau})=\frac{1}{2}\sum_{i=1}^ {N}\|\mathbf{y}_{i}-\hat{\mathbf{y}}_{i}\|^{2}+\sum_{j\in\mathcal{N}_{i}} \boldsymbol{\tau}_{ij}^{T}(\mathbf{y}_{i}-\mathbf{z}_{ij})+\frac{\
u}{2}\sum_{ i=1}^{N}\|\mathbf{y}_{i}-\mathbf{z}_{ij}\|.\]  
The ADMM solution acts in three steps repetitively until the tolerance achieves:  
* Compute \(\mathbf{y}_{i}\): \[\mathbf{y}_{i}[p+1]=(1+\
u d_{i})^{-1}\{\hat{y}_{i}[k]+\
u\sum_{j\in\mathcal{N }_{i}}\mathbf{z}_{ij}[p]-\sum_{j\in\mathcal{N}_{i}}\mathbf{\tau}_{ij}[p]\}.\] (21)
* Compute \(\mathbf{z}_{ij}\): \[\mathbf{z}_{ij}[p+1]=\frac{\mathbf{y}_{i}[p+1]+\mathbf{y}_{j}[p+1]}{2}+\frac{ \boldsymbol{\tau}_{ij}[p]+\boldsymbol{\tau}_{ji}[p]}{2\
u}.\] (22)
* Lagrange multiplier update: \[\boldsymbol{\tau}_{ij}[p+1]=\boldsymbol{\tau}_{ij}[p]+\
u(\mathbf{y}_{i}[p+1] -\mathbf{z}_{ij}[p+1])\] (23)Herein, \(p\) is a iteration of the ADMM optimization process, then this output of this process is \(\mathbf{y}_{i}[k+1]=\mathbf{y}_{i}^{*}[p+1]\). The distributed algorithm is illustrated in Algorithm 1. The convergence analysis of the ALADIN method has been studied clearly for both non-convex and convex optimization problem in [25]. Lemma 3 in [25] has been proven that with the cost function \(f(\mathbf{\alpha})=\frac{1}{2}\sum_{t=1}^{h}\sum_{i\in V}\sum_{j\in\mathcal{N}_{i }}(\alpha_{t,j}-\alpha_{t,j})^{2}\) being twice continuously differentiable and letting \((\mathbf{\alpha}_{t}^{*},\mathbf{\lambda}^{*})\) for \(t=1,\ldots,h\) of problem (5) be a regular KKT point. On the other hand, the Hessian \(\mathbf{B}_{t}=\frac{\partial^{2}}{\partial\mathbf{\alpha}_{t}^{2}}(\frac{1}{2} \mathbf{\alpha}_{t}^{T}\mathbf{\Lambda}\mathbf{\alpha}_{t})+\rho\Sigma_{t}\succ 0\) obviously, since \(\Sigma_{t}\succeq 0\). There exists constants \(\chi_{1},\chi_{2}\) such that for every point \(\mathbf{\alpha}_{t},\lambda\) satisfying the condition convergence of the decoupled minimization problem (7) have unique locally minimizers \(\{\mathbf{y}_{t},t=1,\ldots,h\}\) that satisfy \(\|\mathbf{y}_{t}-\mathbf{\alpha}_{t}\|\leq\chi_{1}\|\mathbf{\alpha}_{t}-\mathbf{\alpha}_{ t}^{*}\|+\chi_{2}\|\mathbf{\lambda}-\mathbf{\lambda}^{*}\|\). Moreover, if \(\frac{1}{\mu}<\mathbf{0}(\|\mathbf{y}_{t}-\mathbf{\alpha}_{t}\|)\) when solving the QP (11), with the \(((\mathbf{\alpha}_{t}^{*},\mathbf{\lambda}^{*}))\) is a regular KKT point, then \(\chi_{1}\|\mathbf{\alpha}_{t}-\mathbf{\alpha}_{t}^{*}\|+\chi_{2}\|\mathbf{\lambda}-\mathbf{ \lambda}^{*}\|\leq\frac{(\chi_{1}+\chi_{2})\omega}{2}(\chi_{1}\|\mathbf{\alpha}_{t }-\mathbf{\alpha}_{t}^{*}\|+\chi_{2}\|\mathbf{\lambda}-\mathbf{\lambda}^{*}\|)^{2}\). This is sufficient to prove local quadratic convergence of the algorithm as \(\chi_{1},\chi_{2}\) are strictly positive constants. As a result, it is effectively applied to our proposed method since it is obviously an equality constrained non-convex optimization problem. One thing to remark here is that in our study, the penalty parameters \(\rho,\mu\) can be updated using the following rules:  
\[\rho[k+1] =\left\{