Highly Nonlinear Approximations for Sparse Signal Representation

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

• Home
• maths@Aston
• EPSRC Home

Oblique Matching Pursuit (OBMP)

The criterion we use for the forward recursive selection of the set $\{v_\ell\}_{\ell \in J} \subset \{v_i\}_{i=1}^M$ yielding the right signal separation is in line with the consistency principle introduced in [2] and extended in [3]. Furthermore, it happens to coincide with the Optimize Orthogonal Matching Pursuit (OOMP) [12] approach applied to find the sparse representation of the projected signal $\hat{P}_{{\cal{W}}}f$ using the dictionary $\{u_i\}_{i=1}^M$

By fixing $\hat{P}_{{\cal{W}}_k}$, at iteration $k+1$ we select the index $\ell_{k+1}$ such that $\Vert\hat{P}_{{\cal{W}}} \vert f \rangle - \hat{P}_{{\cal{W}}_{k+1}}\vert f \rangle \Vert^2$ is minimized.

Proposition 8   Let us denote by $J$ the set of indices $\{\ell_1,\ldots,\ell_k\}.$ Given ${\cal{W}}_k= {\mbox{\rm {span}}}\{\vert u_{\ell_{i}}\rangle \}_{i=1}^k$, the index $\ell_{k+1}$ corresponding to the atom $\vert u_{\ell_{k+1}}\rangle$ for which $\Vert\hat{P}_{{\cal{W}}} f - \hat{P}_{{\cal{W}}_{k+1}}f \Vert^2$ is minimal is to be determined as

$$\ell_{k+1}= \arg\max\limits_{n \in J \setminus J_{k}} \frac{\ver... ...t f\rangle \vert}{\Vert\gamma_n \Vert}, {\Vert\gamma_n\rangle \Vert} \neq 0,$$ (25)

with $\gamma_{n}= u_{n} - \hat{P}_{{\cal{W}}_k} u_{n}$ and $J_{k}$ the set of indices that have been previously chosen to determine ${\cal{W}}_k$.

Proof. It readily follows since $\hat{P}_{{\cal{W}}_{k+1}} f = \hat{P}_{{\cal{W}}_k} f + \frac{ \gamma_n \langle \gamma_n ,f\rangle }{\Vert\gamma_n\Vert^2}$ and hence

$$\Vert\hat{P}_{{\cal{W}}} f - \hat{P}_{{\cal{W}}_{k+1}} f \Vert^2=... ...t^2 - \frac{\vert\langle \gamma_n , f \rangle \vert^2}{\Vert\gamma_n\Vert^2}.$$

Because $\hat{P}_{{\cal{W}}}f$ and $\hat{P}_{{\cal{W}}_k} f$ are fixed, $\Vert\hat{P}_{{\cal{W}}} f - \hat{P}_{{\cal{W}}_{k+1}}f \Vert^2$ is minimized if $\frac{\vert\langle \gamma_n,f\rangle \vert}{\Vert\gamma_n\Vert}, \Vert \gamma_n \Vert \neq 0$ is maximal over all $n\in J\setminus J_{k}$. $\qedsymbol$

The original OBMP selection criterion proposed in [11] selects the index $\ell_{k+1}$ as the maximizer over $n\in J\setminus J_{k}$ of

$$\frac{\vert\langle \gamma_{n} ,f\rangle \vert}{\Vert\gamma_{n}\Vert^2},\quad \Vert\gamma_n\Vert\neq 0.$$

This condition was proposed in [11] based on the consistency principle which states that the reconstruction of a signal should be self consistent in the sense that, if the approximation is measured with the same vectors, the same measures should be obtained (see [2,3]). Accordingly, the above OBMP criterion was derived in [11] in order to select the measurement vector ${w}^{k+1}_{k+1}$ producing the maximum consistency error $\Delta= \vert\langle {w}^{k+1}_{k+1},f - \hat{E}_{{\cal{V}}_k {\cal{W}^\bot}}f \rangle \vert$, with regard to a new measurement ${w}^{k+1}_{k+1}$. However, since the measurement vectors are not normalized to unity, it is sensible to consider the consistency error relative to the corresponding vector norm $\Vert{w}^{k+1}_{k+1}\Vert$, and select the index so as to maximize over $k+1 \in J \setminus J_{k}$ the relative consistency error

$$\tilde {\Delta}= \frac{\vert\langle {w}^{k+1}_{k+1}, f - \hat{E}_... ...ngle \vert}{\Vert{w}^{k+1}_{k+1}\Vert}, \quad \Vert{w}^{k+1}_{k+1}\Vert \ne 0.$$ (26)

In order to cancel this error, the new approximation is constructed accounting for the concomitant measurement vector.

Property 3   The index $\ell_{k+1}$ satisfying (25) maximizes over $k+1 \in J \setminus J_{k}$ the relative consistency error (26)

Proof. Since for all vector ${w}^{k+1}_{k+1}$ given in (19) $\langle {w}^{k+1}_{k+1} , \hat{E}_{{\cal{V}}_k {\cal{W}^\bot}}f \rangle =0$ and $\Vert{w}^{k+1}_{k+1}\Vert= \Vert\gamma_{k+1}\Vert^{-1}$ we have

$$\tilde {\Delta}= \frac{\vert\langle {w}^{k+1}_{k+1}, f \rangle \v... ...}= \frac{\vert\langle \gamma_{k+1} , f \rangle \vert}{\Vert\gamma_{k+1}\Vert}.$$

Hence, maximization of $\tilde{\Delta }$ over $k+1 \in J \setminus J_{k}$ is equivalent to (25). $\qedsymbol$

It is clear at this point that the forward selection of indices prescribed by proposition (25) is equivalent to selecting the indices by applying OOMP [12] on the projected signal $\hat{P}_{{\cal{W}}}f$ using the dictionary $\{u_i\}_{i=1}^M$. The routine for implementing the pursuit strategy for subspace selection according to criterion (25) is OBMP.m. An example of application is given in .

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