1. 噪声分布与最大似然估计的关系

• 噪声类型：矩阵机制中，噪声 $\eta =\tilde{\mathbf{r}}-\mathbf{Ax}$ 服从 拉普拉斯分布 $\eta \sim \text{Lap}({\Delta }_{\mathbf{A}}/ϵ)$。
• 拉普拉斯分布的密度函数：
  $$f({\eta }_i)=\frac{ϵ}{2{\Delta }_{\mathbf{A}}}{e}^{-ϵ|{\eta }_i|/{\Delta }_{\mathbf{A}}}.$$
  其对数似然函数为：
  $$\log f(\eta )=\text{常数}-\frac{ϵ}{{\Delta }_{\mathbf{A}}}\Vert \eta {\Vert }_1.$$
  最大化似然等价于 最小化 $\Vert \eta {\Vert }_1$，即最小化 $\Vert \tilde{\mathbf{r}}-\mathbf{Ax}{\Vert }_1$。

2. 非负约束的必要性

• 原始数据特性：数据库 $\mathbf{x}$ 由非负整数组成（如人口计数）。
• 伪逆解的缺陷：最小二乘解 $\hat{\mathbf{x}}={\mathbf{A}}^{†}\tilde{\mathbf{r}}$ 可能包含负数，违背实际意义。
• 后处理目标：找到非负且与噪声数据最接近的估计值 $\overline{\mathbf{x}}\ge 0$。

3. 优化问题的数学形式

最终的优化问题为：
$$\overline{\mathbf{x}}=\arg \underset{\hat{\mathbf{x}}\ge 0}{\min }\Vert \tilde{\mathbf{r}}-\mathbf{A}\hat{\mathbf{x}}{\Vert }_1.$$
其含义如下：

• 目标函数（$\Vert \cdot {\Vert }_1$）：最大化拉普拉斯噪声下的似然概率。
• 约束条件（$\hat{\mathbf{x}}\ge 0$）：确保估计值符合现实意义。

4. 具体示例说明

场景：

• 数据库 $\mathbf{x}=[x_1,x_2]$ 表示城市和农村人口，真实值 $\mathbf{x}=[100,200]$。
• 策略矩阵 $\mathbf{A}=\left[\begin{array}{cc}1& 1\\ 1& -1\end{array}\right]$，查询总人口和城乡差。
• 噪声响应 $\tilde{\mathbf{r}}=[303,-101]$。

步骤：

1. 最小二乘解：
   $$\hat{\mathbf{x}}={\mathbf{A}}^{†}\tilde{\mathbf{r}}=[101,202].$$
   结果非负，可直接接受。

2. 若噪声导致负值：
   假设 $\tilde{\mathbf{r}}=[300,150]$，则：
   $$\hat{\mathbf{x}}={\mathbf{A}}^{†}\tilde{\mathbf{r}}=[225,75].$$
   仍为非负，无需优化。

3. 需优化的情况：
   若 $\tilde{\mathbf{r}}=[290,90]$，则：
   $$\hat{\mathbf{x}}={\mathbf{A}}^{†}\tilde{\mathbf{r}}=[190,100].$$
   若出现负数（如 $\hat{\mathbf{x}}=[150,-50]$），需通过优化问题修正。

5. 总结

• L1 范数 vs L2 范数：
  • 拉普拉斯噪声的 最大似然估计 对应 L1 范数最小化。
  • 高斯噪声的 MLE 对应 L2 范数最小化（如最小二乘）。
• 非负约束：
  • 强制估计值 $\overline{\mathbf{x}}$ 符合现实数据的非负性。
• 优化问题意义：
  • 在满足实际约束（非负）的前提下，最大化观测到噪声数据的概率。