Sparse recovery, Restricted Isometry Property for ILL-POSED problems

Question

if $\mathbf x$ is $N\times 1$ sparse vector, and $\mathbf A$ is an $M\times N$ matrix with $M<<N$, and we measure $\mathbf y=\mathbf{Ax}$, then compressed sensing theory tells us that we can exactly recover $\mathbf x$ from $\mathbf y$ under some conditions for $\mathbf A$ like RIP.

But what if $\mathbf A$ is an $M\times N$ matrix with $M>>N$ or $M=N$. Now the equation is not under-determined. But the equation can not be solved directly because $\mathbf A$ is now ill-conditioned matrix. To approximate to solution we can apply regularization. Since $\mathbf x$ still sparse we apply $l_1$ reguarization scheme as $$ ||y-Ax||_2^2 + \lambda ||x||_1$$ and find a sparse solution for x where sparsity level is dependent on $\lambda$.

The questions are

1) Do we still need to consider RIP for $\mathbf A$? What effects the acuuracy of the solution of $l_1$ regularization scheme except $\lambda$?

2) Why do we need RIP in compressive sensing and does it have any relation with the values of $M$ and$N$?

3) If $x$ is not sparse does this regularization fail for sure? Or it can still be work like $l_2$ regularization scheme. Maybe better?

Answer 1

The purpose of compression sensing is to sample a signal below Nyquist given that the signal is sparse in a certain transformation. So it only makes sense when $M < N$. Othwersie if $M>N$ or $M=N$ then what you have is conventional sampling anyways. An important property of RIP matrices is that it is guaranteed to only change the length of any vector "very little" as long as the vector is at least $K$-sparse (has at most $K$ non-zero coefficients. By definition its is the following: $$(1-\delta_S)||x||_2^2 \le ||A x||_2^2 \le (1+\delta_S)||x||_2^2$$ where $x$ is the sparse vector and $\delta_s$ is an arbitrary constant close to zero. So yes, $M$ should be less than $N$ for compressive sensing to make sense and infact all the known matrices that follow RIP are known to exist when $M = O(K(log(N/K))$ strictly. Finding these matrices is not trivial and is a NP Hard problem.

So you do not need to consider RIP for A when $M>=N$, because we are now not talking in compressive sensing terms. The $l_2$ terms should now be the objective because convergence can be achieved in the $l_2$ convergence.

If $M>=N$ and $x$ is not sparse then the regularization could still work but $\lambda$ should be adjusted accordingly with apriori knowledge of $x$ not being sparse. Although I dont see any point of the $l_1$ being part of the objective.