Instrumentation & Measurement Magazine 23-2 - 96

Sidebar: Implementing the Brute-Force Technique
The following function implements the brute-force technique. It is simple, but be careful; it is not very efficient.
function x = bf(C, b)
% The function x = bf(C, b) calculates the sparse solution of the equation
% C x = b by the brute force method.
[M N] = size(C);
list_coms = nchoosek(1:N, M);
% The command nchoosek(1:N, M) produces a matrix with all combinations of M
% of the N numbers from 1 to N.
num_coms = length(list_coms);
not_done = 1;
non_zeros = (M+1)/2;
% Assuming that any group of M columns is independent, then a solution with
% fewer than (M + 1)/2 non-zero elements is unique among all such
% solutions.
i = 1;
while not_done
  D = C(:,list_coms(i,:));
  pos_x = D\b;
  num_non_zero = sum(abs(pos_x) > 10^-6);
  % As we are doing numerical calculations, we cannot require that the
  % zero elements be precisely zero. Because of rounding errors that is
  % unlikely to ever happen. Instead we check how many elements have
  % very small absolute values.
  if num_non_zero < non_zeros
   x = zeros(N,1);
   x(list_coms(i,:)') = pos_x;
   not_done = 0;
  else
   i = i+1;
  end
end

	

2 
Cx − x
2
x

Remarks

2

<  .	

Such a matrix is said to ( , s )-RIP.
If a matrix is ( , 2s )-RIP and  < 1, then it can be shown that
any 2s columns of the matrix are linearly independent, and the
brute force
technique can be used to find all s-sparse solutions
 
of Cx = b.  If a matrix is ( , 2s )-RIP and
	

<

1
2 +1

≈ 0.4,	

 
then searching for s-sparse solutions of Cx = b is equivalent to
searching for the solution for which the sum of the absolute val
ues of the elements of x obtains its minimum-a method known
as basis pursuit. As with orthogonal matching pursuit, so with
basis pursuit: Basis pursuit can be used on a subset of the matrices on which the brute force method works. There are, however,
many very efficient algorithms (such as the simplex algorithm
[6] and interior point methods [7]) for solving this problem.
96	

We have seen that when you know enough about a matrix C,
there are many ways of finding a sparse solution if one exists.
We have also seen that the conditions needed to guarantee that
efficient techniques will work are sufficient to guarantee that
the brute force method will work. This explains how a problem that is provably very, very hard to solve can be solved
easily. When you only restrict the class of matrices minimally,
the problem is indeed very, very difficult to solve, and there is
no efficient way to solve it. When you require the matrix C to
satisfy additional conditions, such as having low coherence or
satisfying the RIP, then there are efficient algorithms to solve
the problem.

Compressing Measured Values of a
Signal
Suppose that we are sampling K samples of a signal and that

we store the samples in a vector, y. In addition, assume that we

know that the samples we acquire, y, are a combination of only
s columns of a K × N matrix, A, and that s  K. That is, suppose

IEEE Instrumentation & Measurement Magazine	

April 2020



Instrumentation & Measurement Magazine 23-2

Table of Contents for the Digital Edition of 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