# 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<\epsilon$.

Now that I obtained all $x$'s for which $\left\|Ax-b\right\|^2<\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.

The problem with the $l_0$ approach is it is non-smooth and it is non-convex. A convex approximation is to use the $l_1$ to promote sparsity. There are 3 common formulation that are essentially equivalent - if the parameters are chosen correctly (LASSO, Basis Pursuit De-Noising (BPDN) and Quadratic Problem).

The formulations are: $$LASSO:\qquad \min_x ||Ax-b||_2 \qquad s.t. \quad ||x||_1 \leq \tau$$

$$BPDN:\qquad \min_x ||x||_1 \qquad s.t. \quad ||Ax-b||_2 \leq \sigma$$

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

To see the trade-off in sparsity vs fit examine the extreme choices in $\lambda$. In the case where the system $Ax=b$ is under-determined i.e. there are multiple solutions. If $\lambda = 0$ then the solution is the normal least squares solution, which tends to have a lot of small components across all the vector components i.e. $x$ tends to be vary non-sparse, but the fit is exact. In the other case as $\lambda \rightarrow \infty$ then the fit becomes meaningless and the solution is just the sparsest vector possible which is $x=0$. So intuitively the choice of the value of $\lambda$ trades-off between the fit and the sparsity of the solution vector.

This relationship is a bit harder to see in the other formulations given above, but they are equivalent problems.

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.

I understand that you might already have a set of approximate solutions ("Now that I obtained all $x$ for which"), and look for a "best" sparse solution. The $\ell_0$ count measure (not a norm, nor a quasinorm) is the most natural and homogeneous ($\ell_0(\alpha x) =\ell_0( x)$ for $\alpha\neq 0$), but is not computationally tractable, and very sensitive to noise. Other measures have been designed to address this issue in Comparing measures of sparsity. Among the proposals, the Gini index and the $\ell_1/\ell_2$ norm ratio are quite promising (they are homogeneous too, in contrary to norms). The latter has been used for instance as a stopping criterion in sparse source separation algorithms. It can even be used as a sparsity- inducing penalty, see for instance Euclid in a Taxicab: Sparse Blind Deconvolution with Smoothed $\ell_1/\ell_2$ Regularization.