Highly Nonlinear Approximations for Sparse Signal Representation

Logo EPSRC

Sparsity and `something else'

We present here a `bonus' of sparse representations by alerting that they can be used for embedding information. Certainly, since a sparse representation entails a projection onto a subspace of lower dimensionality, it generates a null space. This feature suggests the possibility of using the created space for storing data. In particular, in a work with James Bowley [35], we discuss an application involving the null space yielded by the sparse representation of an image, for storing part of the image itself. We term this application `Image Folding'.

Consider that by an appropriate technique one finds a sparse representation of an image. Let $ \{v_{\ell_i}\}_{i=1}^K$ be the $ K$-dictionary's atoms rendering such a representation and $ {\cal{V}}_K$ the space they span. The sparsity property of a representation implies that $ {\cal{V}}_K$ is a subspace considerably smaller than the image space $ \mathbb{R}^N \otimes \mathbb{R}^N$. We can then construct a complementary subspace $ {\cal{W}^\bot}$, such that $ \mathbb{R}^N \otimes \mathbb{R}^N = {\cal{V}}_K \oplus {\cal{W}^\bot}$, and compute the dual vectors $ \{w_i^K\}_{i=1}^K$ yielding the oblique projection onto $ {\cal{V}}_K$ along $ {\cal{W}^\bot}$. Thus, the coefficients of the sparse representation can be calculated as:

$\displaystyle c_i= \langle w_i^K, I \rangle ,   i=1,\ldots,K.$ (37)

Now, if we take a vector in $ F \in {\cal{W}^\bot}$ and add it to the image forming the vector $ G = I + F$ to replace $ I$ in (37), since $ F$ is orthogonal to the duals $ \{w_i^K\}_{i=1}^K$, we still have

$\displaystyle \langle w_i^K , G \rangle =\langle w_i^K , I + F \rangle = \langle w_i^K , I 
 \rangle =c_i,\;i=1,\ldots,K.$ (38)

This suggests the possibility of using the sparse representation of an image to embed the image with additional information stored in the vector $ F \in {\cal{W}^\bot}$. In order to do this, we apply the earlier proposed scheme to embed redundant representations [34], which in this case operates as described below.

Embedding Scheme

We can embed $ H$ numbers $ {{h_i, i=1,\ldots,H}}$ into a vectors $ F \in {\cal{W}^\bot}$ as follows.

  • Take an orthonormal basis $ z_i, i=1,\ldots,H$ for $ {{\cal{W}^\bot}}$ and form vector $ F$ as the linear combination

    $\displaystyle F= \sum_{i=1}^H {h_i} z_i.$

  • Add $ F$ to $ I^K$ to obtain $ G= I^K+ F$

Information Retrieval

Given $ G$ retrieve the numbers $ {{h_i, i=1,\ldots,H}}$ as follows.

  • Use $ G$ to compute the coefficients of the sparse representation of $ I$ as in (38). Use this coefficients to reconstruct the image $ \tilde {I}^K= \sum_{i=1}^K c_i^K v_i^K$
  • Obtain $ F$ from the given $ G$ and the reconstructed $ \tilde {I}^K$ as $ F=G- \tilde {I}^K$. Use $ F$ and the orthonormal basis $ z_i, i=1,\ldots,H$ to retrieve the embedded numbers $ {{h_i, i=1,\ldots,H}}$ as

    $\displaystyle {h_i} = \langle z_i , F\rangle ,  i=1,\ldots,H$

One can encrypt the embedding procedure simply by randomly controlling the order of the orthogonal basis $ z_i, i=1,\ldots,H$ or by applying some random rotation to the basis, requiting a key for generating it. An example is given in the next section.

Subsections