# Instrumentation & Measurement Magazine 23-2 - 95

```are going to see, and that knowledge can be used to reduce the
number of measurements you need to make.
We consider the case where you are processing a vector, and
you know that the vector is a linear combination of a very few
vectors out of a "dictionary" of many vectors. In the language

of linear algebra, we assume that the sampled signal, y, is a linear combination of very few of the columns of a matrix C with
many columns. C is the "dictionary," and the columns of C are
the "words." We further assume that C is a K × N matrix-that
every column of C has K elements and that C has N columns.

The assumption that y is a linear combination of the columns of


C can be expressed by saying that y = Cx. The assumption that
relatively few of the columns are needed can be expressed by

saying that all but a very few elements of x are zero.
It is easy to show that if any 2s columns of C are linearly
in 

dependent, then any solution, x, of the equation Cx = b with s or
fewer non-zero elements is unique among all such solutions.
(See Sidebar: Sparse Solutions are Unique.) Vectors with s or
fewer non-zero elements are said to be s-sparse.

Sidebar: Sparse Solutions are
Unique
Theorem: Given a matrix C such that any 2s of its columns are linearly independent, if there is an s-sparse


solution, x0, of the equation Cx = b, then this solution is
the unique s-sparse solution.
Proof. The proof proceeds by contradiction. Sup

pose that there were two solutions, x1 and x2. The

 
xd = x1 − x2, satisfies
difference of these two solutions,


 
C

x
=
C

x
−
C

x
=
0
. Recall that multiplythe equation
d
1
2
ing a vector by a matrix produces a linear combination
of the matrix's columns. In this case, the equation says
that a linear combination of the columns of C equals
zero, and the number of columns is equal to the number


of non-zero elements in xd. Because xd is the difference of
two vectors each of which has no more than s non-zero

elements, xd can have no more that 2s non-zero elements. That is, a combination of 2s (or fewer) columns
of C gives the zero vector. However, by the definition of
linear independence, that means that there are a set of 2s
or fewer columns of C that are not linearly independent.
That, however, contradicts the hypothesis of the theorem. Thus, under the hypotheses of the theorem, the
difference vector must be the zero vector; the two vectors must actually be the same; and we find that if there
is an s-sparse solution of the equation, then this solution
is the unique s-sparse solution.
For a simple example of recovering uniqueness using sparsity, see, for example, the sidebar in [2]. Note,
too, that the theorem does not guarantee that a sparse
solution exists-you need to know that this is the case.
The theorem guarantees that if a sparse solution exists, it
is the unique sparse solution.

April 2020

Developing the Theory of Compressive
Sensing: Finding the Sparse Solution
Suppose that we have a matrix, C, for which any 2s columns are

linearly independent, and we know that the equation Cx = b
has an s-sparse solution. How can we find that solution? This
is a fascinating and important question, and it has many answers. We start from the simplest answer and then consider

The Brute-Force Technique
Consider a matrix C ∈ R K×N for which K = 2s, K ≤ N, and assume
that any 2s columns of C are linearly independent. Then, one
way to search for the unique sparse solution is to attempt to
sets of K columns of C and then to solve
list all the C KN possible
 
the equations Di  z =  b , i = 1,... , CKN where each matrix Di is composed of a different
 set of K of C's columns. When one finds a

solution, z = Di−1b, that is s-sparse, it must correspond to the correct solution. For MATLAB code that implements this method
and returns the sparse solution, see the Sidebar: Implementing
the Brute-Force Technique.
This technique has a major disadvantage. As C's size grows,
the number of iterations grows very, very quickly. Unfortunately, it has been proved that, in general, the problem of
finding a sparse solution is NP-hard [3]. Despite its seeming inefficiency, in some sense, the "inefficient" algorithm we
have described does about as well as one could hope. Luckily,
despite the fact that the problem we are trying to solve is provably very hard to solve, there are still-sometimes-efficient
ways to solve the problem.

Orthogonal Matching Pursuit


Let ci be the ith column of C. If you know that your solution is ssparse and you know that the matrix C's coherence, defined as:

  c ⋅ c
i
j

 ci ⋅ c j


μ ≡ max  
i ≠ j 


 ,



which is a measure of similarity between columns of C, is
less than 1/(2s), then a simple greedy algorithm, orthogonal
matching pursuit, will find the s-sparse solution. (For more
information, see, for example, [4]. For an example of an application to a measurement problem, see [5].) Note that this
condition is restrictive enough that it can be shown that the
conditions of the theorem in Sidebar: Sparse Solutions Are
Unique certainly obtain; the s-sparse solution is certainly
unique; and the brute force method certainly works too. Orthogonal matching pursuit works on a subset of the matrices
for which the brute force method works, but where it works, it
is efficient.

Methods Based on the Techniques of Linear
Programming or Convex Optimization
Though many think that mathematicians have no sense of humor, this is not so-as the next definition shows. A matrix is
said to have the restricted isometry property, known affectionately as the RIP, when for all s-sparse vectors:

IEEE Instrumentation & Measurement Magazine	95

```

# Instrumentation & Measurement Magazine 23-2

No label
Instrumentation & Measurement Magazine 23-2 - No label
Instrumentation & Measurement Magazine 23-2 - Cover2
Instrumentation & Measurement Magazine 23-2 - 1
Instrumentation & Measurement Magazine 23-2 - 2
Instrumentation & Measurement Magazine 23-2 - 3
Instrumentation & Measurement Magazine 23-2 - 4
Instrumentation & Measurement Magazine 23-2 - 5
Instrumentation & Measurement Magazine 23-2 - 6
Instrumentation & Measurement Magazine 23-2 - 7
Instrumentation & Measurement Magazine 23-2 - 8
Instrumentation & Measurement Magazine 23-2 - 9
Instrumentation & Measurement Magazine 23-2 - 10
Instrumentation & Measurement Magazine 23-2 - 11
Instrumentation & Measurement Magazine 23-2 - 12
Instrumentation & Measurement Magazine 23-2 - 13
Instrumentation & Measurement Magazine 23-2 - 14
Instrumentation & Measurement Magazine 23-2 - 15
Instrumentation & Measurement Magazine 23-2 - 16
Instrumentation & Measurement Magazine 23-2 - 17
Instrumentation & Measurement Magazine 23-2 - 18
Instrumentation & Measurement Magazine 23-2 - 19
Instrumentation & Measurement Magazine 23-2 - 20
Instrumentation & Measurement Magazine 23-2 - 21
Instrumentation & Measurement Magazine 23-2 - 22
Instrumentation & Measurement Magazine 23-2 - 23
Instrumentation & Measurement Magazine 23-2 - 24
Instrumentation & Measurement Magazine 23-2 - 25
Instrumentation & Measurement Magazine 23-2 - 26
Instrumentation & Measurement Magazine 23-2 - 27
Instrumentation & Measurement Magazine 23-2 - 28
Instrumentation & Measurement Magazine 23-2 - 29
Instrumentation & Measurement Magazine 23-2 - 30
Instrumentation & Measurement Magazine 23-2 - 31
Instrumentation & Measurement Magazine 23-2 - 32
Instrumentation & Measurement Magazine 23-2 - 33
Instrumentation & Measurement Magazine 23-2 - 34
Instrumentation & Measurement Magazine 23-2 - 35
Instrumentation & Measurement Magazine 23-2 - 36
Instrumentation & Measurement Magazine 23-2 - 37
Instrumentation & Measurement Magazine 23-2 - 38
Instrumentation & Measurement Magazine 23-2 - 39
Instrumentation & Measurement Magazine 23-2 - 40
Instrumentation & Measurement Magazine 23-2 - 41
Instrumentation & Measurement Magazine 23-2 - 42
Instrumentation & Measurement Magazine 23-2 - 43
Instrumentation & Measurement Magazine 23-2 - 44
Instrumentation & Measurement Magazine 23-2 - 45
Instrumentation & Measurement Magazine 23-2 - 46
Instrumentation & Measurement Magazine 23-2 - 47
Instrumentation & Measurement Magazine 23-2 - 48
Instrumentation & Measurement Magazine 23-2 - 49
Instrumentation & Measurement Magazine 23-2 - 50
Instrumentation & Measurement Magazine 23-2 - 51
Instrumentation & Measurement Magazine 23-2 - 52
Instrumentation & Measurement Magazine 23-2 - 53
Instrumentation & Measurement Magazine 23-2 - 54
Instrumentation & Measurement Magazine 23-2 - 55
Instrumentation & Measurement Magazine 23-2 - 56
Instrumentation & Measurement Magazine 23-2 - 57
Instrumentation & Measurement Magazine 23-2 - 58
Instrumentation & Measurement Magazine 23-2 - 59
Instrumentation & Measurement Magazine 23-2 - 60
Instrumentation & Measurement Magazine 23-2 - 61
Instrumentation & Measurement Magazine 23-2 - 62
Instrumentation & Measurement Magazine 23-2 - 63
Instrumentation & Measurement Magazine 23-2 - 64
Instrumentation & Measurement Magazine 23-2 - 65
Instrumentation & Measurement Magazine 23-2 - 66
Instrumentation & Measurement Magazine 23-2 - 67
Instrumentation & Measurement Magazine 23-2 - 68
Instrumentation & Measurement Magazine 23-2 - 69
Instrumentation & Measurement Magazine 23-2 - 70
Instrumentation & Measurement Magazine 23-2 - 71
Instrumentation & Measurement Magazine 23-2 - 72
Instrumentation & Measurement Magazine 23-2 - 73
Instrumentation & Measurement Magazine 23-2 - 74
Instrumentation & Measurement Magazine 23-2 - 75
Instrumentation & Measurement Magazine 23-2 - 76
Instrumentation & Measurement Magazine 23-2 - 77
Instrumentation & Measurement Magazine 23-2 - 78
Instrumentation & Measurement Magazine 23-2 - 79
Instrumentation & Measurement Magazine 23-2 - 80
Instrumentation & Measurement Magazine 23-2 - 81
Instrumentation & Measurement Magazine 23-2 - 82
Instrumentation & Measurement Magazine 23-2 - 83
Instrumentation & Measurement Magazine 23-2 - 84
Instrumentation & Measurement Magazine 23-2 - 85
Instrumentation & Measurement Magazine 23-2 - 86
Instrumentation & Measurement Magazine 23-2 - 87
Instrumentation & Measurement Magazine 23-2 - 88
Instrumentation & Measurement Magazine 23-2 - 89
Instrumentation & Measurement Magazine 23-2 - 90
Instrumentation & Measurement Magazine 23-2 - 91
Instrumentation & Measurement Magazine 23-2 - 92
Instrumentation & Measurement Magazine 23-2 - 93
Instrumentation & Measurement Magazine 23-2 - 94
Instrumentation & Measurement Magazine 23-2 - 95
Instrumentation & Measurement Magazine 23-2 - 96
Instrumentation & Measurement Magazine 23-2 - 97
Instrumentation & Measurement Magazine 23-2 - 98
Instrumentation & Measurement Magazine 23-2 - 99
Instrumentation & Measurement Magazine 23-2 - 100
Instrumentation & Measurement Magazine 23-2 - 101
Instrumentation & Measurement Magazine 23-2 - 102
Instrumentation & Measurement Magazine 23-2 - 103
Instrumentation & Measurement Magazine 23-2 - 104
Instrumentation & Measurement Magazine 23-2 - 105
Instrumentation & Measurement Magazine 23-2 - 106
Instrumentation & Measurement Magazine 23-2 - 107
Instrumentation & Measurement Magazine 23-2 - 108
Instrumentation & Measurement Magazine 23-2 - 109
Instrumentation & Measurement Magazine 23-2 - 110
Instrumentation & Measurement Magazine 23-2 - 111
Instrumentation & Measurement Magazine 23-2 - 112
Instrumentation & Measurement Magazine 23-2 - 113
Instrumentation & Measurement Magazine 23-2 - 114
Instrumentation & Measurement Magazine 23-2 - 115
Instrumentation & Measurement Magazine 23-2 - 116
Instrumentation & Measurement Magazine 23-2 - 117
Instrumentation & Measurement Magazine 23-2 - 118
Instrumentation & Measurement Magazine 23-2 - 119
Instrumentation & Measurement Magazine 23-2 - 120
Instrumentation & Measurement Magazine 23-2 - Cover3
Instrumentation & Measurement Magazine 23-2 - Cover4
https://www.nxtbook.com/allen/iamm/24-6
https://www.nxtbook.com/allen/iamm/24-5
https://www.nxtbook.com/allen/iamm/24-4
https://www.nxtbook.com/allen/iamm/24-3
https://www.nxtbook.com/allen/iamm/24-2
https://www.nxtbook.com/allen/iamm/24-1
https://www.nxtbook.com/allen/iamm/23-9
https://www.nxtbook.com/allen/iamm/23-8
https://www.nxtbook.com/allen/iamm/23-6
https://www.nxtbook.com/allen/iamm/23-5
https://www.nxtbook.com/allen/iamm/23-2
https://www.nxtbook.com/allen/iamm/23-3
https://www.nxtbook.com/allen/iamm/23-4
https://www.nxtbookmedia.com