text:
\section{Preliminaries}
\label{sec:prel-probl-stat}

In this section, we outline notation and the mathematical preliminaries on graph and systems theory, and then lay out the setting of the problem statement.

\subsection{Preliminaries on Graphs \& Consensus}

We denote the real numbers as $\mathbb{R}$, the non-negative reals as $\mathbb{R}_+$, the positive reals as $\mathbb{R}_{++}$, and the real $n$-dimensional Euclidean vector space as $\mathbb{R}^n$.
Vectors in $\mathbb{R}^n$ are written in lower-case $x,y,z$, etc., and matrices in $\mathbb{R}^{n\times m}$ are written in capital-case $M,N,R$, etc.
$I$ denotes the identity matrix.
$\mathbf{1}\in\mathbb{R}^n$ denotes the length-$n$ vector of ones, and $\mathbf{0}$ denotes a matrix of zeros of comfortable dimensions.

A \emph{graph} $\graph$ with $n$ \emph{vertices} (or nodes) is a triple of sets $(\Verts,\Edges,\Weights)$, where $\Verts = [n]$ is a set of labeled vertices, $\Edges \subseteq \Verts\times\Verts$ is a set of $m$ \emph{edges} denoting connections between vertices, and $\Weights \in \mathbb{R}^{m}_{++}$ is a set of \emph{edge weights}, denoting some notion of  `strength' of the corresponding edge.
A graph $\graph$ is \emph{undirected} if edge $ij = ji$, and \emph{directed} otherwise.

The \emph{neighbourhood} of vertex $i$ is $N_i=\{j:ij\in\Edges\}$, and the \emph{unweighted degree} of $i$ as $\mathrm{deg}(i) = |N(i)|$.

A \emph{path} $\mathcal{P}$ is a set of edges $\{i_1i_2,~i_2i_3,\dots,i_{l-2}i_{l-1},~i_{l-1}i_l\}$ where $i_1,\dots,i_l$ are distinct,  and a \emph{cycle} $\cycle$ is a path, except that the first vertex and the last vertex are the same, i.e. $i_1 = i_l$.
An \emph{connected graph} $\graph$ is one in which there is an undirected path between any two vertices in $\graph$.
A \emph{tree} $\tree$ is a connected graph with no cycles, and a \emph{spanning tree} of a connected graph $\graph$ is a tree on the same vertex set as $\graph$ (i.e., $\Verts(\tree) = \Verts(\graph)$), with edges $\Edges(\tree) \subseteq \Edges(\graph)$.
If $\tree$ is a spanning tree of $\graph$, then we can write $\tree\subseteq \graph$, where `$\subseteq$' is to be interpreted setwise.
Note that a tree $\tree$ with $n$ vertices must have exactly $n-1$ edges.

To each vertex $i\in\Verts$, we assign a state $x_i \in \mathbb{R}$.
The dynamics of each vertex state $x_i$ are assumed, unless otherwise stated, to be single-integrator dynamics $\dot{x}_i = u_i$.
By setting $u_i$ to be a weighted average of the states of its neighbours, we arrive at the \emph{consensus dynamics}:
\begin{align}
  \dot x_i = \sum_{j\in N_i} w_{ij}(x_j - x_i).\label{eq:1}
\end{align}

One can also define the \emph{incidence matrix} $D_\graph \in \mathbb{R}^{n\times m}$ of an undirected graph $\graph$, where each column $d_{ij}$ of $D_\graph$ corresponds to an edge $ij \in \Edges$.
The column $d_{ij}$ has 1 in the $i$th position, and $-1$ in the $j$th position; the choice of setting $i=1$ or $j=1$ is arbitrary.
By setting the matrix $W_\graph \in \mathbb{R}^{m\times m}$ to be the diagonal matrix containing the edge weights $w_{ij}$, one can write the (undirected) graph Laplacian as $\lap_\graph = D_\graph W_\graph D_\graph ^\intercal $.

By appropriately stacking $x_i$ into a vector $x\in \mathbb{R}^{n}$, the consensus dynamics in \eqref{eq:1} can be written in vector form as as
\begin{align}
  \dot x = - \lap_\graph x.
\end{align}

A \emph{time-scaled graph} $\graph$ is a quadruple of sets $(\Verts,\Edges,\Weights,\mathcal{S})$, where $\Verts,\Edges$, \& $\Weights$ are as before, and $\mathcal{S} \in \mathbb{R}_{++}^n$ is a set of \emph{time scales} $\{\epsilon_i\}_{i=1}^n$ on the vertices.
We can then define the \emph{time scaled consensus dynamics} as
\begin{align}
  \epsilon_i \dot{x}_i = \sum_{j\in N_i} w_{ij}(x_j - x_i) ~\longleftrightarrow ~E_{\graph}\dot{x}_i = -\lap_{\graph} x,
\end{align}
where $E_\graph = \mathrm{diag}(\{\epsilon_i\}_{i=1}^n)$.

\subsection{Edge Consensus and Problem Configuration}

The problem considered in this paper is derived from the preceding consensus dynamics, but with process and measurement noise.
Consider a graph $\graph$ of $n$ multi-scale integrators, and zero-mean Gaussian process noise $\omega_i(t)$,

\begin{align}
\epsilon_i \dot{x}_i(t) =  u_i(t) + \omega_i(t), \label{eq:consensus}
\end{align}

where $\mathbf{E}\left[\omega(t) \omega(t)^\intercal \right] = \mathrm{diag}(\sigma_{\omega_i}^2) \triangleq\Omega^2 $, $x_i$ is the (scalar) state of the $i$-th agent, $\epsilon_i$ is node $i$'s time scale parameter, and $u_i$ is the control input.
A weighted, noisy, decentralized feedback controller that seeks to bring agents to consensus is given by,
\begin{align}
u_i(t) & = \sum_{j\in N(i)} \left[w_{ij} (x_j(t) - x_i(t)) + v_{ij}(t)\right] \nonumber \\
u(t) & =  D_\graph W_\graph D_\graph^\intercal  x(t) + D_\graph v(t), \label{eq:control}
\end{align}
where the noise over the edge $ij$ is $v_{ij}(t)$, with covariance $\mathbf{E}[v(t) v(t)^\intercal ] = \mathrm{diag}(\sigma_{v_{ij}}^2) \triangleq\Gamma^2$ for all $(i,j) \in \Edges$.
 $W_\graph\triangleq\mathrm{diag}(\mathcal{W})$ is the matrix of edge weights, and  $v(t),u(t)$ are the stacked vectors of measurement noises and control inputs.
Applying~\eqref{eq:control} to the stacked-vector version of~\eqref{eq:consensus} gives a general, time scaled and weighted consensus dynamics with process and measurement noise,
\begin{align} \label{eq:model}
\Sigma_\graph \triangleq
  \begin{cases}
    \dot{x}(t) =  E_{\graph}^{-1} \lap_{\graph} x(t) \\ ~~~~~+ \begin{bmatrix}E_{\graph}^{-1} &  E_{\graph}^{-1} D_\graph\end{bmatrix} \begin{bmatrix} \omega(t) \\ v(t) \end{bmatrix}.
  \end{cases}
\end{align}

 The scaled Laplacian $E_{\graph}^{-1} \lap_{\graph}$ is rank-deficient (it posesses a zero eigenvalue for each connected component of $\graph$), which complicates reasoning about the $\Htwo$ performance of $\Sigma_\graph$.
 Solutions to this problem in the literature include studying the $\Htwo$ norm of the Dirichlet Laplacian, as in \cite{Chapman2015,Hudobadebadyn2019}, or as considered in this paper, a minimal representation of $\Sigma_\graph$ obtained by studying edge consensus, seen in \cite{Zelazo2013,Zelazo2011a,Foight2019a}. In the case of a time scaled graph, the \emph{edge Laplacian} is defined by $\lap^\graph \triangleq D_\graph^\intercal  E_{\graph}^{-1} D_\graph$.
We denote the {edge Laplacian} of a graph $\graph$ with a superscript: $\lap^\graph$, and the {graph Laplacian} with a subscript: $\lap_\graph$.

In~\cite{Zelazo2011a}, it was shown that the graph and edge Laplacians are related by a similarity transformation;~\cite{Foight2019a} extended  the transformation to time-scaled and matrix-weighted graphs.
This similarity transformation is constructed by choosing a spanning tree $\tree\subseteq\graph$, and noting that the cycles can be considered as linear combinations of the spanning tree edges in the following sense.
Let $D_\tree$ denote the incidence matrix of the spanning tree $\tree$, and let  $D_{\graph\setminus\tree}$  denote the incidence matrix of the remaining edges that correspond to the edges completing the cycles in $\graph$.
Define the \emph{Tucker representation} matrix $R_\graph \triangleq [I~~T_\tree]$, where

\begin{align}
    T_\tree = \left[ D_\tree^\intercal D_\tree \right]^{-1} D_\tree ^\intercal D_{\graph\setminus\tree}.
\end{align}
We refer to the matrix $T_\tree$ as the \emph{cycle representation matrix}.
Note that if the graph is a tree, i.e. $\graph = \tree$, then the only choice of spanning tree for $R_\graph$ is in fact $\tree$, and $T_\tree$ is the empty matrix ($R_\graph = I$ in this case).

It suffices to measure the relative states of the nodes $x_i-x_j$ over the edges $ij$ of a spanning tree $\tree\subseteq\graph$ to capture consensus: if $x_i-x_j=0$ for all $ij\in\tree$, then we know that the network is at consensus.
This is the motivation for the edge consensus model, formalized below.
We define the \emph{edge states} for a edge weighted and time scaled graph as $x_e \triangleq S_v^{-1} x$, where the similarity transformation and correponding state matrix are,
\begin{align}
    S_v&= \begin{bmatrix}
             E_{\graph}^{-1} D_\tree \left[D_\tree^\intercal  E_{\graph}^{-1} D_\tree\right]^{-1} &~ \mathbf{1}
         \end{bmatrix}\\
    S_v^{-1} \lap_\graph S_v &= \begin{bmatrix}
                                   \lap^\tree R_\graph W_\graph R_\graph^\intercal &0\\0&0
                               \end{bmatrix},
\end{align}
where $\lap^\tree = D_\tree^\intercal E^{-1}_\graph D_\tree$.

The dynamics of the edge states $x_e$ corresponding to \eqref{eq:model} are then given by
\begin{align}
  \dot x_e =& \begin{bmatrix}
                 -\lap^{\tree} R_\graph W_\graph R_\graph^\intercal  & 0 \\
                 0 & 0
              \end{bmatrix}x_e
             + \begin{bmatrix}
                    D_\tree^\intercal  E_{\graph}^{-1} &  - \lap^\tree R_\graph\\
                    \mathbf{tr}[E_\graph]^{-1}\mathbf{1}^\intercal  & 0
                \end{bmatrix}
             \begin{bmatrix}
                 \omega(t) \\ v(t)
             \end{bmatrix}.       \label{eq:16}
\end{align}
The form of the system matrix in \eqref{eq:16} suggests a partitioning of $x_e$ into the edge states of the chosen spanning tree $\tree$ and, and the consensus subspace, i.e. $x_e = [x_\tree^\intercal  ~~ x_{\mathbf{1}}]^\intercal $.
Finally, we arrive at two models of the spanning tree edge states, differing in their choice of output:
\begin{align}
    \Sigma^\tree[\graph] \triangleq \begin{cases}
      \dot{x}_\tree &= -\lap^{\tree} R_\graph W_\graph R_\graph^\intercal  x_\tree + D_\tree^\intercal E_{\graph}^{-1} \omega\\& - \lap^\tree R_\graph {v}\\
      z &= R_\graph^\intercal  x_\tree
                    \end{cases}\label{eq:2}\\
    \hat{\Sigma}^\tree[\graph] \triangleq \begin{cases}
      \dot{x}_\tree &= -\lap^{\tree} R_\graph W_\graph R_\graph^\intercal  x_\tree + D_\tree^\intercal E_{\graph}^{-1}\omega\\& - \lap^\tree R_\graph {v}\\
      z &=  x_\tree.
                    \end{cases}\label{eq:7}
\end{align}
There are multiple motivations for each of the above models, and the edge consensus formulation in general.
As we can see in~\eqref{eq:16}, the edge state dynamics naturally exclude the zero eigenvalue of $\lap_\graph$.
Also, as proposed in~\cite{Zelazo2011a}, it suffices to measure the $n-1$ relative states across the edges of a spanning tree $\tree$ to determine if the states of the $n$ nodes are at consensus.
Therefore, a satisfactory output measurement of the network is precisely the edge states of that spanning tree as in \eqref{eq:7}.
Of course, the remaining edges that are not in $\tree$ also influence the dynamics, and to study the $\mathcal{H}_2$ norm of the entire system one can take the output of these edge states into account as well.
The model in \eqref{eq:2} has output $z = R_\graph^T x_\tree$, which reconstructs the states of the remaining edges in $\graph\setminus\tree$ using the Tucker representation matrix, and thus considers all edges in the output.

In the next section, we discuss the $\Htwo$ norm as a system-theoretic metric of performance of these models.
For brevity, we may drop the argument of $\Sigma^\tree[\graph]$.

\subsection{Systems Theory and $\Htwo$ Performance}
\label{sec:systems-theory-htwo}
The input-output excitation properties of a linear system $\dot x = Ax + Bu,~y=Cx$ with transfer function $G(s) = C(sI-A)^{-1}B$ can be described using the $\Htwo$ norm,
\begin{align}
  \mathcal{H}_2^2(G) = \dfrac{1}{2\pi} \int_{-\infty}^\infty \mathbf{tr} \left[ G(j\omega)^{*}  G(j\omega) \right] d\omega.
\end{align}
The $\Htwo$ norm measures the steady-state covariance of the output of the system under zero-mean, unit-covariance white noise inputs, or equivalently the root-mean-square of the impulse response of the system.

As discussed in~ \cite{Foight2019a}, the $\Htwo$ norms of the models $\Sigma^\tree[\graph],\hat{\Sigma}^\tree[\graph]$ in \eqref{eq:2} and \eqref{eq:7} are obtained by solving the Lyapunov equation
\begin{align}
  &-\lap^\tree R_\graph W_\graph R_\graph^\intercal  X - X R_\graph W_\graph R_\graph^\intercal  \lap^\tree \\&+ D_\tree^\intercal  E_\graph^{-1}\Omega\Omega^\intercal  E_\graph^{-1} D_\tree + \lap^\tree R_\graph \Gamma \Gamma^\intercal  R_\graph^\intercal  \lap^\tree = 0.\label{eq:8}
\end{align}
An analytic solution to Equation~\eqref{eq:8} can be obtained with a convenient choice of the error covariances $\Omega$ and $\Gamma$, specifically $ \Omega = \sigma_\omega E_\graph^{1/2}$ and $\Gamma = \omega_v W_\graph^{1/2}$.
In this case, the solution of \eqref{eq:8} is given by
\begin{align}
  X^* = \dfrac{1}{2} \left [ \sigma_\omega^2 (R_\graph W_\graph R_\graph^\intercal  )^{-1} + \sigma_v^2 \lap^\tree \right],
\end{align}
and so  the $\Htwo$ norms of  $\Sigma^\tree[\graph],\hat{\Sigma}^\tree[\graph]$ are, respectively,
\begin{align}
 & \mathcal{H}_2^2(\Sigma^\tree[\graph]) = \mathbf{tr}\left[ R_\graph^\intercal  X^* R_\graph\right] \\
                        &= \dfrac{\sigma_\omega^2}{2} \mathbf{tr} \left[ R_\graph^\intercal  (R_\graph W_\graph R_\graph^\intercal  )^{-1} R_\graph \right] + \dfrac{\sigma_v^2}{2} \mathbf{tr} \left[ R_\graph^\intercal  \lap^\tree R_\graph \right] \label{eq:9}\\
 & \mathcal{H}_2^2(\hat{\Sigma}^\tree(\graph)) = \mathbf{tr} \left[ X^* \right]\\
& = \dfrac{\sigma_\omega^2}{2} \mathbf{tr} \left[  (R_\graph W_\graph R_\graph^\intercal  )^{-1}  \right] + \dfrac{\sigma_v^2}{2} \mathbf{tr} \left[  \lap^\tree\right].\label{eq:10}
\end{align}
Of course, the choice of the error covariances causes a loss of generality in the applicability of the analysis of this model.
In \cite{Foight2019a,Foight2019ts}, it was shown that this choice, plus the true error covariances can be combined with an ordering in the semi-definite cone of covariances to reasonably bound the true performance, suggesting that this model is a convenient proxy for general noise models.

It was noted in \cite{Foight2019a} that the contributions of the weights and time scales can be separated in \eqref{eq:9} \& \eqref{eq:10} as,
\begin{align}
  \Htwosq(\Sigma^\tree[\graph]) &= \Htwosq(\Sigma^\tree; W ) + \Htwosq(\Sigma^\tree; E )\\
  \Htwosq(\hat{\Sigma}^\tree[\graph]) &= \Htwosq(\hat{\Sigma}^\tree; W ) + \Htwosq(\hat{\Sigma}^\tree; E )
\end{align}
where
\begin{align}
  &\Htwosq(\Sigma^\tree; W) \triangleq  \dfrac{\sigma_\omega^2}{2} \mathbf{tr} \left[ R_\graph^\intercal  (R_\graph W_\graph R_\graph^\intercal  )^{-1} R_\graph \right]\\
  &\Htwosq(\hat{\Sigma}^\tree; W ) \triangleq \dfrac{\sigma_w^2}{2} \mathbf{tr} \left[  (R_\graph W_\graph R_\graph^\intercal  )^{-1}  \right] \\
  &\Htwosq(\Sigma^\tree; E ) \triangleq \dfrac{\sigma_v^2}{2} \mathbf{tr} \left[ R_\graph^\intercal  \lap^\tree R_\graph \right]\\
  &\Htwosq(\hat{\Sigma}^\tree; E ) \triangleq \dfrac{\sigma_v^2}{2} \mathbf{tr} \left[  \lap^\tree\right].
\end{align}
Furthermore, it was shown in \cite{Foight2019a} that the $\Htwo$ norm of $\Sigma$ can be written in terms of the $\Htwo$ norm of $\hat{\Sigma}$ as follows:
\begin{align}
  &\Htwosq(\Sigma^\tree; W) \\&= \Htwosq(\hat{\Sigma}^\tree; W) +  \dfrac{\sigma_w^2}{2} \mathrm{tr}\left[ T_\tree^\intercal (R_\graph W_\graph R_\graph)^{-1} T_\tree \right]\label{eq:17}\\
  &\Htwosq(\Sigma^\tree; E ) = \Htwosq(\hat{\Sigma}^\tree; E ) + \dfrac{\sigma_v^2}{2} \mathbf{tr}\left[T_\tree^\intercal L^\tree T_\tree \right].
\end{align}
We examine the behaviour of each of these components when an edge is added to a spanning tree -- $\Htwosq(\hat{\Sigma},W)$ and $\Htwosq(\hat{\Sigma},E)$ are discussed in \S\ref{sec:weight-cycle-select}, and $\Htwosq({\Sigma},E)$ \& $\Htwosq({\Sigma},W)$ in \S\ref{sec:contr-time-scal} and \S\ref{sec:contr-edges-mathc} respectively.


TITLE: minimal size of $2-$transitive groups
QUESTION [7 upvotes]: Let $X $ be a set, $|X|=n$ and $G$ be a group with a $2-$transitive action on $X$.
what can be said about the size of $G$?

REPLY [5 votes]: As a complement to Robin Chapman's answer:
Since $G$ is $2-$transitive, its order is divisible by $n\times(n-1)$, not just bounded below by, and so it would be interesting to bound $\dfrac{|G|}{(n\times(n-1))}.$
If $n$ is not a prime power, then it is quite possible for the lower bound to be huge.  The smallest reasonable non-prime, $n=6,$ has its smallest $2-$transitive group with order $60 = 6\times5\times2$.  The next, $n=10,$ has its smallest $2-$transitive group with order $10\times9\times4$.  For most n, the smallest multiple is $\dfrac{(n-2)!}2,$ that is, the alternating group on $n$ points is the smallest $2-$transitive group.  This happens already at $n=22, 33, 34, 35,$ and asymptotically takes over.  Cameron–Neumann–Teague showed this in their $1982$ paper $\text{MR661693}$, and I believe it is covered in Dixon–Mortimer's textbook.
So on the one hand the lower bound for a $2-$transitive group on n points is $n\times(n-1)$ for prime powers $n$, but for most $n$ the lower bound is $\dfrac{n!}2.$


TITLE: Parallel transport curve with corners
QUESTION [5 upvotes]: I am trying to understand the parallel transport along the triangle looking path on the sphere, as in http://en.m.wikipedia.org/wiki/File:Parallel_transport.png. The thing that confuses me is that the curve looks only piecewise continuous, so the only reason the vector points in a new direction is that the parallel transport ignores the rotation that occurs in the corners? I thought curves had to be smooth? What am I missing?

REPLY [0 votes]: Do parallel transport of the vector ${\bf v}:=(1,0)$ along the unit circle beginning and ending at $(1,0)$. Then the vector ${\bf v}$ will be horizontal pointing to the right at all times, even though the circle changes its forward direction continuously by a total amount of $2\pi$.
This is telling you that you should not turn the transported vector ${\bf v}$ at points where the curve $\gamma$ along which you transport has corners.


TITLE: Is this entanglement of formation identity true?
QUESTION [2 upvotes]: Let a tripartite system be given with pure state $\rho_{ABC}$. My adviser said that  the entanglement of formation satisfies the identity
$${E_F}_{A(BC)}^2={E_F}_{AB}^2+{E_F}_{AC}^2$$
Where ${E_F}_{A(BC)}$ is the entanglement of formation considering the bipartite state with parts $A$ and $B+C$.
He further said that ${E_F}_{A(BC)}^2=S_A^2$ the Von-Neumman entropy, and that because of that if we know ${E_F}_{AB}$ we get ${E_F}_{AC}$ by means of
$${E_F}_{AC}^2=S_B^2-{E_F}_{AB}^2.$$
Now is this identity true? He couldn't point me the specific reference, and I've tried searching and found none.
That ${E_F}_{A(BC)}=S_A$ is obvious because the entanglement of formation reduces to the entanglement entropy for pure states. Since $\rho_{ABC}$ is pure, considered a bipartite state between $A$ and $B+C$ it is pure, and the entanglement of formation is the entropy.
My doubt is about the very first identity. If it is true, why is it the case?

REPLY [2 votes]: The first equality is actually an inequality for qubit systems. (See This) I'm not so sure if this inequality holds in general dimension.


TITLE: Differentiating polar functions using complex numbers
QUESTION [0 upvotes]: I was wondering, given some polar function $r(\theta)$ is it possible to convert it into a complex number in exponential form, then differentiate that and then convert it back and have the appropriate derivative of the polar function?
For example take the polar function $r=\cos(a\theta)$, also known as a rose curve for $a\in\mathbb{Q}$. Is it possible to 'complexify' this function (not too sure how possible that is) and then take the derivative?

REPLY [0 votes]: Let $f:\mathbb{R}\to\mathbb{R}$. Furthermore, let $r(f) = \cos(f) \:\mathrm{or} \:\sin(f)$.
Form Eulers formula we know
$$e^{if} = \cos f+i\sin f.$$
We know that $\operatorname{Re}e^{if} = \cos f$ and $\operatorname{Im}e^{if} = \sin f$.
Since derivative and real/imaginary part commute it is allowed to do what you have stated.