# 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 , 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 be the -dictionary's atoms rendering such a representation and the space they span. The sparsity property of a representation implies that is a subspace considerably smaller than the image space . We can then construct a complementary subspace , such that , and compute the dual vectors yielding the oblique projection onto along . Thus, the coefficients of the sparse representation can be calculated as: (37)

Now, if we take a vector in and add it to the image forming the vector to replace in (37), since is orthogonal to the duals , we still have (38)

This suggests the possibility of using the sparse representation of an image to embed the image with additional information stored in the vector . In order to do this, we apply the earlier proposed scheme to embed redundant representations , which in this case operates as described below.

Embedding Scheme

We can embed numbers into a vectors as follows.

• Take an orthonormal basis for and form vector as the linear combination • Add to to obtain Information Retrieval

Given retrieve the numbers as follows.

• Use to compute the coefficients of the sparse representation of as in (38). Use this coefficients to reconstruct the image • Obtain from the given and the reconstructed as . Use and the orthonormal basis to retrieve the embedded numbers as One can encrypt the embedding procedure simply by randomly controlling the order of the orthogonal basis or by applying some random rotation to the basis, requiting a key for generating it. An example is given in the next section.

Subsections