# Sparse recovery, Restricted Isometry Property for ILL-POSED problems

if $$\mathbf x$$ is $$N\times 1$$ sparse vector, and $$\mathbf A$$ is an $$M\times N$$ matrix with $$M<, 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?

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.
• Thank you for your answer. Could you explain what does $M = O(K(log(N/K))$ mean? – johanson Apr 16 at 0:22
• That means of the order of $K(log(N/K))$. Meaning the dimension M of the RIP matrix is decided by this relation. – Dsp guy sam Apr 16 at 6:56
• Is not $l_2$ norms already in objective? What is the difference between minimizing $l_1$ norm subject to $l_2$ norm smaller than 'e' and minimizing $l_2$ norm subject to $l_1$ norm smaller than 'e'? – johanson Apr 22 at 18:51
• The choice of objective function, should reflect the desired property of the signal. If you are sure, as your 3rd question, that the signal is not sparse, then placing a constraint on its cardinality ($l_1)$ norm will naturally not lead to the closest possible fit in the least squares sense. Which would be desired since we know the signal is not sparse, so better optimize it in the least squares sense. – Dsp guy sam Apr 22 at 19:15
• Minimizing $l_1$ norm subject to a $l_2$ constraint is basically trying to find a sparse vector whose norm is bounded, this is somtimes reuired and makes sense, for example, maybe we would not want a sparse vector whose one index lies at a very large value, we might want to find the sparsest x within the unit sphere. – Dsp guy sam Apr 22 at 19:15