差分隐私的定义如下：
给定一个兄弟数据集D和D’，他们两者之间至多相差一条数据。然后给定一个映射函数
f
:
D
→
R
d
f:D\rightarrow R^d
f:D→Rd。它表示的是数据集D到一个d维空间的映射关系。接着，我们在所得到的的函数
f
(
D
)
=
(
x
1
,
x
2
,
.
.
.
,
x
d
)
T
f(D)=(x_1,x_2,...,x_d)^T
f(D)=(x1,x2,...,xd)T上添加拉普拉斯噪声，得到一个输出函数A(D)。
那么有式1：
A
(
D
)
=
f
(
D
)
+
⟮
L
a
p
1
(
Δ
f
ε
)
,
L
a
p
1
(
Δ
f
ε
)
,
.
.
.
,
L
a
p
d
(
Δ
f
ε
)
⟯
T
A(D)=f(D)+\lgroup Lap_1(\frac {\Delta f} \varepsilon ), Lap_1(\frac {\Delta f} \varepsilon ),...,Lap_d(\frac {\Delta f} \varepsilon )\rgroup ^T
A(D)=f(D)+⟮Lap1(εΔf),Lap1(εΔf),...,Lapd(εΔf)⟯T
其中
Δ
f
=
D
,
D
′
m
a
x
∣
∣
f
(
D
)
−
f
(
D
′
)
∣
∣
p
{\Delta f}=\stackrel {max}{_D, _{D'}} ||f(D)-f(D')||_p
Δf=D,D′max∣∣f(D)−f(D′)∣∣p，其中p一般取1，为1-范数。
1-范数：
∣
∣
x
∣
∣
1
=
∑
i
=
1
n
∣
x
i
∣
||x||_1=\sum_{i=1}^{n}|x_i|
∣∣x∣∣1=∑i=1n∣xi∣ ，即向量元素绝对值之和，matlab调用函数norm(x, 1) 。
而算法A满足差分隐私定义的条件是（式2）：
P
r
[
A
(
D
)
=
O
]
≤
e
ε
∗
P
r
[
A
(
D
′
)
=
O
]
P_r[A(D)=O]\leq e^{\varepsilon} * P_r[A(D')=O]
Pr[A(D)=O]≤eε∗Pr[A(D′)=O]
式1中的 A(D) 满足式2
证明见一位大佬的证明
