sl20.m

Non Convex Algorithms for Group Sparse Optimization by Angshul Majumdar @matlab central

function s=SL20(A, x, group, sigma_min)

% Solution to the optimization problem min||s||_2,0 subject to x = As
% This is an NP hard problem. It is solved iteratively by smoothing the
% mixed ||.||_2,0 norm
% This algorithm is based upon the SL0 algorithm from the following webpage
%
% Web-page:
% ------------------
%    http://ee.sharif.ir/~SLzero
%
% % Copyright (c) Angshul Majumdar 2009

% Input
% A = N X d dimensional measurment matrix
% y = N dimensional observation vector
% group = labels

% Output
% s = estimated sparse signal

MaxIter = 2500; j = 0;

    sigma_decrease_factor = 0.5;
    A_pinv = pinv(A);
    mu_0 = 2;
    L = 3;
    ShowProgress = logical(0);

NoOfGroups = length(unique(group));
for i = 1:NoOfGroups
    GroupInd{i} = find(group == i);
end

% Initialization
%s = A\x;
s = A_pinv*x;
sigma = 2*max(abs(s));

% Main Loop
while (sigma>sigma_min) && (j < MaxIter) % && (norm(x-A*s) > err)
    j = j + 1;
    for i=1:L
        delta = OurDelta(s,sigma,GroupInd);
        s = s - mu_0*delta';
        s = s - A_pinv*(A*s-x);   % Projection
    end
    
    if ShowProgress
        fprintf('     sigma=%f, SNR=%f\n',sigma,estimate_SNR(s,true_s))
    end
    
    sigma = sigma * sigma_decrease_factor;
end
    

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function delta=OurDelta(s,sigma,GroupInd)
for i = 1:length(GroupInd)
    delta(GroupInd{i}) = s(GroupInd{i}).*exp(-norm(s(GroupInd{i}))^2/(2*sigma^2));
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function SNR=estimate_SNR(estim_s,true_s)

err = true_s - estim_s;
SNR = 10*log10(sum(true_s.^2)/sum(err.^2));