TransWikia.com

What are the practical constraints on designing Sensing matrix in compressed Sensing?

Signal Processing Asked by Digi1 on March 7, 2021

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,.

2 Answers

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 = PhiPsi$ 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.

Answered by Thomas Arildsen on March 7, 2021

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.

Answered by MimSaad on March 7, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP