Compressed sensing refers to the recovery of a high-dimensional but sparse vector $x\in\mathbb{R}^n$ from its linear measurement $y = Ax+\eta$, where $A\in\mathbb{R}^{m\times n}$ $(m<<n)$ is a measurement matrix and $\eta$ is the measurement noise with a known upper bound $||\eta||_2\leq \epsilon$.

Following is the most popular method to recover the $x$:

$$\hat{x}= \arg\min ||z||_1 , \mbox{such that}\ ||y-Az||_2\leq\epsilon.$$ In order for the above formulation to work, $A$ must satisfy the Restricted Isometry Property (RIP) or Robust Null Space Property (RNSP).

Now, suppose $x$ itself is not sparse but it is sparse in some other basis, say $\Phi\in\mathbb{C}^{n\times n}$. So, $x = \Phi \alpha$, where $\alpha\in\mathbb{C}^n$ is a sparse vector. Now, if we measure the $x$ using any sampling matrix $A$, we would get

$$y= Ax+\eta=A\Phi\alpha +\eta.$$ The corresponding recovery algorithm would be:

$$\hat{\alpha}= \arg\min ||z||_1 , \mbox{such that}\ ||y-A\Phi z||_2\leq\epsilon ,$$

$$\hat{x}= \Phi \hat{\alpha}$$.

Now, my question is how to construct $A$ such that the $A\Phi$ satisfies the RIP or RNSP? I know a tons of method for designing RIP satisfying measurement matrix $A$. But I don't know how to design $A$ such that the product $A\Phi$ satisfies the RIP?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.