function suspect = counterfeit_detection_compressed ( n, coin, correct, k )

%*****************************************************************************80
%
%% counterfeit_detection_compressed detects counterfeit coins.
%
%  Discussion:
%
%    We are given the weights of N coins, and the correct weight of a single 
%    coin.  We are asked to identify the counterfeit coins, that is, those
%    with incorrect weight.  We don't know how many such coins there are.
%
%    We use techniques from compressed sensing.
%
%  Licensing:
%
%    This code is distributed under the GNU LGPL license.
%
%  Modified:
%
%    10 March 2019
%
%  Author:
%
%    John Burkardt
%
%  Reference:
%
%    Kurt Bryan, Tanya Leise,
%    Making do with less: an introduction to compressed sensing,
%    SIAM Review,
%    Volume 55, Number 3, September 2013, pages 547-566.
%
%  Parameters:
%
%    Input, integer n, the number of coins.
%
%    Input, real coin(n), the weights of the coins.
%
%    Input, real correct, the correct weight of a single coin.
%
%    Input, integer k, the number of rows to use in the sensing matrix.
%
%    Output, integer suspect, the index of the suspected counterfeit coin.
%
  coin = coin(:);

  phi = randi ( [ 0, 1], k, n );

  b = phi * coin - correct * sum ( phi, 2 );
%
%  Find x which minimizes ||x||_1 subject to phi*x=b.
%
  f = ones ( n, 1 );
  lb = zeros ( n, 1 );
  ub = ones ( n, 1 );

  x = linprog ( f, [], [], phi, b, lb, [] );
  suspect = find ( x );

  return
end

