Design and Implementation of an Efficient Parallel Algorithm for Sparse Principal Component Analysis

Sparse matrix computations are an important class of algorithms. One of the important topics in this field is SPCA (Sparse Principal Component Analysis), a variant of PCA. SPCA is used to compute the principal components of a matrix. There are various methods for computing the sparse principal components of a dataset. One of them is the congradU (Conditional gradient algorithm with unit step size) method, which is an iterative approach. This method performs a matrix-vector multiplication at each iteration of its execution process. Therefore, we need to accelerate the multiplication operation. In this regard, we propose a parallel algorithm for the congradU method that uses a master/worker model to distribute the rows of the matrix among the cores or processors in a manner that ensures an appropriate workload distribution between them. By optimizing the workload distribution among processors, we can reduce the overall execution time of operations. The proposed algorithm has been tested on randomly generated matrices with different sizes and sparsity percentages. We compare the time to find the first principal component using the proposed algorithm and SVD algorithm. It was observed that by increasing the size and sparsity percentage of the matrix, the proposed algorithm finds the first principal component faster than the SVD algorithm. Also, we compare the time of the multiplication operation in one iteration of the proposed algorithm and the dot operator (in Python), and we observe that with increasing the percentage of sparsity, the proposed algorithm performs better than the dot operator.