IEEE Circuits and Systems Magazine - Q1 2020 - 49

V. Adaptation at the Decoder Side
Though, in principle, any convex optimization solver
can be used to solve BPDN, there is a flourishing literature developing alternative reconstruction algorithms.
For example, instead of depending on the i· i1 norm and
its favorable geometry, signal reconstruction can be approached from completely different points of view, e.g.,
from the estimation, or machine learning, or regression
point of view [39]-[41]. Moreover, procedures exist that
retrieve the original signal by generating solutions to
FIRST QUARTER 2020

y = Bp iteratively and adjusting their sparsity at each
step. Different heuristics may be used to promote sparsity and this gives rise to different methods [5]-[7].
The simple structure of these methods, and their good
performance, make them ideal for CS embodiments
in which the resources devoted to signal reconstruction are limited. As an example, the approach of Orthogonal Matching Pursuit (OMP) tries to reconstruct
supp (p ) = " j ; p j ! 0 , iteratively by looking for the columns of B that have the highest correlation with the
measurements vector y, a simplified pseudo-code being
in Table I.
Among this abundance, few methods concentrate on
adapting the decoding procedure to the features of the
signal. Since the task of the decoder is to retrieve the
sparse representation p, it is most natural to exploit priors applying to that space.

coh-S
coh-C
coh-X
coh-B
coh-L
coh-E

60
50

40
30
20
i.i.d

10
0

40
ARSNR
(a)

pow-C
pow-P
pow-R
60

coh-S
coh-C
coh-X
coh-B
coh-L
coh-E

60
50
40
m

substituting A j, k with m -1/2 sign (A j, k) to obtain antipodal adapted matrices.
Figure 5 and Figure 6 plot the number of measurements against the ARSRN that they allow to achieve.
Since n = 128, the vertical span is limited to m # n/2 = 64
to zoom in the area in which the compression rate is
at least 2:1. From the shape of all the curves in the figures it is clear that performance tends to saturate when
m 2 64.
In all plots, the i.i.d. reference case is the black line.
Plots are from the designer's point of view: one chooses
the reconstruction quality along the horizontal axis and
finds the minimum number of measurements (and thus
the compression ratio) needed to obtain it. Hence, the
lower the curve, the better the method in exploiting the
features of the signal to optimize CS performance.
Note that the methods behave differently in the dictionary and orthonormal basis cases. In particular, it is
very interesting to notice that the best option in the dictionary case (pow-P), yields extremely low performance
in the basis case, in which pow-R consistently delivers
the best performance.
It is also to notice that coherence-based methods
(dashed lines) seem to provide smaller improvements
with respect to power-based methods (solid lines) and
to suffer more from antipodal quantization passing from
Figure 5 to Figure 6. On the contrary, antipodal quantization does not cause any severe loss in performance to
the i.i.d. reference case and to the power-based method.
Overall, adaptation proves to be quite effective. As
an example, consider a target ARSNR of 60 dB for a dictionary-based CS. In both unconstrained or antipodal
A cases, non-adapted CS needs m i.i.d. = 57 measurements for a 2.2:1 compression ratio. The pow-P method reduces it to m pow - P = 38 for unconstrained A and
m pow - P = 40 for antipodal A thus yielding compression
ratios of 3.4:1 and 3.2:1 respectively.
In the basis case, non-adapted CS needs m i.i.d. = 39
measurements for a 3.3:1 compression ratio. Yet, the
pow-R method yields m pow - P = 32 in both the unconstrained and antipodal A cases, thus bringing compression ratio to 4:1.

30
20
i.i.d

10
0

40
ARSNR
(b)

pow-C
pow-P
pow-R
60

Figure 6. Performance of different encoder adaptation policies when A j, k = ! m -1/ 2: (a) D is a random dictionary; (b) D
is a random orthonormal basis.

IEEE CIRCUITS AND SYSTEMS MAGAZINE

IEEE Circuits and Systems Magazine - Q1 2020

Table of Contents for the Digital Edition of IEEE Circuits and Systems Magazine - Q1 2020