Approximating Eigenvectors with Fixed-Point Arithmetic

Abstract

We investigate the adaptation of the spectral clustering algorithm to the privacy preserving domain. Spectral clustering is a data mining technique that divides points according to a measure of connectivity in a data graph. When the matrix data are privacy sensitive, cryptographic techniques can be applied to protect the data. A pivotal part of spectral clustering is the partial eigendecomposition of the graph Laplacian. The Lanczos algorithm is used to approximate the eigenvectors of the Laplacian. Many cryptographic techniques are designed to work with positive integers, whereas the numerical algorithms are generally applied in the real domain. To overcome this problem, the Lanczos algorithm is adapted to be performed with fixed-point arithmetic. Square roots are eliminated and floating-point computations are transformed to fixed-point computations. The effects of these adaptations on the accuracy and stability of the algorithm are investigated using standard datasets. The performance of the original and the adapted algorithm is similar when few eigenvectors are needed. For a large number of eigenvectors loss of orthogonality affects the results.