% Algorithm implementing the Sparse Measurement Matrix
% construction of Radu Berinde and Piotr Indyk in
% "Sparse Recovery Using Sparse Random Matrices"
% d is the number of ones per column
% m is the number of rows
% n is the number of columns
% generally m should be much less than n
% n is limited by (m,d) or
% Written by Igor Carron
% m rows
% n columns
% with these parameters it works with n=10
% but it does not work with n greater than 10
jj = 0;
while sum(A(:,i),1)~=d | jj==47
v1 = diag(A(:,i))'*ones(m,n);
w = A - v1;
if w(:,j)== zeros(m,1)
jj = 47;
% Measurement Matrix is A
Some people might think there is an error in j = 47, they think it is j =42. They are wrong. Also while this is a binary matrix, it can be used with non-binary objects. [ Update: I have made it a function and it is available here. It is working as nicely as the normal measurement matrices on the example set I used it on].
Credit Photo: NASA/JPL/ Space Science Institute, Saturn and Titan on June 9, 2006.