Mar 28, 2015

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 = {r1,r2,...,rL}
with its probability distribution
   P(rj) = pj,   0 < pj <1,   pp+ ... + p= 1
from incomplete linear measurements
   y = Ax
where A is an m-times-n matrix (m < n).

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

  minimize   p1||x - r1||1 + p2||x - r2||1 +...+ pL||x - rL||1
  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.

1 comment:

  1. Hi Masaaki
    This is an interesting approach that I had not thought about before.
    I have previously thought of the binary discrete-valued problem as a special case of what Donoho & Tanner call K-simple signals in, i.e. a 0-simple signal. Have you compared your approach to what they call example 3 in their introduction?
    We have also developed a semi-definite relaxation to tackle undersampled discrete signals in
    Finally, it also seems to me that GAMP should be able to handle this by defining a suitable discrete input probability mass function for it.