Computationally Efficient and Secure Kronecker-based Compressive Sensing

We propose an efficient permuted Kronecker-based sparse measurement matrix for compressive sensing applications. We use sub-matrices to create a block-diagonal matrix and multiply it with a deterministic permutation matrix to measure the sparse or compressible signals. Using ECG signals from the MIT-BIH Arrhythmia database, we show that the reconstructed signal quality is comparable to the ones achieved using standard compressive sensing methods. Our methodology results in an overall reduction in storage and computations and can be generalized to other classes of eligible measurement matrices in compressive sensing. We show that with the use of a securely generated one-time sensing matrix, our proposed method is computationally secure against plaintext and ciphertext-only attacks. The proposed one-time sensing matrix is superior to other measurement matrices in the literature in terms of the number of linear feedback shift register bits required for their generation.