In a typical compressed sensing scenario, $y=Ax$, where $x$ is a sparse signal and $A$ is the sensing matrix.
To reconstruct the sparse signal $x$ from $y$, $A$ should posses the Restricted Isometry Property (RIP). Therefore, if a matrix does not possess RIP the reconstruction of $x$ will not be possible. How can we check a matrix for RIP ?
Secondly what are the practical constraints on designing the sensing matrix $A$ ? Like should the matrix consists of real values or complex? What distribution to use for generating the matrix $A$ ? etc,.
$\begingroup$
$\endgroup$
1
-
2$\begingroup$ RIP is a sufficient by not necessary condition. You can often perform sparse reconstruction with matrices that don't satisfy RIP. The Null-Space property is an alternative measure, but there is no computationally efficient method to compute it either.. $\endgroup$– DavidFeb 16, 2017 at 15:04
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
Checking for RIP of a matrix is an NP-Hard problem which means it is not computationally feasible to accomplish. RIP is used in matrix design mostly in theoretical aspects. Stealing @David 's comments, RIP is a tight condition. To design sensing matrices, another weaker condition named Coherence is used, which its computational complexity is tractable ($O(n^2)$ where $n$ is length of matrix). No matter what type of elements form the matrix, you can always check for its coherence.
A similar question has been asked here: Compressive sensing: numerical generation of RIP matrices . Check it out for more details.
-
$\begingroup$ Thank you. So as long as a matrix have the above property, it can have any distribution, can be of real or complex values ?? what is the physical significance of the entries in $A$ ? $\endgroup$– Digi1Feb 17, 2017 at 8:12
-
$\begingroup$ I am confused, you mean RIP or Coherence? If your matrix satisfies coherence (which you can prove numerically), but since coherence is a weaker condition, you normally have to choose larger matrices than what RIP dictates. About real of complexity of values, I think it is not make any difference but suggest to read something on "Sensing Matrix Design" like sharif.ir/~aamini/publications.html $\endgroup$– MimSaadFeb 17, 2017 at 8:46
-
$\begingroup$ Thanks. The references were helpful. If I want to simulate a compressed sensing system in frequency domain, is it fine if I generate a random complex measurement matrix $A$ or I have to take DFT? $\endgroup$– Digi1Mar 9, 2017 at 13:15
-
$\begingroup$ Generate a random matrix PHI (with any type), usig PHI matrix measure your signal in time domain, recover the signal using PHI * PSI matrix, where PSI is fourier transfom matrix (dftmtx instruction in matlan). $\endgroup$– MimSaadMar 9, 2017 at 19:36
$\begingroup$
$\endgroup$
When you say "practical constraints on designing the sensing matrix", it depends on whether you mean realising the sensing matrix in actual hardware. In that case, physical constraints probably outweigh more idealised theoretical constraints such as RIP or low coherence. You will of course like to try to achieve these characteristics, but in practice you cannot freely choose how to realise the sensing of your signal.
First of all, it is generally more practical to work with the factorisation $A = \Phi\Psi$ where $\Phi$ is the measurement matrix and $\Psi$ is the dictionary matrix. This splits the problem into two; one of realising the measurement matrix $\Phi$ in practical hardware and one of selecting a dictionary $\Psi$ that allows a sparse representation $x$ of your observable signal $z = \Psi x$ (meaning that you sense your signal as $y = \Phi z$).
Even though this factorisation appears to make the problem somewhat easier, you still have to ensure low coherence which is now measured as the mutual coherence between $\Phi$ and $\Psi$, so you are not free to choose them completely independently of each other.
In practice, your sensing hardware may impose some quite limiting restrictions on $\Phi$ so that you are left with the choice of $\Psi$ which is now possibly a trade-off between low coherence between $\Phi$ and $\Psi$ (good) and a not-so-sparse representation $x$ in $\Psi$ (bad) or a higher coherence between $\Phi$ and $\Psi$ (bad) and a very sparse representation $x$ in $\Psi$ (good).
One simple example of optimal coherence between $\Phi$ and $\Psi$ is if your signal $z$ is frequency-sparse. In this case, $\Psi$ should be the IDFT and $\Phi$ is simply a (random) sub-sampling compared to the Nyquist rate which can be represented as an identity matrix with some (most) of its rows removed. And here $z$ represents the time-domain signal sampled at (at least) the Nyquist rate.
