%%%%%%%%%%%%%%%%%% Demo for fig. 2 
%%% "On the Asymptotic Equivalence of Circulant and Toeplitz Matrices,"
%%%  IEEE Transactions on Information Theory 2017.
%%%  by Z. Zhu and M. B. Wakin

close all; clear all;
XN = 101:300:2001; err_1 = []; err_2 = []; err_3 = [];
for N = XN
    t_vec = [1:N-1];
    top_vec = [.5 (1 + (-1).^t_vec)./(1j*2*pi*t_vec)];
    cov_matrx = toeplitz(top_vec);% Window fucntion
    lambda = svd(cov_matrx);
    %% Circulant approximation 1
    c_vec_1 = top_vec + [0 conj(top_vec(N:-1:2))];
    %% Circulant approximation 2
    c_vec_2 = zeros(1,N); c_vec_2(1:floor((N-1)/2)+1) = top_vec(1:floor((N-1)/2)+1);
    c_vec_2(ceil((N-1)/2)+2:N) = conj(top_vec(floor((N-1)/2)+1:-1:2));
    %% Circulant approximation 3
    c_vec_3 = ([N:-1:1].*top_vec+[0:N-1].*[0 conj(top_vec(N:-1:2))])/N;
    %% computing the maximum error
    err_1 = [err_1 max(abs(lambda' -sort(real(fft(c_vec_1)),'descend')))];
    err_2 = [err_2 max(abs(lambda' -sort(real(fft(c_vec_2)),'descend')))];
    err_3 = [err_3 max(abs(lambda' -sort(real(fft(c_vec_3)),'descend')))];
end
figure
plot(XN,err_1,'k*-','linewidth',2);hold on;
plot(XN,err_2,'b:','linewidth',2);hold on;
plot(XN,err_3,'go:','linewidth',2);hold on;
legend('Circulant1','Circulant2','Circulant3','location','best');


