Node

We represent the nodes of our graphs as unsigned integers.

ConnectionGraph

Contains the data describing a graph endowed with a unitary connection.

g the underlying graph C the connection matrix n the number of nodes in the graph degree the vector of weighted degrees L the connection Laplacian

neighbors is used in the MTSF sampling algorithm and contains the NeighborInfo for all nodes

Note that L = diagm(degree) - conj.(C).

WeightedConnectionGraph

Contains the data describing a weighted graph endowed with a unitary connection.

g the underlying graph C the connection matrix n the number of nodes in the graph degree the vector of weighted degrees c_degree the vector of combinatorial degrees L the connection Laplacian

neighbors is used in the MTSF sampling algorithm and contains the NeighborInfo for all nodes

Note that L = diagm(degree) - conj.(C).

NeighborInfo

Contains information relative to the neighborhood of a node.

list the list of neighboring Nodes weight the weights of edges to said neighbors offset the angular offsets of the edges to said neighbors

AliasBuffer

A buffer structure used for the alias method.

table the alias table prb the acceptance probability tables

SmoothingMTSF

Contains the data, describing a MTSF, necessary to perform the smoothing operation.

root_of a vector describing the root of each node (0 if the node is in a unicycle) q_root_size a vector describing the sum of the q's associated to nodes in the tree rooted at each node holonomy_to_root a vector describing the holonomy along the path from each node to its root in the MTSF importance_weight the weight associated to the sampled forest

Counter

A counter used in the MTSF sampling algorithm.

Buffer data used in the MTSF sampling algorithm.

next a vector describing the next node in the path sampled during the process local_holonomy a vector keeping track of the holonomy accumulated along the path to each node during the sampling process state a vector describing whether a node belongs to a unicycle or a (rooted) tree cnt an array of Counters associated to each node cnt_max an array recording the maximum value a Counter (as identified by his id)

ConnectionGraph(graph::SimpleGraph{UInt64},connection_matrix::SparseMatrixCSC{ComplexF64, Int64},weight_matrix::SparseMatrixCSC{Float64, Int64})

Constructs a ConnectionGraph or WeightedConnectionGraph based on the underlying graph, with specified sparse connection_matrix and weight_matrix.

NeighborInfo(v::Node,deg::Vector{UInt64})

Allocates the NeighborInfo for Node v, but does not fill in this information.

AliasBuffer(CG::ConnectionGraph)

Instantiates an AliasBuffer using the WeightedConnectionGraph CG.

SmoothingMTSF(n::UInt64)

Constructs a SmoothingMTSF associated to a graph of size n.

SamplingBuffer(n::UInt64)

Constructs a SamplingBuffer associated to a graph of size n.

init_MTSF!(phi::SmoothingMTSF,n::UInt64)

(Re)-Initializes the SmoothingMTSF phi.

init_buffer!(buf::SamplingBuffer,n::UInt64)

(Re)-Initializes the SamplingBuffer buf.

sample_MTSF!(CG::ConnectionGraph,q_vector::Vector{Float64},phi::SmoothingMTSF,buf::SamplingBuffer)

Samples a MTSF from the ConnectionGraph CG using the node weights in q_vector. The resulting MTSF is stored in the SmoothingMTSF phi, and the SamplingBuffer buf stores additional data used by the algorithm.

In case a non-weakly-incoherent cycle is encountered, samples from the importance-sampling distribution.

sample_MTSF!(CG::WeightedConnectionGraph,q_vector::Vector{Float64},phi::SmoothingMTSF,buf::SamplingBuffer,abuf::AliasBuffer)

Samples a MTSF from the WeightedConnectionGraph CG using the node weights in q_vector. The resulting MTSF is stored in the SmoothingMTSF phi, and the SamplingBuffer buf stores additional data used by the algorithm.

In case a non-weakly-incoherent cycle is encountered, samples from the importance-sampling distribution.

sample_MTSF!(CG::WeightedConnectionGraph,q_vector::Vector{Float64},phi::SmoothingMTSF,buf::SamplingBuffer,abuf::AliasBuffer)

Samples a MTSF from the WeightedConnectionGraph CG using the node weights in q_vector. The resulting MTSF is stored in the SmoothingMTSF phi, and the SamplingBuffer buf and the AliasBuffer abuf store additional data used by the algorithm. Uses the alias method for neighbor computation.

In case a non-weakly-incoherent cycle is encountered, samples from the importance-sampling distribution.

smooth_with_MTSF(CG::ConnectionGraph,q_vector::Vector{Float64},g::Vector{ComplexF64},nb_MTSF::Int64)

Smoothes the signal gon the nodes of the (eventually weighted) ConnectionGraph CG, with respect to the parameters in the q_vector, using nb_MTSF MTSFs. Use of the alias method for sampling in weighted graphs can be turned off by setting use_alias = false.

rb_smooth_with_MTSF(CG::ConnectionGraph,q_vector::Vector{Float64},g::Vector{ComplexF64},nb_MTSF::Int64)

Smoothes the signal g on the nodes of the (eventually weighted) ConnectionGraph CG, with respect to the parameters in q_vector, using nb_MTSF MTSFs. Use of the alias method for sampling in weighted graphs can be turned off by setting use_alias = false.

This is a Rao-Blackwellized version of the smoothing performed by smooth_with_MTSF.

rb_cv_smooth_with_MTSF(CG::ConnectionGraph,q_vector::Vector{Float64},g::Vector{ComplexF64},nb_MTSF::Int64)

Smoothes the signal g on the nodes of the (eventually weighted) ConnectionGraph CG, with respect to the parameters in q_vector, using nb_MTSF MTSFs. Use of the alias method for sampling in weighted graphs can be turned off by setting use_alias = false.

This is a "control-variates" enhanced version of the smoothing performed by rb_smooth_with_MTSF.

_propagate_in_MTSF!(CG::ConnectionGraph,phi::SmoothingMTSF,g::Vector{ComplexF64},f::Vector{ComplexF64})

Propagates the values of the signal g at the roots of the MTSF described by the SmoothingMTSF phi to all the node in the ConnectionGraph CG, the result is stored in f

propagate_average_in_MTSF!(CG::ConnectionGraph,phi::SmoothingMTSF,g::Vector{ComplexF64},f::Vector{ComplexF64})

Propagates and sums the values of the signal g from the nodes in the ConnectionGraph CG to their roots along the MTSF described by the SmoothingMTSF phi, before propagating them back. The result is stored in f.

aligned_l2_loss(f::Vector{ComplexF64},g::Vector{ComplexF64})

Outputs the minimal norm of (f - r g) over all rotations r, for normalized vectors.

aligned_l2_loss(f::Vector{ComplexF64},g::Vector{ComplexF64})

Outputs the minimal norm of (f - r g) over all rotations r, for entry-wise normalized vectors.

epsilon_graph(n::UInt64,eps::Float64,d::Int64)

Outputs an ε-graph with n nodes sampled in [0,1]^d, and an edge if two nodes are less than eps apart.

random_spanning_tree(CG::ConnectionGraph; root::Node=Node(1))

Outputs a uniform spanning tree in CG, with prescribed root.

min_spanning_tree(CG::ConnectionGraph)

Outputs a minimum spanning tree in CG, with abs(cos(theta_{i,j})) as edge-weights.

ust_synchronization(CG::ConnectionGraph,root::Node=Node(1))

Samples a UST and performs a naive synchronization.

mst_synchronization(CG::ConnectionGraph,root::Node=Node(1))

Samples a MST and performs a naive synchronization.

multiplicative_perturbation!(obs::SparseMatrixCSC{ComplexF64,Int64},f::Vector{ComplexF64},a::Float64)

Fills the nonzero entries of obs with angular offsets measured from f perturbed by uniformly distributed noise in [-a,a]. a defaults to 1.