Highly Nonlinear Approximations for Sparse Signal Representation

Logo EPSRC

Updating the oblique projector $ \hat{E}_{{\cal{V}}_k {\cal{W}^\bot}}$ to $ \hat{E}_{{\cal{V}}_{k+1}{\cal{W}^\bot}}$

We assume that $ \hat{E}_{{\cal{V}}_k {\cal{W}^\bot}}$ is known and write it in the explicit form

$\displaystyle \hat{E}_{{\cal{V}}_k {\cal{W}^\bot}}=\sum_{i=1}^k v_i \langle {w}^k_i , \cdot \rangle .$ (17)

In order to inductively construct the duals $ {w}^{k+1}_i, i=1,\ldots,k+1$ we have to discriminate two possibilities
i)
$ {\cal{V}}_{k+1}={\mbox{\rm {span}}}\{v_i\}_{i=1}^{k+1}=
{\mbox{\rm {span}}}\{v_i\}_{i=1}^{k}={\cal{V}}_k$, i.e., $ v_{k+1} \in {\cal{V}}_k.$
ii)
$ {\cal{V}}_{k+1}={\mbox{\rm {span}}}\{v_i\}_{i=1}^{k+1} \supset {\mbox{\rm {span}}}\{v_i\}_{i=1}^{k}={\cal{V}}_k$, i.e. $ v_{k+1} \notin {\cal{V}}_k.$

Case i)

Proposition 4   Let $ v_{k+1} \in {\cal{V}}_k$ and vectors $ w_i^k$ in (17) be given. For an arbitrary vector $ y_{k+1}\in{\cal{H}}$ the dual vectors $ w_i^{k+1}$ computed as

$\displaystyle w_i^{k+1}= w_i^k- \langle u_{k+1}, w_i^k\rangle y_{k+1}$ (18)

for $ i=1,\ldots,k$ and $ w^{k+1}_{k+1}=y_{k+1}$ produce the identical oblique projector as the dual vectors $ w_i^k, i=1,\ldots,k$.

Case ii)

Proposition 5   Let vector $ v_{k+1} \notin {\cal{V}}_k$ and vectors $ w_i^k, i=1,\ldots,k$ in (17) be given. Thus the dual vectors $ w_i^{k+1}$ computed as

$\displaystyle w_i^{k+1}=w_i^k- w_{k+1}^{k+1} \langle u_{k+1}, w_i^k\rangle ,$ (19)

where $ w_{k+1}^{k+1}= \frac{\gamma_{k+1}}{\Vert\gamma_{k+1}\Vert^2}$ with $ \gamma_{k+1}= u_{k+1} - \hat{P}_{{\cal{W}}_k} u_{k+1}$, provide us with the oblique projector $ \hat{E}_{{\cal{V}}_{k+1}{\cal{W}^\bot}}$.

The proof these propositions are given in [10]. The codes for updating the dual vectors are FrInsert.m and FrInsertBlock.m.

Property 2   If vectors $ \{v_i\}_{i=1}^k$ are linearly independent they are also biorthogonal to the dual vectors arising inductively from the recursive equation (19).

The proof of this property is in [10].

Remark 3   If vectors $ \{v_i\}_{i=1}^k$ are not linearly independent the oblique projector $ \hat{E}_{{\cal{V}}_k {\cal{W}^\bot}}$ is not unique. Indeed, if $ \{w_i^k\}_{i=1}^k$ are dual vectors giving rise to $ \hat{E}_{{\cal{V}}_k {\cal{W}^\bot}}$ then one can construct infinitely many duals as:

$\displaystyle \tilde {y}_i= w_i^k+ y_i - \sum_{j=1}^k y_j \langle v_j , w_i^k\rangle 
 \quad i=1,\ldots,k,$ (20)

where $ y_i,  i=1,\ldots,k$ are arbitrary vectors in $ {\cal{H}}$ (see [10]).