# RIP Sensing Matrices Construction for Sparsifying Dictionaries with Application to MRI Imaging
## 1 Introduction  
Compressed sensing provides a framework under which sparse or compressible signals can be stably reconstructed from far fewer linear measurements than their ambient dimension [1, 2]. The number of required measurements depends on the signal complexity in terms of sparsity, and properties of the sensing matrix with respect to sparse vectors, such as the restricted isometry property (RIP) [3]. A sensing matrix \(S\), which embeds high-dimensional signals into a lower-dimensional measurement space, is said to have the RIP of order \(k\) if there exists a constant \(\delta_{k}\in[0,1)\), such that for any \(k\)-sparse vector \(x\in\mathbb{R}^{n}\):  
\[(1-\delta_{k})\|x\|_{2}^{2}\leq\|Sx\|_{2}^{2}\leq(1+\delta_{k})\|x\|_{2}^{2}. \tag{1}\]  
Improving upon [4], [PERSON] [5] showed that \(k\)-sparse and compressible vectors can be stably recovered from observations \(y=Sx+\eta\) with measurement error \(\eta\) bounded by \(\epsilon\), given that \(S\) has the RIP with \(\delta_{2k}<\sqrt{2}-1\) (which has been improved to 0.4652 [6]) via the sparsity promoting convex program:  
\[\operatorname*{minimize}_{x}\|x\|_{1}\quad\text{subject to}\quad\|y-Sx\|_{2} \leq\epsilon. \tag{2}\]  
For certain \(\lambda>0\), (2) can be equivalently reformulated to the problem of minimizing over \(x\) the unconstrained objective \(\frac{1}{2}\|y-Sx\|_{2}^{2}+\lambda\|x\|_{1}\) consisting of a data-fidelity and regularization term, which can be solved using iterative methods [7]. While it is NP-hard to verify the RIP for a given matrix, random matrices from sub-Gaussian or Bernoulli ensembles do possess the RIP with high probability--also when composed with orthonormal bases [8]. In practice, however, many classes of signals aresparse only with respect to a redundant dictionary or tight frame that is non-orthonormal (e.g., Gabor, curvelet, wavelet, or data-driven learned dictionaries). In this case, the sensing matrix \(S\) in (1) has to be replaced by the composition \(SD\), which no longer possesses the RIP. This prevents the RIP as recovery guaranteeing tool in many CS applications. ContributionsWe first present a method to derive a sensing matrix \(S\in\mathbb{R}^{m\times l}\) for a given sparsifying dictionary \(D\in\mathbb{R}^{l\times n}\), such that with high probability, \(SD\) has the RIP for \(m\) on the order of \(k\log(n/k)\), where \(k\) is the sparsity level of a coefficient vector. We use a sufficient condition for the RIP of random matrices that satisfy a concentration of measure inequality [8]. Starting from any random matrix \(A\) of the dictionary dimension for which a random row selection \(\mathcal{E}A\in\mathbb{R}^{m\times n}\) satisfies this concentration inequality, a tailored sensing matrix can be derived from any factorization \(D=GAH\), in which \(G\in\mathbb{R}^{l\times l}\) is invertible and \(H\in\mathbb{R}^{n\times n}\) is orthonormal: for the sensing matrix \(S:=\mathcal{E}G^{-1}\), the composition \(SD\) has then the desired RIP with high probability. We show in Section 3 that the required factorization exists whenever \(D\) and \(A\) have equal rank and detail constructions. A particular implication is that one can, thus, obtain the same RIP-based recovery guarantees for sensing matrix compositions with general over-complete dictionaries as for Gaussian or Bernoulli ensembles with orthonormal bases. We utilize dictionary factorization in the context of CS MRI applications to showcase the viability of our method for a significant purpose. The primary aim of accelerating MRI scans is to lessen the time patients spend in the machines, thereby reducing the discomfort that can result from remaining motionless. The speed at which MRI images are accelerated is affected by the number of rows in an over-complete dictionary. As a result, recovery algorithms aim to use fewer rows while ensuring high-quality image reconstruction.