IEEE Circuits and Systems Magazine - Q1 2020 - 48

using the polytope interpretation of CS when D is an
orthonormal basis.
To illustrate the core concept rotate Figures 3-(b)
until it appears as Figure 4. From this point of view, it
is clear that BP is not effective as the angle i between
ker B and the signal p ) is equal to the angle between the
sparse representation of the signal itself and a facet of
the cross-polytope.
To generalize such an unfavorable condition, indicate with A (p )) the union of the facets that are adjacent to p ). As an example, in Figure 3, A (p )) is made
of the four segments (1-dimensional facets) and the 4
triangles (2-dimensional facets) on the surface of the
blue cross-polytope that have p ) as a vertex. Based on
A (p )), define the set H (p )) of the angles formed by the
sparse representation of the signal with any segment

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

60
50

m

40
30
20
i.i.d

10
0

20

40
ARSNR
(a)

pow-C
pow-P
pow-R
60

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

60
50

m

40
30
20
i.i.d

10
0

20

40
ARSNR
(b)

pow-C
pow-P
pow-R
60

Figure 5. Performance of different encoder adaptation policies when A is unconstrained: (a) D is a random dictionary;
(b) D is a random orthonormal basis.

48

IEEE CIRCUITS AND SYSTEMS MAGAZINE

having p ) as a vertex and lying on A (p )). Problems
arise when the angle i between ker B and p ) belongs
to H (p )).
To prevent this from happening, we may choose a
B such that the angle i is larger than max H (p )). Since
im B < is orthogonal to ker B this translates into the requirement that the angle z between the rows of B (whose
linear combinations yield im B <) and p ) is smaller than
r/2 - max H (p )). If D is orthonormal, the angles between
the rows of B and p ) are the same as those between the
rows of BD < = A and Dp ) = x ) .
Finally, given x ) and assuming that the rows of A
are normalized to the same length, reducing the angle means increasing the magnitude of each entry of
y = Ax, i.e., its energy.
IV. Encoder Adaptation at Work
We test the above methods in a common environment
with n = 128 and in which D is either a random orthonormal matrix or a random dictionary with d = 256 and
normalized columns. Sparsity is set to l = 6.
Each signal window is generated starting from a
random vector x l + N (0, R xl) for a certain R xl. Such
a vector is then decomposed along D by setting
pl = argmin p ! R d p 1 s.t. x l = Dpl. The vector pl is then
sparsified into the vector pm by keeping only the l largest components while setting the others to 0. The signal
is finally generated as x = Dpm. The matrix R xl is chosen
to make x slightly low-pass and L x - 0.03 of the same
magnitude of some classical real-world signals.
Whatever method is used to build the matrix A,
we compute the measurement vector y = Ax + o with
o + N (0, 10 -6 I m) and go from y to an estimation xt of x
by means of BPDN as implemented in [38].
We evaluate the quality of reconstruction with
the Reconstruction Signal-to -Noise -Ratio ( RSNR)
x 22 / x - xt 22 . Performance is assessed by considering
4000 Montecarlo trials and computing the average RSNR
that we indicate with ARSNR. Though average performance is not a complete characterization of the effectiveness of CS it will suffice here to give a general idea of
what can be obtained by adaptation.
As a reference case we assume the one in which the
entries of A, before energy normalization, are independent normals N (0, 1). It is a classical setting that we label as "i.i.d." and allows to quantify the improvements
due to different adaptation policies4
Since hardware implementations greatly benefit from
constraining the A j, k to a small number of possible values, we also consider, as a second setting, the option of
4
The MATLAB code used to obtain these results is available at https://
goo.gl/6hknan.

FIRST QUARTER 2020
https://www.dropbox.com/s/tyqy10wkpwatlk1/supplementary%20material.zip?dl=0 https://www.dropbox.com/s/tyqy10wkpwatlk1/supplementary%20material.zip?dl=0
IEEE Circuits and Systems Magazine - Q1 2020

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