Highly Nonlinear Approximations for Sparse Signal Representation


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

$\displaystyle \ell_{k+1}= \arg\max\limits_{n \in J \setminus J_{k}}
...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

$\displaystyle \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

$\displaystyle \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

$\displaystyle \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

$\displaystyle \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 [*].