DPSR: Differentially Private Sparse Reconstruction via Multi-Stage Denoising for Recommender Systems

Differential privacy (DP) has emerged as the gold standard for protecting user data in recommender systems, but existing privacy-preserving mechanisms face a fundamental challenge: the privacy-utility tradeoff inevitably degrades recommendation quality as privacy budgets tighten. We introduce DPSR (Differentially Private Sparse Reconstruction), a novel three-stage denoising framework that fundamentally addresses this limitation by exploiting the inherent structure of rating matrices – sparsity, low-rank properties, and collaborative patterns. DPSR consists of three synergistic stages: (1) $\mathit{\text{information-theoretic}}\mathit{\text{noise}}\mathit{\text{calibration}}$ that adaptively reduces noise for high-information ratings, (2) $\mathit{\text{collaborative}}\mathit{\text{filtering-based}}\mathit{\text{denoising}}$ that leverages item-item similarities to remove privacy noise, and (3) $\mathit{\text{low-rank}}\mathit{\text{matrix}}\mathit{\text{completion}}$ that exploits latent structure for signal recovery. Critically, all denoising operations occur $\mathit{\text{after}}$ noise injection, preserving differential privacy through the post-processing immunity theorem while removing both privacy-induced and inherent data noise. Through extensive experiments on synthetic datasets with controlled ground truth, we demonstrate that DPSR achieves 5.57% to 9.23% RMSE improvement over state-of-the-art Laplace and Gaussian mechanisms across privacy budgets ranging from $\epsilon =0.1$ to $\epsilon =10.0$ (all improvements statistically significant with $p<0.05$, most $p<0.001$). Remarkably, at $\epsilon =1.0$, DPSR achieves RMSE of 0.9823, $\mathit{\text{outperforming}}\mathit{\text{even}}\mathit{\text{the}}\mathit{\text{non-private}}\mathit{\text{baseline}}$ (1.0983), demonstrating that our denoising pipeline acts as an effective regularizer that removes data noise in addition to privacy noise.