Secure and Verifiable Outsourcing of Large-Scale Nonnegative Matrix Factorization (NMF)

Nowadays, cloud computing platforms are becoming increasingly prevalent and readily available, providing alternative and economic services for resource-constrained clients to perform large-scale computations. This work addresses the problem of secure outsourcing of large-scale nonnegative matrix factorization (NMF) to a cloud in a way that the client can verify the correctness of the results with small overhead. The protection of the input matrix is achieved by a random permutation and scaling encryption mechanism. By exploiting the iterative nature of NMF computation, we propose a single-round verification strategy, which can be proved to be quite effective. Theoretical and experimental results are provided to show the superior performance of the proposed scheme.

1 Introduction

In the big data era, quintillion bytes of data are being created daily at an astounding speed. These data are generated from almost everywhere: digital images and videos, purchase transaction records, cell phone GPS signals, sensors for gathering climate information, posts on social media networks, just to name a few. To become competitive, organizations need to efficiently convert the large amount of raw data into significant insights, guiding their strategies for investment, marketing, research, etc.