# RIP Sensing Matrices Construction for Sparsifying Dictionaries with Application to MRI Imaging
## 5 Experimental Results  
### Sensing Matrix of Sparsifying Dictionaries  
Experiments were conducted to assess the sensing matrix derived based on the dictionary factorizations proposed in Section 3 for CDF 9/7 wavelets and dictionaries derived via K-SVD, for which synthetically generated univariate sparse signals are then shown to be recoverable with the guarantees of Theorem 2. The entries of \(A\in\mathbb{R}^{l\times n}\) are i.i.d. Bernoulli random variables (where \(\pm\frac{1}{\sqrt{n}}\) with equal probability) and Gaussian random numbers (where \(\mathcal{N}(0,n^{-1})\)). \(D\) and \(A\) have equal ranks. Experiments were performed on sparsifying dictionaries of \(\mathbb{R}^{128\times 1024}\), including \(D_{\text{\it wavelet}}\) and \(D_{\text{\it KSVD}}\), which were derived using the K-SVD algorithm, based on the set of training vectors obtained from the \(256\times 256\) gray-scale test image \"Boat\" (parameters of the K-SVD process were set at \(K=1024\), \(L=64\), \(\text{\it unIteration}=50\), \(\text{\it initializationMethod}=\text{\it''GivenMatrix}\), and \(\text{\it errorGoal}=10^{-8}\)). The image was divided into overlapping patches of \(16\times 16\) pixels with stride 2 (in each dimension) and overlaps of \(4\) pixels (in each dimension), which resulted in \(3721\) training patches. As the stride is 2 in each dimension, each patch formed a vector of \(128\) pixels. After the mean of each patch was normalized to zero, the resulting patches were transformed into vectors (via the vec operation) to form the set of training vectors. The dictionary \(D_{\text{\it wavelet}}\) was derived from the CDF 9-7 wavelet. The first 640 columns (i.e., each level has 128 columns and there are 5 levels) in \(D_{\text{\it wavelet}}\) were obtained from the first 5 levels (the support of a wavelet at level 6 is larger than the size of an image patch), whereas the remainder were generated randomly. The column norms of the sparsifying dictionaries were normalized. Figures 1 and 2 present the sparsifying dictionaries and corresponding matrices \(G\), derived for various \(A\) in accordance with (4). The subgraph associated with \(G\) in Figure 2 corresponds to the sensing matrix of \(D\). It is worth noting that the lack of structure in \(G\) does not contradict some research in compressed sensing literature that focuses on designing structured sensing matrices. The structured sensing matrix approach aims to efficiently manage an extensive system's computational resources, such as storage and computational efficiency. In contrast, our research prioritizes creating a sensing matrix that complements a given dictionary, with fewer rows than columns, to maintain the RIP. Exploring the possibility of constructing a structured sensing matrix while retaining the RIP for a given dictionary is an interesting question for future investigation. Under Theorem 2, the following two optimizations derive the same solution, if \(\mathcal{E}G^{-1}D=\mathcal{A}H\):  
\[ \begin{cases}\min_{x}\|z-\mathcal{E}G^{-1}Dx\|_{2}^{2}\\ \|x\|_{0}\leq k,\end{cases}  \tag{11}\]  
and  
\[ \begin{cases}\min_{x}\|z-\mathcal{E}Ax\|_{2}^{2}\\ \|x\|_{0}\leq k.\end{cases}  \tag{12}\]  
Figure 1: Visualization of sparsifying dictionaries (of size \(128\times 1024\)) with integer values ranging from \(0\) to \(255\). Figure 2: Matrix \(G\in\mathbb{R}^{128\times 128}\) of several sparsifying dictionaries \(D\) for various \(A\). Recall that \(D=GAH\) and the sensing matrix of \(D\) is \(\mathcal{E}G^{-1}\). In (**a1,b1**), \(A\) is a Gaussian random matrix. In (**a2,b2**), \(A\) is a Bernoulli random matrix. In (**a1,a2**), \(D=D_{KSVD}\). In (**b1,b2**), \(D=D_{uawolet}\). Note that \(z\) in (11) and (12) are low-dimensional observations of \(x\) obtained from \(\mathcal{E}Ax\) and \(\mathcal{E}\) in (11) and (12) are the same.