Discreteness and Sparsity

Discrete signals may be sparse, whereas sparse signals may not be discrete.

Let us consider the following signal:
   x = [1,1,-1,1,-1,-1,1,1];
This is a discrete signal generated from an alphabet {1,-1}. This is obviously not sparse, but if we transform this into
   x - 1 = [0,0,-2,0,-2,-2,0,0]
we have a sparse signal. Also,
   x + 1 = [2,2,0,2,0,0,2,2]
is sparse. Let's adapt this idea to discrete signal reconstruction.

Discrete Signal Reconstruction  
Find the original n-dimensional discrete signal x over a finite alphabet
   X = {r₁,r₂,...,r_L}
with its probability distribution
   P(r_j) = p_j,   0 < p_j <1,   p₁ + p₂ + ... + p_L = 1
from incomplete linear measurements
   y = Ax
where A is an m-times-n matrix (m < n).

In this problem, each vector x - r_j is sparse, and hence its ell-1 norm may be small if the probability p_j is large. This observation leads to optimization with the sum of absolute values (SOAV):

  minimize   p₁||x - r₁||₁ + p₂||x - r₂||₁ +...+ p_L||x - r_L||₁
  subject to   y = Ax

Let's apply this to binary-valued image reconstruction. The following is a 37x37-pixel binary image disturbed by random Gaussian noise.

Then we transform this into frequency-domain data via discrete Fourier transform (DFT), and then randomly down-sample rows to generate half-size data. Then apply the SOAV optimization to reconstruct the original binary image. The following is the result.

For comparison, we also use the basis pursuit (BP) that minimizes the ell-1 norm of x instead of the sum of absolute values. The following is the result of BP:

This is quite bad since BP only uses the property of sparsity in the original image while the SOAV approach takes the discreteness into account.

If you are interested in this work, please see the original paper:

M. Nagahara, Discrete Signal Reconstruction by Sum of Absolute Values, IEEE Signal Processing Letters, vol. 22 no. 10, pp. 1575-1579, Oct 2015 (to appear)

PDF can be downloaded from here and the MATLAB codes are available here.