TITLE: Homomorphism understanding
QUESTION [0 upvotes]: Let $f \in Hom(G, G')$, $f:G \rightarrow G'$
Moreover if $G, G'$ are sets such that : $(G, \star )$, $(G', \cdot )$are groups we have the following condition on $f$ :
$$f(x \star y) = f(x) \cdot f(y) $$
My question is then : why this particular condition on $f$ ? Why not for example : $f(x \star y) = x \cdot f(y)$ ?
And moreover why finding an homomorphism between two sets is important, does it helps proving something between two groups ?

REPLY [5 votes]: The other answerers have hinted you to your possible misconception. I want to tell you a bit about structure-preservation in general, because this is what an isomorphism does: it tells us that two things (mathematical objects) are essentially the same, just presented to us in two different ways. A homomorphism is a bit weaker, but I will come to it later.
I think graph theory provides us with a very accessible understanding of a structure to preserve. Look at these two networks (graphs):

Graphs consist of nodes and edges between them. The only important thing for graphs is what is connected to what. The actual representation of the graph does not matter at all.
The left example is a rectangle, or $4$-cycle. The right one is also a rectangle but twisted. In the sense of connectedness, these both graphs are structurally the same. But how to say this mathematically? We begin by introducing a notation for connectedness (adjacency): we write $v_1\sim v_2$ for the fact that the nodes $v_1$ and $v_2$ are connected by an edge. On the other hand we have $v_1\not\sim v_3$.
We now want to say that these both graphs are the same. We can show this by giving a way how to transform the left graph into the right one. This can be done by stating which vertex on the left should be mapped to which vertex on the right. We do this via a map $f$. For example we could say $f(v_i)=w_i$. However, this specific transformation is not structure preserving in the following sense: $v_1\sim v_4$ but $w_1\not\sim w_4$. We can state this by
$$v_1\sim v_4 \quad\text{but}\quad f(v_1)\not\sim f(v_4).$$

Just mapping each vertex with the index $i$ on the left to its corresponding vertex with index $i$ on the right will not give us a transformation that demonstrates the equality of the graphs. You see from this failure, that we need to claim the following for the map $f$:
$$v_i\sim v_j\quad\Rightarrow\quad f(v_i)\sim f(v_j).$$
This is the point where you should see the similarity to your group theory homomorphism. And indeed, such maps are called graph homomorphisms. Homomorphism are a very general concept. If two elements of an object have a specific relation to each other, then this relation should be kept when transforming the whole object onto another structurally equivalent object.
An example for a homomorphism would be
$$f(v_1)=w_1,\quad f(v_2)=w_2,\quad f(v_3)=w_4,\quad f(v_4)=v_3.$$
Note that we have not claimed $v_i\not\sim v_j\Rightarrow f(v_1i)\not\sim f(v_j)$ yet. This is indeed not necessary for homomorphisms. For example, the following is a valid structure preserving map for the left graph into the right one:

Many different nodes can be mapped to the same node, as long as they are not connected. Why? because a node is (in this kind of graphs) never connected to itself. So we obey the homomorphism rule. So what we actually found here is that the right "subgraph" consisting of the vertex $w_1$ and $w_3$ is somehow structurally similar to the complete left graph.
This is of course not the kind of identity we want to show with that both graphs are identical. For this we need isomorphisms. An isomorphism is a bijective map $f$, so that both $f$ and $f^{-1}$ are homomorphisms. They are structure preserving in both directions.

But back to group theory. For groups this is very similar. Instead of two elements (nodes) like for graphs, for groups we relate three elements via the expression $g_1\circ g_2 =h$. To preserve this structure via a map $f$ and carry it over to another group we have to claim $f(g_1)* f(g_2)=f(h)$. Now just substitute our former meaning of $h$ into the last equation:
$$f(g_1)* f(g_2)=f(g_1\circ g_2).$$
And this is a group homomorphism. Something that tells you that its image $f(G)$ is somehow similar to the former group $G$. As above, to really talk about two identical groups $G_1$ and $G_2$, you will have to consider bijections $f:G_1\to G_2$ so that both $f$ and $f^{-1}$ are homomorphisms $-$ so called group isomorphisms.


text:
Structure preserving numerical schemes have their roots in geometric integration \cite{hairer2006geometric}, and numerical schemes that build on characterisations of PDEs as metric gradient flows \cite{ambrosio2008gradient}, just to name a few. The overarching aim of structure preserving numerics is to preserve certain properties of the continuous model, e.g mass or energy conservation, in its discretisation. But structure preservation is not just restricted to play a role in classical numerical analysis of ODEs and PDEs. Indeed, through the advent of continuum interpretations of neural networks \cite{haber2017stable, E2017deepode, E2018, Ruthotto2019pde}, structure preservation is also entering the field of deep learning. Here, the main objectives are to use the continuum model and structure preserving schemes to derive stable and converging neural networks and associated training procedures, and algorithms, e.g. neural networks which generalise well.

\subsection{Neural Networks}
Neural networks are a rich class of machine learning models that can be leveraged for many different tasks including regression, classification, natural language processing, reinforcement learning and image generation \cite{lecun2015deep}. While it is difficult to provide an all-encompassing definition for neural networks, they can generally be characterised as a combination of simple, parametric functions between \emph{feature spaces}. These functions act as individual building blocks (commonly called the \emph{layers} of the network). The main mechanism for combining these layers, which we will adopt in this work, is by function composition.

For any $k \in \lbrace 0, \dots, K-1 \rbrace$, let $\FeatureSpace^k$ denote a vector space (our \emph{feature space}). While in most applications, these are simply finite-dimensional Euclidean spaces, we will assume more general structures (such as Banach spaces) when appropriate. With this, we then define a generic layer $$f^k: \FeatureSpace^{k} \times \GenParamSet^{k} \to \FeatureSpace^{k+1},$$
where $\GenParamSet^k$ is the set of possible parameter values of this layer. A neural network
\begin{equation}
    \begin{aligned}
        \Psi: \FeatureSpace \times \GenParamSet &\to \LabelSpace \\
         (x,\theta) &\mapsto z^K
    \end{aligned}
\end{equation}
can then be defined via the iteration
\begin{equation}
\begin{aligned}
    \HiddenVar^0 &= x\\
    \HiddenVar^{k+1} &= f^k(\HiddenVar^{k},\theta^ k), \quad k = 0,\dots, K-1, \label{eq:neuralnet_general_form}
\end{aligned}
\end{equation}
such that $\FeatureSpace^0=\FeatureSpace$ and $\FeatureSpace^K=\LabelSpace$, where $\theta:=(\theta^0,\dots,\theta^{K-1}) \in \GenParamSet^0 \times \cdots \times \GenParamSet^{K-1}=:\Theta$ denotes the entirety of the network's parameters. The first layer is commonly referred to as the neural network's \emph{input layer}, the final layer as the neural network's \emph{output layer}, and all of the remaining layers are called \emph{hidden layers}.

While the above definitions are still quite general, in practice several standard layer types are employed. Most ubiquitous are those that can be written as a learnable affine combination of the input, followed by a simple, nonlinear function: the layer's \emph{activation function}. The quintessential example are \emph{fully-connected layers}
\begin{equation}
    \begin{aligned}
         f: \mathbb{R}^M \times (\mathbb{R}^{M'\times M} \times \mathbb{R}^{M'}) & \to \mathbb{R}^{M'} \\
         (\HiddenVar,(A,b)) &\mapsto \sigma ( A\HiddenVar + b),
    \end{aligned}
    \label{eq:fully_connected}
\end{equation}
whose parameters are the \emph{weight matrix} $A \in \mathbb{R}^{M'\times M}$ and the \emph{bias vector} $b \in \mathbb{R}^{M'}$. Its activation function $\sigma: \mathbb{R}^{M'} \to \mathbb{R}^{M'}$ is typically applied component-wise, e.g. the hyperbolic tangent $[\tanh (\HiddenVar)]_i:= \tanh (\HiddenVar_i)$ or the \emph{rectified linear unit} (ReLU) $[\text{relu}(\HiddenVar)]_i:=\max (0, \HiddenVar_i)$. For classification networks, the most common choice for the output layer's activation function is the \emph{softmax} activation function given by $$[\text{softmax}(z)]_i=\frac{\exp(z_i)}{ \sum^{M'}_{j=1} \exp (z_j) },$$

such that the neural network's output's entries can be regarded as the individual class membership probabilities of the input.
An important extension to the concept of fully-connected layers lie in \emph{convolutional layers} \cite{lecun1989backpropagation} where the matrix-vector product is replaced by the application of a (multi-channel) convolution operator. These are the main building block of neural networks used in imaging applications.

Suppose we are given a set of paired training data $(x_n, y_n)_{n=1}^N \subset \FeatureSpace \times \LabelSpace$, which is the case for predictive tasks like regression or classification. Training the model then amounts to solving the optimisation problem
\begin{align}
    \min_{\theta \in \Theta} \left\{ E(\theta) = \frac1N \sum_{n=1}^N \Loss_n (\Psi(x_n, \theta)) + R(\theta)\right\} . \label{eq1:training}
\end{align}
Here $L_n(y) := L(y, y_n) : \LabelSpace \to \mathbb R_\infty$ is the loss for a specific data point where $\Loss : \LabelSpace \times \LabelSpace \to \mathbb R_\infty := \mathbb R \cup \{\infty\}$ is a general loss function which usually satisfies $\Loss \geq 0$ and $\Loss(y_1, y_2) = 0$ if and only if $y_1 = y_2$. The function $L_n$ is usually smooth on its effective domain $\{y \mid L_n(y) < \infty\}$ and convex. $R : \GenParamSet \to \mathbb R_\infty$ acts as a regulariser which penalises and constrains unwanted solutions. In this setting, solving~\eqref{eq1:training} is a form of empirical risk minimisation \cite{shalev2014understanding}. Typically, variants of stochastic gradient descent are employed to solve this task. The calculation of the necessary gradients is performed using the famous \emph{backpropagation} algorithm, which can be understood as an application of reverse-mode auto-differentiation \cite{linnainmaa1970representation}.

\subsection{Residual Networks and Differential Equations}\label{sec:intro_resnets_ode}
In the following, we will discuss artificial neural networks architectures that arise from the numerical discretisation of time
and parameter dependent differential equations. Differential equations have a long history in the mathematical treatment of neural networks. Initially, neural networks were motivated by biological neurons in the brain. Mathematical models for their interactions are based on nonlinear, time-dependent differential equations. These have inspired some famous artificial neural networks such as the Hopfield networks \cite{hopfield1982neural}.

On a time interval $[0,T]$, the values of the approximation to the solution of the differential equation at different discrete times $0=t^0<t^1< \dots <t^K=T$, e.g. $t^k=k\,h$ and $h=T/K$
, corresponding to the different layers of the network architecture. For a fixed final time $T$, the existence of an underlying continuous model guarantees the existence of a continuous limit as the number of layers goes to infinity and $h$ goes to zero.

In the spirit of geometric numerical integration \cite{hairer2006geometric}, we discuss structural properties of the ANN as arising from the structure preserving discretisation of a differential equation with appropriate qualitative features such as having an underlying symmetry, an energy function or a Lyapunov function, preserving a volume form or a symplectic structure.

\begin{figure}
\def\PicWidth{3cm}
\newcommand{\PlotFrame}[4]{
\node[anchor=south west] at (#4, 0) {\includegraphics[clip, trim=#2, width=\PicWidth]{#1}};
\node[anchor=south west] at (#4, 0) {$k = #3$};
}
\newcommand{\PlotFrames}[3]{
\begin{tikzpicture}[x=\PicWidth+5mm, y=\PicWidth, inner sep=0pt]
\PlotFrame{pics/#1_01}{#2}{0}{0}
\PlotFrame{pics/#1_16}{#2}{15}{1}
\PlotFrame{pics/#1_31}{#2}{30}{2}
\PlotFrame{pics/#1_41}{#2}{40}{3}
\node[anchor=west] at (0,0.5) {\rotatebox{90}{#3}};
\end{tikzpicture}
}
\PlotFrames{halfmoon2d_40layers_ResNet_squared_tanh_seed1_video}{140px 95px 190px 90px}{\texttt{halfmoon2d}}\\[3mm]
\PlotFrames{donut2d_40layers_ResNet_squared_tanh_seed1_video}{140px 95px 195px 90px}{\texttt{donut2d}}\\[3mm]
\PlotFrames{donut2d+_40layers_ResNet_squared_tanh_seed1_video}{210px 150px 350px 120px}{\texttt{donut3d}}
\caption{Evolutions of the ResNet model \eqref{eq1:discreterecursion2} for three different data sets. The upper two rows show evolutions in 2d and the lower row in 3d. The link function $\sigma$ is the hyperbolic tangent
 and the data fit and regulariser are the squared 2-norm, $L_n(z) = \frac12 \|z-y_n\|^2_2$, $R(\theta) = \frac \lambda 2 \|\theta\|^2_2$.} \label{fig1:dynamics}
\end{figure}

Contrary to the 'classical' design principle for layers of affine transformations followed by activation functions (cf. \eqref{eq:fully_connected}), so-called \emph{residual layers} are a variation to this principle, which has risen to become a standard design concept of neural networks. Here, the output of one such layer is again added to its input, which again defines a network, the ResNet~\cite{He2016resnet}, $\Psi: \FeatureSpace \times \GenParamSet \to \FeatureSpace, \Psi(x,\theta) = z^K$ that is now given by the iteration
\begin{equation}
\begin{aligned}
    \HiddenVar^0 &= x\\
    \HiddenVar^{k+1} &= \HiddenVar^{k} + \sigma(A^k \HiddenVar^{k} + b^k), \quad k = 0,\dots,K-1, \label{eq1:discreterecursion}
\end{aligned}
\end{equation}
if $\FeatureSpace=\LabelSpace$. If on the other hand the output space $\LabelSpace$ differs from $\FeatureSpace$, it is common to add another layer $\eta: \FeatureSpace \to \LabelSpace$ on top, which defines a network $\hat{\Psi}:=\eta \circ \Psi: \FeatureSpace \to \LabelSpace$. This is for example a common scenario in classification, where the dimensionality of $\LabelSpace$ is determined by the number of classes.

It is easy to see that \eqref{eq1:discreterecursion} corresponds to a particular discretisation of an ODE. To make the connection more precise, denote by
$z^k := \HiddenVar(t^k), A^k := A(t^k), b^k := b(t^k)$ samples of three functions $\HiddenVar : [0, T] \to \mathbb R^M, A : [0, T] \to \mathbb R^{M\times M}$ and $b : [0, T] \to \mathbb R^M$
. With these notations we can write the ResNet \eqref{eq1:discreterecursion} as $\Psi(x, \theta) = \HiddenVar(T)$ with
\begin{align}
\HiddenVar(t^{k+1}) = \HiddenVar(t^k) + h \sigma(A(t^k) \HiddenVar(t^k) + b(t^k)), \quad k = 0, \ldots, K-1, \quad \HiddenVar(0) = x \label{eq1:discreterecursion2}
\end{align}
if $T = K$ and thus $h = 1$. For general $T$, it can be readily seen that \eqref{eq1:discreterecursion2} corresponds to the forward Euler discretisation of
\begin{align}
    \dot \HiddenVar(t) = f(\HiddenVar(t), \theta(t)), \quad t \in [0, T], \quad \HiddenVar(0) = x \label{eq1:ode}
\end{align}
with $\theta := (A, b) : [0, T] \to \mathbb R^{M\times M} \times \mathbb R^M\cong \mathbb R^{M^2+M}$,
\begin{equation} \label{eq1:vectorfield}
f(\HiddenVar(t), \theta(t)) = \sigma(A(t)\HiddenVar(t) + b(t)).
\end{equation}
Thus, there is a natural connection of the discrete deep learning problem \eqref{eq1:training}+\eqref{eq1:discreterecursion} with the optimal control formulation \eqref{eq1:training}+\eqref{eq1:ode}. The dynamics of the ResNet \eqref{eq1:discreterecursion} as a discretisation of \eqref{eq1:ode} is depicted in Figure \ref{fig1:dynamics}.

From here on we will suppress the dependence on $t$ whenever it is clear from the context.

It is a well-known fact that the optimal control formulation can be phrased as a closed dynamical system by using Pontryagin's principle and this results in a constrained Hamiltonian boundary value problem \cite{Benning2019ode}, the Hamiltonian of this system is given as
\begin{align}
    H(\HiddenVar, \LagrangeMultiplier, \genparam) = \langle\LagrangeMultiplier, f(\HiddenVar, \genparam)\rangle
    \label{eq1:hamiltonian}
\end{align}
where $\LagrangeMultiplier\in T^*\FeatureSpace\equiv\mathbb{R}^M$ is a vector of Lagrange multipliers. The dynamical system is then given by
\begin{align}
\dot \HiddenVar = \partial_\LagrangeMultiplier H, \quad
\dot \LagrangeMultiplier = -\partial_\HiddenVar H, \label{eq1:extended_ode}
\end{align}
subject to the constraint
\begin{align}
 \quad
0 = \partial_\genparam H.  \label{eq1:constraint}
\end{align}
The adjoint equation for $\LagrangeMultiplier$ can be expressed as
\begin{align}
    \dot \LagrangeMultiplier = \partial_z f^T \LagrangeMultiplier, \quad
    p(T) &= \frac{1}{N}\sum_{n=1}^N \partial_\HiddenVar \Loss_n^\prime(z(T)).
\end{align}

In what follows we will review some of the guiding principles of structure preserving deep learning, and in particular recent contributions for new neural networks architectures as discretisations for ODEs and PDEs in Section~\ref{sec:ODEPDE} and the interpretation of the training of neural networks as an optimal control problem in Section~\ref{sec:optimalcontrol}, invertible neural networks in Section \ref{sec:invertible}, equivariant neural networks in Section \ref{sec:equivariant}, and structure-preserving numerical schemes for the training of neural networks in Section \ref{sec:SPT}.

config: arxiv


TITLE: Finding parameters of Poisson LogNormal.
QUESTION [0 upvotes]: Fix $n>1$ and arbitrary large. Let $X=X_1+\cdots+X_n$ has Poisson-LogNormal distribution. That is $X\sim Poisson(\lambda)$ and $\ln(\lambda)\sim Normal(\mu,\sigma)$. If we log-transform $X_i$'s in any arbitrary base, then what can we say about the distribution of $x=\log(X_1)+\cdots+\log(X_n)$? Is it again Poisson-LogNormal?

REPLY [0 votes]: I finally find an answer for my question. Note the following:
Def. A distribution with probability density function $f$ is said to be reproducible if the sum of two independent random variables $X_1$ and $X_2$, each with probability density function $f$, follows a distribution with probability density function of the same form as $f$ but with possibly different parameters.
Prop.(Feller, 1943). The sum of two mixed Poisson variables ($MP(f)$) has an $MP(f)$ distribution if the distribution defined by $f$ is itself reproducible.
In my case Normal Distribution (log-normal distribution) is reproducible.


text:
\chapter{The Arthur Packet of \texorpdfstring{$L(\nu^{\alpha}\rho, \nu^{\alpha-1}\rho;\delta(\nu^\alpha\rho;\s))$\\
 by Colette M\oe glin}{}} \label{appendix-M}

 \section{The representations}

Let $\s$ be an irreducible cuspidal representation of a classical groups $G=G(F)$ and let $\rho$ be an irreducible unitarizable cuspidal representation of a $\GL(d,F)$.
Let $\alpha\in \tfrac12\Z$ be strictly greater then $1$. Suppose that $\nu^\alpha\rho\rtimes\s$ is reducible. Denote by
$
\delta(\nu^\alpha\rho;\s)
$
the unique irreducible square-integrable subquotient of the last representation.

The induced representation
$$
\nu^\alpha\rho\times\nu^{\alpha-1}\rho\rtimes \delta(\nu^\alpha\rho;\s)
$$
has a unique irreducible quotient which will be denoted by $\pi$ (this is the Langlands quotient).

\section{The parameters}

Denote by $\phi$ the Langlands parameter of $\s$. This parameter is an admissible homomorphism of $W_F\times SL(2,\C)$ into $^LG$.
We denote also by $\rho$ the morphism of $W_F$ into $\GL(d, \C)$ which parameterizes the cuspidal representation $\rho$.

The assumption on $\alpha$ regarding the reducibility implies that there exists an admissible homomorphism $\phi_-$ for a classical group of smaller rank than $G$,
which is discrete and for which holds
$$
\phi=\phi_- \ \oplus \ \rho \otimes R[2\alpha-3] \ \oplus \ \rho \otimes R[2\alpha-1],
$$
where $R[n]$ denotes the irreducible $n$-dimensional algebraic representation of the group $SL(2,\C)$.
For this it is necessary that $2\alpha-3\geq0$, i.e. $\alpha\geq \tfrac32$.
If $\alpha= \tfrac32$, there one does not need to write the
term $\rho \otimes R[2\alpha-3]$.

Moreover $\phi_-$ is non-trivial if $G$ is quasi-split, but this is not used in the sequel.

One defines now the Arthur parameter $\psi$. It is the following morphism of $W_F\times SL(2,\C) \times SL(2,\C)$ into $^LG$:
$$
\psi:= \phi_- \otimes R[1] \ \oplus \ \rho \otimes R[2\alpha+1] \otimes R[1] \ \oplus \ \rho \otimes R[1] \otimes R[2\alpha+1] .
$$

\section{The result}

\

{\bf Claim}: The representation $\pi$ is in the Arthur packet associated to $\psi$.

Denote by $\psi_+$ the morphism where one changes a dimension $2\alpha+ 1$ into $2\alpha+ 3$. We have two possibilities and we make the choice that suits us for the proof
(the result is obviously independent of the choice) That is:
$$
\psi_+:= \phi_- \otimes R[1] \ \oplus \ \rho \otimes R[2\alpha+3] \otimes R[1] \ \oplus \ \rho \otimes R[1] \otimes R[2\alpha+1] .
$$
From the section 3.1.2 of \cite{MR2767522}, we know that the representations of the packet associated with $\psi$ are obtained from those associated with $\psi_+$ as follows:

{\sl Let $\tau_+$ be a representation in the packet parameterized by $\psi_+$. Then the term $Jac_{\nu^{\alpha+1}\rho}( \tau_+)$ is either zero or an irreducible representation.
In the second case, this irreducible representation is in the packet associated with $\psi$ and all the representations of the packet associated with $\psi$ are
obtained in this way and for a unique choice of $\tau_+$.}

We will construct in the packet associated with $\psi_+$, a representation denoted $\pi_+$ which will give $\pi$ by the procedure above.

Indeed, according to the construction in the section 3.1.1 in
\cite{MR2767522} (which is a summary of \cite{MR2209850} for the case which matter here of $\ell(\psi)=0$),
 the packet associated with $\psi_+$ contains
the representations of the packet obtained as the unique irreducible sub-representations of the induced representations
$$
\nu^{-\alpha}\rho \times \nu^{-\alpha-1}\rho\rtimes\tau_-,
$$
where $\tau_-$ runs over the representations of the packet
$$
\psi_-:= \phi_- \otimes R[1] \ \oplus \ \rho \otimes R[2\alpha+3] \otimes R[1] \ \oplus \ \rho \otimes R[1] \otimes R[2\alpha-3] .
$$
This even describes all representations of the packet associated with $\psi_+$ if $2\alpha-3>0$, and some are missing if $2\alpha-3=0$, but it does not matter to us.

According to the same reference, the packet associated with $\psi_-$ is formed of the irreducible subrepresentations
of the induced representations
$$
\nu^{\alpha+1}\rho\rtimes\tau',
$$
where $\tau'$ runs over the representations of the packet
$$
\psi':= \phi_- \otimes R[1] \ \oplus \ \rho \otimes R[2\alpha+ 1] \otimes R[1] \ \oplus \ \rho \otimes R[1] \otimes R[2\alpha-3] .
$$
This packet contains the representation $\delta(\nu^\alpha\rho;\s) $, the point is somewhat subtle: the representations of the packet $\psi'$ are the unique irreducible
subrepresentations of the induced representation $ \nu^{\alpha}\rho\rtimes\tau''$ with $\tau''$ in the packet associated to
$$
\phi_- \otimes R[1] \ \oplus \ \rho \otimes R[2\alpha-1] \otimes R[1] \ \oplus \ \rho \otimes R[1] \otimes R[2\alpha-3] .
$$
But this package contains the cuspidal representation $\s$, hence the assertion.

We have thus constructed a representation $\pi_+$ which is an irreducible sub representation
of the induced representation:
$$
\nu^{-\alpha}\rho\times \nu^{-\alpha+1}\rho \times \nu^{\alpha+1}\rho \rtimes \delta(\nu^{\alpha}\rho;\s).
$$
We can exchange $\nu^{\alpha+1}\rho$ and $\nu^{-\alpha}\rho\times \nu^{-\alpha+1}\rho$ (i.e. commute), so $Jac_{\nu^{\alpha+1}\rho} (\pi_+)$ is non-zero and actually is a submodule of the induced representation
$$
\nu^{-\alpha}\rho\times \nu^{-\alpha+1}\rho \rtimes \delta(\nu^{\alpha}\rho;\s).
$$
Since this induced representation has only one irreducible sub representation, which is $\pi$, and one knows a priori that the representation
$Jac_{\nu^{\alpha+1}\rho}(\pi_+)$ is irreducible, we identify this Jacquet module with $\pi$. We have thus shown that $\pi$ is in the packet associated with $\psi$.

\endinput


TITLE: Why this matrix is positive semi-definite？The difference between RLS estimator and OLS estimator with respect to their variance.
QUESTION [0 upvotes]: It seems not obvious to me and I want to know why the matrix C is positive semi-definited ?
See the source :
http://web.vu.lt/mif/a.buteikis/wp-content/uploads/PE_Book/4-4-Multiple-RLS.html
Let L be a 'r x k' constants matrix and rank(L)= r,
Let X be a 't x k' constants matrix and rank(X)= k;
\begin{aligned}
\mathbb{V}{\rm ar} \left(\widehat{\boldsymbol{\beta}}^{(OLS)} \right) - \mathbb{V}{\rm ar} \left(\widehat{\boldsymbol{\beta}}^{(RLS)} \right) &= \sigma^2 \left( \mathbf{X}^\top  \mathbf{X}\right)^{-1}  \mathbf{L}^\top \left( \mathbf{L}\left( \mathbf{X}^\top \mathbf{X} \right)^{-1} \mathbf{L}^\top \right)^{-1}  \mathbf{L} \left( \mathbf{X}^\top  \mathbf{X}\right)^{-1} = \sigma^2 \mathbf{C}
\end{aligned}
Here the matrix C

REPLY [2 votes]: $X^\top X$ is positive definite; so is its inverse.
Since $(X^\top X)^{-1}$ is positive definite, we have $v^\top L (X^\top X)^{-1} L^\top v (L^\top v)^\top (X^\top X)^{-1} (L^\top v) \ge 0$ for any $v$. So $L(X^\top X)^{-1} L^\top$ is positive semi-definite.
Based on your expression it seems $L(X^\top X)^{-1} L^\top$ is also invertible. (I don't think this fact can be deduced from the information you provided.) If so, then this inverse is positive definite.
From there, you can conclude that
$$v^\top (X^\top X)^{-1} L^\top (L(X^\top X)^{-1} L^\top)^{-1} L(X^\top X)^{-1} v
 = w^\top (L(X^\top X)^{-1} L^\top)^{-1} w \ge 0$$
for any $v$, where $w := L(X^\top X)^{-1} v$, so your matrix is positive semi-definite.


TITLE: Is graph isomorphism in UP ${\cap}$ coUP?
QUESTION [10 upvotes]: Is graph isomorphism (the decision problem) in $\mathsf{UP}\cap \mathsf{coUP}$? Here $\mathsf{UP}$ is the class of decision problems accepted by an unambiguous Turing machine (see the complexity zoo).

REPLY [19 votes]: Graph isomorphism is not known to be in $\mathsf{UP}$ nor known to be in $\mathsf{coUP}$.
For $\mathsf{UP}$: the natural nondeterministic algorithm - guess a map between the two graphs and check if it's an isomorphism - has either 0 witnesses (iff the graphs are not isomorphic) or $|\text{Aut}(G)|$ witnesses. Although most graphs have $|\text{Aut}(G)|=1$ (that is, if you pick a random graph on $n$ vertices, the probability that it has any nontrivial automorphsims goes to $0$ quite quickly with $n$), this is not enough to say that there is always at most one witness. This of course does not rule out some other algorithm that could show that graph isomorphism in $\mathsf{UP}$. (After all, it's possible that graph isomorphism is in $\mathsf{P} \subseteq \mathsf{UP}$.)
As for $\mathsf{coUP}$, as pointed out by Peter Shor, we don't even known if graph isomorphism is in $\mathsf{coNP}$, so we certainly don't know if it's in $\mathsf{coUP}$. (Under a plausible derandomization assumption it is in $\mathsf{coNP}$, but I don't know any natural assumption that puts it in either $\mathsf{UP}$ or $\mathsf{coUP}$.)


TITLE: A question on Tight probability measures (regular measure)
QUESTION [8 upvotes]: This is somewhat a basic question, but I'm having difficulty proceeding with a certain part of the proof. I was reading Billingsley "Convergence of Probability Measures", and I encountered the following question:
Question:
Given a metric space $X$ and $\mathscr{B}$ the Borel sigma algebra, prove that a probability measure $P$ on $X$ is tight iff
$$\forall A \in \mathscr{B},\quad \sup \{P(K): K\subset A, K \mbox{ compact}\} = P(A)$$
My Proof:
($\Rightarrow$)
Put $A=X$. Then we have
$$1 = P(X) = \sup \{P(K): K\subset X, K \mbox{ compact}\}$$
By definition of sup, we get $\forall \epsilon > 0$, $\exists K$ compact such that
$$P(K) \geq 1-\epsilon$$ Thus P is tight.
($\Leftarrow$)
Billingsley suggests using the following theorem:
Probability measures on metric spaces are regular. That is
$$\forall A \in \mathscr{B}, \forall \epsilon > 0, \exists F \mbox{  closed}, G \mbox{  open such that}$$
$$F \subset A \subset G, \quad P(G \setminus F) < \epsilon$$
I do not know how to use compactness here. I reasoned that if I could prove that $\forall \epsilon > 0$, $\exists K \subset A$ compact such that $P(A\setminus K) < \epsilon$, I would be done. Since the compact sets in "tightness", needn't be subsets of A, I don't know how to use it. I was able to show the easy inequality which is:
$$\sup \{P(K): K\subset A, K \mbox{ compact}\} \leq P(A)$$
(since $K\subset A$)
I would appreciate any ideas, hints and tips (if not answers) to this. References are also welcome. I searched for "Tight Regular Measures" and "Tight Probability" but to no useful results.

REPLY [0 votes]: Let $\epsilon>0$ be given. There are closed F (By Theorem. 1.1 of billingsly) and compact $K$ such that
        $$P(K)>1-\frac{\epsilon}{2},$$ i.e. $$P(K')<\epsilon/2,$$
and     $$P(A-F)<\epsilon/2,$$
Then we have $P(A-(F\cap K ))<\epsilon$, which proposes $F\cap K$ as desired compact set.


TITLE: How do I find the centralizer for this matrix?
QUESTION [2 upvotes]: Let $B=\begin{pmatrix}
2 & 2 \\
 0& 1 \\
\end{pmatrix} \in GL_2(\mathbb{R})$. Determine the centralizer for $B$.

Here's what I've done so far:
Let $D=\begin{pmatrix}
a & b \\
c & d \\
\end{pmatrix} \in GL_2(\mathbb{R})$.
$\begin{align}
BD&=DB\\
\begin{pmatrix}
2 & 2 \\
 0& 1 \\
\end{pmatrix} \begin{pmatrix}
a & b \\
c & d \\
\end{pmatrix} &= \begin{pmatrix}
a & b \\
c & d \\
\end{pmatrix} \begin{pmatrix}
2 & 2 \\
 0& 1 \\
\end{pmatrix}\\
\begin{pmatrix}
2(a+c) & 2(b+d) \\
 c& d \\
\end{pmatrix}&= \begin{pmatrix}
2a & 2a+b \\
 2c& 2c+d \\
\end{pmatrix}
\end{align} $
From the above, we have:
$\begin{aligned}
2a+2c&=2a\\
2b+2d&=2a+b\\
c&=2c\\
d&=2c+d
\end{aligned}
$
From which we derive:
$\begin{aligned}
c&=0\\
b+2d-2a&=0\\
d&=d \in \mathbb{R} \backslash \{0\}
\end{aligned}$
As you can see, I've managed to determine $c$ and $d$, but I can't seem to figure out $a$ and $b$. What am I missing?

REPLY [2 votes]: $\newcommand{\Set}[1]{\left\{ #1 \right\}}$$\newcommand{\R}{\mathbb{R}}$Allow me to sketch a slightly more conceptual approach.
$B$ has clearly the eigenvalues $2$ and $1$, hence it can be diagonalised, and one sees immediately that
$$
T^{-1} B T = \begin{bmatrix}2 & 0\\0 & 1\end{bmatrix},
\quad
\text{for }
T
=
\begin{bmatrix}1 & -2\\0 & 1\end{bmatrix}.
$$
Now the centraliser of $T^{-1} B T$ is immediately seen to be
$$
\mathbf{C}
=
\Set{
\begin{bmatrix}a & 0\\0 & d\end{bmatrix}
:
a, d \in \R \setminus \Set{0}}.
$$
Hence the centraliser of $B$ is
$$
T \mathbf{C}
 T^{-1}
=
\Set{
\begin{bmatrix}a & 2 a - 2 d\\0 & d\end{bmatrix}
:
a, d \in \R \setminus \Set{0}}.
$$