# Privacy-Preserving Federated Singular Value Decomposition
## 3 The FedPower Algorithm  
Following [PERSON] et al. [18], we assume there are \(n\) node devices, and each device \(i\) holds an independent dataset, an \(s_{i}\)-by-\(d\) matrix \(\mathbb{M}_{i}\). Each row represents a record item, while the columns of each matrix correspond to the same feature space. Moreover, \(\mathbb{M}\) denotes the composition of matrices \(\mathbb{M}_{i}\) such that \(\mathbb{M}^{T}=[\mathbb{M}_{1}^{T},\mathbb{M}_{2}^{T},\ldots,\mathbb{M}_{n}^ {T}]\in\mathbb{R}^{s\times d}\), with \(s=\sum_{i=1}^{n}s_{i}\). The solution proposed by [PERSON] et al. [18] is presented in Algorithm 1 with the following parameters.  
* \(T\): the number of local computations performed by each node device.
* \(\mathcal{I}_{T}^{p}\): the rounds where the node devices and the server communicate, i.e., \(\mathcal{I}_{T}^{p}=\{0,p,2p,\ldots,p\lfloor T/p\rfloor\}\).
* \((\varepsilon,\delta)\): the privacy budget.
* \((\sigma,\sigma^{\prime})\): the variance of noises added by the clients and the server, respectively:\[\sigma=\frac{|T/p|}{\varepsilon\cdot\min_{i}(s_{i})}\sqrt{2\log\Big{(}\frac{1.25 \left\lceil T/p\right\rfloor}{\delta}\Big{)}}\ \ \ \sigma^{\prime}=\frac{|T/p|\max_{i}(p_{i})}{\varepsilon\cdot\min_{i}(s_{i})} \sqrt{2\log\Big{(}\frac{1.25\left\lceil T/p\right\rfloor}{\delta}\Big{)}}\]  
```
0: Datasets \(\{\mathbb{M}_{i}\}_{i=1}^{n}\), target rank \(k\), iteration rank \(r\geq k\), number of iteration \(T\), synchronous set \(\mathcal{I}_{T}^{p}\), and the variance of noises \((\sigma,\sigma^{\prime})\)
0: Approximated eigenspace \(\overline{\mathbb{Z}}_{T}\)
1: initialise \(\mathbb{Z}_{0}^{(i)}=\mathbb{Z}_{0}\in\mathbb{R}^{d\times r}\sim\mathbb{N}(0,1 )^{d\times r}\)
2:for\(t=1\) to \(T\)do
3: each node device \(i\) computes \(\mathbb{Y}_{t}^{(i)}=\mathbb{M}_{i}^{r}\mathcal{I}_{t-1}^{(i)}\), where \(\mathbb{M}_{i}^{r}=\frac{1}{s_{i}}\mathbb{M}_{i}^{T}\mathbb{M}_{i}\)
4:if\(t\in\mathcal{I}_{T}^{p}\)then
5: each node device \(i\) computes \(\hat{\mathbb{Y}}_{t}^{(i)}=\mathbb{Y}_{t}^{(i)}\mathbb{D}_{t}^{(i)}\) (orthogonal transformation)
6: each node device \(i\) adds the Gaussian noise: \(\mathbb{Y}_{t}^{\prime(i)}=\hat{\mathbb{Y}}_{t}^{(i)}+\mathbb{N}^{(i)}\sim \mathbb{N}(0,||\mathcal{I}_{t-1}^{(i)}||_{\max}^{2}\sigma^{2})^{d\times r}\)
7: each node device \(i\) sends \(\mathbb{Y}_{t}^{\prime(i)}\) to the server
8: the server performs perturbed aggregation with an extra Gaussian noise: \(\mathbb{Y}_{t}=\sum_{t=1}^{n}\frac{s_{i}}{s}\mathbb{Y}_{t}^{(i)}+\mathbb{N} \sim\mathbb{N}(0,\max_{i}||\mathcal{I}_{t-1}^{(i)}\mathbb{D}_{t}^{(i)}||_{ \max}^{2}\sigma^{\prime 2})^{d\times r}\)
9: the server broadcasts \(\mathbb{Y}_{t}\) to all node devices
10: each node device \(i\) sets \(\mathbb{Y}_{t}^{(i)}=\mathbb{Y}_{t}\)
11:endif
12: each node device \(i\) performs orthogonalization: \(\mathbb{Z}_{t}^{(i)}=\mathsf{orth}(\mathbb{Y}_{t}^{(i)})\)
13:endfor
14:return approximated eigenspace
```  
**Algorithm 1** Full participation protocol of FedPower by [PERSON] et al. [18].  
In the proposed solution, each node device holds its raw data and processes the SVD locally, its eigenvectors are aggregated on the server by the orthogonal procrustes transformation (OPT) mechanism. The basic idea behind this is to find an orthogonal transformation matrix that maps one set onto another while preserving their relative characteristics. And, the aggregation result is sent back for further iterations. More details (e.g., the computation of \(\mathbb{D}_{t}^{(i)}\)) are given in [18].