RANDOM MATRICES AND APPLICATIONS TO DATA FILTERING
Qi Wang · Research Exchange (Washington State University) · 2003
Preserving privacy is becoming an important issue in data mining.Random perturbation is a widely used technique to protect privacy of sensitive data values.This technique hides the true data records by modifying the data values using additive random noise, but can still estimate the data distribution from the perturbed data set.Our question in this thesis is: does this method really preserve privacy?Large random matrices have many properties.Random matrix theory has been widely used in nuclear physics, the study of the zeros of Reimann zeta function, the study of chaotic systems, and signal processing.After investigating some asymptotic properties of eigenvalues of covariance matrices, this thesis presents a random matrix-based data filtering technique, which we call spectral filtering.This method analyzes the eigenstates (spectrum) of the sample covariance matrix of observed data, and identifies the noisy eigenstates by applying the known asymptotic properties of random matrices.Experiments in the thesis show that this technique can produce good estimate of the true data for a reasonable value of the signal-to-noise ratio (SNR).This questions the effectiveness of additive random perturbation technique.Although spectral filtering technique has the ability to breach privacy in additive random perturbation, there exist other data mining techniques that can preserve privacy.One iv example is multi-party secure sum computation.We examine the relation between the perturbed values using this method and the original ones, and prove that they are statistically independent.This means that it is not possible to estimate the true data values from the perturbed values.Hence multi-party secure sum computation preserves privacy.