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 two other answers. 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 - 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