TITLE: $L^p$-norm minimization under linear constraints: Does the optimum depend on $p$?
QUESTION [0 upvotes]: Consider the following norm minimization program:
\begin{align}
\label{1}
&\min_{x \in \mathbb{R}^d} &&\lVert x - x_0 \rVert_p^p &(1)\\
&\text{subject to } &&Ax-b \ge 0
\end{align}
Here, $\lVert \cdot \rVert_p$ is the $L^p$-norm, with $p \ge 1.$
Is the following statement true?
If $x^*$ is a solution to (1) for some $p \ge 1$, then $x^*$ is also a solution for any $q \ge 1$.
I guess this boils down to showing that the minimal distance between a hyperplane $X$ and the point $x_0$ is always obtained in the same point $x^* \in X$, regardless of which $L^p$-norm is being used.
When I make sketches for the case $d=2$, the statement "looks right", but I could not come up with a proof. Maybe the Hölder inequality can be used in some way?

REPLY [1 votes]: Yes, you are right, the statement is not true. You can sketch the simple following example on $\mathbb{R}^2$. Let $x_0=(1,1)^T$ and
$$A= \begin{pmatrix}
       1 & 0 \\
       \frac{2}{5}&\frac{1}{5}
     \end{pmatrix}.
$$
Then it is easy to see for $p=1$, the minimum is attained at $(2,1)^T$, however for $p=2$, the minimum is attained at $(\frac{9}{5},\frac{7}{5})^T$. The reason is when we consider distance, $p=2$ corresponds to a ball, while $p=1$ corresponds to a square.


text:
\section{Table of Notations Defined in the Main Paper}\label{appendix: table of notations}
For readers' convenience, we summarize the notations used in the main paper in \tabref{tab:notation-table}.
\begin{table}[h!]
  \caption{Table of Notations}
  \label{tab:notation-table}
  \centering
  \begin{tabular}{lll}
    \toprule
    Notations     & Use      \\
    \midrule
    $h,h^{(i)}$ & a hyperplane    \\
    $x, x^{(i)}$ & a point        \\
    $r, r^*$ & target/sampled  region/hypothesis/concept   \\
    $\bracket{\mathbi{u}}, \bracket{\mathbi{v}}$ & dichotomies equivalence classes  \\
    $\eta, \eta_h$ & normal vectors of a hyperplane\\
    $b, b_h$ & bias of a hyperpane\\
    $\xnd$ & data points in $\Rd$ or \data\\
    $\Hnd$ & $n$ hyperplanes set in $\Rd$ or \hypo\\
    $\mathcal{A}(\Hnd)$ & hyperplanes arrangement of set $\Hnd$\\
    $\regionset$ & set of regions induced by hyperplane arrangement $\Hnd$\\
    $\rnd$ & $\#$regions induced by hyperplane arrangement $\mathcal{A}(\Hnd)$\\
    $\boldsymbol{\mathfrak{D}}_{\xnd}$ & set of dichotomies of $\xnd$\\
    $\boldsymbol{\mathfrak{E}}\parenb{\xnd}$ & the set of equivalence classes of homogeneously linear separable dichotomies\\
    $\boldsymbol{\mathfrak{E}}_{\xnd}^{\phi}$ & the set of equivalence classes of $\phi$-separable dichotomies\\
    $r_{\bracket{\mathbi{u}}}$ & random dichotomy (equivalence) class in $\boldsymbol{\mathfrak{E}}_{\xnd}^{\phi}$\\
    $\mathcal{B},\phi,\Upsilon_{\mathrm{dual}} ,\varphi_{\mathrm{dual}}$ &  maps\\
    $\ff\parenb{\cA(\Hnd)}$  & number of faces\\
    $\mathcal{U}$ & uniform distribution\\
    $\Theta$& set of embedded points\\
    $\boldlam$& a matrix\\
    $\mathbb{I}_{[k]}$& set of $k$ indices of naturals\\
    \bottomrule
  \end{tabular}
\end{table}
\clearpage

config: arxiv


TITLE: divisibility on prime and expression
QUESTION [2 upvotes]: This site is amazing and got good answer.
This is my last one.
If $4|(p-3)$ for some prime $p$, then $p|(x^2-2x+4)$.
can you justify my statement?
High regards to one and all.

REPLY [0 votes]: If $x \geq 0$, then $x^2 - 2x + 4 = (x - 1)^2 + 3$.
So then you want to see if $-3$ is a quadratic residue modulo $p$, and that's what you use the Legendre symbol $(\frac{-3}{p})$ for, which gives you a yes ($1$) or no ($-1$) answer.
But $p \equiv 3 \mod 4$ does not guarantee $(\frac{-3}{p}) = 1$, as André's example of $p = 11$ shows. And even if $(\frac{-3}{p})$ does equal $1$, all that tells you is that there is at least one integer $x$ such that $p|(x^2 + 3)$; for example, with $p = 7$, we readily see that $p$ is a divisor of $2^2 + 3, 5^2 + 3, 9^2 + 3, \ldots$ but not $3^2 + 3, 6^2 + 3, 7^2 + 3, \ldots$


text:
\begin{document}

\title{Elementary derivation of Weingarten functions of classical Lie groups}
\author{Marcel Novaes\\
{\small Instituto de F\'isica, Universidade Federal de Uberl\^andia, Uberl\^andia, MG, 38408-100, Brazil}}\date{} \maketitle

\begin{abstract}
Integration of polynomials over the classical groups of unitary, orthogonal and
symplectic matrices can be reduced to basic building blocks known as Weingarten
functions. We present an elementary derivation of these functions.
\end{abstract}

\section{Introduction}

Integration with respect to matrix ensembles is the core of random matrix theory
\cite{Mehta} and an important problem in many areas of mathematical physics.
\cite{handbook} Classical Lie groups of unitary, orthogonal and symplectic matrices,
endowed with the corresponding Haar measure, constitute important classes of matrix
ensembles. Integrals of functions which are polynomials in the matrix elements can be
reduced to the general form \be \int_G \prod_{k=1}^{n_1} U_{i_kj_k} \prod_{\ell=1}^{n_2}
U^*_{m_\ell r_\ell} dU\equiv\left\langle\prod_{k=1}^n U_{i_kj_k}\prod_{\ell=1}^{n_2}
U^*_{m_\ell r_\ell}\right\rangle_G,\ee where $G$ denotes one of the groups and $dU$ the
corresponding Haar measure.

Initial investigations in the physics literature considered the unitary group
$\mathcal{U}(N)$.\cite{wein,creutz,samuel,mello,BB,aubert,esposti} It was found that the
basic integral can be written as a double sum over the symmetric group, \be
\left\langle\prod_{k=1}^n U_{i_kj_k}
U^*_{m_kr_k}\right\rangle_{\mathcal{U}(N)}=\sum_{\tau,\sigma\in S_n} {\rm
Wg}^U(\tau^{-1}\sigma)\prod_{k=1}^n[i_k=m_{\sigma(k)}][j_k=r_{\tau(k)}],\ee where $[i=m]$
is the same as $\delta_{i,m}$ and Wg$^U$ is a function which depends only on the cycle
structure of its argument. Independently of the physicists, Collins \cite{collins}
rediscovered the problem and suggested Wg$^U$ be called the Weingarten function of
$\mathcal{U}(N)$.

The corresponding question for the orthogonal and symplectic groups has also been much
studied. \cite{gorin,prosen,lopez,braun} They too can be written as double sums over
permutations, and the corresponding Weingarten functions Wg$^O$ and Wg$^{Sp}$ have been
found. \cite{CS,CM} Later developments include new approaches (e.g. from Jucys-Murphy
elements, \cite{NovakJucys,zinn}) generalizations (e.g. to compact symmetric spaces
\cite{stolz,mats}) connections (e.g. to factorizations of permutations \cite{MN}) and
applications (e.g. to different polynomial integrals, \cite{banica} to quantum mechanics
\cite{znidaric,novaes,berko}).

Previous works where Weingarten functions were obtained were based either on
representation theory and Schur-Weyl duality,\cite{collins,CS} the theory of Gelfand
pairs,\cite{mats} or Jucys-Murphy elements.\cite{zinn} In contrast, we here derive
Weingarten functions for the classical compact groups by means of some elementary direct
calculations (although we rely on some classical results that can, of course, be
interpreted very naturally in the light of those theories).

The idea consists of five steps: 1)
write the integrand as the derivative of a power sum function; 2) change basis from power
sums to Schur functions; 3) perform the group integral; 4) revert back to power sums; 5)
take the derivative to arrive at the result.

\section{Required facts}

Let us review some well known facts and establish notation and terminology. More
detailed explanations of the concepts introduced below can be found in the classical
monograph by MacDonald \cite{donald}.

Everywhere, $\lambda\vdash n$ means $\lambda$ is a partition of $n$, i.e. a weakly
decreasing sequence of positive integers such that $\sum_i \lambda_i=n$. The number of
non-zero parts is called the length of the partition and denoted by $\ell(\lambda)$. The
partition with $n$ unit parts is denoted $1^n$. We define
$2\lambda\equiv(2\lambda_1,2\lambda_2,...)$ and
$\lambda\cup\lambda\equiv(\lambda_1,\lambda_1,\lambda_2,\lambda_2,...)$.

\subsection{Lie groups}

The unitary group $\mathcal{U}(N)$ is the group of complex $N\times N$ matrices satisfying $U^\dag U=1$,
where $U^\dag$ is the transpose conjugate of $U$.

The orthogonal group $\mathcal{O}(N)$ is the
subgroup of $\mathcal{U}(N)$ of real matrices. This is the isometry group in $\mathbb{R}^N$ with respect to the scalar product
$\{u,v\}=\sum_{i=1}^N u_iv_i$.

Let $J=\left(\begin{array}{cc}0 & 1 \\
-1 & 0\end{array}\right)$, where $0$ and $1$ are, respectively, the zero and the
identity matrix in $N$ dimensions. The unitary symplectic group $Sp(2N)$ is the subgroup of
$\mathcal{U}(2N)$ of complex unitary matrices satisfying $U^DU=1$, where $U^D=JU^TJ^T$. If we define \be\label{prod12}\llangle
u,v\rrangle=\sum_{i=1}^{2N} u_i(J v)_{i}=\sum_{i=1}^{N} u_iv_{i+N}-u_{i+N}v_i,\ee
then $U^D$ plays the role of adjoint of $U$, in the sense that $\llangle
u,Uv\rrangle=\llangle U^Du,v\rrangle$.

\subsection{Permutation groups}

The group of permutations of $n$ elements is $S_n$. The cycle type of $\pi\in S_n$ is the
partition $\lambda\vdash n$ whose parts are the lengths of the cycles of $\pi$ (the cycle
type of the identity in $S_n$ is $1^n$). We denote by $\mathcal{C}_\lambda$ the conjugacy
class of all permutations of cycle type $\lambda$. The length of a permutation is
$\ell(\pi)=\ell(\lambda)$ if $\pi\in\mathcal{C}_\lambda$, and the sign is
$s(\pi)=(-1)^{n-\ell(\pi)}$. We multiply permutations from right to left, e.g.
$(13)(12)=(123)$.

The quantity $\chi_\lambda(\mu)=\chi_\lambda(\pi)$ is the character of the irreducible
representation of $S_n$ labeled by $\lambda$, calculated for a permutation $\pi\in
\mathcal{C}_\mu$. The value $d_\lambda=\chi_\lambda(1^n)$ is the dimension of said
representation. Characters satisfy the orthogonality relation \be \sum_{\tau\in
S_n}\chi_\mu(\tau) \chi_\lambda(\tau\sigma)=
\delta_{\mu,\lambda}n!\frac{\chi_\lambda(\sigma)}{d_\lambda}.\ee

The group $S_{2n}$ has a subgroup called the hyperoctahedral, $H_n$, with $|H_n|=2^nn!$
elements, which is the stabilizer of the permutation $(12)(34)\cdots (2n-1\; 2n)$. The
coset $S_{2n}/H_n=\M_n$ can be represented by permutations called matchings: $\sigma\in
\M_n$ if and only if $\sigma(2i-1)<\sigma(2i)$ and $\sigma(2i-1)<\sigma(2i+1)$.

Given a permutation $\tau\in S_{2n}$, let $\mathcal{G}_\tau$ be a graph with vertices
labeled from $1$ to $2n$ and edges of the forms $\{2i-1,2i\}$ and
$\{\tau(2i-1),\tau(2i)\}$, $1\leq i\leq n$. Since each vertex belongs to one edge of each
form, all connected components of $\mathcal{G}_\tau$ are cycles of even length. The coset
type of $\tau$ is the partition of $n$ whose parts are half the number of edges in the
connected components of $\mathcal{G}_\tau$.

Two permutations $\tau,\sigma$ in $S_{2n}$
have the same coset type if and only if they belong to the same double coset, i.e. if
$\tau=h_1\sigma h_2$ with $h_1,h_2,\in H_n$. We denote by $[\tau]$ the coset type of
$\tau$. We may denote by $H_\tau$ the double coset of $\tau$. Its order is \be |H_\tau|=\frac{4^nn!|\mathcal{C}_{[\tau]}|}{2^{\ell([\tau])}}.\ee

Introduce a map from $S_n$ to $S_{2n}$, taking a permutation
$\pi\in\mathcal{C}_\lambda$ into another permutation
$\widetilde{\pi}\in\mathcal{C}_{2\lambda}$. This map is such that the image of the cycle
$(i_1,i_2,\cdots, i_r)$ in $\pi$ is the cycle $(2i_1-1,2i_1,2i_2-1,2i_2,\cdots,
2i_r-1,2i_r)$ in $\widetilde{\pi}$. This map is useful because the coset type of
$\widetilde{\pi}$ is $\lambda$.

The average \be \omega_\lambda(\tau)=\frac{1}{|H_n|}\sum_{\xi \in
H_n}\chi_{2\lambda}(\tau\xi)\ee is called a zonal spherical function. It is obviously
invariant under (left and right) action of $H_n$ and hence depends only on the coset type
of its argument. These functions satisfy \be\label{omegas} \sum_{\tau\in
\M_{n}}\omega_\lambda(\tau)\omega_\mu(\tau^{-1}\sigma)=\delta_{\lambda,\mu}
\frac{(2n)!}{2^nn!}\frac{\omega_\lambda(\sigma)}{d_{2\lambda}},\ee and also \be
\sum_{\lambda\vdash
n}d_{2\lambda}\omega_\lambda(\sigma)\omega_\lambda(\tau)=\frac{(2n)!}{|H_\tau|}\delta_{[\sigma],[\tau]}.\ee

The average \be \psi_\lambda(\tau)=\frac{1}{|H_n|}\sum_{\xi \in
H_n}\chi_{\lambda\cup\lambda}(\tau\xi)s(\xi),\ee where $s(\xi)$ is the sign of $\xi$, is
called a twisted zonal spherical function. Under action by $H_n$ it is invariant up to
sign: $\psi_\lambda(\tau\xi)=s(\xi)\psi_\lambda(\tau)$. These functions satisfy \be
\sum_{\tau\in \M_{n}}\psi_\lambda(\tau)\psi_\mu(\tau^{-1}\sigma)=\delta_{\lambda,\mu}
\frac{(2n)!}{2^nn!}\frac{\psi_\lambda(\sigma)}{d_{\lambda\cup\lambda}},\ee and also \be
\sum_{\lambda\vdash
n}d_{\lambda\cup\lambda}\psi_\lambda(\sigma)\psi_\lambda(\tau)=\frac{(2n)!}{|H_\sigma|}s(\sigma)s(\tau)\delta_{[\sigma],[\tau]}.\ee

\subsection{Power sum symmetric functions}

Power sum symmetric functions of matrix argument are given by \be
p_\lambda(X)=\prod_{i=1}^{\ell(\lambda)} p_{\lambda_i}(X),\ee with $p_m(X)={\rm
Tr}(X^m)$. They are clearly symmetric functions of the eigenvalues of $X$. If $X$ has
dimension $N$ and $\pi\in S_n$ has cycle type $\lambda$, then\be
p_{\pi}(X)=p_\lambda(X)=\sum_{i_1,...,i_n=1}^N\prod_{k=1}^nX_{i_ki_{\pi(k)}}.\ee

Power sums are produced from some summations. Let $\delta_{ab}$ denote the usual
Kronecker delta function. Given $j=(j_1,j_2,...j_n)$ and $m=(m_1,m_2,...,m_n)$, define
the function \be \delta_\tau[j,m]=\prod_{k=1}^n\delta_{j_km_{\tau(k)}},\ee for any
$\tau\in S_n$. Then we have \be\label{power1} \sum_{j_1\cdots j_n=1}^N\sum_{m_1\cdots
m_n=1}^N \delta_\tau[j,m]\delta_\sigma[j,m]\prod_{k=1}^n
y_{j_k}y_{m_k}=p_{\tau^{-1}\sigma}(x),\ee where \be\label{x2y} x_i=y_i^2,\quad 1\leq
i\leq N.\ee

Let $e(j)$ be the vector with elements given by $(e(j))_i=\delta_{ij}$. With the
definitions from Section 2.1 we have \be \{ e(j_1),e(j_2)\}=\delta_{j_1,j_2},\quad
\llangle e(j_1),e(j_2)\rrangle=\delta_{j_1+N,j_2}-\delta_{j_1,j_2+N}.\ee For any
$\tau\in S_{2n}$, define \be\label{Del}
\Delta_\tau[j]=\prod_{k=1}^n\{e(j_{\tau(2k-1)}),e(j_{\tau(2k)})\},\ee and
\be\label{Delprime} \Delta'_\tau[j]=\prod_{k=1}^n \llangle
e(j_{\tau(2k-1)}),e(j_{\tau(2k)})\rrangle. \ee Notice that the behavior of these
functions under action of the hyperoctahedral group is $\Delta_{\tau\xi}=\Delta_\tau$ and
$\Delta'_{\tau\xi}=s(\xi)\Delta'_\tau$. The summations that produce power sums are
\be\label{power2} \sum_{j_1\cdots j_{2n}=1}^N
\Delta_{\tau}[j]\Delta_{\sigma}[j]\prod_{k=1}^{2n} y_{j_k}=p_{[\tau^{-1}\sigma]}(x),\ee
and \be\label{power3} \sum_{j_1\cdots j_{2n}=1}^{2N}
\Delta'_{\tau}[j]\Delta'_{\sigma}[j]\prod_{k=1}^{2n}
y_{j_k}=(-1)^ns(\tau)s(\sigma)(-2)^{\ell([\tau^{-1}\sigma])}p_{[\tau^{-1}\sigma]}(x),\ee where $[\tau]$ is the coset
type of $\tau$, while the variables satisfy $y_{i+N}=y_i$ and (\ref{x2y}).

\subsection{Jack polynomials}

Power sums and Schur functions are related by \be s_\lambda(X)=\sum_{\pi\in
S_n}\chi_\lambda(\pi)p_\pi(X)=\sum_{\mu\vdash
n}|\mathcal{C}_\mu|\chi_\lambda(\mu)p_\mu(X), \ee and \be p_\lambda(X)=\sum_{\mu\vdash
n}\chi_\mu(\lambda)s_\mu(X).\ee Schur functions are generalized by Jack polynomials,
$J_\lambda^{(\alpha)}(x)$, which depend on the parameter $\alpha$. They are recovered when
$\alpha=1$: \be J_\lambda^{(1)}(x)=\frac{n!}{d_\lambda}s_\lambda(x).\ee The polynomials
$J_\lambda^{(2)}$ and $J_\lambda^{(1/2)}$ are called zonal polynomials and quaternion
zonal polynomials, respectively. The former are related to power sums according to
\be\label{JtopO} J_\lambda^{(2)}(X)=\sum_{\mu\vdash n}
|\mathcal{C}_\mu|2^{n-\ell(\mu)}\omega_\lambda(\mu)p_\mu(X),\ee and \be
p_{[\tau]}(x)=\frac{2^nn!}{(2n)!}\sum_{\lambda\vdash n}d_{2\lambda}
\omega_\lambda(\tau)J_\lambda^{(2)}(x).\ee For the latter, the first relation is
\be\label{JtopS} J_\lambda^{(1/2)}(X)=(-1)^{n}\sum_{\mu\vdash
n}|\mathcal{C}_\mu|\psi_\lambda(\widetilde{\pi})p_\mu(X),\ee where $\pi$ is any
permutation of cycle type $\mu$ and $\widetilde{\pi}$ is its image under the map
introduced in Section 2.2. The second relation is \be p_{[\tau]}(x)=\frac{(-4)^nn!}{(2n)!}
\left(\frac{-1}{2}\right)^{\ell([\tau])}\sum_{\lambda\vdash n}d_{\lambda\cup\lambda}
s(\tau)\psi_\lambda(\tau)J_\lambda^{(1/2)}(x),\ee valid for any $\tau\in S_{2n}$.

The value of the Jack polynomial when all arguments are equal to $1$ is given by
\be\label{J1N} J_\lambda^{(\alpha)}(1^N)=\alpha^n\prod_{j=1}^{\ell(\lambda)}
\frac{\Gamma(\lambda_j+(N-j+1)/\alpha)}{\Gamma((N-j+1)/\alpha)}.\ee

Jack polynomials arise from integrals of Schur functions over Lie groups. Let $dU$, $dO$
and $dS$ denote the normalized Haar measures over $\mathcal{U}(N)$, $\mathcal{O}(N)$ and
$Sp(2N)$, respectively. The orthogonality relation \be\label{orthog} \int_{\mathcal{U}(N)}
dU s_\lambda(A^\dag U)s_\mu(BU^\dag)=\delta_{\mu,\lambda}\frac{J^{(1)}_\lambda(A^\dag
B)}{J^{(1)}_\lambda(1^N)}\ee  holds because Schur functions are actually irreducible
characters of the unitary group. We also have the relations \be\label{relO}
\int_{\mathcal{O}(N)}dO s_\mu(AO)=\delta_{\mu,2\lambda}\frac{J^{(2)}_\lambda(A^T
A)}{J^{(2)}_\lambda(1^N)},\ee and \be\label{averageS}\int_{Sp(2N)}dS
s_\mu(AS)=\delta_{\mu,\lambda\cup\lambda}2^{-\ell(\lambda)}\frac{J^{(1/2)}_\lambda(A^DA)}{J^{(1/2)}_\lambda(1^N)}.\ee
In the last equation $A$ and $S$ are $2N\times 2N$ complex matrices. All the above integrals vanish
unless $\ell(\lambda)\leq N$.

\section{Derivation}

\subsection{Unitary Group}

We start from the basic identity \be \prod_{k=1}^n
U_{a_kb_k}=\frac{1}{n!}\prod_{k=1}^n\frac{\partial }{\partial A^*_{a_kb_k}}
p_{1^n}(A^\dag U),\ee which can be easily verified. We express power sums in terms of
Schur functions, use (\ref{orthog}) to perform the group integral, and then revert back
to power sums to get \be \int_{\mathcal{U}(N)} dU \prod_{k=1}^n
U_{a_kb_k}U^*_{d_kc_k}=\frac{1}{n!^2}\sum_{\substack{\lambda\vdash n\\\ell(\lambda)\leq
N}} \frac{d_\lambda}{J^{(1)}_\lambda(1^N)}\sum_{\pi \in
S_n}\chi_\lambda(\pi)\prod_{k=1}^n\frac{\partial }{\partial A^*_{a_kb_k}}\frac{\partial
}{\partial B_{m_kr_k}}p_{\pi}(A^\dag B).\ee In order to take the derivative, we expand
$p_\pi$ as a trace, \be p_{\pi}(A^\dag
B)=\sum_{i_1,...,i_n=1}^N\sum_{j_1,...,j_n=1}^NA^\dag_{i_kj_k}B_{j_ki_{\pi(k)}}.\ee
Taking the derivative and summing over the $i$'s and $j$'s produces \be
\sum_{\theta,\rho\in
S_n}\prod_{k=1}^n\delta_{a_k,d_{\rho\theta^{-1}(k)}}\delta_{b_k,c_{\rho\pi^{-1}\theta^{-1}(k)}}.\ee

Finally, we change variables as $\rho=\sigma\theta$ and then $\tau=\sigma\theta
\pi^{-1}\theta^{-1}$. This last change preserves cycle type, so that
$\chi_\lambda(\pi)=\chi_\lambda(\sigma^{-1}\tau)=\chi_\lambda(\tau^{-1}\sigma)$. The sum
over $\pi$ is then just $n!$, and we arrive at \be  \int_{\mathcal{U}(N)} dU
\prod_{k=1}^n U_{a_kb_k}U^*_{d_kc_k}=\sum_{\sigma\tau \in S_n}{\rm
Wg}^U(\tau^{-1}\sigma)\delta_\sigma[ad]\delta_\tau[bc],\ee where \be {\rm
Wg}^U(\tau^{-1}\sigma)=\frac{1}{n!}\sum_{\substack{\lambda\vdash n\\\ell(\lambda)\leq N}}
\frac{d_\lambda}{J^{(1)}_\lambda(1^N)}\chi_\lambda(\tau^{-1}\sigma),\ee is the unitary
Weingarten function.

\subsection{Orthogonal Group}

In the same spirit, we start by writing \be \prod_{k=1}^{2n}
O_{a_kb_k}=\frac{1}{(2n)!}\prod_{k=1}^{2n}\frac{\partial }{\partial A_{a_kb_k}}
p_{1^{2n}}(A^T O).\ee Changing to Schur functions and using (\ref{relO}) we get
\be\frac{1}{(2n)!}\sum_{\substack{\lambda\vdash n\\\ell(\lambda)\leq N}}
\frac{d_{2\lambda}}{J^{(2)}_\lambda(1^N)}\prod_{k=1}^{2n}\frac{\partial }{\partial
A_{a_kb_k}}J^{(2)}_\lambda(A^T A).\ee We return to power sums in order to take the
derivative. Taking $\pi\in S_n$ to be any permutation with cycle type $\mu$, we write \be
\int_{\mathcal{O}(N)} dO\prod_{k=1}^{2n}
O_{a_kb_k}=\frac{1}{(2n)!}\sum_{\substack{\lambda\vdash n\\\ell(\lambda)\leq N}}
\frac{d_{2\lambda}}{J^{(2)}_\lambda(1^N)}\sum_{\mu\vdash
n}|\mathcal{C}_\mu|2^{n-\ell(\mu)}\omega_\lambda(\mu)\prod_{k=1}^{2n}\frac{\partial
}{\partial A_{a_kb_k}}p_\pi(A^T A).\ee

The derivative \be \prod_{k=1}^{2n}\frac{\partial }{\partial A_{a_kb_k}}p_\pi(A^TA)=
\sum_{i_1,...,i_n=1}^N\sum_{j_1,...,j_n=1}^N\prod_{r=1}^{n}\frac{\partial }{\partial
A_{a_{(2r-1)}b_{(2r-1)}}}\frac{\partial }{\partial
A_{a_{(2r)}b_{(2r)}}}A^T_{i_{r}j_{r}}A_{j_{r}i_{\pi(r)}},\ee will, upon summing over the
$i$'s and $j$'s, always lead to a matching among the $a$'s and a matching among the
$b$'s, i.e. something like $\Delta_\tau[a]\Delta_\sigma[b]$. By construction, these
matchings will satisfy $[\tau^{-1}\sigma]=\mu$, and each such pair will appear exactly
$2^{\ell(\mu)}n!/|\mathcal{C}_\mu|$ times for any $\pi$. Hence, we can write
\be\int_{\mathcal{O}(N)} dO\prod_{k=1}^{2n} O_{a_kb_k}=\sum_{\tau,\sigma\in \M_n}{\rm
Wg}^O(\tau^{-1}\sigma)\Delta_\tau(a)\Delta_\sigma(b),\ee where \be {\rm
Wg}^O(\tau^{-1}\sigma)=\frac{2^nn!}{(2n)!}\sum_{\substack{\lambda\vdash
n\\\ell(\lambda)\leq N}}
\frac{d_{2\lambda}}{J^{(2)}_\lambda(1^N)}\omega_\lambda(\tau^{-1}\sigma)\ee is the
Weingarten function of $\mathcal{O}(N)$.

\subsection{Symplectic Group}

Let $\pi\in S_n$ be any permutation of cycle type $\mu$ and $\widetilde{\pi}$ be its
image under the map in Section 2.2, so that $[\widetilde{\pi}]=\mu$. Calculations
analogous to those in the previous section lead to \be\int_{Sp(2N)} dS\prod_{k=1}^{2n}
S_{a_kb_k}=\frac{(-1)^n}{(2n)!}\sum_{\substack{\lambda\vdash n\\\ell(\lambda)\leq N}}
\frac{d_{\lambda\cup\lambda}}{J^{(1/2)}_\lambda(1^N)}\sum_{\mu\vdash
n}|\mathcal{C}_\mu|2^{-\ell(\mu)}\psi_\lambda(\widetilde{\pi})\prod_{k=1}^{2n}\frac{\partial
}{\partial A_{a_kb_k}}p_\pi(A^D A),\ee where we have used (\ref{JtopS}) and
(\ref{averageS}). The derivative $\prod_{k=1}^{2n}\frac{\partial }{\partial
A_{a_kb_k}}p_\pi(A^DA)$ leads to a matching among the $a$'s and a matching among the
$b$'s, but with such minus signs as to produce  $(-1)^n\Delta'_\tau[a]\Delta'_\sigma[b]$.
Again, these matchings satisfy $[\tau^{-1}\sigma]=\mu$, and each such pair appears
$2^{\ell(\mu)}n!/|\mathcal{C}_\mu|$ times for any $\pi$. Therefore, \be \int_{Sp(2N)}
dS\prod_{k=1}^{2n} S_{a_kb_k}=\sum_{\tau,\sigma\in \M_n}{\rm
Wg}^{Sp}(\tau^{-1}\sigma)\Delta'_\tau[a]\Delta'_\sigma[b],\ee where \be {\rm
Wg}^{Sp}(\tau^{-1}\sigma)=\frac{n!}{(2n)!}\sum_{\substack{\lambda\vdash
n\\\ell(\lambda)\leq N}}
\frac{d_{\lambda\cup\lambda}}{J^{(1/2)}_\lambda(1^N)}\psi_\lambda(\tau^{-1}\sigma)\ee is
the Weingarten function of $Sp(2N)$.

\section*{Acknowledgments} Financial support from CNPq is gratefully acknowledged, as well as from grant 2012/00699-1, S˜\~ao Paulo
Research Foundation (FAPESP).


TITLE: Question about spectral theorem for compact operators
QUESTION [0 upvotes]: Consider the following fragment:

Questions:
(1) Does every non-zero eigenvalue occur in the $\{\lambda_i: i =1, 2, \dots\}$?
(2) Why if $\lambda \ne 0$ is the eigenspace of $\lambda$ finite dimensional? I can see this must be the case if $(1)$ is true.

REPLY [0 votes]: (1) this is the statement of the spectral theorem. Assume one eigenvalue $\tilde \lambda$ is missing in the enumeration in the theorem. Then the associated eigenvector $\tilde v$ is orthogonal to all the other eigenvectors that are used in the spectral theorem. This implies
$\tilde v \in \ker T^{\perp\perp}=\ker T$. Hence $\tilde \lambda=0$, contradiction.


TITLE: Not understanding velocity addition (or substraction maybe) in special relativity
QUESTION [0 upvotes]: Suppose there is a train that has a velocity of $v=0.6c$. It travels $L_0$ distance in $T_0$ time. They are measured by a person sitting on a bench beside the track. So from train's perspective distance should be $L=L_0 (1-v^2/c^2)$ and time should be $T=T_0/(1-v^2/c^2)$ so should't a passenger think the train is moving with velocity, $V=L/T$ where $V<V_0$. Can you please explain this from Einstein velocity addition perspective?

REPLY [1 votes]: Suppose train's and track's clocks are set to zero when the first wagon passes by the bench. The clocks of the wagons are syncronized in the train's frame.
In the time $T_0$, according to the bench clock, the clock in the wagon, that is now passing by, is:
$$T = T_0\frac{1} {\sqrt{1-\frac{v^2}{c^2}}}$$
As the train has velocity $v$, the length from the first wagon to this one is $L_0 = vT_0$ for the bench frame.
The same distance to the first wagon, measured by the train is greater, because it is measured at its own frame. And the formula for length contraction is from the stationary to the moving frame, in this case from the train to the track:
$$L_0 = L \sqrt{1-\frac{v^2}{c^2}}$$
So, the velocities are $v$ for both frames.


TITLE: Expected weight of biochromatic/monochromatic edges
QUESTION [0 upvotes]: Let $G= (V,E)$ be an undirected graph with real-valued edge weights.  Let $W$ denote the total sum of edge weights. Suppose we color all of the vertices either red or blue, independently at random.  We say that an edge is ”bichromatic” if its endpoints have two colors,  and ”monochromatic” if both its endpoints have the same color. We say that an edge is ”monochromatically red” if both endpoints are red
$a)$  What is the expected total weight of bichromatic edges (as a function of $W$?
$b)$  What is the expected total weight of monochromatically red edges?
$c)$ What is the expected total weight of monochromatically blue edges?
$d)$  What is the expected total weight of monochromatic edges?
I can't figure out this question.
I tried taking the graph as square and tried taking cases as follows:

When all are red/blue - weight fo bio is zero
When one is red and all others are blue(the same when one is blue and other are red) - we have two biochromatic weights
When there are two blue and two red: We can have two different cases where we have "two"( when the same color is one edge) or four(alternate red-blue).

That gives a total of 10 total biochromatic edges and we know that total weight of the graph is $W$, but how can I possibly relate this to W if I don't know the individual weights of the edges?

REPLY [1 votes]: All you need is linearity of expectation. Each edge has four equiprobable possibilities: monochromatic red, monochromatic blue, and two versions of bichromatic, so it contributes $\frac14$ of its weight to each of those cases. Thus the expected weight of monochromatic red edges is $\frac W4$, the same for monochromatic blue, and the expected weight of bichromatic edges is $\frac W2$ (and the same for monochromatic red and blue together).


TITLE: Prove $f_x(0,0) , f_y(0,0)$ exist
QUESTION [1 upvotes]: Let $f(x,y)= (xy)^{1/3}$
Using definition of the partial derivatives, prove $f_x(0,0), f_y(0,0)$ both exist.
Show that the directional derivative for $f$ in any direction other than $i$ or $j$ does not exist at the origin.

REPLY [0 votes]: I assume that for $t\in{\mathbb R}$ the expression $t^{1/3}$ is defined as $\ {\rm sgn}(t)\>|t|^{1/3}$.
It follows that $${f(x,0)-f(0,0)\over x}=0\qquad(x\ne0)\ ,$$
which implies $f_x(0,0)=0$; and similarly $f_y(0,0)=0$.
Let $u:=(\cos\phi,\sin\phi)$ be a fixed unit vector. Then by definition the directional derivative of $f$ at $(0,0)$ in direction $u$ is given by
$$\eqalign{D_uf(0,0)&=\lim_{t\to 0+}{f(t\cos\phi,t\sin\phi)-f(0,0)\over t}=
\lim_{t\to 0+}{t^{2/3}|\cos\phi\>\sin\phi|^{1/3}\over t}\cr &=\lim_{t\to 0+}{|\cos\phi\>\sin\phi|^{1/3}\over t^{1/3}}\ ,\cr}$$
if the limit on the right hand side exists. But when $\phi$ is not an integer multiple of ${\pi/2}$ this limit does not exist.


TITLE: Is there a way to find solution if all variables cancel out?
QUESTION [1 upvotes]: Factory A produces: 12 Tables and 6 Chairs per hour
Factory B produces:  8 Tables and 4 Chairs per hour

How hours does EACH factory need to work to produce 48 Tables and 24 Chairs?
The linear equations are:
$$12A+8B=48$$
$$6A+4B=24$$
The first equation is twice the second, so everything cancels out.
But with trial and error, you find 3 solution:

A=0 and B=6
A=2 and B=3
A=4 and B=0

What does it mean when variables cancel out or when all of them are zeroes?

REPLY [0 votes]: If both factories work together, in 1 hour they produce 20 tables and 10 chairs. Thus, it will require 2 hours and 24 minutes to produce required number of tables and chairs. ($20x=48, x=2.4$ hours, $10x=24, x=2.4$). I agree that the problem is ambiguous.


TITLE: What are the non-trivial solutions of this system?
QUESTION [0 upvotes]: Let $a, b, c \in R$. How could I show that the homogeneous system of linear equations has only the trivial solution $\left(\begin{array}{c}0\\0\\0\end{array}\right)$?
\begin{align}
(a^2 + 1)x_1 + (ab)x_2 + (ac)x_3 = 0\\
(ab)x_1 + (b^2 + 1)x_2 + (bc)x_3 = 0\\
(ac)x_1 + (bc)x_2 + (c^2 + 1)x_3= 0
\end{align}

REPLY [0 votes]: As user 1551 writes, rewriting as $({\bf I}+{\bf vv}^T)$ is useful. Then you can just use knowledge of how a rank 1 perturbation affects the eigensystem. In this case adding 1 to the eigenvalue in the direction of $\hat{\bf v}$. So the eigenvalues will be all 1 except in the $\bf \hat{v}$ direction which would be 2. Since no eigenvalue is 0, the null space is empty and the only solution could be the zero vector.


TITLE: FOL to English translation questions.
QUESTION [0 upvotes]: I am trying to translate the following FOL Tarski's World Block language to English sentence, and some of the sentences seems quite complicated. I will really appreciate it if anyone can help verify that my attempted solutions are correct.
Question 1: $\exists x [Dodec(x) \wedge \neg \exists y (Cube(y) \wedge BackOf(y, x))]$
First, I change the above to:  $\exists x [Dodec(x) \wedge \forall y \neg(Cube(y) \wedge BackOf(y, x))]$ I then translate this to:
"There exists some dodecahedron such that no cubes are to the back of it". I am not sure if this sentence correctly describes $\forall y \neg(Cube(y) \wedge BackOf(y, x))$, because if I try to distribute the negation into the parenthesis, then it becomes: $\forall y (\neg Cube(y) \vee \neg BackOf(y, x))$ which I think the translate changes to: "There exists some dodecahedron such that there are either no cubes at all or $x$ is not to the back of $y$". I think it sounds a little weird.
I am uncertain if any of these translations make sense based on the given FOL.
Question 2: $\forall x((Cube(x) \wedge \exists y BackOf(y,x)) \rightarrow Small(x))$
Translates to: "For every cube where some object $y$ is behind it, then all the cubes are small"
I am confused with the meaning of the antecedent $\forall x((Cube(x) \wedge \exists y BackOf(y,x))$, does this mean that if we arrange the objects, then each individual cube must have some $y$ behind it, or does it mean that there must be some $y$ that is/are behind all cubes, for example if we arrange 2 cubes and 2 $y$'s from left(front of) to right(back of):
1) Cube > $y$ > Cube >> $y$ Or:
2) Cube > Cube > $y$ > $y$, if this is true then shouldn't it be: "For all cube where some object $y$ is behind all of the cubes, then all the cubes are small"
Question 3: $\forall x ((Dodec(x) \wedge \exists y (Cube(y) \wedge LeftOf(x, y)) \rightarrow Large(x))$ translates to:
"If every dodecahedron is to the left of some cube, then all dodecahedrons are large."
Question 4: $\forall x(Tet(x) \rightarrow (\forall y( Cube(y) \rightarrow FrontOf(x, y)))$ Translates to:
"All tetrahedrons are in front of all cubes"
Question 5: $\neg \exists x(Dodec(x) \wedge \exists y BackOf(y, x))$
I changed the above to: $\forall x \neg (Dodec(x) \wedge \exists y BackOf(y, x))$ then this translates to:
"No dodecahedrons are to the back of some object $y$" Or
"Either there are no dodecahedrons or no $y$'s are in the back of any dodecahedrons"
Sorry my post is a bit long, and thank you for taking the time to read this post.

REPLY [2 votes]: Your first translation is fine ... and much more natural than the second one!
No.  It is that any cube with some object behind it is small.  Your translation is the translation of the following FOL sentence:

$\forall x(Cube(x) \wedge \exists y BackOf(y,x)) \rightarrow \forall x \ Small(x))$
Do you see the difference?

You make the same mistake as with 2.  Now that you know what 2 translates to, can you try 3 again?
Correct.  You could also say: Any tetrahedron is in front of any cube
Look closely at the arguments of the $BackOf$ predicate: which object is in the back of which object?


TITLE: Fourier Analysis of a Time Series
QUESTION [1 upvotes]: The picture below displays experimental data on concentration oscillations in a chemical reaction. I would like to find frequency characteristics of the series.
More specifically, assuming that the signal is presented in the form
$$F(t)=F_{trend}(t)+\sum_{j} f_j e^{-i\omega_j t},\qquad 0\leq t \leq T,$$
how does one compute the frequencies $\omega_1<\omega_2<\omega_3<...$?

REPLY [1 votes]: Compute the Fourier Transform of $F(t) -F^{trend}(t)$ and then take the logarithm of the squared modulus and plot the result. You should see a maximum that will be the fundamental. Use the FFT. Say you have 1500 data points in the time series. Use an FFT of at least 2048 to 4096 points. Zero fill the rest of the points. This will have the benign effect of making the power spectrum smoother. The Niquist frequency will be $N_f = \frac{1}{2 \Delta x}$, where $\Delta x$ is the sampling interval. The Niquist frequency is the maximum recoverable frequency, without aliasing, from evenly sampled data.
To convert to angular frequency, multiply by $2 \pi$. The linear frequency interval is just $\Delta \epsilon_j= 2 N_f / N$, where $N$ is the size of the FFT. The angular frequencies are
$ \omega_j = 2\pi \Delta \epsilon_j = \frac{\pi}{\Delta x N}(N/2 - j), j = 0,1,...,N-1.$
The goto book is still "The Fast Fourier Transform" by E. O. Brigham.
 I hope this helps.


TITLE: Examples of algebra, σ-algebra, and neither
QUESTION [0 upvotes]: I've read multiple explanations of the differences between algebras and σ-algebras, but I'm struggling to understand how something with that deals with things that are "countably infinite" (σ-algebras) can be a subset of something that deals with finite things (algebras).  If σ-algebras are subsets of algebra and not all collections are algebras, there should be three relevant classes:

Neither algebra nor σ-algebra
Algebra but not σ-algebra
Both algebra and σ-algebra

Can someone list out three similar collections with slight differences and explain how the differences determine which category that each is in?  Specifically, what is the requirement for a collection to be a σ-algebra that is not present in other algebras?
I'm aware that all algebras must include $\{\emptyset, \Omega\}$ and that each $A$ must have an $A^c$.

REPLY [1 votes]: So, rather than give three examples out of the blue, I'm going to start with a non-algebra and add sets to the collection until we get a $\sigma$-algebra.
Let's start with the collection
$$\{(a,b]\mid a< b \in\mathbb{R}\cup\{\pm\infty\}\}$$
Of half-closed (not necessarily finite) intervals. This is not an algebra, nor a $\sigma$-algebra, as it is not closed under taking any unions or complements.
We we consider the collection of finite unions of such sets, we get an algebra - it is closed under finite unions by definition, and
$$(a,b]^c =(-\infty,a]\cup(b,\infty]$$
so it is closed under complements.
But it is not closed under countable unions:
$$\cup_{n\geq 2} (0,1-\frac{1}{n}] = (0,1)$$
is not in the collection. So in order to complete the to a $\sigma$ algebra, we also need to include all open and (to preserve complements) closed intervals of the real line too.
Hopefully that helps. As for why $\sigma$-algebras are a subset of algebras: every $\sigma$-algebra is closed under countable unions, and hence closed under finite unions. Hence every $\sigma$-algebra is an algebra.


TITLE: Numerical Calculation of Eigenvalues of a large real Symmetric tridiagonal matrix
QUESTION [5 upvotes]: If I have an $N \times N$ matrix where every entry is zero except for along the super-diagonal and sub-diagonal, where the each entry is the conjugate of the last, like the following $5 \times 5$ matrix
$$\begin{bmatrix}0 & (1-t) & 0 & 0 & 0 \\(1-t) & 0 & (1+t) & 0 & 0 \\0 & (1+t) & 0 & (1-t) & 0 \\0 & 0 & (1-t) & 0 & (1+t)\\0 & 0 & 0 & (1+t) & 0 \end{bmatrix}$$
where $t$ is some parameter. Imagine a much larger matrix following the same pattern.
Is there any way, numerical or otherwise to find the eigenvalues?

REPLY [1 votes]: This is not a full solution, but may give you some clues:
The trace of this matrix is zero, so the sum of eigenvalues should be zero. In fact for every odd power of the matrix the trace is zero.
If you multiply the matrix by itself the trace of new matrix is no longer zero, so the sum of eigenvalues of the squared matrix is not zero. In fact, again, every even power has non-zero trace, which leads me to believe that the eigenvalues will consist of non-zero pairs $\lambda, -\lambda$ and $0$ (maybe repeated values of $0$ for even order matrix, not sure).
So indeed, for the $5 \times 5$ matrix you have there, if I just use Mathematica to get the eigenvalues: $\left\{0,-\sqrt{t^2+3},\sqrt{t^2+3},-\sqrt{3 t^2+1},\sqrt{3 t^2+1}\right\}$. Maybe if you try with different orders of matrices you will be able to develop some formula in terms of $n$, where $n$ is the order of the matrix.


TITLE: How to integrate $x\sin(1+2x)$
QUESTION [2 upvotes]: Can someone be kind enough to show me the steps to integrate this, I'm sure it's by parts but how do I split up the sin part?
$$x\sin(1+2x)$$

REPLY [0 votes]: I would start with an integration by substitution first. So, let $z=1+2x$ and note that this implies $x=\frac{z-1}{2}$, so we obtain the following. $$\frac14\int(z-1)\sin z\operatorname{d}z=\frac14\int z\sin\operatorname{d}z-\frac14\int \sin z\operatorname{d}z$$
Then, integrating $\sin z$ is standard, while $z\sin z$ is a standard easy example of integration by parts (and is probably in your notes!).


TITLE: Show that if $a_n(X_n-X) \overset{\mathcal{D}}\to Z$ then $X_n \overset{P}\to X$.
QUESTION [5 upvotes]: Let $(a_n)\subseteq \Bbb{R}$ be a sequence such that $a_n \to \infty$. Let $(X_n)$ be a sequence of random variables such that $a_n(X_n-X) \overset{\mathcal{D}}\to Z$ fore some random variables $X$ and $Z$.
Show that $X_n \overset{P}\to X$.

So I have some sort of Idea why should this happen. Since $a_n \to \infty$ for $a_n(X_n - X)$ to have a "finite" limit, say $Z$, then $X_n - X \to 0$ somehow. (The excercise says that the convergence must be in probability.) But Im having a lot of trouble in making this ideas more precise. I've tried with characteristic functions for the convergence in distribution. Got to nothing. Any hint?

REPLY [3 votes]: Let $Z_n=a_n(X_n-X)$. We are told that $\frac{1}{a_n}\to 0$ so, in particular, $\frac{1}{a_n}\overset{P}{\to}0$. So by Slutsky's Theorem, $X_n-X=\frac{1}{a_n}\times Z_n\overset{d}{\to}0\times Z=0$. But convergence in distribution to constant is equivalent to convergence in probability to that same constant, so we conclude that $X_n-X\overset{P}{\to}0$.

REPLY [0 votes]: $a_n(X_n-X)\stackrel{\mathcal{D}}{\to}Z$ implies that $\mathbb{P}\left(|Z|<\infty\right)=1$ - $Z$ should be a proper random variable.
If the claim would not hold for some $\varepsilon$, then:
$$
\exists\varepsilon>0: \lim_{n\to\infty}\mathbb{P}\left(|X_n-X|>\varepsilon\right)\neq 0\Rightarrow \limsup_{n}\mathbb{P}\left(|X_n-X|>\varepsilon\right)=\delta(\varepsilon)>0
$$
Thus, $\exists\sigma:\mathbb{N}\to\mathbb{N}: \sigma(i)<\sigma(i+1)$ and
$$
\mathbb{P}\left(|X_{\sigma(i)}-X|>\varepsilon\right)=\delta(\varepsilon)\left(1-\frac{1}{i}\right)
$$
Since $a_n\to\infty$, thus $a_{\sigma(n)}\to\infty$ as well. Choose $\theta:\mathbb{N}\to\mathbb{N}: a_{\theta(\sigma(n))}<a_{\theta(\sigma(n+1))}$ (an inscreasing subsequence of $a_{\sigma(n)}$ - this must exist, as $a_n\to\infty$.
$$
\mathbb{P}\left(|a_{\theta(\sigma(n))}||X_{\theta(\sigma(n))}-X|>|a_{\theta(\sigma(n))}|\varepsilon\right)>\delta(\varepsilon)\left(1-\frac{1}{\theta(n)}\right)\geq \delta(\varepsilon)\left(1-\frac{1}{n}\right)
$$
Since $a_n(X_n-X)$ converges to $Z$ in distribution, so does any subsequence of it. Let $Y_n=a_{\theta(\sigma(n))}(X_{\theta(\sigma(n))}-X)$. Then by the previous claim,
$$
F_{Y_n}(-|a_{\theta(\sigma(n))}|\varepsilon)+1-F_{Y_n}(|a_{\theta(\sigma(n))}|\varepsilon)>\delta(\varepsilon)\left(1-\frac{1}{n}\right)\geq\frac{\delta(\varepsilon)}{2}
$$
Since $a_{n}\to \infty$ and $a_{\theta(\sigma(n))}$ is an increasing sequence, $\forall x\in\mathbb{R}\exists N_x\in\mathbb{N}:\forall n>N_x$
$$
|x|<\varepsilon|a_{\theta(\sigma(n))}|\Rightarrow
$$
$$
\forall n>N_0: F_{Y_n}(-|x|)+1-F_{Y_n}(|x|)\geq \frac{\delta(\varepsilon)}{2}
$$
But as $Z$ is a proper random variable, $\lim_{x\to-\infty}F_Z(x)=0$ and $\lim_{x\to\infty}F_Z(x)=1$, and $F$ is a non-decreasing function, thus:
$$\forall \varepsilon'>0:\exists x(\varepsilon')\in\mathbb{R}: \forall x>|x(\varepsilon')|: F(-x)+1-F(x)<\varepsilon'$$
Now choose $\varepsilon'=\frac{\delta(\varepsilon)}{3}$, thus by the convergence in distribution:
$$
\frac{\delta(\varepsilon)}{2}\leq\lim_{n\to\infty}F_{Y_n}(-|x(\delta(\varepsilon)/3)|)+1-F_{Y_n}(|x(\delta(\varepsilon)/3)|)\leq\frac{\delta(\varepsilon)}{3}
$$
Which is a contradiction.


TITLE: Delta method with uniformly convergent transformation
QUESTION [0 upvotes]: Let's say I have an estimator $T_n$ of $T$ and have established that
$\sqrt{n}(T_n - T) = O_p(1)$ so that $\sqrt{n}(T_n - T)$ converges in distribution to some limit $G$.
Let $f$ be differentiable around $T$. Then by Taylor+Young:
$$
\begin{aligned}
    \sqrt{n}(f(T_n) - f(T)) &= f'(T)\sqrt{n}(T_n - T) + o_p(\sqrt{n}(T_n - T))\\
                            &= f'(T)\sqrt{n}(T_n - T) + o_p(O_P(1))\\
                            &= f'(T)\sqrt{n}(T_n - T) + o_p(1)
\end{aligned}
$$
and therefore $\sqrt{n}(f(T_n) - f(T))$ converges in distribution to $f'(T)G$ by Slutsky's theorem. So far so good.
Now let's say that I in addition consider an estimator $f_n$ of $f$ and have established that $f_n$ converges uniformly to $f$ over the domain of $T$.
That is: $\sup_{t} |f_n(t) - f(t)| = o_P(1)$
Can I then also conclude that $\sqrt{n}(f_n(T_n) - f(T))$ converges to the same limiting distribution $f'(T)G$ as $\sqrt{n}(f(T_n) - f(T))$ does?
I have tried to do the decomposition
$$
    \sqrt{n}(f_n(T_n) - f(t)) = \sqrt{n}(f_n(T_n) - f(T_n)) + \sqrt{n}(f(T_n) - f(T))
$$
where the last term now is the same as before, and the first term should hopefully  converge to zero in probability, but I am confused by the $\sqrt{n}$ factor and if the order is small enough for this to work.
What step am I missing?

REPLY [1 votes]: I will provide a counter-example.
Define $f(z) = z^2$, and $f_n(z) = z^2 +\frac {z}{n^{1/4}}$
Then $|f_n-f| = |\frac {z}{n^{1/4}}|$ and $\lim_{n\rightarrow \infty} \sup_z|\frac {z}{n^{1/4}}| =0$, as long as $z$ is finite. In our case we want to examine $T_n$ as the argument of $f_n$. Since $T_n$ is an estimator that converges, I take it $T_n$ is a finite quantity for any $n$. Although we could conceive of a $T_n$ such that it becomes infinite for some finite range of $n$, it would "be a gamble" to have such an estimator. And in any case, this is a counter example that places bounds on how general the result we        seek can be -it doesn't necessarily rule it out completely. So $f_n$ converges uniformly to $f$.
We examine the expression
$$\sqrt{n}(f_n(T_n) - f(T)) = \sqrt{n}\left(T_n^2 +\frac {T_n}{n^{1/4}} - T^2\right) =  \sqrt{n}\left(T_n^2  - T^2\right) + \sqrt{n}\frac {T_n}{n^{1/4}} $$
$$=\sqrt{n}(f(T_n) - f(T)) + n^{1/4}T_n$$
which diverges.
Intuitively, $f_n$ can contain terms that go to zero and allow for uniform convergence to $f$, but not at a fast enough rate compared to $\sqrt n$. The consequence is that the distance $(f_n(T_n) - f(T))$ becomes asymptotically unbounded when multiplied by $\sqrt n$. So it appears that the rate of convergence of $f_n$ to $f$ is important for the desired result.


TITLE: Turning an observation about triangles into a formal proof
QUESTION [0 upvotes]: I realize that some of this is going to come off as pretentious and I'm sorry if so. I'm just genuinely curious. Recently I've made an observation regarding isosceles triangles.
Take some number $\omega$ and $\triangle ABC$, where $C$ is the top vertex. If $\overleftrightarrow{AC}$ and $\overleftrightarrow{BC}$ both have a length of $\omega \sqrt5$, and $\overleftrightarrow{AB}$ has a length of $2\omega$, then there exists an inscribed square $\square LMNO$ with sides of length $\omega$ where two of the vertices are the midpoints of $\overleftrightarrow{AC}$ and $\overleftrightarrow{BC}$ respectively. Here is an example $\triangle ABC$ to illustrate what I mean.
I don't think this is life-changing or anything, I just think it's really cool and would like some help writing a proof for it.

REPLY [1 votes]: Let us denote the midpoint of $AB$ (which is the origin in your diagram) by $D$.
Define $L, M, N, O$ to be the midpoints of $DA, AC, CB, BD$ respectively. We need to show that $LMNO$ is indeed a square with side length $\omega$.
By midline/midpoint theorem, we have $ML // CD$ and $ML = \frac12CD$.
Similarly $NO // CD$ and $NO = \frac12CD$.
By the properties of an isosceles triangle (or SSS congruence), $AB \perp CD$.
By Pythagoras Theorem, $CD = \sqrt{AC^2 - AD^2} = \sqrt{5\omega^2 - \omega^2} = 2\omega$.
Hence $ML = NO = \omega$ and $ML // NO$. This shows that $LMNO$ is a parallelogram.
Since $LO = 2(\frac12\omega) = \omega = ML = NO$, $LMNO$ is a rhombus.
Since $LM // CD$, $LM \perp AB$. Hence $LMNO$ is a square.


text:
\section{Introduction}
\label{sec:intro}
Distributed implementations of stochastic optimization algorithms have become the standard in large-scale model training \cite{Tensorflow2016,ScaleParameterServer2014,DistributedDual2010,MXNet15,RevisitDML2016,DistBelief12,caffe2,Draco2018,DracoSysML2018}.
Most machine learning frameworks, including Tensorflow \cite{Tensorflow2016}, MxNet \cite{MXNet15}, and Caffe2 \cite{caffe2}, implement variants of mini-batch SGD as their default distributed training algorithm.
During a distributed iteration of mini-batch SGD a {\em parameter server} (PS) stores the global model, and $P$
{\em compute nodes} evaluate a total of $B$ gradients; $B$ is commonly referred to as the {\em batch size}.
Once the PS receives the sum of these $B$ gradients from every compute node, it applies them to the global model and sends the model back to the compute nodes, where a new distributed iteration begins.

The main premise of a distributed implementation is speedup gains, \ie how much faster training takes on $P$ vs $1$ compute node.
In practice, these gains usually saturate beyond a few tens of compute nodes \cite{DistBelief12,paleo17,CeZhang_DecentralizedTraining18}.
This is because communication becomes the bottleneck, \ie for a fixed batch of $B$ examples, as the number of compute nodes increases, these nodes will eventually spend more time communicating gradients to the PS rather than computing them.
To mitigate this bottleneck, a plethora of recent work has studied low-precision training and gradient sparsification, \eg  \cite{qsgd17, terngrad17, deep_gradient_compression17}.

An alternative approach to alleviate these overheads is to increase the batch size $B$, since $B$ directly controls the communication-computation ratio.
Recent work develops sophisticated methods that enable large-batch training on state-of-the-art models and data sets \cite{Goyal_LargeBatchFacebook17,Hoffer_LargeBatchBetter_17,You_LargeBatch32KImageNet_2017}. At the same time, several studies suggest that large-batch training can affect the generalizability of the models~\cite{Keskar_LargeBatchSharpMinima_16}, can slow down convergence \cite{Kakade2017, Misha2017, GradientDiversity2018AISTAT}, and is more sensitive to hyperparameter mis-tuning~\cite{Masters_LargeBatchSensitive_2017}.

Several theoretical results \cite{MiniBatch_OptimalSize2012,Misha2017,MiniBatch_LS2016,GradientDiversity2018AISTAT,Kakade2017,Misha2017} suggest that, when
the batch size $B$ becomes larger than a problem-dependent threshold $B^*$, the total number of iterations to converge significantly increases, rendering the use of larger $B$ a less viable option. Some of these studies, implicitly or explicitly, indicate that the threshold $B^*$ is controlled by the {similarity} of the gradients in the batch.

In particular, \cite{GradientDiversity2018AISTAT} shows that the  measure of {\it gradient diversity} directly controls the relationship of $B$ and the convergence speed of mini-batch SGD. Gradient diversity measures the similarity of concurrently processed gradients, and \cite{GradientDiversity2018AISTAT} shows theoretically and experimentally that the higher the diversity, the more amenable a problem is to fast large-batch training, and by extent to speedup gains in a distributed setting.

A large volume of work has focused on how the structure of neural networks can affect the complexity or capacity \cite{DeepComplexity14,Barron_ANNExpressivePower_91,Lu_ExpressivePower_Wide17} of the model, its representation efficiency \cite{DeepwideSumproduct11}, and its prediction accuracy \cite{DenseNet17,ResNetCVPR16}.
However, there is little work towards understanding how the structure of a neural network affects its amenability to distributed speedup gains.

\begin{wrapfigure}{r}{0.41\columnwidth}
\centering
\includegraphics[width=0.41\textwidth]{Figure/Parallel_Example/graph_intro.pdf}
\vspace{-0.5cm}
	\caption{\small Impact of neural network structure on amenability to large-batch training. This is for fully-connected models with ReLUs on MNIST. For each fully-connected network, we vary the batch size and measure the number of epochs to converge to $96\%$ accuracy. Wider and shallower networks require less epochs to converge than narrower and deeper ones, which suggests that the former are more suitable to scale out to more compute nodes.}\label{fig:Framework}
\end{wrapfigure}
In this work, through analyzing the gradient diversity of different network architectures, we take a step towards addressing the following question:
\begin{quotation}
\textit{How does the structure of a neural network affect its amenability to fast  large-batch training?}
\end{quotation}

\noindent{\bf{Our contribution}}
We establish a theoretical connection between the structure (depth and width)  of neural networks and their gradient diversity, which is an indicator of how large batch size can become, without slowing down the speed of convergence \cite{GradientDiversity2018AISTAT}.
In particular, we prove how gradient diversity varies as a function of width and depth for two types of networks:
2-layer fully-connected linear and non-linear neural networks, and multi-layer fully-connected linear neural networks.
Our theoretical analysis indicates that, perhaps surprisingly, gradient diversity increases monotonically as width increases and depth decreases.
On a high-level, wider networks provide more space for the gradients to become diverse.
This result suggests that wider and shallower networks are more amenable to fast large-batch training compared to deeper ones. Figure \ref{fig:Framework} provides an illustrative example of this phenomenon.

We provide extensive experimental results that support  our theoretical findings.
We present experiments on fully-connected and residual networks on CIFAR10, MNIST, EMNIST, Gisette, and synthetic datasets.
In our experimental setting, we fix the number of network parameters, vary the depth and width, and measure (after tuning the step size) how many passes over the data it takes to reach an accuracy of $\epsilon$ with batch size $B$.
We observe that for all networks there exists a threshold $B^*$, and setting the batch size larger than the threshold leads to slower convergence. The observed threshold $B^*$ becomes smaller when the network becomes deeper, validating our theoretical result that deeper networks are less amenable to fast large-batch training.

The main message of our work is that  communication bottlenecks in distributed mini-batch SGD can be partially overcome not only by designing communication-efficient algorithms, but also by optimizing the architecture of the neural network at hand in order to enable faster large-batch training.


TITLE: Constructing sequence of nested closed sets in separable $T_{3\frac 1 2}$ space
QUESTION [0 upvotes]: Let $X$ be a separable $T_{3\frac 1 2}$ space. In other words, for every closed $A \subset X$ and every $x \in X \setminus A$, there is a continuous function $f : X \to [0,1]$ for which $f(x) = 0$ and $f|_A =1$. In particular, $X$ is regular.
My question: Given a closed $A \subset X$, I want to construct a sequence of open sets $\{B_n\}_{n \geq 1}$, for which $B_1 \supset B_2 \supset B_3 \supset \cdots$, and for which $A = \mathop{\bigcap}_{n \geq 1} B_n$. Is this possible?
What I've tried:
Since $X$ is separable, let $Q = \{q_n\}_{n \geq 1} \subset X \setminus A$ be a countable dense subset; since $X$ is regular, for each $n$, there are open sets $U_n, V_n \subset X$ for which $q_n \in V_n$, $A \subset U_n$, and $U_n \cap V_n = \emptyset$. The first thing I thought to do was take $B_n = \mathop{\bigcap}_{i=1}^n U_i$. Clearly $A \subset \mathop{\bigcap}_{n \geq 1}B_n$, but we don't have equality; it could be that all of the open sets $V_n \ni q_n$ somehow "miss" some points outside of $A$, for example.
So maybe we can find a way to ensure $\{V_n\}_{n \geq 1}$ covers $X \setminus A$. Given $x \in X \setminus A$, denoting $V_x, U_x \subset X$ to be disjoint open sets with $x \in V_x$ and $A \subset U_x$, we clearly have $\{V_x\}_{x \in X \setminus A}$ is an open cover of $X \setminus A$, but separable and $T_{3\frac 1 2}$ does not imply Lindelöf, so we can't extract a countable subcover of $X \setminus A$.
Any suggestions for how to proceed? Or is this statement not true to begin with?

REPLY [1 votes]: That's trivial: $B_n := A$ for each $n$. Or did you perhaps want the $B_n$'s to be open rather than closed? Then this is equivalent for the space to be perfect (i.e., closed sets are $G_\delta$). Then it is false, since there are lots of separable Tychonoff spaces, which are not perfect, for instance the Stone-Cech compactification of the integers.