Fig. 1 Averages SNR of the algorithms vs sparsity, expressed in percentage of the number of equations $n$. The algorithms SL0, LARS, LASSO, MP, OMP, STOMP are the most representative in the area.

Fig. 2 Relative number (in %) of correctly recovered atoms not equal to zero. An atom is considered correctly reconstructed if the deviation from the true value of the estimated value is less than 5%.

Fig. 3 Average computational times of the algorithms vs sparsity, expressed in percentage of the number $n$ of equations.

Fig. 4 Each point on the grid shows the cumulative mean square error (MSE) between the original and reconstructed signals. The grid of $\delta\times\rho$ values is done with $\delta$ ranging in the interval [.01, 5] and $\rho$ ranging in [.01, 1], where $\rho=k/n$, $\delta=n/m$ and $n\times m$ represents the dictionary size.

Description

We provide a fast iterative method for finding sparse solutions to underdetermined linear systems. It is based on a fixed-point iteration scheme which combines nonconvex Lipschitzian-type mappings with canonical orthogonal projectors. The former are aimed at uniformly enhancing the sparseness level by shrinkage effects, the latter are used to project back onto the space of feasible solutions. The iterative process is driven by an increasing sequence of a scalar parameter that mainly contributes to approach the sparsest solutions.

Details

We developed two new heuristics (called LiMapS and $k$-LiMapS respectively) for the classical sparse recovery problem $\min_{\alpha} || \alpha ||_{0} \quad \mbox{such that}\quad s=\Phi\alpha.$ They rely on a parametric class $\left\{G_\lambda : \lambda \geq 0 \right\}$ of nonlinear mappings which turn to be useful to solve the sparsity minimization problem above by the Picard iterative scheme: $$\alpha_{t+1} = G_{\lambda_t}(\alpha_{t}):=\alpha_t - \text{Proj}_{\text{ker} \Phi} [\alpha_t\odot e^{-\lambda|\alpha_t|}]$$ We show that given a sequence $\{\lambda_t\}_{t\geq 0}$, the iterative scheme converges when $\sum_{t} \frac{1}{\lambda_t}<+\infty$. To study this minimization problem, we first introduce a smooth relaxed version, approximating the original problem when $\lambda\to+\infty$: $$\min_{\alpha} || \alpha ||_{\langle \lambda \rangle} \quad \mbox{such that}\quad s=\Phi\alpha$$ where the family $\{ || \cdot ||_{\langle\lambda \rangle}:\lambda >0\}$ is a collection of suitable pseudo-norms. We find that, under reasonable assumptions, the local minima of the latter relaxed problem are asymptotically stable fixed points of the Picard scheme $G_\lambda$. We also give some evidence that, for sufficiently large $\lambda$, the sparsest solution is ''close'' to a fixed point of $G_\lambda$.

Limaps Algorithm

This algorithm results in a new regularization method for sparse representation based on the Picard fixed-point iteration schema above which combines two Lipschitzian-type mappings, a nonlinear one aimed to uniformly enhance the sparseness level of a candidate solution and a linear one which projects back into the feasible space of solutions. It is shown that this strategy locally minimizes a problem whose objective function falls into the class of the $\ell_p$-norm and represents an effective approximation of the $\ell_0$-norm in the intractable sparsity minimization problem. Numerical experiments on randomly generated signals using classical stochastic models show better performances of the proposed technique with respect to a wide collection of well known algorithms for sparse representation, as shown in the Figures 1-3.

The Matlab implementation of Limaps Algorithm can be downloaded from the Software Section

$k$-Limaps Algorithm

Analogously to the well known greedy strategy called Orthogonal Matching Pursuit (OMP), k-LiMapS is a new algorithm for solving the sparse approximation problem over redundant dictionaries where the input signal is restricted to be a linear combination of at most k atoms of a fixed dictionary. The basic strategy of the method relies on a family of nonlinear mappings which results to be contractive in a interval close to zero. By iterating contractions and projections the method is able to extract the most significant components also for noisy signal which subsumes an ideal underlying signal having sufficiently sparse representation. For reasonable error level, the fixed point solution of such iterative scheme provides a sparse approximation containing only the nonzero terms characterizing the unique sparsest representation of the ideal noiseless sparse signal. The heuristic method so derived has been applied both to synthetic and real data generated by combining exact signals drawn by usual Bernoulli-Gaussian model and Gaussian noise. The Figure 4 depicts both the k-LiMapS and OMP mean square errors over the data.

The annealing-like behavior exhibited by klimaps hitting the non required coefficients already at the beginning of the first iterations (15 and 30) for a 10-sparse signal, as shown in the following plotting:

The Matlab implementation of $k$-Limaps Algorithm can be downloaded from the Software Section

References

1) Adamo, Alessandro; Grossi, Giuliano. A fixed-point iterative schema for error minimization in k-sparse decomposition. Signal Processing and Information Technology (ISSPIT), 2011 IEEE International Symposium on, 167-172, 2011, IEEE
2) Adamo, Alessandro; Grossi, Giuliano. Sparsity recovery by iterative orthogonal projections of nonlinear mappings. Signal Processing and Information Technology (ISSPIT), 2011 IEEE International Symposium on, 173-178, 2011, IEEE