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*

_{1},

*r*

_{2},...,

*r*

_{L}}

*with its probability distribution*

**P**(

*r*

_{j}) =

*p*

_{j}, 0 <

*p*

_{j}<1,

*p*

_{1 }+

*p*

_{2 }+ ... +

*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*is large. This observation leads to optimization with the

_{j}*sum of absolute values (SOAV)*:

minimize

*p*

_{1}||

*x*-

*r*

_{1}||

_{1}+

*p*

_{2}||

*x*-

*r*||

_{2}_{1}+...+

*p*

_{L}||

*x*-

*r*

_{L}||

_{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:If you are interested in this work, please see the original paper:

M. Nagahara, Discrete Signal Reconstruction by Sum of Absolute Values,PDF can be downloaded from here and the MATLAB codes are available here.IEEE Signal Processing Letters, vol. 22 no. 10, pp. 1575-1579, Oct 2015 (to appear)

Hi Masaaki

ReplyDeleteThis 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 http://dx.doi.org/10.1109/JPROC.2010.2045630, 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 http://vbn.aau.dk/en/publications/downsampling-of-dft-precoded-signals-for-the-awgn-channel(18feb133-b4d2-4e62-867b-1714dae6c931).html

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.