TITLE: Differentiable Manifolds, Metric Space Structure, Lipschitz Continuity
QUESTION [1 upvotes]: I would like to prove that if $f:M\rightarrow M$ is a continuously differentiable mapping on a compact manifold, then $f$ must be Lipschitz continuous.  However, I do not know how to properly interpret what a Lipschitz continuous function on a manifold should be.  To define this, I would need a metric space structure on the manifold.
Really, I would like to know how I should formulate and state that proposition.  But as a concrete question, is it possible to define a metric $d:M\times M\rightarrow \mathbb{R}$, inducing the topology on $M$, such that we may write $M$ as a finite union of charts so that the coordinate functions are isometries between the Euclidean metric on $\mathbb{R}^n$ and the metric $d$ on $M$?
I know very little beyond the definition of a differentiable manifold.

REPLY [2 votes]: You can introduce a metric on $M$ wich induces the topology. This is a standard result from differential geometry. One way of doing this is to introduce a scalar product (usually denoted $g$, also called a Riemannian metric) on each tangent space in a smooth way. It is not difficult to show that this is possible by patching it together from local charts with a partition of unity. Once you have a scalar product you can define the lengths of smooth curves $\gamma:[0,1]\rightarrow M$ by defining
$$\ell(\gamma) := \int_0^1 \sqrt{g_{\gamma(t)}(\gamma^\prime(t), \gamma^\prime(t))}d\, t$$
Once you have a notion of length you can define
$$d(p,q):= \inf\{\ell(\gamma):\gamma \text{ is a smooth curve from $p$ to $q$}\}$$
(Assume $M$ to connected)
It can then be shown that this is a metric on $M$ which, in fact, is compatible with the topology. And of course you can then define Lipshitz continuity for $f:M\rightarrow M$ in the usual way.
Alternatively you can embed $M$ into some $\mathbb{R}^d$ -- according to a theorem of Whitney this is always possible. Then you can define a metric by requiring this to be an isometry.
In general $M$ will, however, not be locally isometric to some $\mathbb{R}^n$ (regardless of how you choose the metric).
For details you should consult textbooks on Differential Geometry.


TITLE: Measurable Functions over finite or countables sets
QUESTION [0 upvotes]: Let $X$ be a countable or finite set and $u$ a measure over $(X,\Sigma)$. Let $A=${$A_1,A_2,...$} be the set of atoms of $(X,\Sigma)$. Prove that if $f: X\to \mathbb R $ is a measurable function, then $f$ is constant over each atom $A_i$, meaning: If $x$,$y$ $\in$ $A_i$ then is true that $f(x)=f(y)$.
I have really no clue about how to prove this.

REPLY [0 votes]: Well, here is what i managed to write:
Since $f$ is measurable, ${f^{-1}}(-\infty,a]$ $\in$ $\Sigma$ $\forall a\in \mathbb R$.
Supouse that $f(x) \neq f(y)$. Then, exists a $c$ such that $f(x) < c < f(y)$. So, if we consider the set {$f$ $\leq$ $c$}, $x$ $\in$ {$f$ $\leq$ $c$} but $y$ $\notin$ {$f$ $\leq$ $c$}.
But i'm stuck here. I don't know what the next step would be, can i say something about the Atoms? Since $x,y$ $\in$ $A_i$, where $A_i$ is an atom?


TITLE: Is there a closed form for the integral $\int_u^{\infty}(x+a)^ve^{-bx}dx$
QUESTION [1 upvotes]: I'm looking for the close form of the integral $\int_u^{\infty}(x+a)^ve^{-bx}dx$, where $u,a,b$ are positive real numbers (b could be integer in special case), $v$ is a complex number. Are there anyone aware of it? Thanks in advance!

REPLY [3 votes]: $$
\int_u^\infty(x+a)^{\nu}\mathrm{e}^{-bx}dx
$$
lets make the sub $t = x+ a$ we find
$$
\mathrm{e}^{ab}\int_{u+a}^\infty t^\nu\mathrm{e}^{-b(t-a)}dt = \mathrm{e}^{ab}\int_{u+a}^\infty t^\nu\mathrm{e}^{-bt}dt =\frac{\mathrm{e}^{ab}}{b^{\nu+1}}\int_{b(u+a)}^\infty s^{\nu}\mathrm{e}^{-s}ds
$$
If we map $\nu \to \alpha - 1$ we find
$$
\frac{\mathrm{e}^{ab}}{b^{\nu+1}}\int_{b(u+a)}^\infty s^{\nu}\mathrm{e}^{-s}ds = \frac{\mathrm{e}^{ab}}{b^{\nu+1}}\int_{b(u+a)}^\infty s^{\alpha-1}\mathrm{e}^{-s}ds
$$
The latter is the form of the incomplete gamma function
$$
\Gamma(s,x) = \int_x^\infty t^{s-1}\mathrm{e}^{-t}dt
$$
so we have
$$
\frac{\mathrm{e}^{ab}}{b^{\nu+1}}\int_{b(u+a)}^\infty s^{\alpha-1}\mathrm{e}^{-s}ds = \frac{\mathrm{e}^{ab}}{b^{\nu+1}}\Gamma(\alpha,b(u+a)) = \frac{\mathrm{e}^{ab}}{b^{\nu+1}}\Gamma(\nu+1,b(u+a))
$$
We have suitable conditions on $\alpha$ and thus $\nu + 1$.


TITLE: How does upwards acceleration affect tension on whirling mass?
QUESTION [1 upvotes]: Consider the following setup and problem:

When solving this problem, I had the  intuition that the string tension $T_A$ would be equal to $T_B$, which does not agree with the solutions.
What would lead you to know the string tensions in both cases are, in fact, different?

REPLY [0 votes]: If you look at the balance of forces on the mass you will notice that $T\,\cos\theta = m\,g$ and since the angle is different, the tension must be different.


TITLE: Proving $(\frac{n}{p})$, a Legendre symbol, is multiplicative
QUESTION [3 upvotes]: Proof:
if $p|n$ or $p|m$ then $p|nm$, so $(\frac{mn}{p})=0=(\frac{n}{p})(\frac{m}{p})$
If $p \nmid n$, then
$$(\frac{mn}{p}) \equiv (mn)^{\frac{p-1}{2}}(mod \text{ } p)$$
$$(\frac{mn}{p}) \equiv n^{\frac{p-1}{2}}m^{\frac{p-1}{2}}(mod \text{ } p)$$
$$(\frac{mn}{p}) \equiv (\frac{n}{p})(\frac{m}{p})(mod\text{ } p)$$
$$(\frac{mn}{p}) = 1\text{ } \textrm{or} \text{ } -1$$
$$(\frac{n}{p})(\frac{m}{p}) = 1\text{ } \textrm{or} \text{ } -1$$
$$(\frac{mn}{p}) \equiv (\frac{n}{p})(\frac{m}{p})(mod \text{ } p)$$
so $$(\frac{mn}{p})=(\frac{n}{p})(\frac{m}{p})$$
My question is how $$(\frac{mn}{p}) \equiv (\frac{n}{p})(\frac{m}{p}) \text{ }(mod\text{ } p)$$
becomes equality.

REPLY [2 votes]: The Legendre symbol is always $0$, $1$, or $-1$, by definition.  So you have a congruence mod $p$ where each side is actually just one of $0$, $1$, and $-1$ (and actually, in this case you know they can't be $0$).  Unless $p=2$, the only way two such numbers can be congruent mod $p$ is if they are actually equal.  You need to handle the case $p=2$ separately (but that case is rather trivial).


TITLE: Does the equation $\displaystyle min_{x,y} f(x,y)=min_{y}min_{x}f(x,y)=min_{x}min_{y}f(x,y)$ always hold for a minimization problem?
QUESTION [2 upvotes]: For a minimization problem of function $f(x,y)$, does the equation $min_{x,y} f(x,y)=min_{y}min_{x}f(x,y)=min_{x}min_{y}f(x,y)$ always hold?
I saw this equation somewhere. It does the minimization in a sort of iterated way, treating either $x$ or $y$ as a constant first. But what about a saddle point? If I use Hessian matrix to consider the convexity of $f(x,y)$, it will let me know it doesn't work if there's a saddle point, while this iterated method may still give me a value.
I think this kind of problems falls into optimization, and I also wonder if  $min_{y}max_{x}f(x,y)=max_{x}min_{y}f(x,y)$ holds.

REPLY [1 votes]: Let $X$ and $Y$ be arbitrary non-empty sets and let $f:X\times Y\to\mathbb R$ be a function.

Claim: $\inf_{(x,y)\in X\times Y}f(x,y)=\inf_{x\in X}\inf_{y\in Y}f(x,y)$.

This includes the possibility that any of the infima is $-\infty$. If all of the infima involved are actually attained, then you can replace “$\inf$ ” with “$\min$.”
Therefore, the answer to your question is affirmative, with the caveat that $\min_{y\in Y}f(x,y)$ may not exist (because the infimum value is not attained by any $y\in Y$) for some of the $x\in X$, even if the joint minimum $\min_{(x,y)\in X\times Y}f(x,y)$ does exist.

Proof: For any $x_0\in X$ and and $y_0\in Y$, it is clear that $$f(x_0,y_0)\geq\inf_{(x,y)\in X\times Y}f(x,y).$$ Leaving $x_0$ fixed and allowing $y_0$ to vary, we then have that $$\inf_{y\in Y}f(x_0,y)\geq\inf_{(x,y)\in X\times Y}f(x,y).$$ This is true for any fixed $x_0\in X$, so we can now take infimum over $X$ to obtain $$\inf_{x\in X}\inf_{y\in Y}f(x,y)\geq\inf_{(x,y)\in X\times Y}f(x,y).$$
For the reverse inequality, fix again $x_0\in X$ and $y_0\in Y$. Clearly, we have that $$\inf_{x\in X}\inf_{y\in Y}f(x,y)\leq\inf_{y\in Y}f(x_0,y)\leq f(x_0,y_0).$$ Now we can take infimum on the right-hand side over all of $X\times Y$ to obtain that $$\inf_{x\in X}\inf_{y\in Y}f(x,y)\leq\inf_{(x,y)\in X\times Y}f(x,y),$$ which completes the proof. $\quad\blacksquare$

For the interchangeability of the maximum and minimum operators, please consult this thread.


TITLE: CDF of $X=\min\{X_1, X_1\cdot X_2\}$
QUESTION [2 upvotes]: I have random variable (RV) $X$ where $X=\min\{X_1, X_1\cdot X_2\}$. Further, $X_1$ and $X_2$ are independent but not identical RVs with exponential distributions, i.e., $f_{X_1}(x_1)=\frac{1}{m_1}e^{-\frac{x_1}{m_1}}$ and $f_{X_2}(x_2)=\frac{1}{m_2}e^{-\frac{x_2}{m_2}}$.
I want to find the CDF of $X$, and I start as follows, but I am not sure how I can write following two terms in integral forms:
$$F_X(x) = \mathsf P(X < x) = \mathsf P(X_1 < x \mid  X_2 \geqslant 1) + \mathsf P(X_1\cdot X_2 < x \mid X_2 < 1).$$
Can some one help me to write $F_X(x)$ in integral form using $X_1$ and $X_2$ PDFs/CDFs?

REPLY [1 votes]: You were close.
$\begin{align}F_X (x) & =\mathsf P(X\leq x)
\\ & = \mathsf P(\min\{X_1, X_1X_2\}\leq x)
\\ & = \mathsf P(X_1X_2 \leq x\cap X_2 \leq 1)+\mathsf P(X_1 <x\cap X_2 > 1)
\\ & = \int_{0}^{1} \int_0^{x/t}\frac {\mathrm e^{-t/m_2-s/m_1}}{m_1m_2}\operatorname d s\operatorname d t+\int_1^\infty\int_0^{x}\frac {\mathrm e^{-t/m_2-s/m_1}}{m_1m_2}\operatorname d s\operatorname d t
\end{align}$


text:
\section{Algorithmic AMP phase transition regime}\label{app:AMPregime}

In this appendix we show that the right-hand side of the bound in theorem~\ref{AMP-theorem} for signal strength and sparsity scaling like $\lambda_n \rho_n^2= w$
and $\rho_n = \Omega((\ln n)^{-\alpha})$ with $w, \alpha\in \mathbb{R}_{+}$, tends to zero as $n\to +\infty$. We focus on the Bernoulli prior case but the arguments generalizes to Bernoulli-Rademacher prior.

Let us first upper bound $\gamma_n^{t}$ in terms of $\lambda_n$ and $\rho_n$ in the Bernoulli case. First we use the bound $\vert f_t^\prime(x)\vert \leq \sqrt{\lambda_n}$ (see lemma~\ref{lem:PL_cond}) to bound
$$\max\{1, \hat{\textsf{b}}_1\}  \max\{1, \hat{\textsf{b}}_2\} \cdots  \max\{1, \hat{\textsf{b}}_{t-1}\} \leq \lambda_n^{\frac{t-1}{2}}.$$
From the explicit AMP iteration (see appendix G second formula for example) we have
$\tau^n_{t} \leq \rho_n$. Since $\nu_n = 12\rho_n$ we get
$(\nu^n +  \tau^n_{1})  (\nu^n +  \tau^n_{1} +  \tau^n_{2})  \cdots  (\nu^n + \sum_{i=1}^{t} \tau^n_{i}) \leq (12\rho_n + \rho_n) (12\rho_n + 2\rho_n) \cdots (12\rho_n + t \rho_n) \leq \frac{1}{6} (12+t)! \rho_n^{t}$.
Putting everything  together we get:
$$
\gamma_n^t \leq \frac{1}{6} (12+t)! \rho_n^{t} \lambda_n^{2t  -1+ \frac{t-1}{2}} .
$$
Now we use the scaling (which is the correct scale for the phase transition to happen) $\lambda_n = w \rho_n^{-2}$ and get:
$$
\gamma_n^t \leq \frac{1}{6} (12+t)! \frac{w^{\frac{5t -3}{2}}}{\rho_n^{4t-3}} .
$$
Therefore
$$
\textsf{bound}_t \leq  C C_{t} \exp\Big\{ - \frac{6c}{w^\frac{5t -3}{2}} \frac{c_{t} }{(12 + t)!} \rho_n^{4t-3} n \epsilon^2 \Big\}.
$$
Now the $t$ dependence in the constant $c_t=[C^t (t!)^C]^{-1}$ (from now on $C$ is a generic positive constant) and using Stirling's approximation $t! \approx \sqrt{2\pi t} \, t^t \, e^{-t}$ this scales at dominant order as $[C^t (t^t)^C]^{-1}$. So we have at dominant order
$$
\textsf{bound}_t \approx  C C_{t} \exp\{ - C e^{\pm Ct - C t \ln t} e^{(4t-3)\ln(\rho_n)} e^{\ln n} \epsilon^2 \}.
$$
Now set the number of iterations to $t = o(\frac{\ln n}{\ln\ln n})$. We get $t\ln t = o(\ln n)$ so $\pm Ct - C t \ln t = o(\ln n)$ and
\begin{align}
\textsf{bound}_t \approx  C C_{t} \exp\{ - C e^{- o(\ln n)} e^{ o(\frac{\ln n}{\ln\ln n}) \ln(\rho_n)} e^{\ln n} \epsilon^2 \}.\label{worsen}
\end{align}
We set $\rho_n = \Theta\big( \frac{1}{(\ln n)^\alpha}\big) = \frac{C}{(\ln n)^\alpha}$. Then
$\ln\rho_n = \ln C - \alpha\ln\ln n$ and we get
$$
\textsf{bound}_t \approx  C C_{t} \exp\{ - C e^{- o(\ln n)} e^{ o(\frac{\ln n}{\ln\ln n}) (C - \alpha\ln\ln n)} e^{\ln n} \epsilon^2 \}.
$$
This leads to
\begin{align*}
\textsf{bound}_t & \approx  C C_{t} \exp\{ - C e^{- o(\ln n) + C o(\frac{\ln n}{\ln\ln n}) - \alpha o(\ln n)} e^{\ln n}
\epsilon^2 \}
\nonumber \\ &
\approx  C C_{t} \exp\{ - C e^{(\ln n) - (1+ \alpha) o(\ln n) + C o(\frac{\ln n}{\ln\ln n})}
\epsilon^2 \}
\nonumber \\ &
\approx  C C_{t} \exp\{ - C e^{(\ln n)[ 1 - (1+ \alpha) o(1)] + C o(\frac{1}{\ln\ln n})}
\epsilon^2 \}
\nonumber \\ &
\approx  C C_{t} \exp\{ - C n^{1 - o_\alpha(1)}
\epsilon^2 \}.
\end{align*}
One can check that the prefactor $C_t=[C^t (t!)^C]$ does not change the dominant order for $t = o(\frac{\ln n}{\ln\ln n})$. This shows that the bound vanishes as $n\to+\infty$ for $\lambda = w \rho_n^{-2}$ and $\rho_n =\Theta(\frac{1}{(\ln n)^\alpha})$ for any $\alpha\ge 0$. {As seen from \eqref{worsen} the bound worsen with decreasing $\rho_n$. So the result extends to $\rho_n=\Omega(\frac{1}{(\ln n)^\alpha})$.}

Note also that in the case of the rescaled bound of remark 1 below theorem~\ref{AMP-theorem}, the previous derivation is unchanged, up to the constant appearing in the $o_\alpha(1)$ that is changed some other $o_\alpha(1)$ (for $n$ big enough). Indeed, because $\rho_n =\Omega(\frac{1}{(\ln n)^\alpha})$ the $\rho_n^2$ or $\rho_n^4$ appearing in the rescaled bound can be absorbed in the $o_\alpha(1)$ of the previous derivation, for $n$ large enough.

config: arxiv