Contents

% An example of recovery a sparse solution x from Ax = b using linearized Bregman iteration with Nesterov's acceleration
% The nonzero entries of x have iid Gaussian random values

Generate problem data

rand('seed', 0); randn('seed', 0);

m = 250; n = 500; % matrix dimension m-by-n
k = 25; % sparsity

A = randn(m,n); % random matrix
x_ref = zeros(n,1); % true vector
x_ref(randsample(n,k)) = randn(k,1); % Gaussian random values
b = A*x_ref; % finish generating equations Ax = b

Solve problem

alpha = 5*norm(x_ref,inf); % don't need to be exact, roughly 1 - 10 times norm(x_ref,inf) is fine
opts.tol = 1e-4; % stop once norm(Ax-b)<tol*norm(b)
opts.x_ref = x_ref;

t0 = tic;
[x,out] = lbreg_accelerated(A,b,alpha,opts);
time = toc(t0);

Reporting

fprintf('time = %4.2e, ', time);
fprintf('solution relative error = %4.2e\n\n', norm(x - x_ref)/norm(x_ref));

figure;
plot(1:out.iter, out.hist_obj, 'k-', 'LineWidth', 2);
title('Dual objective')
xlabel('iteration'); ylabel('dual objective');

figure;
semilogy(1:out.iter, out.hist_err/norm(x_ref), 'k-', 'LineWidth', 2);
title('Primal solution relative error')
xlabel('iteration'); ylabel('||x - x_{ref}||_2/||x_{ref}||_2');

time = 2.52e-02, solution relative error = 1.28e-04

Download this m-file

Published with MATLAB® R2012b