0
$\begingroup$

I am trying to use matlab and YALMIP to solve a graph learning problem of recovering eigenvalues from the eigenvectors of the covariance of sampled graph signal data. This is to implement the algorithm in https://graphex.mit.edu/sites/default/files/documents/2017_Poster_Segarra.pdf. A better explanation is their paper https://ieeexplore.ieee.org/document/7990048. My objective is to estimate the Adjacency matrix. I have tried different versions of the constraints and other troubleshooting, but lambda is always NaN or very small, and estimated_A is also very small, so interpreted as 0. This is my first time working through this kind of optimization problem and I appreciate any assistance. Thank you.

My code is

% Generate a random network with 100 nodes
N = 100;
G = gsp_sensor(N);
A = G.A;
D = diag(sum(A, 2));
L = D - A;   % Laplacian matrix

% Generate observed graph signals
X = sin(rand(N, N));

% Diffuse graph signals using the heat equation
alpha = .5;
X_diff = zeros(N, N);
for t = 1:N
    X_diff(:, t) = (eye(N) - alpha * L) * X(:, t);
end

% Compute sample covariance matrix
C = (X_diff * X_diff') / N;

% Extract spectral templates by computing the eigenvectors and eigenvalues of the sample covariance matrix
[V, D] = eig(C);

% Formulate optimization problem with YALMIP
A_est = sdpvar(N, N, 'full');  % Unknown graph shift operator (Laplacian matrix)
lambda = sdpvar(N, 1);       % Unknown eigenvalues

options = sdpsettings('verbose', 2, 'solver', 'sedumi');
% Define the objective function (minimize L1 norm of A)
objective = norm(A_est(:), 1);

% Set up the constraints
constraints = [A_est == V * diag(lambda) * V', A_est == A_est', diag(A_est) == zeros(N, 1), A_est >= 0, sum(A_est, 2) ==1];

% Define objective function
objective = norm(A_est(:), 1);

% Solve SDP problem using YALMIP
sol = solvesdp(constraints, objective, options);

disp(value(A_est));
disp(value(lambda));

I am currently not able to even reproduce the assumption that the eigenvectors of the graph shift operator (adjacency matrix) are equal to the eigenvectors of the signal covariance matrix.

% Define the size of the matrix
N = 5;

% Create a symmetric simple graph GSO (Adjacency matrix)
A = zeros(N);  % Initialize
for i = 1:N-1
    for j = i+1:N
        A(i, j) = 1;
    end
end
A = A + A';  % Make symmetric

% Compute eigenvectors of the GSO
[VA, ~] = eig(A);

% Generate white signals: N signals of length N
X = randn(N, N);  % White signals have a covariance matrix that is the identity matrix

% Apply the eigenvectors as a filter to the white signals
X_filtered = VA * X;

% Compute the covariance matrix of the filtered signals
C = cov(X_filtered');

% Compute eigenvectors of the signal covariance matrix
[VC, ~] = eig(C);

% Compare eigenvectors (This will be qualitative. For quantitative, consider using norms or inner products)
disp('Eigenvectors of A:');
disp(VA);
disp('Eigenvectors of C:');
disp(VC);
$\endgroup$
5
  • $\begingroup$ What have you already done to debug your script? $\endgroup$ Commented Dec 4, 2023 at 18:41
  • $\begingroup$ Hi Wolfgang, so far I have deleted and tried to modify the constraints, I have also tried to use the eigenvectors of the original A and L matrixes. The best I have gotted is an all-ones lambda vector and a trivial matrix with ones in the diagonal. $\endgroup$
    – user86422
    Commented Dec 4, 2023 at 21:14
  • $\begingroup$ Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. $\endgroup$
    – Community Bot
    Commented Dec 5, 2023 at 12:44
  • $\begingroup$ Have you solved this problem? I am currently looking for a reproduction code for this paper. $\endgroup$
    – hh hh
    Commented Dec 28, 2023 at 9:32
  • $\begingroup$ I haven't been able to create a sucessful algorithm to reporduce their results, and I am also having issues with creating data that matches their assumption: that the eigenvectors of the GSO are the same as the eigenvectors of the signal covariance matrix. $\endgroup$
    – user86422
    Commented Jan 28 at 15:25

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.