Highly Nonlinear Approximations for Sparse Signal Representation

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

• Home
• maths@Aston
• EPSRC Home

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:

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

$$\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
  $$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
  $${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.

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