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
