基于线性Bregman迭代的矩阵补全MATLAB代码

% Comparison of different linearized Bregman approaches on recovering a sparse solution x from Ax = b 
% The nonzero entries of x have iid Gaussian random values
% The entries of A are +/- 1 randomly

clear

%% Generate problem data
rand（‘seed‘ 0）; randn（‘seed‘ 0）;

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

A = sign（randn（mn））; % random matrix
x_ref = zeros（n1）; % true vector
x_ref（randsample（nk）） = randn（k1）; % Gaussian random values
b = A*x_ref; % finish generating equations Ax = b

%% set parameters
alpha = 5*norm（x_refinf）; % don‘t need to be exact roughly 1 - 10 times norm（x_refinf） is fine
opts.tol = 1e-6;   % stop once norm（Ax-b）opts.maxit = 2000; % run maximally 1000 iterations
opts.x_ref = x_ref;

%% LBreg: fixed stepsize ---
opts.stepsize = 2/alpha/normest（A*A.‘1e-2）; % roughly 2/alpha/norm（A）^2
t0 = tic;
[xout] = lbreg_fixedstep（Abalphaopts）;
time = toc（t0）;
fprintf（‘iter = %d time = %4.2e ‘ out.iter time）;
fprintf（‘solution relative error = %4.2e\n‘ norm（x - x_ref）/norm（x_ref））;
opts = rmfield（opts ‘stepsize‘）;

%% LBreg: Barzilai-Borwein and non-montone line search ---
opts.stepsize = 2/alpha/normest（A*A.‘1e-2）; % roughly 2/alpha/norm（A）^2
t0 = tic;
[x1out1] = lbreg_bbls（Abalphaopts）;
time = toc（t0）;
fprintf（‘iter = %d time = %4.2e ‘ out1.iter time）;
fprintf（‘solution relative error = %4.2e\n‘ norm（x1 - x_ref）/norm（x_ref））;
opts = rmfield（opts ‘stepsize‘）;

%% LBreg: accelerated no restart ---
t0 = tic;
[x2out2] = lbreg_accelerated（Abalphaopts）;
time = toc（t0）;
fprintf（‘iter = %d time = %4.2e ‘ out2.iter time）;
fprintf（‘solution relative error = %4.2e\n‘ norm（x2 - x_ref）/norm（x_ref））;

%% LBreg: skip: monotonic gradient scheme ---
opts.reset = 6;
t0 = tic;
[x3out3] = lbreg_accel_w_reset（Abalphaopts）; % no restart
time = toc（t0）;
fprintf（‘iter = %d time = %4.2e ‘ out3.iter time）;
fprintf（‘solution relative error = %4.2e\n‘ norm（x3 - x_ref）/norm（x_ref））;
opts = rmfield（opts ‘reset‘）;

%% Reporting
figure;
plot（1:out.iter  out.hist_obj  ‘k-‘ ...
     1:out1.iter out1.hist_obj ‘b--‘ ...
     1:out2.iter out2.hist_obj ‘g--‘ ...
     1:out3.iter out3.hist_obj ‘r--‘ ...
     ‘LineWidth‘ 2）;
legend（‘fixed stepsize‘ ‘BB+line search‘ ‘Nesterov accel‘ ‘Nesterov+skip‘‘Location‘‘SouthEast‘）;
title（‘Dual objective‘）
xlabel（‘iteration‘）; ylabel（‘dual objective‘）;

figure;
semilogy（1:out.iter  out.hist_err/norm（x_ref）  ‘k-‘ ...
         1:out1.iter out1.hist_err/norm（x_ref） ‘b--‘ ...
         1:out2.iter out2.hist_err/norm（x_ref） ‘g--‘ ...
         1:out3.iter out3.hist_err/norm（x_ref） ‘r--‘ ...
         ‘LineWidth‘ 2）;
legend（‘fixed stepsize‘ ‘BB+line search‘ ‘Nesterov accel‘ ‘Nesterov+skip‘‘Location‘‘NorthEast‘）;
title（‘Primal solution relative error‘）
xlabel（‘iteration‘）; ylabel（‘||x - x_{ref}||_2/||x_{ref}||_2‘）;

%%