# Distributed Consensus for Global Matrix Formation in the Principal Component Pursuit Scenario
## 3 Algorithm
\(\lambda_{1}(A)=1\) and \(|\lambda_{i}|<1\) for all \(i>1\), indicating \(A\) has a dominant eigenvalue of \(1\). 2. \(A\mathbf{1}=\mathbf{1}\) and \(\mathbf{1}^{T}A=\mathbf{1}^{T}\), showing \(A\) is doubly stochastic and the vector of ones, \(\mathbf{1}\), is both a right and left eigenvector corresponding to the eigenvalue \(1\). The consensus update rule for agent \(i\) is: \[x_{i}^{k+1}(\mathcal{X}_{i})=\sum_{j\in\mathcal{N}_{i}}A_{ij}x_{j}^{k}( \mathcal{X}_{i})\] (6)  
To prove convergence, we utilize the eigenvalue decomposition of \(A\), \(A=V\Lambda V^{-1}\), and leverage the geometric decay of components associated with eigenvalues \(|\lambda_{i}|<1\). As \(k\rightarrow\infty\), all components except those aligned with \(\mathbf{1}\) diminish, leading to convergence towards an average state across the network. The optimization problem is formulated as:  
\[\min_{L,S}\|L\|_{*}+\beta\|S\|_{1}\quad\text{s.t.}\quad L+S=M \tag{7}\]  
and by introducing the augmented Lagrangian, the problem is rephrased as:\[\theta(L,S,Y)=\|L\|_{*}+\beta\|S\|_{1}+\langle Y,M-L-S\rangle+\frac{\mu}{2}\|M-L-S \|_{F}^{2} \tag{8}\]  
where \(\|\cdot\|_{*}\) denotes the nuclear norm (sum of singular values), \(\|\cdot\|_{1}\) denotes the \(l_{1}\) norm (sum of absolute values of the matrix entries), \(\langle\cdot,\cdot\rangle\) represents the inner product, and \(\|\cdot\|_{F}^{2}\) is the Frobenius norm squared. Update \(L\) with \(S\) and \(Y\) fixed. Given \(S\) and \(Y\), the update for \(L\) is obtained by minimizing \(\theta(L,S,Y)\) with respect to \(L\). This step involves solving:  
\[L^{k+1}=\arg\min_{L}\Bigl{(}\|L\|_{*}+\frac{\mu}{2}\|M-L-S^{k}+\mu^{-1}Y^{k}\| _{F}^{2}\Bigr{)} \tag{9}\]  
This problem is a proximal operation that can be efficiently solved using the singular value thresholding (SVT) operator \(D_{\tau}\), defined as:  
\[D_{\tau}(X)=U\cdot S_{\tau}(\Sigma)\cdot V^{*} \tag{10}\]  
where \(X=U\Sigma V^{*}\) is the singular value decomposition of \(X\), and \(S_{\tau}(\Sigma)\) applies a shrinkage operation to the singular values \(\Sigma\), reducing each singular value \(\sigma_{i}\) by \(\tau\), but not to below zero. In this context, \(\tau=\mu^{-1}\). Update \(S\) with \(L\) and \(Y\) fixed. After updating \(L\), \(S\) is updated by minimizing \(\theta(L,S,Y)\) with \(L^{k+1}\) and \(Y^{k}\) fixed, leading to:  
\[S^{k+1}=\arg\min_{S}\Bigl{(}\beta\|S\|_{1}+\frac{\mu}{2}\|M-L^{k+1}-S+\mu^{-1}Y ^{k}\|_{F}^{2}\Bigr{)} \tag{11}\]  
This optimization step is akin to a soft thresholding operation on each element of the matrix \(M-L^{k+1}+\mu^{-1}Y^{k}\) and can be efficiently solved using the shrinkage operator \(S_{\beta\mu}\), which for a given matrix \(X\) and threshold \(\tau\), requires:  
\[S_{\tau}[X]_{ij}=\operatorname{sign}(X_{ij})\max(|X_{ij}|-\tau,0) \tag{12}\]  
Update \(Y\). Finally, the Lagrange multiplier \(Y\) is updated to account for the discrepancy between \(M\) and the current approximation \(L^{k+1}+S^{k+1}\):  
\[Y^{k+1}=Y^{k}+\mu(M-L^{k+1}-S^{k+1}) \tag{13}\]  
Convergence. The iterative updates for \(L\), \(S\), and \(Y\) guarantee convergence to the global optimum under convex conditions. The SVT and shrinkage operators ensure that each step moves towards minimizing the objective function while adhering to the constraint \(L+S=M\). Updating \(Y\) adjusts for the equality constraint violation, ensuring that as \(k\to\infty\), \(L^{k}+S^{k}\to M\), thus solving the original decomposition problem. Finally, we need to prove that convex relaxation solves the original non-convex problem. It could be that there is not enough information to perfectly disentangle the low-rank and sparse components. To prevent this from happening, the assumption that the low-rank component \(L\) is not sparse is employed; this is called the incoherence condition [29]. Another identifiability issue arises if the sparse matrix is low-rank. Then, the following assumptions are required [16].