Is there any trade-off between the sparseness and residual of the constructed data? I am going to test a sparsity promoting algorithm with different parameters to solve the $Ax=b$ to obtain a sparse model $x$. I have to test different parameters for which my algorithm results in different answers for $x$. 

With different $x$'s there are different $Ax=\hat{b}$ 's. To have a better comparison, I forced my algorithm to iterate while the $\left\|Ax-b\right\|^2&lt;\epsilon$. 

Now that I obtained all $x$'s for which $\left\|Ax-b\right\|^2&lt;\epsilon$ , how can I determine which model, $x$, is better? I know that I am looking for a model that is more sparse and have a better fit to $b$ but I think I have to consider somehow a trade-off between the sparseness and residual.
You can reformulate your problems as a minimization problem:

$$P1:  \min_x  \|Ax -b\|_2^2 + \lambda \|x\|_o $$

Where $\|x\|_o$ is the $\ell_o$ norm of x where it is the number of nonzero elements. Looking for a solution to p1 is essentially looking for a solution that best explains the model $\|Ax -b\|$ while having sparse coefficients. The problem is NP non convex NP hard and is extremely difficult to optimize. Another approach is to use the best convex envelope to the $\ell_o$ norm which is the $\ell_1$ norm.

$$P2:  \min_x  \|Ax -b\|_2^2 + \lambda \|x\|_1 $$

Under some conditions on A, the two problems are in fact equivalent in the sense they have the same global optimal solution. There are many efficient solvers for P2 including ADMMS, randomized methods, ISTA and FISTA.

To solve P2 in MATLAB, SPAMS is your friend here.