l2p_re.m

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

function x = l2p_re(A,y,p,group)

% Solution to the non-convex optimization problem min||x||_2,p subject to 
% y = Ax
% This algorithm is based upon the Reweighted L2 algorithm from the
% following paper
%
% "Iteratively Reweighted Algorithms for Compressive Sensing"
% by Rick Chartrand and Wotao Yin
% Algorithm implemented as featured in:
% http://math.lanl.gov/Research/Publications/Docs/chartrand-2008-iteratively.pdf
% 
% Copyright (c) Angshul Majumdar 2009

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

% Output
% x = estimated sparse signal

if nargin < 5
     err = 1e-5;
end

MaxIter = 2500;
epsilon = 1;
NGroup = max(group);
for i = 1:NGroup
    GInd{i} = find(group == i);
end
% u_0 is the L_2 solution which would be exact if m = n,
% but in Compressed expactations are that m is less than n
u_0 = A\y;
u_old = u_0;
j=0;
while (epsilon > err) && (j < MaxIter) % && (norm(y-A*u_old) > err)
	j = j + 1;
    for i = 1:NGroup
        w(GInd{i}) = (norm(u_old(GInd{i}))^(2) + epsilon).^(p/2-1);
    end
	% w = (u_old.^(2) + epsilon).^(p/2-1);
	v = 1./w;
	Q_n = diag(v,0);
	tu = inv(A*Q_n*A');
	u_new = Q_n * A' * tu * y;
	if lt(norm(u_new - u_old,2),epsilon^(1/2)/100)
		epsilon = epsilon /10;
	end
	u_old = u_new;
end
x=u_new;