Finish 2010-05-05 12:00:00 UTC

CoSamp - Nuit Blanche - version 10

by Igor Carron

Status: Passed
Results: 190934415 (cyc: 3, node: 340)
CPU Time: 89.117
Score: 381943.0
Submitted at: 2010-05-02 00:30:12 UTC
Scored at: 2010-05-02 00:32:42 UTC

Current Rank: 4194th (Highest: 1279th )
Based on: CoSamp - Nuit Blanche - version 9 (diff)
Basis for: CatCheckilg (diff)
Basis for: CoSamp - Nuit Blanche - version 11 (diff)
Basis for: CoSamp - Nuit Blanche - version 12 (diff)

Comments
Igor Carron
02 May 2010
This entry uses the CoSamp code. One of the few reconstruction code used in Compressive Sensing. More codes can be found here: http://sites.google.com/site/igorcarron2/cs#reconstruction

Nuit Blanche is a blog focused on Compressive Sensing: http://nuit-blanche.blogspot.com/search/label/CS
Alan Chalker
10 May 2010
This entry was submitted during the Daylight phase and was eligible for the Sunday Push prize
Alan Chalker
11 May 2010
This entry gets a result of 304116581 on the test suite (113182166 more than the contest suite). It has a ranking of 4199 compared to all other entries run against the test suite according to the data set provided by Jan Keller.
Please login or create a profile.
Code
function Aest = solver(imageSize, queryLimit)

nmeas = max(1,floor(imageSize/20))

if nmeas == 1
       nmeas = max(1,querylimit)
end
 
for i=1:nmeas
       v = rand(imageSize);
       vt1 = v < 0.5;
       mask = vt1;
       vt2=double(vt1);
       pixelSum = queryImage(mask);
       B(i,:) = reshape(vt2,imageSize*imageSize,1);
       y(i) = pixelSum;
end
sigma_min = max(1,floor(imageSize/2));
            [xx,dd] = cosamp(B, y',sigma_min,1.0e-4);
Aest = reshape(xx,imageSize,imageSize);


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [Sest,d]=cosamp(Phi,u,K,tol1)

% Cosamp algorithm
%   Input
%       K : sparsity of Sest
%       Phi : measurement matrix
%       u: measured vector
%       tol1 : tolerance for approximation between successive solutions. 
%   Output
%       Sest: Solution found by the algorithm
%       d   : success index (d=1 is success, d = 0 is no convergence)
%
% Algorithm as described in "CoSaMP: Iterative signal recovery from 
% incomplete and inaccurate samples" by Deanna Needell and Joel Tropp.
% 
% This implementation was written by David Mary
%
% This script/program is released under the Commons Creative Licence
% with Attribution Non-commercial Share Alike (by-nc-sa)
% http://creativecommons.org/licenses/by-nc-sa/3.0/
% Short Disclaimer: this script is for educational purpose only.
% Longer Disclaimer see  http://igorcarron.googlepages.com/disclaimer

% Initialization
Sest=zeros(size(Phi,2),1);
utrue = Sest;
v=u;
t=1; T2=[];
while t < 101 
[k,z]=sort(abs(Phi'*v));k=flipud(k);z=flipud(z);
Omega=z(1:2*K);
T=sort(union(Omega,T2));phit=Phi(:,T);
% The next step is the one that can be improved with a Conjugate Gradient
% algorithm
b=abs(pinv(phit)*u);
[k3,z3]=sort((b));k3=flipud(k3);z3=flipud(z3);
Sest=zeros(size(utrue));
Sest(T(z3(1:K)))=abs(b(z3(1:K)));
[k2,z2]=sort(abs(Sest));k2=flipud(k2);z2=flipud(z2);
T2=z2(1:K);
v=u-Phi*Sest;
d=0;n2=norm(abs(v),'inf');
if n2 < tol1
    d=1;t=1e10;
end
 t=t+1;
 end
 d = 0