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, p1 + p2 + ... + pL = 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:
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.
