GSP_LEARN_GRAPH_LOG_DEGREES - Learn graph from pairwise distances using negative log prior on nodes degrees

Usage

[W, stat] = gsp_learn_graph_log_degrees(Z, a, b)
[W, stat] = gsp_learn_graph_log_degrees(Z, a, b, params)

Description

Inputs:

Z : Matrix with (squared) pairwise distances of nodes a : Log prior constant (bigger a -> bigger weights in W) b : ||W||_F^2 prior constant (bigger b -> more dense W) params : Optional parameters

Outputs:

W : Weighted adjacency matrix stat : Optional output statistics (adds small overhead)

'W = gsp_learn_graph_log_degrees(Z, a, b, params)' computes a weighted adjacency matrix \(W\) from squared pairwise distances in \(Z\), using the smoothness assumption that \(\text{trace}(X^TLX)\) is small, where \(X\) is the data (columns) changing smoothly from node to node on the graph and \(L = D-W\) is the combinatorial graph Laplacian. See the paper of the references for the theory behind the algorithm.

Alternatively, Z can contain other types of distances and use the smoothness assumption that

is small.

The minimization problem solved is

subject to \(W\) being a valid weighted adjacency matrix (non-negative, symmetric, with zero diagonal).

The algorithm used is forward-backward-forward (FBF) based primal dual optimization (see references).

Example:

G = gsp_sensor(256);
f1 = @(x,y) sin((2-x-y).^2);
f2 = @(x,y) cos((x+y).^2);
f3 = @(x,y) (x-.5).^2 + (y-.5).^3 + x - y;
f4 = @(x,y) sin(3*((x-.5).^2+(y-.5).^2));
X = [f1(G.coords(:,1), G.coords(:,2)), f2(G.coords(:,1), G.coords(:,2)), f3(G.coords(:,1), G.coords(:,2)), f4(G.coords(:,1), G.coords(:,2))];
figure; subplot(2,2,1); gsp_plot_signal(G, X(:,1)); title('1st smooth signal');
subplot(2,2,2); gsp_plot_signal(G, X(:,2)); title('2nd smooth signal');
subplot(2,2,3); gsp_plot_signal(G, X(:,3)); title('3rd smooth signal');
subplot(2,2,4); gsp_plot_signal(G, X(:,4)); title('4th smooth signal');
Z = gsp_distanz(X').^2;
% we can multiply the pairwise distances with a number to control sparsity
[W] = gsp_learn_graph_log_degrees(Z*25, 1, 1);
% clean up zeros
W(W<1e-5) = 0;
G2 = gsp_update_weights(G, W);
figure; gsp_plot_graph(G2); title('Graph with edges learned from above 4 signals');

This code produces the following output:

# iters:  663. Rel primal: 9.9921e-06 Rel dual: 6.3593e-06  OBJ 9.532e+01
Time needed is 0.555383 seconds

Additional parameters

• params.W_init : Initialization point. default: zeros(size(Z))
• verbosity : Default = 1. Above 1 adds a small overhead
• maxit : Maximum number of iterations. Default: 1000
• tol : Tolerance for stopping criterion. Defaul: 1e-5
• step_size : Step size from the interval (0,1). Default: 0.5
• max_w : Maximum weight allowed for each edge (or inf)
• w_0 : Vector for adding prior c/2*||w - w_0||^2
• c : multiplier for prior c/2*||w - w_0||^2 if w_0 given
• fix_zeros : Fix a set of edges to zero (true/false)
• edge_mask : Mask indicating the non zero edges if "fix_zeros"

If fix_zeros is set, an edge_mask is needed. Only the edges corresponding to the non-zero values in edge_mask will be learnt. This has two applications: (1) for large scale applications it is cheaper to learn a subset of edges. (2) for some applications we don't want some connections to be allowed, for example for locality on images.

The cost of each iteration is linear to the number of edges to be learned, or the square of the number of nodes (numel(Z)) if fix_zeros is not set.

The function is using the UNLocBoX functions sum_squareform and squareform_sp. The stopping criterion is whether both relative primal and dual distance between two iterations are below a given tolerance.

To set the step size use the following rule of thumb: Set it so that relative change of primal and dual converge with similar rates (use verbosity > 1).