# Laplace Input and Output Perturbation for Differentially Private Principal Components Analysis

Authors: Yahong Xu; Geng Yang; Shuangjie Bai
Journal: Security and Communication Networks
 (2019)

---

## Abstract

With the widespread application of big data, privacy-preserving data analysis has become a topic of increasing significance. The current research studies mainly focus on privacy-preserving classification and regression. However, principal component analysis (PCA) is also an effective data analysis method which can be used to reduce the data dimensionality, commonly used in data processing, machine learning, and data mining. In order to implement approximate PCA while preserving data privacy, we apply the Laplace mechanism to propose two differential privacy principal component analysis algorithms: Laplace input perturbation (LIP) and Laplace output perturbation (LOP). We evaluate the performance of LIP and LOP in terms of noise magnitude and approximation error theoretically and experimentally. In addition, we explore the variation of performance of the two algorithms with different parameters such as number of samples, target dimension, and privacy parameter. Theoretical and experimental results show that algorithm LIP adds less noise and has lower approximation error than LOP. To verify the effectiveness of algorithm LIP, we compare our LIP with other algorithms. The experimental results show that algorithm LIP can provide strong privacy guarantee and good data utility.


---

## Body

## 1. Introduction

In many modern information systems, the amount of data is very large. Massive data increase the difficulty of data analysis and processing. Principal component analysis (PCA) is a standard data analysis method, which can be used to reduce the data dimensionality. More specifically, it projects the original high-dimensional data to the space of principal components composed by the eigenvectors of the covariance matrix of the data to get low-dimensional data, which can represent most of information of the original data. PCA simplifies the data, making data easier to use while saving on the computational complexity of the algorithm. For example, face recognition is much faster when first projecting the data into lower dimension.Financial and medical data often deal with private or sensitive information. If machine learning tasks or data mining algorithms work directly on the original data, the outputs of these algorithms will leak private information, which may pose potential threats to individuals. Therefore, privacy preservation has become an urgent problem that needs to be solved. Differential privacy (DP) [1] is an effective and provable privacy protection model. It attends to hide private information while ensuring basic statistics of the original data. The notion of differential privacy has two types: ε,0-DP and ε,δ-DP [2]. ε,0-DP is usually called pure differential privacy, while ε,δ-DP with δ>0 is called approximate differential privacy. ε,δ-DP is a weaker version of ε,0-DP as the former provides freedom to violate strict differential privacy for some low probability events.There are several approaches to making approximate PCA while satisfying differential privacy. Input perturbation adds noise to the data before computing the PCA, while output perturbation adds noise to the output of PCA. We can add Laplace noise to implement input perturbation and output perturbation. Both approaches can effectively simplify data and preserve the data privacy; however, there are few studies on their performance. At the same privacy protection level, better performance (less noise and lower error) mean better data utility. In this paper, we propose two differential privacy principal component analysis algorithms and evaluate their performance.Our main contributions are as follows:(1)
We apply Laplace mechanism to propose two differential privacy principle component analysis algorithms, Laplace input perturbation (LIP) and Laplace output perturbation (LOP), and give proof for itsε,0-DP.(2)
We offer two criteria, i.e., noise magnitude and approximation error, to evaluate the performance of two algorithms. Less noise and lower approximation error result in better performance. Through theoretical verification, we ensure that LIP has better performance than LOP.(3)
We conduct the experiments to verify the performance of LIP and LOP in terms of noise magnitude and approximation error on five real datasets. We further explore the variation of performance of the two algorithms with different parameters such as number of samples, target dimension, and privacy parameter. The experimental results show that at the different parameters, algorithm LIP always adds less noise and has lower approximation error than LOP. Compared with other algorithms, LIP can also provide good data utility.The rest of the paper is organized as follows. Section3 introduces principle component analysis, differential privacy, and Laplace mechanism. Section 4 first describes the two differential privacy principle component analysis algorithms and then analyzes the privacy and utility. Section 5 shows the performance of two algorithms on five real datasets. Section 6 concludes the paper.


## 2. Related Work

Since Dwork proposed the concept of differential privacy, data preservation in the field of data mining and machine learning has received considerable attention. The current research studies mainly focus on privacy-preserving classification, regression, and frequent itemset mining.Classification technology plays an important role in data prediction, which aims to build models that can describe and distinguish data. The typical privacy protection classification algorithms are SuLQ-Based ID3, DiffP-C4.5, and DiffGen. The basic idea of SuLQ-Based ID3 [3] is to add noise to true count value before calculating the information gain of the attributes and finally generate the corresponding decision tree. Although this method can satisfy differential privacy, the added noise is too large. To overcome the disadvantages of SuLQ-Based ID3, DiffP-C4.5 [4] first selects and splits attributes by exponential mechanism. However, this method can only support few analyses and queries. The classification accuracy of DiffGen [5] is higher than SuLQ-Based ID3 and DiffP-C4.5 from the perspective of theory and practical application; unfortunately, when the dimension of the classification attribute is very large, the selection method based on the exponential mechanism is inefficient and may exhaust the privacy budget. Frequent itemset mining is an effective data analysis method; it aims to discover itemsets that frequently appear in the dataset. Bhaskar et al. proposed algorithm truncated frequency (TF) [4]; it reduces the number of candidate itemsets depending on their own frequency. However, when the number of target itemsets is large, this method will fail. Considering this weakness, Li et al. proposed algorithm PrivBasis [5] according to the idea of θ-base (θ is a threshold) to generate candidate itemsets. However, generating θ-base is not very easy. Inspired by Zeng and Li, Wang et al. proposed algorithm PrivSuper [6] that randomly truncates transactions in a dataset, which will cause large truncation error. Regression is a common data analysis method in machine learning; it is a quantitative relationship that determines the interdependence of two or more attributes. The typical regression algorithms based on differential privacy are logistic regression and linear regression. In algorithms LPLog [7] and ObjectivePerb [8], the noise magnitude is decided by the sensitivity of the weight vector and the cost of computing sensitivity is high. Considering the disadvantages of the two algorithms, algorithm functional mechanism (FM) [9] controls the noise magnitude by the sensitivity of function itself instead of the weight vector.However, there are few studies on differential privacy principal component analysis. Blum et al. [10] first proposed the early input perturbation framework SULQ, but not for data publishing. Chaudhuri et al. [11] proposed a privacy-preserving PCA algorithm MOD-SULQ based on the exponential mechanism, which can be used for data publishing. Kapralov and Talwar [12] argued that the algorithm (Chaudhuri et al.) lacks convergence time guarantee, and they also designed a complex algorithm using the exponential mechanism, but it is complicated to implement for high-dimensional data. Dwork et al. [13] provided the algorithms for ε,δ-DP, adding Gaussian noise to the original sample covariance matrix. Inspired by Dwork, Imtiaz et al [14, 15] and Jiang et al. [2] designed their algorithms for ε,0-DP. Both of them added Wishart noise with parameters chosen to have a better utility bound.


## 3. Preliminaries

Given a datasetX=x1,x2,…,xnT where xi∈Rd is the i-th record. The matrix X∈Rn×d contains information about d attributes of n individuals (generally d<n). Following previous work on privacy-preserving PCA, we also assume xi2≤1, ⋅2 denotes the l2 norm. For a vector a∈Rd, a2=∑i=1dai2.The covariance matrix of the original data is(1)A=1nXTX=1n∑i=1nxiTxi,where A is a d×d symmetric matrix.The principal components are obtained by computing the eigenvalues and corresponding eigenvectors of the covariance matrixA:(2)Avi=λivi,where λi1≤i≤d is the eigenvalue, denoting the proportion of information that corresponding component includes. Larger λi means the component is more important. We assume λi are ordered decreasingly, i.e., λ1≥λ2≥⋯≥λd≥0. vi is the corresponding eigenvector.In order to reduce the data to low dimension, a target dimensionk is needed. We want to select first k eigenvectors which correspond to the top k eigenvalues. Given a threshold α0≤α≤1, α denotes accumulative contribution rate of the principal components [16]. Target dimension k can be decided by(3)∑i=1kλi∑i=1dλi≥α.SupposeVk=v1,v2,…,vk is the first k eigenvectors of A, vi and vj are orthonormal. We project the original data X to the Vk to get low-dimensional data:(4)Y=XVk,where Y∈Rn×k; we can also get the rank-k approximation [17] of X:(5)Z=XVkVkT.Our algorithms want to keep the statistics ofX as much as possible, and the approximation error between Z and X can be measured by(6)MSE=Z−XF.Lower MSE provides better data utility.⋅F denotes the Frobenius norm. For a matrix C∈Rm×n, CF=∑i=1m∑j=1ncij2.Now, we introduce the definition of differential privacy.Definition 1 (differential privacy) [18].
A randomized mechanismM is differentially private if for any neighbouring datasets D and D′ (with at most one different record) and for all output OO⊆RangeM,(7)PrMD∈O≤eε×PrMD′∈O,where ε is the privacy budget controlling the strength of privacy guarantee; lower ε ensures more privacy.
Sensitivity is the key parameter that determines how much noise is required.Definition 2 (sensitivity) [19].
For a functionf:D⟶Rd and any neighbouring datasets D and D′, the sensitivity of f is defined as(8)Δf=maxD,D′fD−fD′1.
The sensitivity describes the largest change due to an data entry replacement. SensitivityΔf is only related to the function f.
The Laplace mechanism adds independent noise to the data; we useLapb to represent the noise sampled from Laplace distribution with a scaling of b.Definition 3 (Laplace mechanism) [19].
Given a datasetD, for a function f:D⟶Rd, with sensitivity Δf, the mechanism M provides ε-DP satisfying(9)MD=fD+LapΔfε.
Here,Lap⋅ is a random variable. Its probability density function is(10)px=12be−x/b.


## 4. Proposed Algorithms and Analysis

In this section, we describe two differential privacy principal component analysis algorithms: LIP and LOP. Through theoretical analysis, we prove the two algorithms satisfyε,0-DP. Meanwhile, we investigate the utility of proposed algorithms.


### 4.1. Algorithm Description

In algorithm LIP, we use Laplace distribution to generate symmetric noise matrix and then add it to the data covariance matrix. After computing the eigenvalues and corresponding eigenvectors of the noised covariance matrix, we select firstk eigenvectors to make up principal components space. In the end, we obtain low-dimensional data by projecting the original high-dimensional data to the principal components space. Algorithm LIP is described in Algorithm 1.Algorithm 1:Laplace input perturbation (LIP).
Input: matrix X∈Rn×d, number of samples n, attributes d, privacy parameter ε;
Output: Z1: the rank-k approximation matrix
(1)
Compute covariance matrixA=1/nXTX;
(2)
Noise matrixE1∈Rd×d is a symmetric matrix where the upper triangle is d2+d/2 i.i.d. sample from Lap2d/nε, and each lower triangle entry is copied from the opposite position;
(3)
Add noiseA′=A+E1;
(4)
Compute eigenvalues and corresponding eigenvectors of the noised covariance matrixA′vi′=λi′vi′;
(5)
Given a thresholdα, select top k eigenvectors Vk′ of A′, low-dimensional data Y1=XVk′;
(6)
The rank-k approximation matrix Z1=Y1Vk′T;V
k
′ are the first k eigenvectors of the noised covariance matrix A′, which is close to the true first k eigenvectors Vk of covariance matrix A [13].Besides adding noise prior to computing PCA, we also add noise to the output of PCA. According to differential privacy parallel composition [20], the whole dataset is private as long as each record is private; a simple idea is adding noise to each record to protect private information. However, if this privacy preservation method is directly applied to big data, the introduced noise will significantly increase so that data utility dramatically drops. In order to reduce noise without decreasing the level of privacy preservation, we can add noise to fewer but most important parts of data. Algorithm LOP projects the original high-dimensional data to the principal component space to get low-dimensional data. The low-dimensional data are important data, so we add noise to them to protect data privacy. Algorithm LOP is described in Algorithm 2.Algorithm 2:Laplace output perturbation (LOP).
Input: matrix X∈Rn×d, number of samples n, attributes d, privacy parameter ε;
Output: Z2: the rank-k approximation matrix
(1)
Compute covariance matrixA=1/nXTX;
(2)
Compute eigenvalues and corresponding eigenvectorsAvi=λivi;
(3)
Given a thresholdα, select top k eigenvectors Vk of A, low-dimensional data Y2=XVk;
(4)
Noise matrixE2 is a n×k matrix where the whole elements are i.i.d. samples from Lap2d/ε
(5)
Add noiseY2′=Y2+E2;
(6)
The rank-k approximation matrix Z2=Y2′VkT;


### 4.2. Privacy Analysis

Before proving that LIP and LOP satisfyε,0-DP, we should analyze the sensitivities of these two algorithms. Suppose there are two neighbouring datasets X=x1,…,xi,…,xnT∈Rn×d and X′=x1,…,xi′,…,xnT∈Rn×d where xi≠xi′, we assume the normalized data vector xi2≤1.Lemma 1.
In algorithm LIP, for all the input data, denotefX=1/nXTX; then, the sensitivity of the function fX equals 2d/n.Proof.
Suppose thatA1 and A2 are the covariance matrices of X and X′, respectively.(11)
A
1
=
1
n
X
T
X
,
A
2
=
1
n
X
′
T
X
′
.According to Definition 2, the sensitivity of functionfX is maxA1−A21. Then, we have(12)A1−A21=1nXTX−1nX′TX′1=1nxiTxi−xi′Txi′1,where ⋅1 denotes the l1 norm, for a matrix C∈Rm×n, C1=maxj∑i=1mcij1≤j≤n. For the normalized xi2≤1, we have(13)A1−A21=1nxiTxi−xi′Txi′1≤1nxiTxi1+xi′Txi′1≤2dn.Theorem 1.
Algorithm LIP satisfiesε,0-DP.Proof.
ForA′ derived from algorithm LIP on X and X′, we obtain A′=A1+N1 and A′=A2+N2 where N1 and N2 are the corresponding noise matrices.(14)
f
A
′
∣
X
f
A
′
∣
X
′
=
p
N
1
p
N
2
=
e
n
ε
/
2
d
N
2
1
−
N
1
1
,where pN1 and pN2 are the density functions of the output functions at neighbouring datasets X and X′. According to Lemma 1, we have(15)N21−N11≤N2−N11=A1−A21≤2dn.Combining equations (14) and (15), we can obtain(16)PA′∣XPA′∣X′≤eε.Therefore, algorithm LIP satisfiesε,0-DP.Lemma 2.
In algorithm LOP, givenVk, denote gX=XVk; then, the sensitivity of the function gX equals 2d.Proof.
Suppose thatY1, Y2 and Vk, Vk′ are the low-dimensional data and first k orthogonal eigenvectors of X and X′, respectively.(17)
Y
1
=
X
V
k
,
Y
2
=
X
′
V
k
′
.According to Definition 2, the sensitivity of functiongX is maxY1−Y21. Then, we have(18)Y1−Y21=XVk−X′Vk′1.SinceVk=v1,…,vk and Vk′=v1′,…,Vk′ are both composed of k unit orthogonal eigenvectors,(19)Y1−Y21=XVk−X′Vk′1≤X−X′1≤xi−xi′1.For the normalizedxi2≤1, we have(20)Y1−Y21≤xi−xi′1≤xi1+xi′1≤2d.Theorem 2.
Algorithm LOP satisfiesε,0-DP.Proof.
ForY′ derived from algorithm LOP on X and X′, we obtain Y′=Y1+N1 and Y′=Y2+N2, where N1 and N2 are the corresponding noise matrices.(21)
g
Y
′
∣
X
g
Y
′
∣
X
′
=
p
N
1
p
N
2
=
e
ε
/
2
d
N
2
1
−
N
1
1
,where pN1 and pN2 are the density functions of the output functions at neighbouring datasets X and X′. According to Lemma 2, we have(22)N21−N11≤N2−N11=Y1−Y21≤2d.Combining equations (22) and (23), we can obtain(23)PY′∣XPY′∣X′≤eε.Therefore, algorithm LOP satisfiesε,0-DP.


### 4.3. Utility Analysis

In Section4.2, we proved that algorithms LIP and LOP both satisfy ε,0-DP. Next, we evaluate the performance of the two algorithms. In order to protect data privacy, we add noise to covariance matrix and low-dimensional matrix in LIP and LOP, respectively. Adding noise may have effect on the performance of algorithms, and noise magnitude directly determines the magnitude of effect. In addition, approximation error also describes the performance of algorithms. Better data utility means less noise and lower approximation error, so we evaluate algorithms LIP and LOP in terms of noise magnitude and approximation error.Theorem 3.
For a given privacy parameterε, algorithm LIP adds less noise than LOP. The larger the samples n and target dimension k are, the less noise the algorithm LIP adds than LOP.Proof.
In algorithm LIP, noise matrixE1 has d2 elements, each element adds noise Lap2d/nε, and the variance of noise is about N1=Od4/n2ε2.In algorithm LOP, noise matrixE2 has n⋅k elements, each element adds noise Lap2d/ε, and the variance of noise is about N2=Onkd2/ε2.Now, we compareN1 and N2 to measure the noise magnitude of two algorithms:(24)N1=Od4n2ε2=Od2⋅d2n2ε2<Od2⋅n2n2ε2<Od2ε2<Onkd2ε2=N2,where d<n. From formula (24), we observe N1<N2, that is, algorithm LIP adds less noise than LOP.Letθ=N1/N2=Od4/n2ε2/Onkd2/ε2=Od2/n3k<O1 be the noise ratio. We observe that θ<1. Furthermore, θ and n, k show strong negative correlation. That is, if we take a larger sample n and target dimension k, LIP will add less noise than LOP.Theorem 4.
For a given privacy parameterε, algorithm LIP has lower error than LOP in the rank-k approximation of raw data.Proof.
In algorithm LIP, the rank-k approximation of X is(25)Z1=XVk′Vk′T.In algorithm LOP, the rank-k approximation of X is(26)Z2=XVk+E2VkT.Let(27)MSE1=Z1−XF=XVk′Vk′T−XF,(28)MSE2=Z2−XF=XVk+E2VkT−XF.MSE1 and MSE2 denote approximation errors inX and Z1, X and Z2, respectively. Now, we compare MSE1 and MSE2 to measure the approximation errors of two algorithms. Based on linear algebra, we have(29)XVkVkT−XF2=λk+1+⋯+λdλ1+⋯+λdXF2.In equation (29), Vk and λ1,…,λd are computed with the accurate matrix A while Vk′ is computed based on the matrix A′ with noise in equation (27). Theorem 6 in Dwork et al. [13] provides the closeness between Vk and Vk′. Vk′ not only captures large amount of variance, but is also close to the Vk of A. Theorem 6 in Dwork et al. [13] also gives the upper bound between Vk and Vk′; when σk−σk2=ωnΔε,δ, there is(30)VkVkT−Vk′Vk′TF=OknΔε,δσk2−σk+12,where Δε,δ=2ln1.25/δ/ε is the noise parameter in Gaussian distribution. In Gaussian mechanism [13], noise matrices are samples from N0,Δε,δ2, equalling Lap0,2d/nε in our Algorithm 1. σk is a singular value in SVD; according to the relationship between PCA and SVD, we have σk2=λk.From equation (30), we know that Vk and Vk′ are very close but still have little difference. Under the effect of difference and noise, we have(31)XVk′Vk′T−XF>XVkVkT−XF.Combining equations (29) and (31), we have(32)MSE1=XVk′Vk′T−XF>λk+1+⋯+λdλ1+⋯+λdXF.From equation (28), Vk is computed based on the accurate matrix A.(33)MSE2=XVk+E2VkT−XF=XVkVkT−X+E2VkTF.According toA+BF≤AF+BF, we have(34)MSE2≤XVkVkT−XF+E2VkTF≤λk+1+⋯+λdλ1+⋯+λdXF+E2VkTF.Letη=MSE1/MSE2; η<1 indicates algorithm LIP has lower approximation error than LOP:(35)η=MSE1MSE2>λk+1+⋯+λd/λ1+⋯+λdXFλk+1+⋯+λd/λ1+⋯+λdXF+E2VkTF>11+E2VkTF/λk+1+⋯+λd/λ1+⋯+λdXF.E
2 is a n×k matrix. With the increase of target dimension k, the value of E2VkTF will increase, while λk+1+⋯+λd/λ1+⋯+λd will decrease. Thus, approximation error ratio η decreases and maxη<1. Since η<1, LIP has lower error than LOP in the rank-k approximation of raw data.Theorem 3 and Theorem 4 prove that algorithm LIP adds less noise and has lower approximation error than LOP, that is, algorithm LIP outperforms LOP in data utility.


## 4.1. Algorithm Description

In algorithm LIP, we use Laplace distribution to generate symmetric noise matrix and then add it to the data covariance matrix. After computing the eigenvalues and corresponding eigenvectors of the noised covariance matrix, we select firstk eigenvectors to make up principal components space. In the end, we obtain low-dimensional data by projecting the original high-dimensional data to the principal components space. Algorithm LIP is described in Algorithm 1.Algorithm 1:Laplace input perturbation (LIP).
Input: matrix X∈Rn×d, number of samples n, attributes d, privacy parameter ε;
Output: Z1: the rank-k approximation matrix
(1)
Compute covariance matrixA=1/nXTX;
(2)
Noise matrixE1∈Rd×d is a symmetric matrix where the upper triangle is d2+d/2 i.i.d. sample from Lap2d/nε, and each lower triangle entry is copied from the opposite position;
(3)
Add noiseA′=A+E1;
(4)
Compute eigenvalues and corresponding eigenvectors of the noised covariance matrixA′vi′=λi′vi′;
(5)
Given a thresholdα, select top k eigenvectors Vk′ of A′, low-dimensional data Y1=XVk′;
(6)
The rank-k approximation matrix Z1=Y1Vk′T;V
k
′ are the first k eigenvectors of the noised covariance matrix A′, which is close to the true first k eigenvectors Vk of covariance matrix A [13].Besides adding noise prior to computing PCA, we also add noise to the output of PCA. According to differential privacy parallel composition [20], the whole dataset is private as long as each record is private; a simple idea is adding noise to each record to protect private information. However, if this privacy preservation method is directly applied to big data, the introduced noise will significantly increase so that data utility dramatically drops. In order to reduce noise without decreasing the level of privacy preservation, we can add noise to fewer but most important parts of data. Algorithm LOP projects the original high-dimensional data to the principal component space to get low-dimensional data. The low-dimensional data are important data, so we add noise to them to protect data privacy. Algorithm LOP is described in Algorithm 2.Algorithm 2:Laplace output perturbation (LOP).
Input: matrix X∈Rn×d, number of samples n, attributes d, privacy parameter ε;
Output: Z2: the rank-k approximation matrix
(1)
Compute covariance matrixA=1/nXTX;
(2)
Compute eigenvalues and corresponding eigenvectorsAvi=λivi;
(3)
Given a thresholdα, select top k eigenvectors Vk of A, low-dimensional data Y2=XVk;
(4)
Noise matrixE2 is a n×k matrix where the whole elements are i.i.d. samples from Lap2d/ε
(5)
Add noiseY2′=Y2+E2;
(6)
The rank-k approximation matrix Z2=Y2′VkT;


## 4.2. Privacy Analysis

Before proving that LIP and LOP satisfyε,0-DP, we should analyze the sensitivities of these two algorithms. Suppose there are two neighbouring datasets X=x1,…,xi,…,xnT∈Rn×d and X′=x1,…,xi′,…,xnT∈Rn×d where xi≠xi′, we assume the normalized data vector xi2≤1.Lemma 1.
In algorithm LIP, for all the input data, denotefX=1/nXTX; then, the sensitivity of the function fX equals 2d/n.Proof.
Suppose thatA1 and A2 are the covariance matrices of X and X′, respectively.(11)
A
1
=
1
n
X
T
X
,
A
2
=
1
n
X
′
T
X
′
.According to Definition 2, the sensitivity of functionfX is maxA1−A21. Then, we have(12)A1−A21=1nXTX−1nX′TX′1=1nxiTxi−xi′Txi′1,where ⋅1 denotes the l1 norm, for a matrix C∈Rm×n, C1=maxj∑i=1mcij1≤j≤n. For the normalized xi2≤1, we have(13)A1−A21=1nxiTxi−xi′Txi′1≤1nxiTxi1+xi′Txi′1≤2dn.Theorem 1.
Algorithm LIP satisfiesε,0-DP.Proof.
ForA′ derived from algorithm LIP on X and X′, we obtain A′=A1+N1 and A′=A2+N2 where N1 and N2 are the corresponding noise matrices.(14)
f
A
′
∣
X
f
A
′
∣
X
′
=
p
N
1
p
N
2
=
e
n
ε
/
2
d
N
2
1
−
N
1
1
,where pN1 and pN2 are the density functions of the output functions at neighbouring datasets X and X′. According to Lemma 1, we have(15)N21−N11≤N2−N11=A1−A21≤2dn.Combining equations (14) and (15), we can obtain(16)PA′∣XPA′∣X′≤eε.Therefore, algorithm LIP satisfiesε,0-DP.Lemma 2.
In algorithm LOP, givenVk, denote gX=XVk; then, the sensitivity of the function gX equals 2d.Proof.
Suppose thatY1, Y2 and Vk, Vk′ are the low-dimensional data and first k orthogonal eigenvectors of X and X′, respectively.(17)
Y
1
=
X
V
k
,
Y
2
=
X
′
V
k
′
.According to Definition 2, the sensitivity of functiongX is maxY1−Y21. Then, we have(18)Y1−Y21=XVk−X′Vk′1.SinceVk=v1,…,vk and Vk′=v1′,…,Vk′ are both composed of k unit orthogonal eigenvectors,(19)Y1−Y21=XVk−X′Vk′1≤X−X′1≤xi−xi′1.For the normalizedxi2≤1, we have(20)Y1−Y21≤xi−xi′1≤xi1+xi′1≤2d.Theorem 2.
Algorithm LOP satisfiesε,0-DP.Proof.
ForY′ derived from algorithm LOP on X and X′, we obtain Y′=Y1+N1 and Y′=Y2+N2, where N1 and N2 are the corresponding noise matrices.(21)
g
Y
′
∣
X
g
Y
′
∣
X
′
=
p
N
1
p
N
2
=
e
ε
/
2
d
N
2
1
−
N
1
1
,where pN1 and pN2 are the density functions of the output functions at neighbouring datasets X and X′. According to Lemma 2, we have(22)N21−N11≤N2−N11=Y1−Y21≤2d.Combining equations (22) and (23), we can obtain(23)PY′∣XPY′∣X′≤eε.Therefore, algorithm LOP satisfiesε,0-DP.


## 4.3. Utility Analysis

In Section4.2, we proved that algorithms LIP and LOP both satisfy ε,0-DP. Next, we evaluate the performance of the two algorithms. In order to protect data privacy, we add noise to covariance matrix and low-dimensional matrix in LIP and LOP, respectively. Adding noise may have effect on the performance of algorithms, and noise magnitude directly determines the magnitude of effect. In addition, approximation error also describes the performance of algorithms. Better data utility means less noise and lower approximation error, so we evaluate algorithms LIP and LOP in terms of noise magnitude and approximation error.Theorem 3.
For a given privacy parameterε, algorithm LIP adds less noise than LOP. The larger the samples n and target dimension k are, the less noise the algorithm LIP adds than LOP.Proof.
In algorithm LIP, noise matrixE1 has d2 elements, each element adds noise Lap2d/nε, and the variance of noise is about N1=Od4/n2ε2.In algorithm LOP, noise matrixE2 has n⋅k elements, each element adds noise Lap2d/ε, and the variance of noise is about N2=Onkd2/ε2.Now, we compareN1 and N2 to measure the noise magnitude of two algorithms:(24)N1=Od4n2ε2=Od2⋅d2n2ε2<Od2⋅n2n2ε2<Od2ε2<Onkd2ε2=N2,where d<n. From formula (24), we observe N1<N2, that is, algorithm LIP adds less noise than LOP.Letθ=N1/N2=Od4/n2ε2/Onkd2/ε2=Od2/n3k<O1 be the noise ratio. We observe that θ<1. Furthermore, θ and n, k show strong negative correlation. That is, if we take a larger sample n and target dimension k, LIP will add less noise than LOP.Theorem 4.
For a given privacy parameterε, algorithm LIP has lower error than LOP in the rank-k approximation of raw data.Proof.
In algorithm LIP, the rank-k approximation of X is(25)Z1=XVk′Vk′T.In algorithm LOP, the rank-k approximation of X is(26)Z2=XVk+E2VkT.Let(27)MSE1=Z1−XF=XVk′Vk′T−XF,(28)MSE2=Z2−XF=XVk+E2VkT−XF.MSE1 and MSE2 denote approximation errors inX and Z1, X and Z2, respectively. Now, we compare MSE1 and MSE2 to measure the approximation errors of two algorithms. Based on linear algebra, we have(29)XVkVkT−XF2=λk+1+⋯+λdλ1+⋯+λdXF2.In equation (29), Vk and λ1,…,λd are computed with the accurate matrix A while Vk′ is computed based on the matrix A′ with noise in equation (27). Theorem 6 in Dwork et al. [13] provides the closeness between Vk and Vk′. Vk′ not only captures large amount of variance, but is also close to the Vk of A. Theorem 6 in Dwork et al. [13] also gives the upper bound between Vk and Vk′; when σk−σk2=ωnΔε,δ, there is(30)VkVkT−Vk′Vk′TF=OknΔε,δσk2−σk+12,where Δε,δ=2ln1.25/δ/ε is the noise parameter in Gaussian distribution. In Gaussian mechanism [13], noise matrices are samples from N0,Δε,δ2, equalling Lap0,2d/nε in our Algorithm 1. σk is a singular value in SVD; according to the relationship between PCA and SVD, we have σk2=λk.From equation (30), we know that Vk and Vk′ are very close but still have little difference. Under the effect of difference and noise, we have(31)XVk′Vk′T−XF>XVkVkT−XF.Combining equations (29) and (31), we have(32)MSE1=XVk′Vk′T−XF>λk+1+⋯+λdλ1+⋯+λdXF.From equation (28), Vk is computed based on the accurate matrix A.(33)MSE2=XVk+E2VkT−XF=XVkVkT−X+E2VkTF.According toA+BF≤AF+BF, we have(34)MSE2≤XVkVkT−XF+E2VkTF≤λk+1+⋯+λdλ1+⋯+λdXF+E2VkTF.Letη=MSE1/MSE2; η<1 indicates algorithm LIP has lower approximation error than LOP:(35)η=MSE1MSE2>λk+1+⋯+λd/λ1+⋯+λdXFλk+1+⋯+λd/λ1+⋯+λdXF+E2VkTF>11+E2VkTF/λk+1+⋯+λd/λ1+⋯+λdXF.E
2 is a n×k matrix. With the increase of target dimension k, the value of E2VkTF will increase, while λk+1+⋯+λd/λ1+⋯+λd will decrease. Thus, approximation error ratio η decreases and maxη<1. Since η<1, LIP has lower error than LOP in the rank-k approximation of raw data.Theorem 3 and Theorem 4 prove that algorithm LIP adds less noise and has lower approximation error than LOP, that is, algorithm LIP outperforms LOP in data utility.


## 5. Experimental Results and Analysis

In this section, we will give some experimental results to verify that algorithm LIP outperforms LOP in data utility. We compare algorithms LIP and LOP in terms of noise magnitude and approximation error. In addition, we investigate the variation of performance of the two algorithms with different key parameters such as number of samplesn, target dimension k, and privacy parameter ε. Five UCI datasets are used in our experiments: Secom [21], Covtype [22], Musk [23], Handwritten [24] and Waveform [25]. We preprocess the data by subtracting the mean and normalizing data to meet the condition xi2≤1. We select target dimension k so that the accumulative contribution rate of the principal components α is at least 85%. In all cases, we show the average performance over 100 runs of each algorithm.


### 5.1. Experiments for Noise Magnitude

In this section, we evaluate the performance of algorithms LIP and LOP by comparing the magnitude of introduced noise. In Theorem 3, the ratio of introduced noiseθ=N1/N2=Od2/n3k indicates that θ and n, k have strong negative correlation and θ<1. In the experiment, we verify that above conclusions are correct (we use the Frobenius norm of noise matrices E1 and E2 to represent N1 and N2).In order to better present the experimental results of all datasets in one figure, we unify the noise ratioθ, and all the objects are scaled to same size (θ in datasets Secom, Covtype, Musk, Handwritten, and Waveform are 1, 105, 102, 102, and 103 times the original value, respectively). For this experiment, we keep number of samples n fixed to investigate the relationship between the ratio of introduced noise θ and target dimension k. In Figure 1 we observe that even expanding the value of θ, θ is always less than 1; with the increase of value k, the ratio of introduced noise θ on five datasets continuously decreases. That is, θ and k are negatively correlated; the larger the target dimension k is, the less noise the LIP adds than LOP. The result is consistent with Theorem 3.Figure 1
Variation ofθ with different values of target dimension k.Then, we explore the effect of samplesn on the ratio of introduced noise θ. In case of fixing target dimension k, Figure 2 shows θ is always less than 1, and θ decreases as the value of n increases in five datasets. That is, θ and n are negatively correlated; the larger the samples n are, the less noise the LIP adds than LOP. The result is consistent with Theorem 3.Figure 2
Variation ofθ with different values of samples n. (a) Secom. (b) Covtype. (c) Musk. (d) Handwritten. (e) Waveform.
(a)
(b)
(c)
(d)
(e)


### 5.2. Experiments for Approximation Error

In this section, we evaluate the performance of algorithms LIP and LOP by comparing the approximation error. In Theorem 4, the ratio of approximation errorη=MSE1/MSE2 indicates that η<1. Thus, in the experiment, we verify (1) η is less than 1 and (2) η and k are negatively correlated while η and ε are positively correlated.In Theorem 3 and Section5.1, we observe that the larger the target dimension k is, the less noise the algorithm LIP adds than LOP. Less noise results in lower error. In addition, we further explore mathematical expression of η in Theorem 4 and find that η<1, and η and k are negatively correlated. Similarly, we unify the approximation error ratio η, and all the objects are scaled to same size (η in each dataset is 103, 102, 103, 102, and 102 times the original value). For this experiment, we keep privacy parameter ε fixed to investigate the relationship between the ratio of approximation error η and target dimension k. As shown in Figure 3, when the value of k increases, the ratio of approximation error η decreases and maxη<1. In other words, η and k are negatively correlated, which means when k is larger, LIP has lower error than LOP in the rank-k approximation of raw data. The experimental result is consistent with Theorem 4.Figure 3
Variation ofη with different values of target dimension k.Finally, we explore the variation ofη with privacy parameter ε. Similarly, we unify the approximation error ratio η, and all the objects are scaled to same size (η in each dataset is 10, 10, 103, 103, and 102 times the original value). In Figure 4, for all the datasets, we observe that as ε increases, the ratio of approximation error η increases. Furthermore, η and ε are positively correlated, even in the case of no privacy preserving, i.e., ε=10, η is still less than 1. It can be explained as follows: Dwork et al. pointed out that Vk′ is close to the true top k eigenvectors eigenvectors Vk in input perturbation [13], that is, algorithm LIP is not very sensitive to privacy parameter ε. Output perturbation due to directly adding noise to the output and privacy parameter ε plays a negative role in data utility. Lower ε means more noise and higher approximation error. Thus, when ε increases, MSE1 decreases slightly while MSE2 decreases greatly and η=MSE1/MSE2 increases. Therefore, at the same privacy protection level, algorithm LIP has lower error than LOP in the rank-k approximation of raw data.Figure 4
Variation ofη with different values of privacy parameter ε.


### 5.3. Experiments for Accuracy

In Sections5.1 and 5.2, we verify that algorithm LIP outperforms LOP in data utility. To verify the effectiveness of algorithm LIP compared with the existing algorithms AG [13] and PPM [26], we evaluate the classification accuracy on Handwritten and Waveform datasets. The classifier used in the experiment is linear support vector machine (SVM). In SVM, there are many parameters that can affect accuracy; we mainly consider the influence of privacy parameter ε on the accuracy.In Figure5, we show the variation of accuracy with different values of ε. For all the datasets, we observe that as ε increases (higher privacy risk), the accuracy increases significantly, which indicates that the value of ε has an important effect on accuracy. On the other hand, the accuracy of algorithms AG and LIP are higher than that of PPM on the two datasets. In addition, algorithm AG outperforms LIP in accuracy; it can be explained as the utility gap between ε,δ-DP and ε,0-DP (AG satisfies ε,δ-DP and LIP satisfies ε,0-DP). ε,0-DP provides stronger privacy guarantee and weaker data utility than ε,δ-DP. For large enough ε, our algorithm LIP can match the performance of AG. More important, it can provide a stronger privacy guarantee than AG. In conclusion, algorithm LIP achieves both strong privacy guarantee and good data utility.Figure 5
Variation of accuracy with different values of privacy parameterε. (a) Handwritten. (b) Waveform.
(a)
(b)


## 5.1. Experiments for Noise Magnitude

In this section, we evaluate the performance of algorithms LIP and LOP by comparing the magnitude of introduced noise. In Theorem 3, the ratio of introduced noiseθ=N1/N2=Od2/n3k indicates that θ and n, k have strong negative correlation and θ<1. In the experiment, we verify that above conclusions are correct (we use the Frobenius norm of noise matrices E1 and E2 to represent N1 and N2).In order to better present the experimental results of all datasets in one figure, we unify the noise ratioθ, and all the objects are scaled to same size (θ in datasets Secom, Covtype, Musk, Handwritten, and Waveform are 1, 105, 102, 102, and 103 times the original value, respectively). For this experiment, we keep number of samples n fixed to investigate the relationship between the ratio of introduced noise θ and target dimension k. In Figure 1 we observe that even expanding the value of θ, θ is always less than 1; with the increase of value k, the ratio of introduced noise θ on five datasets continuously decreases. That is, θ and k are negatively correlated; the larger the target dimension k is, the less noise the LIP adds than LOP. The result is consistent with Theorem 3.Figure 1
Variation ofθ with different values of target dimension k.Then, we explore the effect of samplesn on the ratio of introduced noise θ. In case of fixing target dimension k, Figure 2 shows θ is always less than 1, and θ decreases as the value of n increases in five datasets. That is, θ and n are negatively correlated; the larger the samples n are, the less noise the LIP adds than LOP. The result is consistent with Theorem 3.Figure 2
Variation ofθ with different values of samples n. (a) Secom. (b) Covtype. (c) Musk. (d) Handwritten. (e) Waveform.
(a)
(b)
(c)
(d)
(e)


## 5.2. Experiments for Approximation Error

In this section, we evaluate the performance of algorithms LIP and LOP by comparing the approximation error. In Theorem 4, the ratio of approximation errorη=MSE1/MSE2 indicates that η<1. Thus, in the experiment, we verify (1) η is less than 1 and (2) η and k are negatively correlated while η and ε are positively correlated.In Theorem 3 and Section5.1, we observe that the larger the target dimension k is, the less noise the algorithm LIP adds than LOP. Less noise results in lower error. In addition, we further explore mathematical expression of η in Theorem 4 and find that η<1, and η and k are negatively correlated. Similarly, we unify the approximation error ratio η, and all the objects are scaled to same size (η in each dataset is 103, 102, 103, 102, and 102 times the original value). For this experiment, we keep privacy parameter ε fixed to investigate the relationship between the ratio of approximation error η and target dimension k. As shown in Figure 3, when the value of k increases, the ratio of approximation error η decreases and maxη<1. In other words, η and k are negatively correlated, which means when k is larger, LIP has lower error than LOP in the rank-k approximation of raw data. The experimental result is consistent with Theorem 4.Figure 3
Variation ofη with different values of target dimension k.Finally, we explore the variation ofη with privacy parameter ε. Similarly, we unify the approximation error ratio η, and all the objects are scaled to same size (η in each dataset is 10, 10, 103, 103, and 102 times the original value). In Figure 4, for all the datasets, we observe that as ε increases, the ratio of approximation error η increases. Furthermore, η and ε are positively correlated, even in the case of no privacy preserving, i.e., ε=10, η is still less than 1. It can be explained as follows: Dwork et al. pointed out that Vk′ is close to the true top k eigenvectors eigenvectors Vk in input perturbation [13], that is, algorithm LIP is not very sensitive to privacy parameter ε. Output perturbation due to directly adding noise to the output and privacy parameter ε plays a negative role in data utility. Lower ε means more noise and higher approximation error. Thus, when ε increases, MSE1 decreases slightly while MSE2 decreases greatly and η=MSE1/MSE2 increases. Therefore, at the same privacy protection level, algorithm LIP has lower error than LOP in the rank-k approximation of raw data.Figure 4
Variation ofη with different values of privacy parameter ε.


## 5.3. Experiments for Accuracy

In Sections5.1 and 5.2, we verify that algorithm LIP outperforms LOP in data utility. To verify the effectiveness of algorithm LIP compared with the existing algorithms AG [13] and PPM [26], we evaluate the classification accuracy on Handwritten and Waveform datasets. The classifier used in the experiment is linear support vector machine (SVM). In SVM, there are many parameters that can affect accuracy; we mainly consider the influence of privacy parameter ε on the accuracy.In Figure5, we show the variation of accuracy with different values of ε. For all the datasets, we observe that as ε increases (higher privacy risk), the accuracy increases significantly, which indicates that the value of ε has an important effect on accuracy. On the other hand, the accuracy of algorithms AG and LIP are higher than that of PPM on the two datasets. In addition, algorithm AG outperforms LIP in accuracy; it can be explained as the utility gap between ε,δ-DP and ε,0-DP (AG satisfies ε,δ-DP and LIP satisfies ε,0-DP). ε,0-DP provides stronger privacy guarantee and weaker data utility than ε,δ-DP. For large enough ε, our algorithm LIP can match the performance of AG. More important, it can provide a stronger privacy guarantee than AG. In conclusion, algorithm LIP achieves both strong privacy guarantee and good data utility.Figure 5
Variation of accuracy with different values of privacy parameterε. (a) Handwritten. (b) Waveform.
(a)
(b)


## 6. Conclusions

In this paper, we propose two algorithms Laplace input perturbation (LIP) and Laplace output perturbation (LOP) for differential privacy principal component analysis. We compare the performance of LIP and LOP in terms of noise magnitude and approximation error via theoretical analysis. Then we conduct many experiments to verify the performance of two algorithms on five data sets. In the experiments, we show the variation of performance of the two algorithms with different parameters such as privacy parameter, target dimension and samples. Our theoretical and experimental results indicate that algorithm Laplace input perturbation (LIP) adds less noise and has lower approximation error than Laplace output perturbation (LOP). Last, to verify the effectiveness of algorithm LIP, we compare our LIP with other recent algorithms AG and PPM, the experimental results show that algorithm LIP can provide strong privacy guarantee and good data utility.



---

*Source: 9169802-2019-11-03.xml*