Title

On the Lower Bound of Reconstruction Error for Spectral Filtering Based Privacy Preserving Data Mining

Publication Type

Conference Proceeding Article

Publication Date

9-2006

Abstract

Additive Randomization has been a primary tool to hide sensitive private information during privacy preserving data mining. The previous work based on Spectral Filtering empirically showed that individual data can be separated from the perturbed one and as a result privacy can be seriously compromised. Our previous work initiated the theoretical study on how the estimation error varies with the noise and gave an upper bound for the Frobenius norm of reconstruction error using matrix perturbation theory. In this paper, we propose one Singular Value Decomposition (SVD) based reconstruction method and derive a lower bound for the reconstruction error. We then prove the equivalence between the Spectral Filtering based approach and the proposed SVD approach and as a result the achieved lower bound can also be considered as the lower bound of the Spectral Filtering based approach.

Discipline

Information Security

Research Areas

Information Security and Trust

Publication

Knowledge Discovery in Databases: PKDD 2006: 10th European Conference on Principles and Practice of Knowledge Discovery in Databases, Berlin, Germany, September 18-22: Proceedings

Volume

4213

First Page

520

Last Page

527

ISBN

9783540460480

Identifier

10.1007/11871637_51

Publisher

Springer Verlag

City or Country

Berlin, Germany

Additional URL

http://dx.doi.org/10.1007/11871637_51