incorrect gft results with a ring graph

[1taroh]

I found a bug that makes an incorrect gft result with a ring graph.

Example

Gfted one-hot vector's amplitude is constant.
And its phase should be a line.
However, this example shows gft makes an incorrect result.

N = 64;
G = gsp_ring(N);
G = gsp_compute_fourier_basis(G);

f = zeros(N);
f(10) = 1;

plot(1:N,angle(gsp_gft(G,f)))
xlim([1 N])
ylim([-pi pi])
ylabel("phase [rad]")
yticks([-pi,0,pi])

The cause

This is because the sort of eigenvalues and eigenvectors in

gspbox/utils/gsp_compute_fourier_basis.m

Lines 77 to 85 in a7d9aac

	if isfield(G,'type') && strcmp(G.type,'ring')==1 % && mod(G.N,2)==0
	U = dftmtx(G.N)/sqrt(G.N);
	E = (2-2*cos(2*pi*(0:G.N-1)'/G.N));
	inds = gsp_classic2graph_eig_order( G.N );
	% [G.E, inds]=sort(E,'ascend');
	G.e = E(inds);
	if strcmp(G.lap_type,'normalized')
	G.e = G.e/2;
	end

However, this sort is important when we talk about graph frequency...

[nperraud]

Hi @1taroh
Thanks for reporting this.
Is the line 87 the problem?
https://github.com/epfl-lts2/gspbox/blob/a7d9aac5e239f1bcb37a9bb09998cc161be2732f/utils/gsp_compute_fourier_basis.m#L87C5-L87C21
Could you try to fix it?

[1taroh]

Thank you for replying.

Yes, this sort makes the error.

I try to fix it.

In pygsp, the eigenvector matrix of a ring graph is a real matrix.
I'll try to do the same in gsptoolbox.
This modification means we do not consider the phase.
People who want to consider it like me should use DFT matrix.