Instrumentation & Measurement Magazine 23-2 - 97




that y = Ax, and we know that x is s-sparse. It should be possible

to compress y. One way would be to find the linear combina

tion of columns of A that gives y-to find x-and to save the
location of the columns and the "amount" of each that goes

into y. That, however, is not generally a simple problem. Often
it is possible to "design" an additional M × K , M  K matrix, B,
that we can use to compress
our measurements by calculating


b
=
By
with
only M elements. Thus, each
a compressed
vector


b
is
a
linear
combination
of the elements of y, and
element
of

b does not have many elements. This is the "compression" of
compressive sensing.




At this point, we find
 that b = By = BAx ≡ Cx where C = BA.

Given that x is sparse, b is a combination of a few columns of
C. As we have seen, in order to be able to find a sparse vector


x given b, the matrix C must satisfy certain conditions. If x is
s-sparse, then at a minimum we need to know that any 2s columns of C are linearly independent. It is easy to show that this
implies that any 2s columns of A must be linearly independent.
The matrix A is derived from the signals being sampled.
Once it is chosen, the matrix B must be designed in such a way
that C is appropriate for use with one of the three types of algorithms described above. One way of designing the matrix B
is to draw its elements randomly. (For more about this possibility see, for example, [8].) Another method, and the one we
use, is to draw matrices from a set of matrices with desirable
properties and then check to see whether the matrix is actually
appropriate.
Having found an appropriate matrix B, let C = AB. The matrix C is now our
 dictionary, our words are the columns of C,
and the vector b is a linear combination of a small number of
columns of C.
 

To recover y, we calculate the s-sparse solution of Cx = b us
ing one of the three methods described above. Having found x,



we then recover y by calculating y = Ax.

The Signal and How We Sample It
We designed and built a system that uses compressive sensing to take samples at a rate lower than the Nyquist rate, sends
the samples to a PC running MATLAB, and then uses MATLAB to un-compress the samples. The measurement system
has several stages and involved doing a bit of interesting analog electronics work.
As we have discussed, compressive sensing can be used
when you know that your signal is a linear combination of a
few signals from a larger set of signals. To keep things simple, we assumed that our signal was either a constant or one
of three frequencies-all of which were lower than 1 kHz, and
one of which was close to 1 kHz. Because the sinusoid's phase
was not known, we had to assume that the sinusoid was a
linear combination of a sine and a cosine at one of "our" frequencies. Thus, our A matrix has seven columns.
We then took five samples of the signal and stored them using a simple analog delay line of our own design. Thus, our A
matrix has five rows. At this stage, we sampled at 2 kHz-but
these samples were not transmitted to the "outside" world,
and this is not the rate at which our microcontroller's A/D
April 2020


sampled. These five samples are "our" y-and the next stage
is to compress them.


To summarize, at this stage we know that y = Ax where the

matrix A has seven columns and five rows, the vector x has

seven elements, and the vector y has five elements. One column of A is a constant vector, and the other six columns are
samples of sines and cosines at the three frequencies we are using. As we either send one of "our" sinusoids or a constant, we



know that y = Ax and x is 2-sparse. We want to take advantage

of the fact that the vector x never has more than two non-zero

elements to compress the vector y.
Because, other than the microcontroller we used, we built
everything, we wanted to compress the samples in the simplest possible way. To do this, we "designed" the matrix B to
have four rows and five columns and to have all of its elements

be zeros or ones. In this way, B takes the five samples in y and
compresses them into the four elements of b. The design considerations turn out to be quite interesting.

Designing the "Compression Matrix"
Despite the fact that for large problems the brute force method
is not practical, for relatively small ones it is practical, and it
gives you somewhat more freedom when choosing the matrix
B. For this reason, we decided to use the brute force method to
un-compress our data. We drew potential B matrices at random from the set of matrices all of whose elements were ones
and zeros and tried to determine how well the brute force
method would perform for each matrix-to what extent it
would be noise-resistant.
In order to make this determination, we made use of the
condition number. (See the Sidebar: The Condition Number

Sidebar: The Condition Number of
a Matrix



Let A be a "generic" invertible
matrix, and let x and b



be vectors
that satisfy Ax = b. Then

 you can calculate x
−1
as A b. Suppose that the vector b is something that was
measured and that the measurement was noisy-that
rather
  than measuring the exact value, you measured
b + n. Then, when you try to calculate x, you actually
 


calculate A −1 b + n = x + A −1n. We need to know how
−1 
to know how
big an annoyance is A n may be. We need

−1
A
b
.
large this term may be relative
to

In the worst case, A −1b is "amplified" very little

while A −1n is amplified a lot. The condition number is
designed to measure how bad the worst case here can
be.
For symmetric matrices, the condition number is the
ratio of the absolute value of the largest eigenvalue (in
absolute value) of the matrix to the absolute value of the
smallest eigenvalue (in absolute value) of the matrix.
(For more information about the condition number, see,
for example, [9].)

(

)

IEEE Instrumentation & Measurement Magazine 97

Instrumentation & Measurement Magazine 23-2

Table of Contents for the Digital Edition of Instrumentation & Measurement Magazine 23-2