Boolean matrix compressed sensing

Abstract

In real-world datasets, leveraging the low-rank and sparsity properties enables developing efficient algorithms across a diverse array of data-related tasks, including compression, compressed sensing, matrix completion, etc. Notably, these two properties often coexist in certain real-world datasets, especially in Boolean datasets and quantized real-valued datasets. To harness the advantages of low-rank and sparsity simultaneously, we adopt a technique inspired by compressed sensing and Boolean matrix completion. Our approach entails compressing a low-rank sparse Boolean matrix by performing inner product operations with a randomly generated Boolean matrix. We then propose a decoding algorithms based on message-passing techniques to recover the original matrix. Our experiments demonstrate superior recovery performance of our proposed algorithms compared to Boolean matrix completion, with equal measurement requirements.