# Code to extract sparse transport support from Markov Graph

Hi,

If the target map satisfies a marjov random field structure, then the inverse transport map will be sparse. I know how to extract the nonzero components from the MRF. But I was wondering if you had code to do this automatically? I see in this example: https://transportmaps.mit.edu/docs/example-inverse-stochastic-volatility-6d.html?highlight=conditional%20independence You do it by hand.

I just wanted to check if you already wrote this code before doing it myself.

Thanks,

Patrick
asked Feb 9, 2023 in usage

+1 vote

Hi Patrick,

Thank you very much for your question! Given a marginal random field (MRF), the sparsity of the inverse transport map (i.e., the active variables set in the code you referenced) can be extracted from a variable elimination algorithm applied to the graph. We have implemented this code as part of our SING algorithm for learning the structure of graphical models from data, which alternates using a sparse map to learn the adjacency of the graph with extracting the map sparsity from the adjacency matrix.

The code block to extract the active variables as a list given a matrix A encoding the edges of the MRF is:

# Variable elimination moving from highest node (dim-1) to node 2 (at most)
dim = A.shape[0]
ALower = np.tril(A)
for i in range(dim-1,1,-1):
non_zero_ind  = np.where(ALower[i,:i] != 0)[0]
if len(non_zero_ind) > 1:
co_parents = list(itertools.combinations(non_zero_ind,2))
for j in range(len(co_parents)):
row_index = max(co_parents[j])
col_index = min(co_parents[j])
ALower[row_index, col_index] = 1.0

# Find list of active_vars
active_vars = []
for i in range(dim):
actives = np.where(ALower[i,:] != 0)
active_list = list(set(actives[0]) | set([i]))
active_list.sort(key=int)
active_vars.append(active_list)

Please let us know if you have any other questions!

Best,

Ricardo

answered Feb 11, 2023 by (12 points)