Sparse recovery, Restricted Isometry Property for ILL-POSED problems
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 &lt; N$. Othwersie if $M&gt;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&gt;=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&gt;=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.