# RIP Sensing Matrices Construction for Sparsifying Dictionaries with Application to MRI Imaging
## 3 Sensing Matrix Construction  
Signal complexity, in terms of sparsity, determines the amount of possible under-sampling in CS. Constructions utilizing randomness can produce RIP matrices for which the number of required measurements \(m\) scales linearly with the sparsity level \(k\) of the vector to be recovered. Such matrices can be derived from distributions for which the following concentration of measure inequality, resembling (1), holds, such as for subgaussian or Bernoulli ensembles. **Theorem 1** ([8]). : _Let \(0<\delta_{k}<1\) and \(A\in\mathbb{R}^{m\times n}\) be an iid random matrix. If \(\mathbb{E}\|Ax\|_{2}^{2}=\|x\|_{2}^{2}\) for all \(x\in\mathbb{R}^{n}\), and for any \(\epsilon\in(0,1)\) the concentration inequality \(\mathbb{P}(\|Ax\|_{2}^{2}-\|x\|_{2}^{2}]\geq\epsilon\|x\|_{2}^{2})\leq 2e^{-l( \epsilon)}\) holds for some \(c(\epsilon)>0\) and all \(x\in\mathbb{R}^{n}\), then there exists \(c_{1},c_{2}>0\) (depending only on \(\delta_{k}\)) such that, whenever \(k\leq\frac{c_{1}m}{\log(n/K)}\), the RIP (1) holds for \(A\) with probability at least \(1-2e^{-c_{2}m}\)._  
Random matrices satisfying the concentration inequality are universal with respect to orthonormal bases [8], i.e., the same RIP conclusions hold for their products with unitary matrices. We use this universality to derive sensing matrices for any sparsity-inducing dictionary by random row selection of an invertible transform adapted to the dictionary. **Theorem 2**. : _Let \(D\in\mathbb{R}^{l\times n}\) (\(l\leq n\)) be a dictionary, \(A\in\mathbb{E}^{l\times n}\) and \(\mathcal{E}\in\mathbb{E}^{m\times l}\) matrices such that \(\mathcal{E}A\) satisfies the assumptions of Theorem 1. Suppose the dictionary allows a factorization \(D=GAH\) for some invertible \(G\) and orthonormal \(H\). Then \(S:=\mathcal{E}G^{-1}\in\mathbb{R}^{m\times l}\) is a sensing matrix for \(D\) such that, with probability as in Theorem 1, \(SD\) has the RIP whenever \(m\gtrsim k\log(n/k)\)._  
In this construction \(SD\) equals \(\mathcal{E}AH\), which implies the claim due to the above mentioned universality. The existence of a factorization \(D=GAH\) as assumed in Theorem 2 requires \(A\) and \(D\) to have equal rank. We next show that the latter also suffices. Given a full-rank sparsifying dictionary, the sensing matrix construction of Theorem 2 can therefore (with probability one) be carried out, starting from a Gaussian matrix \(A\) of the same dimensions as the dictionary, and a random row selection \(\mathcal{E}\). **Proposition 1**. : _Let \(A,D\in\mathbb{R}^{l\times n}\) with \(l\leq n\). Then, the following statements are equivalent:_  
1. _There exists an invertible_ \(G\in\mathbb{R}^{l\times l}\) _and orthonormal_ \(H\in\mathbb{R}^{n\times n}\) _such that_ \(GD=AH\)_;_
2. _There exists an invertible_ \(G\in\mathbb{R}^{l\times l}\) _with_ \(GDD^{\top}G^{\top}=AA^{\top}\)_;_
3. \(A\) _and_ \(D\) _have equal rank._  
Proof. : We show that (iii) implies (ii), and in turn (i). Assuming (iii), \(AA^{\top}\) and \(DD^{\top}\) have equal rank. Their respective spectral decompositions \(Q_{A}\Sigma_{A}Q_{A}^{\top}\) and \(Q_{D}\Sigma_{D}Q_{D}^{\top}\) can, thus, be assumed to have zeros in the same positions of the diagonal matrices \(\Sigma_{A},\Sigma_{D}\). Replacing those zero diagonal entries by ones to result in \(\Sigma_{A}^{\prime},\Sigma_{D}^{\prime}\), the matrix \(G:=Q_{A}(\Sigma_{A}^{\prime}\Sigma_{D}^{\prime-1})^{1/2}Q_{D}^{\top}\) is invertible and:  
\[GDD^{\top}G^{\top} =GQ_{D}\Sigma_{D}Q_{D}^{\top}G^{\top}\] \[=Q_{A}(\Sigma_{A}^{\prime}\Sigma_{D}^{\prime-1})^{1/2}\Sigma_{D}( \Sigma_{A}^{\prime}\Sigma_{D}^{\prime-1})^{1/2}Q_{A}^{\top}=AA^{\top}.\]  
Defining \(H:=A^{+}GD+N_{A}N_{D}^{\top}\), with \(A^{+}\) denoting the pseudo-inverse of \(A\), and \(N_{A}\), respectively \(N_{D}\), having pairwise orthonormal columns spanning the nullspaces of \(A\), respectively \(D\), implies:  
\[AH=AA^{+}GD+AN_{A}N_{D}^{\top}=AA^{+}GD=GD\]  
since \(AA^{+}\) is the identity on the range of \(A\), which contains the range of \(G\).