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

CoSamp - Nuit Blanche - version 7

by Igor Carron

Status: Passed
Results: 196586089 (cyc: 3, node: 327)
CPU Time: 92.813
Score: 393280.0
Submitted at: 2010-05-01 23:49:47 UTC
Scored at: 2010-05-01 23:52:15 UTC

Current Rank: 4195th (Highest: 1279th )
Based on: CoSamp - Nuit Blanche - version 6 (diff)
Basis for: CoSamp - Nuit Blanche - version 8 (diff)

Comments
Igor Carron
01 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 Saturday Leap prize
Alan Chalker
11 May 2010
This entry gets a result of 307922654 on the test suite (111336565 more than the contest suite). It has a ranking of 4202 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/15))

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