Highly Nonlinear Approximations for Sparse Signal Representation

• Project Overview
• Tutorial [.ps | .pdf]
• Source code
• Examples
• Publications
• EIFS
• SCEIFS
• Acknowledgements

• Home
• maths@Aston
• EPSRC Home

Implementing corrections

Let us discuss now the possibility of correcting bad moves in the forward selection, which is specially necessary when dealing with ill posed problems. Indeed, assume we are trying to approximate a signal which is $K$-sparse in a given dictionary, and the search for the right atoms become ill posed after the iteration, $r$, say, with $r>K$. The $r$-value just indicates that it is not possible to continue with the forward selection, because the computations would become inaccurate and unstable. Hence, if the right solution was not yet found, one needs to implement a strategy accounting for the fact that it is not feasible to compute more than $r$ measurement vectors. A possibility is provided by the swapping-based refinement to the OOMP approach introduced in [13]. It consists of interchanging already selected atoms with nonselected ones.

Consider that at iteration $r$ the correct subspace has not appeared yet and the selected indices are labeled by the $r$ indices $\ell_1,\ldots,\ell_r$. In order to choose the index of the atom that minimizes the norm of the residual error as passing from approximation $\hat{P}_{{\cal{W}}_r}f$ to approximation $\hat{P}_{{\cal{W}}_{r \setminus j}}f$ we should fix the index of the atom to be deleted, $\ell_j$ say, as the one for which the quantity

$$\frac{\vert c_i^r\vert}{\Vert w_i^r\Vert}, i=1,\ldots,r.$$ (27)

is minimized [13,14].

The process of eliminating one atom from the atomic decomposition is called backward step while the process of adding one atom is called forward step. The forward selection criterion to choose the atom to replace the one eliminated in the previous step is accomplished by finding the index $\ell_i, i=1,\ldots,r$ for which the functional

$$e_n= \frac{\vert\langle \nu_n , f \rangle \vert}{\Vert \nu_n \Vert}, \quad \nu_n = u_n - \hat{P}_{{\cal{W}}_{r \setminus j}} u_n ,\quad \Vert\nu_n\Vert\neq 0$$ (28)

is maximized. In our framework, using (22), the projector $\hat{P}_{{\cal{W}}_{r \setminus j}}$ is computed as

$$\hat{P}_{{\cal{W}}_{r \setminus j}} = \hat{P}_{{\cal{W}}_r} - \... ...angle w_i^r , w_j^r \rangle \langle w_j^r, \cdot \rangle }{\Vert w_j^r\Vert^2}.$$

The swapping of pairs of atoms is repeated until the swapping operation, if carried out, would not decrease the approximation error. The implementation details for an effective realization of this process are given in [13]. Moreover, the process has been extended to include the swapping of more than a pair of atoms. This possibility is of assistance in the application of signal splitting, see [15]. A number of codes for implementing correction to Pursuit Startegis can be found in Pursuits.

This project is supported by EPSRC (EP/D062632/1)