text:
\subsection{Main Results\label{sec:Main-Results}}

We make the following assumptions throughout the paper.
\begin{enumerate}[label={(A.\arabic*)}]
\item \label{asmp:A1}The elements of $\dmtx$ are drawn from the i.i.d. Gaussian distribution: $\dmtxi_{ij} \iid \mathcal{N}(0,\,\frac{1}{p})$.
\item \label{asmp:Abeta} $\sgl = - \boldsymbol{1}_p$, where $\boldsymbol{1}_p$ denotes the all-ones vector.
\item \label{asmp:A2}The noise is Gaussian: $\noise \sim \mathcal{N}(\boldsymbol{0},\nvarp \mI_n)$.
\item \label{asmp:A3}$\liminf_{p\to\infty}\sampratio > 1/2$ and $\limsup_{p\to\infty}\sampratio/\log p < \infty$.
\item \label{asmp:A4}$\liminf_{p\to\infty}\nsdp^2 \log^2 p > 0$ and $\limsup_{p\to\infty}\nsdp^2 < \infty$.
\end{enumerate}

In \ref{asmp:Abeta}, we assume that each coordinate of true signal is $-1$ to simplify our derivations. All the results still hold for arbitrary $\sgl$, due to the rotational symmetry of $\dmtx$.  In \ref{asmp:A3}, the requirement that $\liminf_{p\to\infty}\sampratio > 1/2$ is related to the fundamental limits of convex relaxation for structural signal reconstruction. In \cite{chandrasekaran2012convex}, it is shown that, if $\limsup_{p\to\infty}\sampratio\leq \frac{1}{2}$, the box-relaxation decoder cannot successfully recover $\sgl$ even in the noiseless case. In \ref{asmp:A4}, we essentially require $\nsdp^2 > c / \log^2 p$ for some $c > 0$. This restriction is due to the limitations of our current proof techniques. We expect that many of our results still hold without this restriction.

To state our main results, we first need to introduce the following potential function:
\begin{equation}\label{eq:F}
F_p(\tau; \nsdp^2, \sampratio) =\frac{\tau}{2}\left(\sampratio-\frac{1}{2}\right)+\frac{\nsdp^{2}}{2\tau}+\frac{\tau}{2}\int_{\frac{2}{\tau}}^{\infty}\left(x-\frac{2}{\tau}\right)^{2}\Phi(dx),
\end{equation}
where $\Phi$ is the CDF of the standard normal distribution. One can verify that $F_p$ is a strictly convex function of $\tau \in (0, \infty)$. (See Appendix~\ref{appen:1Dopt} for details.) Thus, one can uniquely define
\begin{equation}\label{eq:tau}
\optS \bydef \min_{\tau > 0} F_p(\tau; \nsdp^2, \sampratio) \hspace{1em} \text{and} \hspace{1em} \opttau \bydef \argmin{\tau > 0} F_p(\tau; \nsdp^2, \sampratio).
\end{equation}
Another quantity that will be crucial in our analysis is
\begin{equation}\label{eq:lambda}
\optlam \bydef p\Phi(-\tfrac{1}{\opttau}).
\end{equation}

\begin{thm}
\label{thm:PT_limitlaw_Ne}
Under \ref{asmp:A1}-\ref{asmp:A4}, and if $\limsup_{p\to\infty} \tfrac{\optlam}{\sqrt{\log p}} < \infty$, then
\begin{equation}
\label{eq:TV_inf}
d_{\text{TV}}(\neb,\mathscr{P}(\optlam)) \le \frac{\polylog p}{p^{1/5}},
\end{equation}
where $d_{\text{TV}}$ is the total variation (TV) distance and $\mathscr{P}(\lambda)$ denotes a Poisson distribution with parameter $\lambda$.
\end{thm}
\begin{rem}
The theorem, whose proof can be found in \sref{mainthmproof}, characterizes the asymptotic distribution of $\neb$ under certain scaling regimes of $(\sampratio, \nsdp^2)$. It shows that the law of $N_e$ converges to that of a Poisson random variable with parameter $\lambda_p$, if $\optlam$ grows no faster than $\sqrt{\log p}$. This requirement on $\lambda_p$ is not satisfied in the setting studied in \cite{thrampoulidis2016ber} where both $\sampratio$ and $\nsdp^2$ are kept as fixed constants and consequently $\lambda_p = \mathcal{O}(p)$. In that case, one can expect that $\sqrt{p}[\tfrac{\neb}{p}-\Phi(-\tfrac{1}{\opttau})]$ converges to a Gaussian distribution.
\end{rem}

The fact that $N_e$ can have a limiting Poisson law is not surprising. Recall from its definition in \eref{NEB} that $N_e$ is a sum of $p$ Bernoulli random variables $\{\I_{\{\soli_{i}\neq\beta_{i}\}}\}$. Moreover, one can show that $\P(\soli_{i}\neq\beta_{i}) \approx \Phi(-\tfrac{1}{\opttau})$ and that these Bernoulli random variables are close to being independent. Consequently, the law of $N_e$ is approximately a Binomial distribution $\mathcal{B}(p, \Phi(-\tfrac{1}{\opttau}))$ with an expected value equal to $\lambda_p$. As $p \to \infty$ with $\lambda_p = \mathcal{O}(\sqrt{\log p})$, it is well-known that the Binomial distribution converges to a Poisson distribution (\emph{i.e.}, the ``law of small numbers''). The technical contribution of this paper is to make the above arguments precise and rigorous. The main tool we use is the leave-one-out approach (see, \emph{e.g.}, \cite{el2018impact}), also known as the cavity method in statistical physics \cite{luo2001cavity,ramezanali2015cavity}. It allows us to carry out a detailed probabilistic analysis of the random optimization problem in \eref{box_LASSO}.
\begin{figure}
	\centering
	\begin{centering}
\psfrag{$\alpha$}{$\delta$}
\subfloat[$p = 200$\label{fig:Poisson_PMF200}]{\begin{centering}
\includegraphics[scale=0.29]{fig/Poisson_PMF_200}
\par\end{centering}
}\hphantom{}\subfloat[$p = 1000$\label{fig:Poisson_PMF1000}]{\begin{centering}
\includegraphics[scale=0.29]{fig/Poisson_PMF_1000}
\par\end{centering}
}\hphantom{}\subfloat[$p = 10000$\label{fig:Poisson_PMF10000}]{\begin{centering}
\includegraphics[scale=0.29]{fig/Poisson_PMF_10000}
\par\end{centering}
}
\par\end{centering}
\caption{
\label{fig:Poisson_PMF}Comparison of the empirical distribution of $N_e$ and the limiting Poisson distribution, over three different problem dimensions. In the experiments, we set $\nsdp^2 = 1$ and choose $\delta_p$ so that $\lambda_p \approx 1.1$ for all three values of $p$.
}\end{figure}

In our proof of Theorem~\ref{thm:PT_limitlaw_Ne}, we did not attempt to optimize the rate of convergence shown on the right-hand side of \eref{TV_inf}. The actual rate is likely to be faster. In \fref{Poisson_PMF}, we compare the empirical distribution of $N_e$, obtained after averaging over $10^4$ independent trials, against the limiting Poisson distribution for three different problem dimensions. We can see that, even at a moderate dimension of $p = 200$, the Poisson approximation is already accurate.

The characterization given in Theorem~\ref{thm:PT_limitlaw_Ne} allows us to study the conditions under which the box-relaxation decoder can perfectly recover the target signal. Let $\Pc \bydef \P(N_e = 0)$ denotes the probability of perfect recovery. We can show that a phase transition of $\Pc$ emerges when the following quantity
\begin{equation}\label{eq:PTline}
\ptline \bydef \frac{\sampratio-1/2}{2\nsdp^{2}\log p}
\end{equation}
is near $1$.

\begin{prop}
\label{prop:PT}
Under \ref{asmp:A1}-\ref{asmp:A4}, and if $\lim_{p\to\infty} \ptline = \limptline$, then
\begin{equation}
\lim_{p\to\infty}\Pc=\begin{cases}
1, & \text{if }\limptline > 1,\\
0, & \text{if }\limptline < 1.
\end{cases}\label{eq:Ne_transition}
\end{equation}
If $\limptline = 1$, a more refined characterization is available. Specifically, assume that
\begin{equation}\label{eq:alphap_nearPT}
\ptline(x) = 1 - \frac{\log\log p}{2\log p} + \frac{x - \log\sqrt{4\pi} }{\log p},
\end{equation}
for some constant $x\in\R$ (and thus $\ptline(x) \overset{p\to\infty}{\longrightarrow} 1$), then
\begin{equation}
\label{eq:Ne_2ndOrder_transition}
\lim_{p\to\infty}\Pc= e^{-e^{-x}},
\end{equation}
where the right-hand side is the CDF of the Gumbel distribution.
\end{prop}
\begin{rem}
The above proposition, proved in \sref{PT}, characterizes the scaling regimes of $(\sampratio, \nsdp^2)$ over which perfect recovery is achievable. The possible scalings are also flexible. For example, if we keep the sampling ratio $\sampratio$ at a fixed value $\delta > 1/2$, it then follows from \eref{PTline} and \eref{Ne_transition} that $\nsdp^2 = \frac{\delta - 1/2}{2 \log p}$ is the critical noise variance threshold for perfect recovery to happen. Alternatively, if we fix the noise variance $\nsdp^2 \equiv \sigma^2$, then the critical threshold for the sampling ratio is $\sampratio = 1/2 + 2 \sigma^2 \log p$.
\end{rem}

\begin{figure}
\begin{centering}
\psfrag{$\alpha$}{$\delta$}
\subfloat[\label{fig:phasediagram}]{\begin{centering}
\includegraphics[scale=0.38]{fig/phasediagram_100000}
\par\end{centering}
}\hphantom{}\subfloat[\label{fig:1stOrderTransition}]{\begin{centering}
\includegraphics[scale=0.38]{fig/Prr_transition}
\par\end{centering}
}\hphantom{}\subfloat[\label{fig:2ndOrderTransition}]{\begin{centering}
\includegraphics[scale=0.38]{fig/Prr1}
\par\end{centering}
}
\par\end{centering}
\caption{
\label{fig:phasetransitionplot} (a) Phase diagram of the box-relaxation decoder. Each pixel represents
the value of $\Pc$ under a specific $(\sampratio,\protect\nvarp)$. The red curve is
the theoretical transition boundary: $\sigma_p^{2}\log p=\frac{\sampratio-1/2}{2}$.
(b) Phase transition of $\Pc$ with respect to $\ptline$. The dashed line represents
the theoretical threshold. (c) Near the phase transition boundary, $\Pc$ is well-approximated by the Gumbel distribution. In all three experiments, $\Pc$ is estimated by averaging over $10^4$ independent trials. In (b) and (c), we fix $\sampratio=1$ and vary $\alpha_p$ and $x$ by changing $\nsdp^2$.}
\end{figure}

To illustrate Proposition~\ref{prop:PT}, we show some results from
numerical experiments. In \fref{phasediagram}, we plot the
phase diagram of the empirical values of $\Pc$ under different choices of $(\sampratio,\nsdp^2)$, as well as the theoretical
phase transition boundary separating the regimes of perfect/nonperfect
recovery. In \fref{1stOrderTransition}, we plot $\Pc$ as a function of $\ptline$ (by fixing $\sampratio = 1$ and varying $\nsdp^2$). A transition indeed takes place near $\ptline = 1$, and the transition becomes sharper as we increase the problem dimension $p$. When $p$ is not very large, a more accurate approximation of $\Pc$ is given by the Gumbel distribution. This is illustrated in \fref{2ndOrderTransition}, where we zoom in the region near the phase
transition and compare the empirical success probability against the theoretical prediction given in \eref{Ne_2ndOrder_transition}.

\subsection{Related Work}

The precise analysis of high-dimensional signal estimation has already been the subject of a vast literature. Underpinning these rich results are several powerful techniques developed over the years, including the nonrigorous replica method from statistical physics \cite{tanaka2002statistical,kabashima2009typical,zdeborova2016statistical}, approximate message passing (AMP) \cite{bayati2011dynamics,donoho2009message,rangan2019vector}, the cavity method \cite{luo2001cavity,ramezanali2015cavity} and leave-one-out analysis \cite{el2018impact}, Gaussian min-max theorem (GMT) \cite{stojnic2013framework,thrampoulidis2018precise}, as well as the geometric framework based on Gaussian width \cite{chandrasekaran2012convex} and statistical dimensions \cite{amelunxen2014living}.

The box-constrained least square problem in \eref{box_LASSO} has been previously analyzed in \cite{thrampoulidis2016ber,thrampoulidis2018symbol} using GMT techniques. Analysis of similar problems can also be carried out by AMP \cite{jeon2015optimality}. However, these existing studies consider the setting where both the sampling ratio $\sampratio$ and the noise variance $\nsdp^2$ are kept as constants as $p \to \infty$. Under such scalings, one can establish that the empirical measure of $\optx$, defined as $\widehat{\mu}(\optx) \bydef \frac{1}{p}\sum_{i=1}^{p} \delta_{\optxi{i}}$, converges to some deterministic limiting measure. However, the convergence of the empirical measure is insufficient for our purpose: flipping the signs of $o(p)$ entries of $\optx$ will completely change the number of error bits $N_e$, but it has no effect on the limiting empirical measure. In view of this, we choose to use the leave-one-out approach, which allows us to construct a surrogate of $\optx$, denoted by $\opts$, in our analysis. We show that $\|\optx-\opts\|_\infty \to 0$ but the statistical properties of $\opts$ are much easier to obtain. We will elaborate on this point in Sec. \ref{sec:Proof-Sketch}.

Our work considers settings where $(\sampratio, \nsdp^2)$ can scale with the problem dimension $p$. Similar settings with flexible scalings have been explored in other contexts, including, \emph{e.g.}, sparse linear regression \cite{wainwright2009sharp,david2017high,reeves2019all}, spiked matrix estimation \cite{barbier20190}, and low-rank matrix recovery \cite{abbe2015exact}. These studies established the precise conditions under which perfect recovery in these problems is achievable. In our work, we go one step further by establishing the asymptotic distribution of the number of error bits $N_e$.


text:
\section{Subfield of Subfield is Subfield}
Tags: Subfields

\begin{theorem}
Let $R$ be a [[Definition:Ring with Unity|ring with unity]].
Let $K_1, K_2$ be [[Definition:Field (Abstract Algebra)|fields]], such that:
: $K_1$ is a [[Definition:Subfield|subfield]] of $R$
: $K_2$ is a [[Definition:Subfield|subfield]] of $K_1$
Then $K_2$ is a [[Definition:Subfield|subfield]] of $R$.
\end{theorem}

\begin{proof}
Let $K_1$ be a [[Definition:Subfield|subfield]] of $R$ and $K_2$ be a [[Definition:Subfield|subfield]] of $K_1$.
Then by definition:
:$K_1 \subseteq R$
:$K_2 \subseteq K_1$
From [[Subset Relation is Transitive]] it follows that $K_2 \subseteq R$
So by definition $K_2$ is a [[Definition:Subfield|subfield]] of $R$.
{{qed}}
[[Category:Subfields]]
g8qj1gxkqsgvlury7jpgaahfpiooiz9
\end{proof}

config: wiki


TITLE: A trivial question regarding the supremum of a set
QUESTION [1 upvotes]: Let $E$ be a subset of nonnegative real numbers. Suppose $E$ is bounded above and put $T = \{ x^2 : x \in E \}$. Say $\alpha = \sup E $. Then, $\alpha^2 = \sup T $.
Attempt:
Since $E$ is bounded above, the sup of $E$ exists. In fact, $x \leq \sup E = \alpha $ for all $ \in E$. Since $x \geq 0 $, it follows that $x^2 \leq \alpha^2 $. Hence, $\alpha^2 $ is an upper bound for the set $T$. To show it is the supremum of $T$, we have to prove that if $\beta < \alpha^2 $, then $\beta $ is not an upper bound of $T$. If this is false, then $x^2 \leq \beta $ for all $x \in E$. In particular, $x \leq \sqrt{ \beta } $. It follows that $\alpha \leq \sqrt{ \beta } $ since $x \in E$ was arbitrary. Hence, $\alpha^2 \leq \beta $. Contradiction.
I feel as is the last couple of sentences need maybe more justification or perhaps it is just wrong. I don't know. Hope you guys can help me with that.
Also, is this problem still holds if we say $E$  is a subset of all real numbers? MY answer is negative. Consider $E = \{ -2, -1 \} $. Then, $T = \{ 1, 4 \} $. Hence, $\sup E = -1 \implies ( \sup E )^2 = 1 \neq 4 = \sup T  $.

REPLY [1 votes]: Your approach is correct for showing $\alpha^2$ is an upper bound for $T$
For showing  $\alpha^2$ is supremum of $T$
An easy way for me is:let $\beta $ be an upper bound of $T$ .To show $\beta\geq \alpha^2$
Now $\beta \geq x^2;x\in E$.Since $E$ is bounded above  hence it contains its supremum $\alpha$.
So $\beta \geq \alpha^2$.
If $E$ is not bounded above there is no guarantee that it will contain its supremum


TITLE: polar coordinate verification
QUESTION [1 upvotes]: I am trying to verify polar coordinate transformation.
$$
\mathbf{r}\left(x,y\right)=x\hat{\mathbf{x}}+y\hat{\mathbf{y}}
$$
also,
$$
\mathbf{r}\left(\rho,\theta\right)=\rho\hat{\mathbf{\rho}}+\theta\hat{\mathbf{\theta}}
$$
subject to, when going from cartesian to polar
$$
\rho=\sqrt{x^2+y^2}\\
\theta=\arctan\left(\frac{y}{x}\right)
$$
and
$$
\hat{\mathbf{\rho}}=\cos\theta\hat{\mathbf{x}}+\sin\theta\hat{\mathbf{y}}\\
\hat{\mathbf{\theta}}=-\sin\theta\hat{\mathbf{x}}+\cos\theta\hat{\mathbf{y}}
$$
I want to start with $\mathbf{r}\left(\rho,\theta\right)$ and show how I can get to $\mathbf{r}\left(x,y\right)$. First I substitute
$$
\rho \hat{\mathbf{\rho}}+\theta \hat{\mathbf{\theta}}=\sqrt{x^2+y^2}\left(\cos\theta\hat{\mathbf{x}}+\sin\theta\hat{\mathbf{y}}\right)+\arctan\left(\frac{y}{x}\right)\left(-\sin\theta\hat{\mathbf{x}}+\cos\theta\hat{\mathbf{y}}\right)
$$
I then substitute $\cos\theta=\frac{x}{\sqrt{x^2+y^2}}$ and $\sin\theta=\frac{y}{\sqrt{x^2+y^2}}$.
I am left with the first term simplifying to $x\hat{\mathbf{x}}+y\hat{\mathbf{y}}$, but the second term becomes
$$
\arctan\left(\frac{y}{x}\right)\left(-\frac{y}{\sqrt{x^2+y^2}}\hat{\mathbf{x}}+\frac{x}{\sqrt{x^2+y^2}}\hat{\mathbf{y}}\right)
$$
which I cannot quite see how to reduce to zero algebraically. Any advice?

REPLY [1 votes]: The problem you have is with the equation
$$
\mathbf{r}\left(\rho,\theta\right)=\rho\hat{\mathbf{\rho}}+\theta\hat{\mathbf{\theta}}
$$
If you go from the origin along $\hat{\mathbf{\rho}}$ for a distance $\sqrt{x^2+y^2}$, you get to the point $(x,y)$. There is no reason to go any distance along $\hat{\mathbf{\theta}}$. The new reference frame has already the first axis towards the $(x,y)$ point. Your equation is then $$
\mathbf{r}\left(\rho,\theta\right)=\rho\hat{\mathbf{\rho}}
$$
Then all the rest of your calculations are correct.


TITLE: Vector space for which finite-dimensionality is open
QUESTION [7 upvotes]: Is there a vector space for which it is unknown whether it is finite-dimensional or infinite-dimensional?
This vector space should be somehow "naturally occuring" in the sense that it is interesting as a vector space itself. Otherwise one could take e.g. the set of all twin primes (or any set of which finiteness is unknown) and consider it as a free vector space over some field to get a trivial example.

REPLY [7 votes]: I don't know if it's a satisfying answer, but if you take a real number $\alpha$, its transcendence on $\mathbb{Q}$ is equivalent to $\mathbb{Q}[\alpha]$ being of infinite dimension. So for instance, the dimension of $\mathbb{Q}[\gamma]$ is unknown.
While this seems like a crafted example (and it is), looking at $\mathbb{Q}[\alpha]$ is absolutely natural when studying the algebraic properties of a real number.


TITLE: For $X$ not necessarily finite there exists a subspace $Y$ of codimension $1$ and $f:X\to\mathbb{K}$ such that $Y=\ker f$.
QUESTION [0 upvotes]: I need show this exercise:
**
If $Y\neq 0$ is a vectorial subspace of $X$ so that $\dim (X/ Y)=1$ then exist a lineal functional $f:X\to \mathbb{K}$ so that $Y=\ker f$.
**
I already showed this in the case that $X$ has a finite dimension (using bases). This is my proof for finite case:
If $Y$ is a subspace of $X$ of codimension $1$ and $\dim X=n$, let $\{y_1, \ldots, y_{n-1}\}$ be a basis of $Y$ and let $y_n\in X$ so that $\{y_1, \ldots, y_n\}$ is a basis de of $X$.
Clearly the linear functional $f :X \to \mathbb{K}$ so that $f(y_i)=0$ for $i=1, \ldots, n-1$ and $f(y_n)=1$  satisfies that  $Y=\ker f$.
How can I show my exercise without using finite dimension of X?

REPLY [1 votes]: $\dim (X/Y)=1$, therefore, by definition, there is an isomorphism $\phi:X/Y\to\Bbb K^1$. Then, you can consider the functional $f=\phi\circ \pi_Y$, where $\pi_Y:X\to X/Y$ is the quotient map.

REPLY [1 votes]: By assumption there is a vector $x_0\in X\setminus Y$ such that $X/Y=span\{x_0+Y\}$. So now define $f:X\to \mathbb{K}$ by $f(x)=\lambda$ where $x+Y=\lambda x_0+Y$. This is clearly a well defined linear functional, and we have $f(x)=0$ if and only if $x+Y=0+Y$, which happens if and only if $x\in Y$.


TITLE: Prove that $f$ is not onto
QUESTION [1 upvotes]: Let $f: G\to H$ be a homomorphism and let $|G| = 10$ and $|H| = 4$
Prove that f is not onto.

REPLY [3 votes]: By the first isomorphism theorem, $G/\ker f \cong \mathrm{im} f$. Also, the kernel is a subgroup of $G$ hence its order has to divide $10$ by Lagrange. Hence the possibilities for the order of the kernel of $f$ are $2$, $5$ or $1$. (If the order is $10$ then $f$ is the zero map and of course not surjective onto $H$.)
If the order of the kernel was $2$ (or $1$) then the order of the image would be $5$ (or $10$). Of course this is not possible since $H$ has only 4 elements.
If the order of the kernel is $5$ then the order of the image is $2$ so that $f$ is not onto surjective.


text:
\section{Conclusion}

In this study, we analyzed a certain type of transductive learning models and derived their optimization and generalization guarantees under the weak learnability condition (w.l.c.). Our idea was to interpret multi-scale GNNs as an ensemble of weak learners and apply boosting theory. As a special case, we showed that a particular type of multi-scale GNNs has a generalization bound that is decreasing with respect to the number of node aggregations under the condition. To the best of our knowledge, this is the first result that multi-scale GNNs provably avoid the over-smoothing from the viewpoint of learning theory. We confirmed that our models, coined GB-GNNs, worked comparably to existing GNNs, and that their empirical behaviors were consistent with theoretical observations. We believe that exploring deeper relationships between the w.l.c.\ and the underlying graph structures such as graph spectra is a promising direction for future research.

config: arxiv


TITLE: Calculate the divisor of the differential $dx/y$ on $C$ and use the result to show that $C$ has genus $g$.
QUESTION [0 upvotes]: (Silverman's The Arithmetic of Elliptic Curves Exercise 2.14) For this exercise we assume that char K $\neq 2$. Let $f(x)\in K[x]$ be a polynomial of degree $d\geq 1$ with nonzero discriminant, let $C_0/K$ be the affine curve given by the equation
$$C_0 : y^2=f(x)=a_0x^d+a_1x^{d-1}+\dots+a_{d-1}x+a_d$$
and let $g$ be the unique integer satisfying $d-3<2g\leq d-1$.
(a) Let $C$ be the closure of the image of $C_0$ via the map
$$ [1,x,x^2,\dots,x^{g-1},y] : C_0\to \mathbb{P}^{g+2}$$
Prove that $C$ is smooth and that $C\cap \{X_0\neq 0\}$ is isomorphic to $C_0$. The curve $C$ is called a hyperelliptic curve.

I have already proved this part by I wanted to provide it since (b) does refer to it.

(b) Let
$$
f^*(v)=v^{2g+2}f(1/v)=
\begin{cases}
a_0+a_1v+\dots+a_{d-1}v^{d-1}+a_dv^d & \text{ if $d$ is even} \\
a_0v+a_1v^2+\dots+a_{d-1}v^{d}+a_dv^{d+1} & \text{ if $d$ is odd}
\end{cases}
$$
Show that $C$ consists of two affine pieces
$$ C_0 : y^2=f(x)
\hspace{1cm} \text{ and } \hspace{1cm}
C_1:w^2=f^*(v) $$
"glued together" via the maps
\begin{equation*}
\begin{aligned}
C_0 & \to C_1 \\
(x,y) & \mapsto (1/x,y/x^{g+1})
\end{aligned}
\end{equation*}
\begin{equation*}
\begin{aligned}
C_1 & \to C_0 \\
(v,w) & \mapsto (1/v,w/v^{g+1})
\end{aligned}
\end{equation*}

Proof of (b): Using the dehomogenization in (a), we have already shown
that $C$ consists of $C_0$ and $C_1$. Note that $C_0$ contains all but
one or two points of $C$, but these points were shown to be in $C_1$.
Thus these are the only two necessary pieces. What is left to show is
"gluing" portion.
We need only consider points on $C$ that are on both the affine
part of $C_0$ (where $X_0\neq 0$) and the affine part of $C_1$ (where
$X_{g+1}\neq 0$). Now, using the coordinates of $C_0$, we see that
$X_{g+1}=x^{g+1}$. Thus $$ v
=\dfrac{X_g}{X_{g+1}}
=\dfrac{x^g}{x^{g+1}}
=\dfrac{1}{x} $$ Also $$ u
=\dfrac{X_{g+2}}{X_{g+1}}
=\dfrac{x^{g+2}}{x^{g+1}}
=\dfrac{y}{x^{g+1}} $$ Thus the gluing map $C_0\to C_1$ is  $$(x,y)\mapsto (1/x,y/x^{g+1})$$
Now let's look at the other direction. Recall that using the
coordinates of $C_1$, we have $X_0=v^{g+1}$. Thus $$ x
=\dfrac{X_1}{X_0}
=\dfrac{v^g}{v^{g+1}}
=\dfrac{1}{v} $$ and $$ y
=\dfrac{X_{g+2}}{X_0}
=\dfrac{v^{g+2}}{v^{g+1}}
=\dfrac{u}{v^{g+1}} $$ Thus the gluing map $C_1\to C_2$ is  $$ (v,u)\mapsto (1/v,u/v^{g+1}) $$

** My question is why $\dfrac{x^{g+2}}{x^{g+1}}=\dfrac{y}{x^{g+1}}$? And similarly, $\dfrac{v^{g+2}}{v^{g+1}}=\dfrac{u}{v^{g+1}}$? **

(c) Calculate the divisor of the differential $dx/y$ on $C$ and use the result to show that $C$ has genus $g$. Check your answer by applying Hurwitz's formula (II.5.9) to the map $[1,x] : C \to \mathbb{P}^1$. (Note that Exercise 2.7 does not apply, since $C\not\subset \mathbb{P}^2$).

** For (c), I am not sure how to calculate the divisor of the differential. Do I find $dx/y$ by taking the derivative of the mappings in (b)?

(d) Find a basis for the holomorphic differentials on $C$. (Hint: Consider the set of differential forms $\{x^i dx/y : i=0,1,2,\dots.\}$ How many elements in this set are holomorphic?

REPLY [0 votes]: (b) Since $C$ is defined with the map
$$
[1,x,\dots,x^{g-1},y] :  C_0 \to \mathbb{P}^{g+2}
$$
and since $K$ is algebraically closed,
$\dfrac{x^{g+2}}{x^{g+1}}=\dfrac{y}{x^{g+1}}$ and  $\dfrac{v^{g+2}}{v^{g+1}}=\dfrac{w}{v^{g+1}}$
(c) First, let's compute $\,dx/y$. Using the maps from (b), we have
$v=\dfrac{1}{x}$ and $w=\dfrac{y}{x^{g+1}}$
Let's rewrite this equations so that we have $x$ and $y$ equal to functions of $u$, and $w$.
$x=\dfrac{1}{v}$ and $y=\dfrac{w}{v^{g+1}}$
We can differentiate the first equation and get: $\,dx=-\dfrac{1}{v^2}\,dv$.
Hence $$\dfrac{\,dx}{y}=-\dfrac{v^{g-1}}{w}\,dv$$
Recall that a divisor is a formal $\mathbb{Z}$-linear combination of points. The divisor of a differential is of the form $\sum_i n_iP_i$ where the $P_i$ are the points at which the differential has a zero or pole, and $n_i$ is the order of zero or pole.
Since the discriminant is nonzero (i.e. $f$ is separable), we have $d$ distinct roots. Also since $\,dx=-\dfrac{1}{v^2}\,dv$, we have a double poles at $(0,1)$ at $(0,-1)$.
Hence the divisor of the differential is
$$div(\,dx/y)=P_1+P_2+\dots+P_d-2(0,1)-2(0,-1)$$
What remains to do is actually check that the genus of $C$ is $g$ via Hurtwiz's formula. Let's defined the map $\pi=[1,x]:C\to\mathbb{P}^1$, with genuses $g_1$ and $g_2$ respectively. By Hurtwiz's Formula,
$$2g_1-2=\deg(\pi)(2g_2-2)+\sum\limits_{P\in C} (e_\pi(P)-1)$$
Recall that the genus of the projective line is $0$, and $\deg(\pi)=2$. So,
$$2g_1-2=-4+\sum\limits_{P\in C} (e_\pi(P)-1)$$
Associated to $C$ is a double cover $\pi:C\to \mathbb{P}^1$ of the projective line. This cover has $2g+2$ ramification points. Hence
\begin{gather*}
2g_1-2=-4+(2g+2) \\
2g_1-2=2g-2 \\
g_1=g
\end{gather*}
Hence $C$ has genus $g$.
(d) Let $\{x^i\,dx/y | i=0,\dots,g-1\}$. (Note that $0\leq i\leq g-1$ is due to the fact that $K$ is algebraically closed.) To show that this is a suitable basis for holomorphic differentials on $C$. It is enough to show that $x^i\,dx/y$ is holomorphic. i.e. We need to compute the divisor of $x^i\,dx/y$ and show that it has no poles.
Let's begin with the cases where $i=0$. Recall that the equation of $C$ is $y^2=f(x)$. So when we differentiate it, we have the relation
$$2y\,dy=f'(x)\,dx  \iff  \dfrac{\,dx}{y}=\dfrac{\,dy}{f'(x)} $$
Since $C$ is nonsingular, then $y$ and $f'(x)$ can't both vanish. Hence $\,dx/y$ is holomorphic.
Since $x^i$ will just yield zeroes (and not poles), we can use the same argument above when $0<i\leq g-1$. Hence
$$\{x^i\,dx/y | i=0,\dots,g-1\}$$
is the basis for the holomorphic differentials on $C$.


TITLE: How many caesium clocks are there on each GPS satellite ? Is there any other atomic clock on-board?
QUESTION [5 upvotes]: I am trying to find how many caesium atomic clocks are carried by each of the GPS satellites. And whether the satellites also carry other atomic clocks, such as rubidium or hydrogen clocks.

REPLY [6 votes]: https://science.nasa.gov/science-news/science-at-nasa/2002/08apr_atomicclock/: "Each of the 24 GPS satellites carries 4 atomic clocks on board." Maybe something has changed since then.
EDIT (10/01/17):http://space.skyrocket.de/doc_sdat/navstar-2.htm : "GPS-2 (Global Positioning System) or Navstar-2 (Navigation System using Timing And ranging) are improved satellites of the second generation of the GPS navigation system...Each spacecraft carried 2 rubidium and 2 cesium clocks."
EDIT (10/01/17): @MartinBeckett : the following document seems recent: ftp://tycho.usno.navy.mil/pub/gps/gpsb2.txt "The design life of the Block II/IIA satellite is 7.3 years; each contain four atomic clocks:  two Cesium (Cs) and two Rubidium (Rb)...The design life of the Block IIR satellite is 7.8 years; each contains three Rb atomic clocks"
EDIT (Feb 23, 2022):

There are currently several dozen GNSS satellites in orbit. GPS and
GLONASS satellites carry Rb (rubidium) and Cs (caesium) frequency
standards, whereas Galileo satellites are equipped with PHM (passive
hydrogen maser) and Rb clocks. In the case of BeiDou, the clocks used
are of either Rb or HMAC (Hydrogen Maser Atomic Clock) standards

(https://www.mdpi.com/1424-8220/21/7/2396/htm )
See also https://qzss.go.jp/en/technical/satellites/index.html Looks like the answer to your question may depend on the generation of the satellite system.


TITLE: Bayes Estimator with Two Parameters
QUESTION [2 upvotes]: In a Bayesian approach to simple linear regression, suppose the intercept $\Theta_1$ and slope $\Theta_2$ of the regression line are a-priori independent with $\Theta_1\sim N(0,\tau^2_1)$ and $\Theta_2\sim N(0,\tau^2_2)$  Given $\Theta_1=\theta_1$ and $\Theta_2=\theta_2$, data $Y_1,...,Y_n$ (responses in the regression model) are independent with $Y_i\sim N(\theta_1+\theta_2x_i, \sigma^2)$, with the $x_i$ being the predictors.  The variance $\sigma^2$ is known, and $x_1,...,x_n$ are constants summing to $0$.
Find the Bayes estimators of $\Theta_1$ and $\Theta_2$ under squared error loss.

Here's where I'm confused; the expressions for the PDFs of the posterior distribution of each estimator are dependent on the other unknown quantity; hence so should their expected values (which is the Bayes estimator).
For example, holding $\theta_2$ constant, I calculate that:
$$f_{\Theta_1}\propto \frac{\exp((\sum\theta_1+\theta_2x_i-y_1)^2/2\sigma^2)}{(2\pi\sigma^2)^{n/2}}\cdot\frac{\exp(-\theta_1^2/(2\tau_1^2))}{\sqrt{2\pi\tau_1^2}}$$
But clearly this quantity is dependent on $\theta_2$! So clearly I've done something wrong here, but I don't know how to do this properly.  What are the Bayes estimators for both $\Theta_1$ and $\Theta_2$?

REPLY [1 votes]: The prior distribution of the pair $(\Theta_1,\Theta_2)$ is
$$
\text{constant} \cdot \frac 1 {\tau_1\tau_2} \exp\left( \frac{-1} 2 \left( \frac{\theta_1^2}{\tau_1^2} + \frac{\theta_2^2}{\tau_2^2} \right) \right) \, d\theta_1 \, d\theta_2.
$$
The likelihood is
$$
L(\theta_1,\theta_2) = \text{constant} \cdot \exp\left( \sum_{i=1}^n (\theta_1 + \theta_2 x_i - y_i)^2 \right).
$$
\begin{align}
(\theta_1 + \theta_2 x_i - y_i)^2 & = \theta_1^2 + \theta_2^2 x_i^2 + y_i^2 + 2\theta_1\theta_2 x_i - 2\theta_1 y_i - 2\theta_2 x_i y_i \\[10pt]
\sum_{i=1}^n (\theta_1 + \theta_2 x_i - y_i)^2 & = n\theta_1^2 + \theta_2^2 SSXX + \text{constant} + 2\theta_1\theta_2\cdot0 - 2\theta_1 n \overline y - 2\theta_2 \mathbb x \cdot\mathbb y
\end{align}
You'll have some algebra to do, but when you multiply the likelihood by the prior you should get
$$
\text{constant} \cdot \exp(\text{quadratic form in $\theta_1,\theta_2$}) \, d\theta_1\,d\theta_2.
$$
This will be a normal distribution, and the mean and variance can be read off from the form of this function. The mean should be a vector with two scalar components and the variance should be a $2\times2$ positive-definite matrix giving the two variances of scalar random variables and their covariance.


TITLE: About the small set expansion conjecture
QUESTION [9 upvotes]: Given a graph $G=(V,E)$ and a $\delta > 0$ one wants to calculate $h(G,\delta)=min_{\vert S\vert \leq \delta \vert V \vert } \phi(S)$. ($\phi(S) = \frac{ E(S,\bar{S}) }{d min \{\vert S \vert , n - \vert S\vert \}  }$) The ``small-set expansion conjecture" states that it is NP-Hard to determine if this is below $\epsilon$ or above $1-\epsilon$ for $\epsilon = 1/O(log(\frac{1}{\delta} ) )$

For context one notes that $h(G,\delta = \frac{1}{2})$ is the Cheeger constant which is known to be NP-hard to bound. But there does seem to exist values of $\delta$ (which ones?) for which $\phi(G,\delta)$ can be computed in polynomial time?

Towards understanding the small-set expansion conjecture one seems to prove this statement,

If $W$ is the span of the Laplacian eigenvectors of $G$ such that their eigenvalues are less than some $\lambda \in [0,1]$ and if every $w \in W$ satisfies $\mathbb{E}_i[w_i^4 ] \leq C ( E_i [w_i ^2 ]  )^2$ then for every set $S$ such that $\vert S \vert \leq \delta \vert V \vert$ we have $\phi(S) \geq \lambda(1 - \sqrt{C \delta}  )$

[Reference, Lemma 8 here, http://www.boazbarak.org/sos/files/lec2d.pdf ]

My questions are,

How does the above theorem help understand the conjecture stated at the beginning? What is the relationship between the two?
Why should such vectors $w$ exists as demanded in the theorem? What is the intuition behind looking at such $w$?
What is the intuition behind choosing that specific value of $\epsilon$ as in the statement of the conjecture?

REPLY [11 votes]: I think the following should answer your questions, even though it's not exactly in the same order.
The original formulation of the small set expansion conjecture states that, analogously to the Unique Games Conjecture, for every $\epsilon >0$ there exists $\delta>0$ so that it is NP-hard to determine whether in a graph $G$ it's the "YES" case where there exists a $\delta$-sized set with expansion less than $\epsilon$ or it's the "NO" case where every $\delta$-sized set has expansion at least $1-\epsilon$. The paper of Raghavendra, Steuerer, and Tulsiani https://www.cs.cornell.edu/~dsteurer/papers/ssereductions.pdf showed that this is equivalent to the case where $\epsilon = O(\log (1/\delta))$ and in fact the case where in the NO case, for every $\delta' \geq \delta$, sets of size $\delta'$ have at least the same expansion as they would in the "$\epsilon$-noisy Gaussian graph" (see the paper for the precise statement).  The reason for the relation $\epsilon = O(\log (1/\delta))$ is because this is the relation between those parameters in the Gaussian noise graph. This result of Raghavendra et al can be thought of as the small-set expansion analog for the paper of Khot, Kindler, Mossell and O'Donnell who showed a similar result for unique games, giving a very precise relation between the parameters $1/\delta$ (which in the unique games setting is known as the alphabet size) and $\epsilon$.
The result you mention discussed in my lecture notes is from Section 8 in my paper with Brandao, Harrow, Kelner, Steurer and Zhou ( https://www.cs.cornell.edu/~dsteurer/papers/hypercontract.pdf ). What we show there, roughly speaking, is that a graph is a small set expander if and only if the span of eigenvectors corresponding to low eigenvalues of its Laplacian does not contain an "analytically sparse" vector.
The intuition is the following: consider the following two extremes:
1) A random vector $w$. In this case, the distribution of entries of $w$ is approximately the Gaussian distribution, and so this satisfies that $\mathbb{E}_i w_i^4 = O(\mathbb{E}_i w_i^2)^2$.
2) A vector $w$ that is the characteristic vector of a set of measure $\delta$ (i.e. it has $1$ in the coordinates belonging to the set, and $0$ in the others). In this case, $\mathbb{E}_i w_i^4 = \delta \gg \delta^2 = (\mathbb{E}_i w_i^2)^2$.
Now, roughly speaking, the subspace $W$ corresponding to eigenvalues smaller than $\epsilon$ of the Laplacian corresponds to set which have expansion at most $\epsilon$ in the graph. So, if there exists a $\delta$-sized set with such expansion then there would be a vector $w$ (namely the projection of the characteristic vector of this set to $W$) with $\mathbb{E}_i w_i^4 \gg (\mathbb{E}_i w_i^2)^2$. The other direction (which is more challenging to prove but turns out to be true) is that if there is a vector $w$ with this property then we can also find a set with $o(1)$ measure with not too good expansion.