Restricted Structural Random Matrix for Compressive Sensing

2020Β·Arxiv

Abstract

Abstract

Compressive sensing (CS) is well-known for its unique functionalities of sensing, compressing, and security (i.e. CS measurements are equally important). However, there is a tradeoff. Improving sensing and compressing efficiency with prior signal information tends to favor particular measurements, thus decrease the security. This work aimed to improve the sensing and compressing efficiency without compromise the security with a novel sampling matrix, named Restricted Structural Random Matrix (RSRM). RSRM unified the advantages of frame-based and block-based sensing together with the global smoothness prior (i.e. low-resolution signals are highly correlated). RSRM acquired compressive measurements with random projection (equally important) of multiple randomly sub-sampled signals, which was restricted to be the low-resolution signals (equal in energy), thereby, its observations are equally important. RSRM was proven to satisfies the Restricted Isometry Property and shows comparable reconstruction performance with recent state-of-the-art compressive sensing and deep learning-based methods.

1. Introduction

Compressive Sensing (CS) [1, 2, 3, 4] is an emerging sampling technique that directly captures a sparse or compressible signal in a compressed form via random projection:

where denotes the sampling matrix. CS is well known for its unique functionalities of simultaneous sampling, compressing, and security (or democracy).

Sensing. With the linear projection sampling, CS guarantees to reconstruct signal at a high probability if the

sampling matrix satisfies some condition, like the Restricted Isometry Property (RIP) [3, 4], as

The asymmetric RIP condition was developed [53, 54] to allow the difference in upper and lower bound.

* Corresponding author. E-mail address: bjeon@skku.edu. # Thuong Nguyen Canh was with College of Information and Communication Engineering, Sungkyunkwan University, South Korea. He is

In the literature, CS widely uses the Gaussian Random Matrix (GRM) due to its theoretical guarantee. Unfortunately, GRM requires significant computation and storage for its fully random structure. Over the past decades, researchers have sought to reduce its computational complexity. These studies can be classified as (i) block-based CS (BCS), which relies on processing signals in a block-based manner [5, 6, 7]; (ii) frame-based sensing, which samples each signal dimension separately in Kronecker CS (KCS) [8-11], random sample signals in fast-transform domains [12, 13], circulant random matrix [14], or sparse random matrices [15]. In general, frame-based CS is preferred for high sampling efficiency [8-13] and BCS for coding efficiency [16, 18, 19], parallel sampling [37].

Compressing. As the number of acquired measurements is significantly smaller than the signal dimension, , CS achieves compressing capabilities. As a sampling technique, CS assumes no information about the to-be-sampled signal, except for the sparsity prior. Meanwhile, standard compression methods (e.g., JPEG and HEVC) know the to-be-compressed signals, thereby encode them at higher coding efficiencies than CS [16, 17]. To overcome this drawback, researchers have been utilized other signal priors, such as the low-frequency prior (i.e. the human visual system is more sensitive to lower frequencies) [20-26], structural of signals (i.e. tree-sparse in wavelet [27] or zig-zag order in DCT [28]), perceptual prior (in image/video applications [29]), and smoothness prior (nearby samples are highly correlated) [16-19]. Multi-scale CS [20-24] and hybrid CS [25, 26] captured more low-frequency components to utilize the low-frequency prior. Weighted sampling exploited the structure of signal [27-29] to capture more important components without influencing the perceptual quality. The smoothness prior [16-19] was used for predictive coding in BCS because the nearby block measurements are highly correlated.

Security. CS measurements are equally important due to the randomness of the sampling matrix, thus named democracy property [30]. It is possible to recover signals from CS acquisitions despite damaged/degraded or lost measurements, which enable error-resilient applications [31]. Additionally, if GRM is used as a sampling matrix, then CS measurements are also following the Gaussian distribution. Therefore, despite revealing the energy of the signal, the sampling matrix was used as the private key providing a certain level of security [32-36]. As a result, numerous studies have attempted to analyze the theoretical security performance [32, 33], practical applications in multimedia capturing [50, 51] and/or transmission including cloud computing (e.g., for error resilience [31], to improve visual privacy protection [34], or for encryption [35, 36], cloud server-side protection [50, 51]). CS was further combined with conventional encryption techniques like random scrambling/flipping, chaos methods [51], etc.

There is, however, a trade-off between these functionalities. Researchers often used prior information to reduce sampling computation or improve sampling efficiency without considering the security. Utilizing prior information leads to reducing the randomness of the projection, tends to favour particular measurements. As a result, CS measurements are no longer equally important. For instance, reducing complexity with BCS reveals the signal structure by evaluating the block measurementβs energy. Alternatively, CS-based security methods reduce sampling and compressing performance and may even increase the sampling complexity.

In this work, we develop Generalized Structural Sensing Matrix (GSSM) and derived a special version named Restricted Structural Random Matrix (RSRM). RSRM is targeted to improve sensing efficiency, reduce complexity while maintaining the security/democracy property. Theoretically, RSRM unifies the advantages of BCS, the structural frame-based, and utilizes the smoothness prior which is held for compressible and structure sparse signals. We prove the asymmetric RIP condition of GSSM, symmetric RIP condition of RSRM together with RIP supported experiments. Practically, RSRM is a combination of CS with conventional under-sampling methods such as partial sub-sampling, multiple-images super-resolution, and coded imaging. RSRM randomly sub-samples multiple LR signals, which is equal in energy, then apply random block-based sampling for each. Therefore, each measurement of RSRM is equally important, thus the democracy is preserved. Note that, our work focusses on the security approach in the encoder part in which security, sampling, and compression are performed simultaneously.

The contributions of this paper are summarized are following β’ Propose a Generalized Structural Sensing Matrix from block-based and structural frame-based sampling.

β’ Present the asymmetric RIP of GSSM and derived the conditions to improve its RIP condition.

β’ Propose a Restricted Structural Random Matrix as a special case of GSSM by utilizing the local smoothness prior via global manner with Restricted Permutation.

We briefly review the related works in Section II. Section III introduces the generalized structural sensing matrix and its asymmetric RIP condition. Section IV proposes the restricted structure random matrix, a special version of GSSM, to achieve the best RIP condition taking the advantage of the global smoothness prior, especially for compressible and structure sparse signals. We present support experiments and reconstruction performance in Section V. Finally, we draw conclusions in Section VI.

For notation convention, a scalar value is written in normal form as , a vector is represented in normal bold as while a matrix is denoted in capital bold notation as . Other notations are given in Table 1.

Table 1. Notations and descriptions

2. Related Work

2.1. Sampling Complexity Reduction

2.1.1. Block-Based Compressive Sensing (BCS)

Motivated by the block-by-block processing of the JPEG and MPEG standards, block-based CS (BCS) [5, 6]

divides -d signal to non-overlapping blocks of size , then samples each with the sampling matrix

where is a GRM matrix. As a result, BCS demands less memory storage and computational complexity for the sampling process as well as reconstruction (i.e., reconstruction requires multiple matrix multiplications with the sampling matrix). Each BCS observation carries information about a nonoverlap portion of the signal, thereby, enables parallel sampling and reconstruction. We can reduce the acquisition time with the single pixel camera [37]. However, the energy of each block measurement might reveal a low-resolution version of the signals as in [38], thereby BCS compromises the democracy property.

2.1.2. Frame-Based Sensing: A Structurally Random Matrix

The scrambled Fourier transform [3] was the first structurally random matric by randomly selecting Fourier

coefficients primally used for MRI acquisition. It was further generalized by T. T. Do et al. [12] to the structurally random matrix (SRM). SRM first permutates the signal, then captures measurements by scrambled transform matrix which is created by randomly selects rows of a fast transform matrix (e.g., DCT) as

where denote the random sub-sampling and permutation matrices, respectively. A scale

factor is often used to normalize the energy of measurements. For efficiency sampling, a block-based version of SRM (BSRM) is also considered as

Since the sampling order is not important in CS, we reorder the elements of so that it becomes a block diagonal of a smaller size . The transform matrix is also a block diagonal matrix at a smaller size of . The permutation matrix can be divided horizontally into sub-sampling matrices . Note that, each row and column of have only one position of value 1. SRM enables fast sampling and reconstruction and can be interpreted as BCS of a permutated signal. Unlike BCS, each block signal is randomly sub-sampled from the original signal; thus, they are equally important. Even though BSRM reveals no information about the signal via evaluating measurement, using a well-known fast transform significantly reduces the randomness of the sampling matrix. Since the number of sparsifying transform is limited, the attacker can guess the sampling matrix faster. Thus, this work utilizes the block-based GRM random matrix instead. Using GRM adds more complexity to the conventional BSRM but still much faster than fully random matrix with GRM while outperforming reconstruction performance and preserve the democracy. Other frame-based matrices like binary, circulant matrices, chaos method, etc. are out of the scope of this paper.

Fig. 1. Proposed RSRM: random sample of sub-sampled images which are restricted to be low-resolution images.

2.2. Conventional Under-Sampling Methods

Prior to CS, conventional methods to reduce the sampling rate are partial sampling (PS), super-resolution (SR) from single/multiple images, and coded imaging (CI). In PS, a signal is acquired at random locations with or without well-designed patterns. Instead of sampling a high-resolution (HR) signal, low-resolution (LR) signals are captured and recovered missing high-frequency contents by super-resolution. Coded imaging was designed to increase the frame-rate by assigning each frame a coded mask.

At a low subrate, CS also performs poorly, even with a GRM. Therefore, it is straightforward to combine conventional under-sampling methods and CS to further improve sampling efficiency. For CS+PS, the authors [44, 45] captured CS measurements form the partially sampled signal. For CS+SR, the authors [46, 47] sampled multiple LR measurements and performed super resolution-based reconstruction. CS has been combined with CI to improve the temporal imaging in [48]. Our work combines all methods (PS, SR, and CI) into CS, as illustrated in Fig. 1. Firstly, we utilize PS, SR, and CI by capturing multiples LR images with unique random sub-sampling patterns. We, then, acquire CS measurements of each random LR images. Thus, reconstruction from our proposed measurements is equivalent to recovering images from multiple compressed LR measurements.

3. Generalized Sparse Structural Matrix

3.1. Proposed Generalized Sparse Structural Matrix (GSSM)

From the definition of BCS and BSRM, we proposed a generalized sparse structural matrix (GSSM) as

β’ is constructed by concatenating sub-sampling matrices which is generated by selecting random subsets of the identity matrix denote the minimum and maximum number of times a sample in sub-sampling matrices . We stress that, in this paper, we do not consider the extreme case of since it throws away the signal information.

β’ is a block diagonal matrix with sensing matrices

β’ is a block diagonal matrix with sub-sampling matrices which is generated by selecting random subsets of the identity matrix

We interpret GSSM as a two-step sampling of: (i) sub-sample the to-be-sampled signal , then (ii) capture each sub-sampled signal with a corresponding matrix . GSSM measurements can be formulated as

From its definition, GSSM is a generalization of BSRM and BCS with extensions. Firstly, GSSM relaxes the condition in BCS and BSRM to can be a non-square matrix. Secondly, can be any sampling matrix and is not limited to a fast transform as in BSRM. In fact, GRM is selected to preserve democracy. Both BCS and BSRM can be easily derived from GSSM. For BCS, we set to an identity matrix and use the same size ). For BSRM, we use a fast transform matrix for , different sizes of and as a random permutation of the identity matrix

3.2. The RIP Condition of GSSM

In this section, we are going to prove the asymmetric RIP condition of GSSM. From the results of RIP conditions and characteristics of BCS and BSRM, we aim for the conditions to achieve the best RIP of GSSM.

for sparse signals , with a restricted isometry constant , then GSSM matrix defined in eq. (6) satisfies the asymmetric RIP condition

for all sparse signals denotes the sparsity of the sub-sampled signal In eq. (19), the value are the minimum and maximum number of times a sample in is selected in the set , respectively, which are defined as

where denotes the -th row and -th columns of sub-sampling matrix The extreme case of considered as it throws away the signal information.

satisfies RIP for sparse signals, it also satisfies RIP for all with the isometric constant From eq. (6), the energy of the GSSM observation is

Using eq. (11) and taking the summation of inequalities of the RIP conditions of , we obtain

By defining eq. (12) becomes

In addition, each sub-sampled signal consists of randomly selected samples from samples of . Thus, for random sub-sampling, one sample can be selected multiple times. From eq. (10) and

where represent the -th element of . The summation for all location from eq. (14) can be taken as

Alternatively, the energy of sub-sampled signal

This is because randomly selected samples from the identity matrix , and each row has only one value of 1. From eq. (15) and (16), we have

As , eq. (14) becomes

By replacing this equality in eq. (13), we have

By dividing all inequality to the non-negative value q, eq. (19) becomes eq. (9).

Therefore, the sensing matrix

that satisfies with the restricted isotropy . GSSM satisfies the traditional RIP at

3.3. Analysis of the RIP Condition of GSSM

From the RIP condition in Section 3.2, GSSM does not guarantee the asymmetric RIP condition for all signals in dimension (but for all -sparse signal with This condition can be satisfied for (i) a very sparse signals with , (ii) or distributed/structured sparse signals so that we can design the random selection . While it is straight forward for the first case, the second case is held for structure sparse images (i.e. block sparse, structure sparse in DCT, DWT).

In this section, we aim to design an instance of GSSM (i.e., design ) to achieve better RIP condition. In order to do so, the targeted GSSM matrix should satisfy the following conditions:

S1 β Small RIP range. From Eq. (19), at a given , GSSM achieves the smallest RIP range at visualized in Fig. 2, and also satisfy the conventional RIP condition. This means, each sample of signal is equally and selected number of times. We can observe that both BCS and BSRM satisfy this condition at the special case of . However, our GSSM does not limit to this special case. It should be noted that, from the definition of GSSM, we do not consider the case of as it throws away signal information.

Fig. 2. Illustration of the RIP range of GSSM matrix. The smaller RIP range, the better RIP condition.

. To achieve a small value of should satisfy RIP with a small restricted isometric . In addition, depends on the sparsity of signal is the sparsity of signal ) as well as the size of sampling matrix . In general, a smaller sparsity level requires less measurement

(i.e., smaller ) for perfect reconstruction. However, the sparsity level is unknown at the sampling. Therefore, the best solution to achieve S2 is

β’ (S2A) Equal size of (by setting ) and large block size

β’ (S2B) Equal sparsity level (by designing the sub-sampling set

4. Restricted Structural Random Matrix

Regarding these RIP criteria, BCS satisfies S1 and S2A and BSRM satisfies S1 only. BCS uses the same block

size of the sampling matrix

, thus satisfies S2A. BSRM captures signals of size by a sampling matrix ; these are likely to have different sizes due to their random generation. As a result, BSRM does not satisfy S2A. Selecting samples from the non-overlapping window in BCS or fully random samples in BSRM might meet the S2B condition for some types of signals but not for all. For random sparse signals, how to perform sub-sampling does not matter much due to the randomness. However, for compressible or structure random signal with the smoothness prior, there is possible to design sub-sampling set to achieve an equally sparse level

Thus, we unify the advantages of both BCS and BSRM as β’ S1: design to satisfy (like BCS and BSRM) to have better RIP and satisfy the traditional RIP.

β’ S2A: use the same size for each block (like BCS)

β’ To preserve security, is randomly generated (like BSRM)

However, further development is required since neither BCS nor BSRM satisfy the S2B condition.

4.1. Design Matrix πΉ

4.1.1. Restricted Random Permutation with the Global Smoothness Prior

To satisfy S2B, we designed the matrix so that the sub-sampled signals have a small and equally sparsity level. In order to do so, the smoothness prior, existed in many signals like compressible, structure sparse, etc., was utilized. For instance, in block-sparse signal, if a location has a non-zero value, then its nearby locations most likely to have non-zero values. In compressible signals, nearby samples are also highly correlated. In this work, we, however, utilized the smoothness prior in a global manner. That is, LR instances of compressible, structure sparse signals are highly correlated, equally in energy, and similar sparsity level.

Therefore, we restricted the sub-sampling matrix to output sub-sampled signal as a random LR instance of the input signal to enforce similarity in structure among . For the special case of and design operators as shown in Fig. 3 and Algorithm 1. Notation randperm() and reshape() are functions for random permutation and reshaping, respectively. We referred this sub-sampling method as the restricted random permutation (RRP) as the input signal is permutated to create random LR instances. Our RRP matrix can be represented in terms of a binary matrix or a random integer vector of . To show the advantage of RRP over the block-by-block selection in BCS, and random permutation in BSRM, the sub-sampled instances of various signal types are visualized in Fig. 4.

For random sparse signals, there is no difference between sub-sampling methods due to the randomness of the non-zero value locations. Block-by-block sub-sampling in BCS can exploit the sparsity in the compressible signals but the sparsity level in each sub-sampled signal is likely different. Additionally, BCS is inefficient for the block-sparse signals as we have three very sparse and a very dense sub-sampled signal, thus poor S2B condition. Random permutation (RP) in BSRM can handle block-sparse signals but completely destroy the structure of compressible signal (thus not satisfy S2B for compressible signal). Our restricted random permutation preserves the structure of both compressible and block-sparse signals. Thanks to the global smoothness prior, the sub-sampled signals of RRP are highly correlated, thereby, result in a similar sparsity level for block-sparse and compressible signals in the transform domain.

Fig. 3. Illustration of Restricted Random Permutation in Algorithm 1 with signal dimension of block size

4.1.2. Multiple Restricted Random Permutation, π > π/ππ΅ or p=q>1

It is well-known that the larger block-size is, the sparser signal is, the better RIP condition and reconstruction performance can be achieved [14, 15]. Both BCS and BSRM, however, limit to the relationship . Therefore, the large can benefit RIP condition of each sampling matrix , but also result in a small number of sub-sampled signals which leads to a higher chance to waste measurements. As the to-be-sampled signal is unknown, we capture each sub-sampled signal with the same number of measurements the worst case of block-sparse signal in Fig. 4, BCS could waste measurements to captures zero-level sparse signal, while not spending enough measurement to capture the dense signal.

Fig. 4. Sub-sampled signals of block-by-block (in BCS), random permutation (in BSRM) and restricted random permutation (in RSRM).

Random permutation in BSRM and restricted random permutation seems to work well for all types of signals. However, there is a higher possibility of measurements waste at the large (or small ). That is, unluckily, we can partition sub-sampled signals to have very sparse or very dense. Thus, one-time division to multiple sub-sampled signal one time (i.e. ) might not be enough to guarantee the S2B. In fact, the RIP condition only requires not the special case of (as in BCS and BSRM). By using , we sub-sampling the whole signal multiple times and avoid the worst scenario of measurement waste for all types of signals. As visualized in Fig. 5, for block-sparse signal, the first RRP results in a sub-sampled signal that much sparser than the others. The second RRP, however, selects a different set of sub-sampled signals thus avoid wasting measurements.

This is very important because we do not assume the structure of signal in advanced. Multiple RRPs are used to have large block size for better performance and large to prevent the worst case of wasting measurement.

4.2. Design Matrix π±

Since is a block diagonal matrix, its local operator can be difference in the Distinct Block Diagonal (DBD) or identical in the Repeated Block Diagonal (RBD) [6]. We can represent these matrices as a combination of . DBD is achieved by using different sets of random matrices and sub-sampling RBD is achieved by using the same As reported in [6], DBD shows a better RIP condition than RBD as well as better reconstruction performance at a cost of higher complexity and storage of multiple random matrices . Additionally, is designed as orthogonal to save the complexity of matrix multiplication and captures signal more efficiently.

In this work, we proposed a new type diagonal matrix of Restricted Distinct Block Diagonal matrix (RDBD) which is a hybrid combination of DBD and RBD. Our RDBD uses each matrix multiple times. It requires significant less distinct block than DBD to reduce complexity. As example in Fig. 5, RBD requires one matrix , DBD demands four matrices, but our RDBD needs only two matrices. To maintaining high quality, we should design the random selection matrix accordingly.

Fig. 5. Comparison of various types of block matrices , same colour means same matrix and vice versa.

4.3. Design Matrix π«

Utilize all orthogonal random vector of can benefit the measurement to capture different signal information. Therefore, we designed as RRP matrix but with the diagonal version of Algorithm 1 as shown in Fig. 5. Each set of corresponds to a distinct orthogonal random matrix . Thus, we can reduce the number of distinct random matrix in comparison with the RDBD framework. Additionally, at a special case of very similar sub-sampled signals , our method corresponds to capture a low-resolution image at much higher subrate. This is equivalent to favoring the low-frequency prior in [24] where authors tried to capture low-resolution images at higher subrate. However, our proposed method can favor low-frequency prior without sacrificing democracy and high-frequency contents.

4.4. Proposed Restricted Structural Random Matrix (RSRM)

This section summarizes our proposed method, which is named to as the restricted structural random matrix (RSRM).

We can interpret RSRM as a two-step sampling process, as described in Fig. 1: (i) generate multiple random low-resolution signals and then (ii) sample each with the same number of measurements. The algorithm is given in Algorithm 2. RSRM benefits form the large block size and large number of sub-sampling to prevent the measurement waste. In addition, RSRM has lower complexity than fully random GRM, slightly more complexity than BCS, slightly less than BSRM with GRM structure. High reconstruction performance is also reported in the experimental results. Meanwhile, the restricted random permutation preserves the democracy property. We visualized the RSRM at the special case of 1 (RSRM1) in Fig. 6. We can observe four distinct brands corresponding to four sub-sampling signals. RSRM1 and BSRM sampling matrices appear more random than BCS.

Fig. 6. Visualization of various sampling matrices ( ) at signal dimension and block size The randomness is observed in CS, BSRM, and RSRM. BCS is very sparse outside the diagonal, thereby, later reveals the signal energy.

4.5. RSRM with Kronecker Compressive Sensing for High Dimensional Signal and Reconstruction

At large block size , RSRM might still demand high complexity and storage, especially for high dimensional

signals like images and videos. Thus, we incorporated RSRM to separable sampling. We used two RSRM matrices for vertical and horizontal sampling. We used group sparse representation (GSR) [41] to represent image as

where denote the group dictionary and group sparse coefficients, respectively. Utilizing the group sparsity as the cost function , the restoration of KCS is given as

where is a 2D representation of 1D signal via a vectorized function as denotes the Frobenious norm. Similar to [9], we use split Bregman optimization to divide and solve Eq. (21).

Table 2. Comparison between CS, BCS, SRM, and RSRM at image size and block size

5. Experimental Results

5.1. Evaluation of the RIP Condition

This section evaluates the RIP conditions of CS, BCS, BSRM, and RSRM at (RSRM1). All sampling matrices are derived from GSSM with the configuration in Table 2 and GRM is used as the sampling matrix Similar to [6], we count the number of sensing matrices that satisfy the RIP condition at a given 1000 signals . The signals are random sparse, block-structure sparse [39], and compressible signals. The results are shown in Fig. 7, 8, and 9. Each subfigure contains 10 plots: one for CS (black) and three plots each for BCS (blue dash), BSRM (green dotted dash), and RSRM1 (red solid line) at different block sizes of 128, 256, and 512. We use the location of the plot to distinguish between plots; plots that are closer to the top left have a larger block size . In general, the greater the number of measurements , the better the RIP condition.

5.1.1. Random Sparse Signals

We generated 1000 sparse signals with the sparse level of by assigning a non-zero value for random locations. Since the non-zero is random, the difference in the sparsity level between sub-samples becomes less at larger s. Therefore, the sub-sampling method plays little role. All methods BCS, BSRM, and RSRM1 are likely to satisfy S2B for relatively less sparse signals (i.e., large ) as their RIP gaps are shorted in comparison with RIP condition of fully random GRM (CS). Satisfying S2A condition, BCS and RSRM1 were expected to show better RIP condition than BSRM. At , the order of decreasing RIP conditions is CS, BCS, RSRM1, and BSRM. In fact, RSRM1 shows almost identical performance to BCS at 6 , 128. However, at , RSRM1 even shows a similar RIP condition to fully random CS. In general, RSRM1 has better RIP condition than both BCS and BSRM for all block sizes and measurements.

Fig. 7. Percentages of matrices of BCS, BSRM, and RSRM1 that satisfy RIP for all random sparse signals of size

versus isometric constant . The sparsity level is s = 16 and 32 in the first and second rows, respectively. The number of measurements is in the first, second, and third columns, respectively. The curve towards the top left shows the better RIP condition.

5.1.2. Block-Sparse Signals

In block-sparse signals, non-zero values are located in a few non-overlapping blocks [39]. This section generates block-sparse signals at sparsity levels with a block-sparse size of 256 and a block sparsity level of 2. That is, we generate s non-zero values located in two random blocks of size 256 and left the other two blocks all zero. BCS fails to satisfy S2B as one of its sub-sampled signals has zero sparsity level, . With a random permutation, the sub-sampled signals in BSRM are less likely to has than BCS. Our RSRM1βs sub-sampled signals are not only block sparse but also likely to have similar sparsity level, thus offers better RIP, especially at small measurement and small block size . This argument also agreed with the conclusion for BCS in [6].

5.1.3. Compressible Signals

In practice, compressible signals (e.g., audio, images, and video) are very common. Additionally, we can always approximate a compressible signal -sparse signal in a given sparsifying domain [40], like DCT and DFT. This section generated 1D compressive signals by extracting random rows and columns of test sequences in conventional video coding standards: Cactus, Kimono, and QBTerrace. Compressible signals have strong smoothness prior so that the block signals in BCS are also compressible and can be approximated with the sparsity level . However, the sparsity level between these block signals is likely different. The adaptive BCS scheme was proposed to take advantage of the different sparsity levels [38]. Unfortunately, the sparsity level is unknown in the sampling stage. Alternatively, BSRM destroys the smoothness prior of the signal due to the random selection, especially at small . Meanwhile, RSRM1 preserves signal structures thanks to the smoothness prior and produces a better RIP condition than BCS and BSRM, especially at the small block size and measurement rate

Fig. 8 Percentages of matrices (BCS, BSRM, and RSRM1) that satisfy the RIP condition (for all 1000 block-sparse signals of size 102 , block-sparse size = 256, block sparsity = 2) versus the isometric constant at various measurements (left to right 128) and various block sizes

Fig. 9 Percentages of matrices (BCS, BSRM, and RSRM1) that satisfy the RIP condition for all compressible signals of size block-sparse size = 256, and block sparsity = 2, versus the isometric constant at various measurements (left to right and block size

5.2. Evaluation of the Security/Democracy

5.2.1. Evaluate Secured Measurements

With the restricted random permutation, each sub-sampled signal in RSRM is an LR version of the original signal with equal energy. Also, the structure of signals is also preserved in the LR images. Additionally, each block is sampled with a GRM matrix. Therefore, there is no measurement loss and measurements of RSRM are also equally important. Fig. 12 demonstrates the correlation between nearby measurements. There is a strong correlation between the nearby pixels in the spatial domain but not the measurement domains. Also utilizing signal prior, but RSRMβs observations are less correlated than the multi-scale sampling with MR-KCS. In Fig. 13, while low-frequency are easily located in MRKCS, no visible difference is shown in the other sampling scheme. Additionally, by evaluating the energy of each block measurement, an LR image is revealed in the BCS scheme.

Fig. 12 Correlation between to nearby pixels/measurements Lena at subrate 0.1 in spatial and compressed domains.

Table 3. Storage requirement of various matrices for image of size 256Γ256, subrate 0.25,

5.2.2. Complexity of Sampling Matrices

The complexity of sampling matrices is evaluated in terms of storage requirements. As in Table 3, the float parameter represents the size of the random matrix and binary parameter represent the size of the permutation matrices . At subrate = 0.25, RSRM required only 0.25Γ2562 float parameters, similar to BCS and less than BSRM. All frameworks (BCS, BSRM, RSRM) used the same size of matrix but, RSRM demanded little storage for matrix . The larger number is, the more storage is required. However, the increment storage for (in binary) is much smaller than that of the matrix (in floats) and still significant less than the fully random CS. On the other hand, the separable sampling scheme greatly reduces the complexity of the conventional frame-based sensing. Also, RSRM only slightly increases complexity for the binary matrix in comparison with BCS and BSRM.

We also evaluate the complexity of the sensing operation and reconstruction in terms of the number of additions and multiplication for the sampling operation The conventional frame-based CS requires and multiplications to captures measurements. As are determined binary matrices, they can be implemented without matrix multiplication (i.e., pre-select/rearrange sampling matrices and signals). Therefore, all other matrices BCS, BSRM, and our RSRM requires additions and multiplications for acquisition. Our RSRM at only adds more storage but maintain the same computational complexity as BCS and BSRM, regardless the value

It should be noted that the BSRM for comparison is BSRM with diagonal GRM matrix. The conventional BSRM in the original work [12] requires fewer complexity thanks to the fast transform. It only needs to store a transform matrix of 128Γ128. The matrix multiplication is also faster with a fast transform. Therefore, our RSRM would have little more storage requirement with the same computation as BCS and BSRM with GRM but little more complex than BSRM with a fast transform. In exchange, RSRM can preserve democracy property.

Fig. 13 Measurements of various sampling schemes at subrate 0.1. BCS measurement are captured at block size 8Γ8, 100 (over 102) measurements at each block is reshaped to 10Γ10 measurement block and concatenated to form the larger image.

5.2.3. One-Time Sensing with Triple Level Protection

Even though CS measurements reveal the signal energy, it enables computational security at a certain level with low power complexity which is essential for resource-constrained applications like (visual) sensor network. By treating the measurement matrix as the security key, sampled signal as the plaintext, and compressed measurements as ciphertext [32-34, 50]. Sensing matrix and measurements are sent to the receiver through a private and public channel, respectively. In this scenario, attackers can perform a plain attack [33] (i.e., manipulate input and capture the corresponding output). Since CS is a linear sampling technique, attackers can guess the sensing matrix after a certain amount of time. In this regard, the best security system is one-time sampling [33] by changing and resending the sampling matrices frequently. This approach, however, causes significant overhead over the private channel. Bilevel protection [36] is proposed to reduce the transmission overhead by using both a sensing matrix and a sparsifying basis as primary keys. The sparsifying matrix is very limited to a few bases like DCT, DWT, etc. In our RSRM, we use as primary keys to provide triple-level protection. Changing the binary matrices instead of significantly reduces the overhead over the private channel. Note that, even though is restricted to random LR sub-sampling, the number of possible spaces for is still significantly large, especially for high dimensional signal and large block size. For instance, if , then there is possible combination of

Fig. 14. PSRN [dB] of RSRM-KCS over KCS at various for the first, second, and last rows, respectively.

Enabling simultaneous sampling, compression, and security, CS enables very low power and simple linear encoder, thus, becomes very attractive for the Internet of Things (IoT) applications [49, 50]. Additionally, the low computation capacity of IoT devices cannot handle a very large sampling matrix, thus block-based and structure frame-based sensing is favored.

However, further simplicity comes with the cost of reducing reconstructed image quality as well as compromise the security property. Fortunately, with our RSRM framework, reconstruction quality can be further improved without compromise security property at a cost of little extra complexity. Additionally, by pre-rendering multiple sets of a completed of restricted permutation matrices , or utilizing circulant structure. Instead of sending the sampling matrix , we can send the indexes of matrices (already known in both encoder and decoder) to further reduce transmission overhead.

5.3. Reconstruction Performance of RSRM

This section presents the βPSNR [dB] results of the proposed RSRM under Kronecker sampling (KCS-RSRM) in comparison with the conventional KCS with GSR reconstruction (KCS-GSR) shown in Fig. 8. Surprisingly, our KCS-RSRM outperforms KCS-GSR using the same GSR reconstruction, especially at low subrate.

5.3.1. Block size ππ΅

Similar to 1D experiments, the performance improves as the size of increases. In general, RSRM shows the best gain at a large block size , with up to 2.1 dB gain in Cameraman at a subrate 0.25. However, there is an exception for a very small subrate. At a subrate of 0.05, RSRM shows a significant PSNR gain at smooth and complexly textured images (Lena, Peppers, and Cameraman, except Barbara which has strong local smoothness. We select as the best solution as RSRM shows gains for all test images.

5.3.2. Number of sub-sampled signals π = πππ΅/π and π = π = π

As RSRM does not limit to . We evaluate . At block size , number of sub-sampling blocks is . A larger value of is preferred to prevent the worst case of the measurement waste for the block-sparse and compressible signals. However, a large value leads to smaller number of measurements for each , which subsequently affects the RIP condition of . Fig. 14 shows that increasing the value of leads to better performance, especially at a high subrate. However, increasing the size of also results in larger , which creates more complexity. We select for our RSRM.

5.4. Comparison with State-of-the-Art Sensing Schemes

We used RSRM under the KCS with and GSR reconstruction (named KCS-RSRM) is compared with state-of-the-art algorithms: multiple-scale BCS (MH-BCS [23]), BCS with GSR recovery (BCS-GSR [40]), KCS with GSR recovery (KCS-GSR) [11], and recent deep learning BCS frameworks with DR2Net [42] and CSNet [43].

As in Table 3, KCS-RSRM produces the best PSNR performance compared with other reconstruction schemes, especially at low subrate. Surprisingly, KCS-RSRM even improves the results by 0.78 dB in average compared to KCS-GSR (which uses GRM as the sampling matrix, same reconstruction) with up to 3.09 dB gain at a low subrate of 0.01 for the Lena, and 1.08 at high subrate 0.03 for the Cameraman. For a structure image (like Barbara) or a very smooth signal (like Peppers), KCS-RSRM produces an average gain of 0.5 dB. Compared to recent deep-learning methods, KCS-RSRM offers better performance for complex images (e.g., Lena), images with a strong local structure (e.g., Barbara), highly compressible images (e.g., Cameraman), and smooth images (e.g., Peppers). As CSNet joints trained sampling and reconstruction at a corresponding subrate, its sampling matrix tends to capture more low-frequency information which is similar to exploit low-frequency prior in the multi-scale sampling scheme. With the external deep-learning prior, CSNet shows better reconstruction for the Mandrill, Boats, Goldhill, and Man images.

From Fig. 14 and Fig. 15, KCS-RSRM demonstrates the best visual quality. We also can observe that CSNet favors low-frequency images and experiences losses in high-frequency content. The reconstruction results of CSNet are blurred at the edges and in textured areas. Alternatively, KCS-RSRM is able to reconstruct sharp edges and structured areas (e.g., Lenaβs hair and Barbaraβs neck) better than KCS-GSR.

5.5. Discussions and Future Work

Despite showing the asymmetric RIP condition of GSSM for , this work mainly evaluated the special case of . By doing so, all samples are equally important, thus preserve democracy property. However, the current RSRM framework is single-scale sampling which can be extend to multi-scale. That is, we could consider important samples (i.e., edges, texture) more often than the others, thus results in the case of . The multi-scale version of RSRM can further improve the reconstruction quality but at a cost of compromise democracy property. This extension is out of the scope of this paper and left for the future work.

Fig. 15. Visual quality comparison of various sampling schemes for the Barbara image at subrate 0.1.

As a generalized form BCS and BSRM, and simplified of frame-based sensing, our proposed sampling matrix RSRM could be used anywhere that those techniques are applicable. Firstly, it is true that we cannot visit the signal multiple times in practice, thereby difficult to choose the pixels to process. We design as a set of restricted random permutations given the signal dimension and block size, and regardless the signal structure. Additionally, this is not the drawback of our method only but a well-known problem of CS. CS is a sequential sampling scheme, i.e. measurements are captured sequentially. Thus, implementation of the CS system for practical applications remains challenging, especially for fast-changing signals. On the other hand, the dimension of the to-be-sampled signals is assumed for the implementation. The signal resolution is defined by the resolution of the digital micromirror device (DMD) in the single-pixels camera [37], by the resolution of the coded pattern in the lensless imaging [55]. Therefore, it is straight forward to implement our RSRM to existing CS framework.

In single pixel-camera, we can pre-define locations of random LR images, then redirect the DMD at the corresponding locations to the corresponding multiple single-pixels. Each single-pixel captures measurements of a random LR image. This is for the case of with a single RRP. For the case of multiple RRP, multiple light splitters can be used with multiple DMDs and multiple single-pixels. Therefore, similar to BCS, RSRM enables parallel acquisitions to reduce sampling time. On the other hand, we also can implement RSRM under lensless imaging [55] system. We can sequentially capture measurements of each random LR image β specified by the coded pattern. As conventional lensless imaging is also sequential sampling, using our RSRM matrix results in the same acquisition time.

According to [50], our framework can be applied for image/video and audio security as well as outsourcing security over the cloud [51]. While many applications are considered compressive sensing for security applications only where the signal is known, our approach is considered the security during the sampling process which is closer to physical level security and/or camera side security [56]. More details analysis on the security applications as well as further advance the storage requirement with circulant structure of are left for future work.

6. Conclusion

In this work, we proposed a novel restricted structurally random matrix (RSRM) that combines the advantages of block-based and structured frame-based frameworks and utilizes the global smoothness prior. Our RSRM offers a better RIP conditions than BCS and BSRM for various types of signals, including random sparse, block-sparse, and compressible. Especially for compressible signals, RSRM even improves the sampling efficiency over the fully random matrix and produce comparable performance with the state-of-the-art deep learning-based method without sacrificing the democracy. Additionally, RSRM also has the potential of reducing the bitrate overhead for CS-based IoT security systems.

Acknowledgement

The authors would like to thank Dr. Trinh Van Chien for his thoughtful comments and Dr. Wuzhen Shi for making his source codes available for comparison. This work is supported in part by the National Research Foundation of Korea (NRF) grant (2017R1A2B2006518) funded by the Ministry of Science and ICT.

References

[1]. E. J. Candes and M. B. Wakin, βAn introduction to compressive sampling,β IEEE Signal Processing Magazine, vol. 25, no. 2, pp. 21β30, Mar. 2008.

[2]. D. L. Donoho, βCompressed sensing,β IEEE Trans. Info. Theo., vol. 52, no. 4, pp. 1289β1306, Apr. 2006.

[3]. J. Romberg, βImaging via compressive sampling,β IEEE Sig. Process. Mag., vol. 25, no. 2, pp. 14β20, Mar. 2008.

[4]. S. Foucart and H. Rauhut. A Mathematical Introduction to Compressive Sensing. Springer Birkhauser Basel, 2013.

[5]. L. Gan, βBlock compressed sensing of natural images,β in Inter. Conf. Digital Sig. Process., pp. 403 β 406, Jul. 2007.

[6]. J. Y. Park, H. L. Yap, C. J. Rozell, and M. B. Wakin, βConcentration of measure for block diagonal matrices with applications to compressive signal processing,β IEEE Trans. Sig. Process., vol. 59, no. 12, pp. 5859β5875, Dec. 2011.

[7]. K. Q. Dinh, H. J. Shim, and B. Jeon, βSmall-block sensing and larger-block recovery in block based compressive sensing of images,β Signal Process.: Image Comm., vol. 55, pp. 10 β 22, Mar. 2017.

[8]. M. F. Duarte and R. G. Baraniuk, βKronecker Compressive Sensing,β IEEE Trans. Image Process., vol. 21, no. 2, pp. 494 β 504, Feb. 2012.

[9]. T. N. Canh, K. Q. Dinh, and B. Jeon, βTotal variation reconstruction for Kronecker compressive sensing with a new regularization,β in Picture Coding Symp., pp. 261β264, Dec. 2013.

[10]. T. N. Canh, K. Q. Dinh, and B. Jeon, βCompressive sensing reconstruction via decomposition,β Signal Process.: Image Comm., vol. 49, pp. 63β78, Nov. 2016.

[11]. T. N. Canh and B. Jeon, βGroup sparse representation for Kronecker compressive imaging,β in Conf. Image Process. Image Under., Feb. 2016.

[12]. T. T. Do, L. Gan, N. H. Nguyen, and T. D. Tran, βFast and efficient compressive sensing using structurally random matrices,β IEEE Trans. Sig. Process., vol. 60, no. 1, pp. 139 β 154, Jan. 2012.

[13]. W. Guo, J. Qin, and W. Yin, βA new detail-preserving regularization scheme,β SIAM J. Imaging Sci., vol. 7, no. 2, pp. 1309β 1334, Jan. 2014.

[14]. W. Yin, S. Morgan, J. Yang, and Y. Zhang, βPractical compressive sensing with Toeplitz and circulant matrices,β in SPIE Visual Comm. Image Process., vol. 7744, pp. 77440K, 2010.

[15]. Y. Dong, J. Sun, and S. Wang, βSparse block circulant matrices for compressed sensing,β IET Comm., vol. 7, no. 13, pp. 1412 β 1418, Sep. 2013.

[16]. S. Mun and J. E. Fowler, βDPCM for quantized block based compressed sensing of images,β in Proc. Euro. Sig. Process. Conf., pp. 1424 β 1428, Aug. 2012.

[17]. L. Wang, X. Wu, and G. Shi, βBinned progressive quantization for compressive sensing,β IEEE Trans. Image Process, vol. 21, no. 6, pp. 2980β2990, Jun. 2012.

[18]. K. Q. Dinh, H. J. Shim, and B. Jeon, βMeasurement coding for compressive imaging using a structural measurement matrix,β in IEEE Inter. Conf. Image Process., pp. 10 β13, Sept. 2013.

[19]. X. Gao, J. Zhang, W. Che, X. Fan, and D. Zhao, βBlock based compressive sensing coding of natural images by local structural measurement matrix,β in Data Compress. Conf., p. 133β142, Apr. 2015.

[20]. Y. Tsaig and D. L. Donoho, βExtensions of compressed sensing,β J. Sig. Process., vol. 86, no. 3, pp. 549β571, Mar. 2006.

[21]. J. Y. Park and M. B. Wakin, βA multiscale framework for compressive sensing of video,β in IEEE Pict. Coding Symp., pp. 197β200, May 2009.

[22]. J. E. Fowler, S. Mun, and E. W. Tramel, βMultiscale block compressed sensing with smoothed projected Landweber reconstruction,β in EURO Sig. Process. Conf., pp. 564β568, Aug. 2011.

[23]. B. Adcock, A. C. Hansen, C. Poon, and B. Roman, βBreaking the coherence barrier: A new theory for compressed sensing,β arXiv preprint arXiv:1302.0561, 2013.

[24]. T. N. Canh, K. Q. Dinh, and B. Jeon, βMulti-scale/multiresolution Kronecker compressive imaging,β in IEEE Inter. Conf. Image Process., pp. 2700β2704, Sept. 2015.

[25]. Y. Li, A. C. Sankaranarayanan, L. Xu, R. Baraniuk, and K. F. Kelly, βRealization of hybrid compressive imaging strategies,β J. Opt. Soc. America A, vol. 31, no. 8, pp. 1716 - 1720, Aug. 2014.

[26]. T. N. Canh, K. Q. Dinh, and B. Jeon, βHybrid Kronecker compressive sensing for images,β in IEEE Inter. Conf. Advanc. Tech. Comm., pp. 554β558, Oct. 2014.

[27]. H. Lee, H. Oh, S. Lee, and A. C. Bovik, βVisually weighted compressive sensing: measurement and reconstruction,β IEEE Trans. Image Process., vol. 22, no. 4, pp. 1444 β 1455, Apr. 2013.

[28]. K. Q. Dinh, T. N. Canh, and B. Jeon, βCompressive sensing of video with weighted sensing and measurement allocation,β in IEEE Inter. Conf. Image Process., pp. 2065β2069, Sept. 2015.

[29]. S. H. Safavi and F. T. Azar, βCube-based perceptual weighted Kornecker compressive sensing: can we avoid non-visible redundancies acquisition?β J. Visual Comm. Image Repres., vol. 49, pp. 338 β 350, Nov. 2017.

[30]. J. N. Laska, P. T. Boufounos, M. A. Davenport, and R. G. Baraniuk, βDemocracy in action: Quantization, saturation, and compressive sensing,β J. Appl. Comp. Harm. Anal., vol. 31, no. 3, pp. 429 β 443, Nov. 2011.

[31]. H. C. Huang and F. C. Chang, βError resilience for compressed sensing with multiple-channel transmission,β J. Inf. Hiding and Multimedia Sig. Process, vol. 6, no. 5, pp. 847β856, Sep. 2015.

[32]. V. Cambareri, M. Mangia, F. Pareschi, R. Rovatti, and G. Setti, βOn Known-plaintext attacks to a compressed sensing-based encryption: a quantitative analysis,β IEEE Transactions on Information Forensics and Security, vol. 10, no. 10, pp. 2182β 2195, Oct. 2015.

[33]. T. Bianchi, V. Bioglio, and E. Magli, βAnalysis of one-time random projections for privacy preserving compressed sensing,β IEEE Transactions on Information Forensics and Security, vol. 11, no. 2, pp. 313β327, Feb. 2016.

[34]. V. Cambareri, M. Mangia, F. Pareschi, R. Rovatti, and G. Setti. Low-complexity multiclass encryption by compressed sensing. IEEE Transactions on Signal Processing, 63(9):2183β2195, May 2015.

[35]. R. Fay, βIntroducing the counter mode of operation to compressed sensing-based encryption,β Info. Process. Letters, vol. 116, no. 4, pp. 279 β 283, Apr. 2016.

[36]. L. Zhang, K. W. Wong, Y. Zhang, and J. Zhou, βBilevel protected compressive sampling,β IEEE Trans. Multimedia, vol. 18, no. 9, pp. 1720β1732, Sept. 2016.

[37]. M. Duarte, M. A. Davenport, D. Takbar, J. N. Laska, T. Sun, K. F. Kelly, and R. G. Baraniuk, βSingle-pixel imaging via compressive sampling,β IEEE Sig. Process. Mag., vol. 25, no. 2, pp. 83β91, Mar. 2008.

[38]. Q. H. Nguyen, K. Q. Dinh, V. A. Nguyen, C. V. Trinh, Y. Park, and B. Jeon, βRate allocation for block-based compressive sensing,β J. Broadcast Engineering, vol. 20, no. 3, pp. 398-407, Mar. 2015.

[39]. Y. C. Eldar, P. Kuppinger, and H. Bolcskei, βBlock-sparse signals: Uncertainty relations and efficient recovery,β IEEE Trans. Sig. Process., vol. 58, no. 6, pp. 3042 β 3054, Jun. 2010.

[40]. A. Cohen, W. Dahmen and R. DeVore, Compressed sensing and best k-term approximation,J. Amer. Math. Soc., vol 22, pp. 211-231, 2009.

[41]. J. Zhang, D. Zhao, and W. Gao, βGroup-based sparse representation for image restoration,β IEEE Trans. Image Process., vol. 23, no. 8, pp. 3336 β 3351, Aug. 2014.

[42]. H. Yao et al., βDR2Net: Deep Residual Reconstruction Network for Image Compressive Sensing,β [online] at arXiv:1702.05743, 2017.

[43]. S. Wuzhen et al., βDeep network for compressed image sensing,β in IEEE Inter. Conf. Mult. Expo, pp. 877-882, 2017.

[44]. T. N. Canh and B. Jeon, βSpatially scalable Kronecker compressive sensing of still images,β IEIE Trans. Sig. Process., vol. 52, no. 10, pp. 1838 β 1848, Oct. 2015.

[45]. J. Yang, W. E. I. Sha, H. Chao, and Z. Jin, βAn adaptive random compressive partial sampling method with TV recovery,β Springer Applied Informatic, 2016.

[46]. W. Saafin, M. Vega, R. Molina, and A. K. Katsggelos, βImage super-resolution from compressed sensing observations,β in IEEE Inter Conf. Image Process., pp. 4268 β 4272, Sept. 2015.

[47]. T. N. Canh, K. Q. Dinh, and B. Jeon, βMulti-resolution Kronecker compressive imaging,β IEIE Trans. Smart Process. Computing, vol. 3, no. 1, pp. 19 β 27, Nov. 2014.

[48]. T.H. Tsai, P. Lull, X. Yuan, L. Carin, and D. J. Brady, βCoded Aperture Compressive Spectral-Temporal Imaging,β Imaging and Applied Optics, 2015.

[49]. Y. Zhang, Y. Xiang, and L. Yu, Secure compressive sensing in multimedia data, cloud computing and IoT, SpringerBriefs in Signal Processing, 2019.

[50]. Y. Zhang, Y. Xiang, L. Y. Zhang, Y. Rong, and S. Guo, βSecure Wireless Communications Based on Compressive Sensing: A Survey,β IEEE Communications Surveys & Tutorials, vol. 21, no. 2, 2019.

[51]. L. Yu, J. P. Barbot, G. Zheng, and H. Sun, βCompressive sensing with chaotic sequence,β IEEE Signal Processing Letters, vol. 17, no. 8, Aug. 2010.

[52]. C. Wang, B. Zhang, K. Ren, and J. M. Roveda, βPrivacy-assured outsourcing of image reconstruction service in cloud,β IEEE Trans. Emerg. Topics Comput., vol. 1, no. 1, pp. 166β177, Jun. 2013.

[53]. J. D. Blanchard, C. Cartis, and J. Tanner, βCompressed Sensing: How sharp is the restricted isometry property?β, SIAM Review, vol. 53, no. 1, pp. 105 β 125, 2011.

[54]. M. Chiani, A. Elzanaty, A. Giorgetti, βAnalysis of the Restricted Isometry Property for Gaussian Random Matrices,β IEEE Global Communications Conference, 2015.

[55]. G. Huang, H. Jiang, K. Matthews, and P. Wilford, βLensless imaging by compressive sensing,β IEEE International Conference on Image Processing, 2013.

[56]. T. N. Canh and. H. Nagahara, βDeep Compressive Sensing for Visual Privacy Protection in FlatCam Imaging,β Proc. IEEE International Conference on Computer Vision Workshops, 2019.