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

CoSamp - Nuit Blanche - version 19

by Igor Carron

Status: Passed
Results: 145027373 (cyc: 3, node: 371)
CPU Time: 137.052
Score: 299011.0
Submitted at: 2010-05-02 13:12:39 UTC
Scored at: 2010-05-02 13:16:38 UTC

Current Rank: 4188th (Highest: 1506th )
Based on: CoSamp - Nuit Blanche - version 18 (diff)
Basis for: CoSamp - Nuit Blanche - version 20 (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 224346132 on the test suite (79318759 more than the contest suite). It has a ranking of 4194 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))


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/5);
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