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

CoSamp - Nuit Blanche - version 28

by Igor Carron

Status: Passed
Results: 144886774 (cyc: 3, node: 378)
CPU Time: 134.679
Score: 296837.0
Submitted at: 2010-05-02 22:36:20 UTC
Scored at: 2010-05-02 22:49:41 UTC

Current Rank: 4187th (Highest: 1860th )
Based on: CoSamp - Nuit Blanche - version 27 (diff)

Comments
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 223945676 on the test suite (79058902 more than the contest suite). It has a ranking of 4193 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)
queryLimit = queryLimit -1;
nmeas = min(queryLimit,floor(imageSize*imageSize/1000));
nmeas = max(1,nmeas);

mask1 = true(imageSize);
pixelSum1 = queryImage(mask1)
 
for i=1:nmeas
       v = rand(imageSize);
       vt1 = v < 0.5;
       mask = vt1;
       vt2=double(vt1);
       pixelSum = queryImage(mask);
      pixelSum = pixelSum - pixelSum1/2;
      vt2 = vt2 - 1/2*ones(imageSize);
       B(i,:) = reshape(vt2,imageSize*imageSize,1);
       y(i) = pixelSum;
end
nmeas1 = floor(nmeas/7);
sigma_min = max(1,nmeas1);
            [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