# Distributed Consensus for Global Matrix Formation in the Principal Component Pursuit Scenario
## 3 Algorithm  
Because each agent measures only a part of \(M\), it is expected to use a distributed consensus. The question is whether it is required to solve the optimization problem in a distributed way while the consensus is reached in the solution, or if there is another, more straightforward way to achieve this still only using local information. The method studied and implemented here is to reach the first consensus based on local information to converge to the global matrix \(M\). Since it is allowed that agents share redundant measurements, a filter is proposed such that the agent does not change its own initial measurements; however, note that this is still a local rule since each agent knows which data it measured. In other words, the algorithm updates a subset \(\mathcal{X}_{i}\) of the full matrix indices corresponding to the unobserved entries; hence, only \(x_{i}^{k}(\mathcal{X}_{i})\) is updated. In the results section, an example of why this step is required is presented. The only global shared parameter is the number of agents \(l\). Then, using convex relaxation in the optimization problem, together with alternate direction optimization, each agent can exactly reproduce the original global \(L\) and \(S\) under some weak assumptions. To solve (3), each agent performs convex relaxation [14], which optimally actually recovers the original solution under some assumptions, of the following form:  
\[\min_{L,S}\quad\|L\|_{*}+\beta\|S\|_{1}\qquad\text{s.t.}\qquad L+S=M \tag{4}\]  
where \(\|\cdot\|_{*}\) is the nuclear norm, given by the sum of singular values, which is a proxy for the rank of the matrix, and \(\|\cdot\|_{1}\) is the one-norm of the matrix viewed as a vector, given by the sum of the magnitudes of each entry in the matrix, which is a proxy for the \(\|\cdot\|_{0}\) norm of a matrix. The hyperparameter \(\beta=\frac{1}{\sqrt{\max(n,m)}}\)[16]. Here, the strategy of the augmented Lagrange multiplier is implemented:  
\[\theta(L,S,Y)=\|L\|_{*}+\beta\|S\|_{1}+\langle Y,M-L-S\rangle+\frac{\mu}{2}\| M-L-S\|_{F}^{2} \tag{5}\]  
A generic Lagrange multiplier would solve this by updating the Lagrange multiplier with \(Y^{k+1}=Y^{k}+\mu(M-L^{k}-S^{k})\) after finding \(L^{k},S^{k}\) by minimizing \(\theta(L,S,Y)\). However, here, we avoid solving a sequence of convex programs by first minimizing \(\theta\) with respect to \(L\), with \(S\) fixed, minimizing \(\theta\) with respect to \(S\) with \(L\) fixed, and then updating the Lagrange multiplier matrix \(Y\). This method speeds up the computation since minimizing \(\theta\) with respect to \(L\) and \(S\) separately is straightforward. In fact [16], the argument that minimizes \(\theta\) with respect to \(S\) is \(S_{\beta\mu}(M-L+\mu^{-1}Y)\), where \(S_{\tau}[x]=sgn(x)max(|x|-\tau,0)\) is a shrinkage operator applied to each element of the matrix. Similarly, let \(D_{\tau}(X)\) denote the singular value thresholding operator given by \(D_{\tau}(X)=US_{\tau}(\Sigma)V^{*}\), where \(X=U\Sigma V^{*}\) is any singular value decomposition. Then, the argument that minimizes \(\theta\) with respect to \(L\) is \(D_{\mu}(M-S-\mu^{-1}Y)\). This strategy is summarized in Algorithm 1. Additionally, some restrictions on \(A\), \(L\), and \(S\) are required for the method to converge and to solve the optimization problem. **Theorem 1**. : _Consider a global matrix \(M\) that can be decomposed into low-rank \(L\) and sparse \(S\) matrices as \(M=L+S\) and a static undirected connected graph of agents \(x_{i}\) described by an adjacency matrix \(A\). Each agent measures part of the global matrix \(M\) in such a way that \(M\) is totally observed, with possibly overlapped entries. Algorithm 1 provides the steps such that at the end of the algorithm each agent knows \(L\) and \(S\) of the global \(M\)._  
We outline the proof. Proof. : Given a network of agents with interactions described by a doubly stochastic matrix \(A\), we assume the following properties for \(A\):  
1.