TITLE: How can I find this integral
QUESTION [0 upvotes]: How can I find this integral? please help
$$I=\int_0^1\frac{e^{-\sqrt{x}}}{\sqrt{x}}\ dx.$$

REPLY [2 votes]: Set  $\displaystyle\sqrt x=u\implies \frac{dx}{2\sqrt x}=du$
When $x=0,u=0$ and for $x=1,u=\sqrt1=1$
$$I=2\int_0^1e^{-u}du=2\cdot\frac{e^{-u}}{-1}\large|_0^1$$


TITLE: finding the stationary points of $f(x)=\frac{1}{2}x^TAx+x^Tb+a$
QUESTION [0 upvotes]: So we have the function $f(x)=\frac{1}{2}x^TAx+x^Tb+a$. Here $x,b \in \mathbf{R}^d$. $a \in \mathbf{R}$, $A$ is $d\times d$ symmetric, positive definite matrix with distinct positive eigenvalues. I need to find the stationary points of this function, let $x=\langle x_1,...,x_d\rangle, b= \langle b_1,...,b_d\rangle$.
Ok so $A=UDU^T$ where $U=[u_1,...,u_d]$. $D=diag\{\lambda_1,...,\lambda_d\}$
with $\lambda_1>...>\lambda_d$.
Hence, $f(x)=x^TUDU^Tx+x^Tb+a$.
$\triangledown f=?$

REPLY [1 votes]: Your approach is a good one if you switch from $x$-space to $y$-space, $y:=U^Tx$, before searching for the stationary point. Here's another approach. Since $\partial_if=A_{ij}x_j+b_i$, $\nabla f=Ax+b$, so a stationary point satisfies $x=-A^{-1}b$. This point is a minimum, because $\partial_i\partial_jf=A_{ij}$ is positive-definite. In particular, the non-negative function $\frac12(x+A^{-1}b)^TA(x+A^{-1}b)=\frac12x^TAx+b^Tx+\frac12b^TA^{-2}b$ is, up to an additive constant, $f$.


TITLE: $|P(A)| = 2^{|A|}$ question
QUESTION [1 upvotes]: For the following question:
Let $A = \{ 1,2,3,4,5 \}$, $B = \{ a,b,c,d,e \}$, and $C = \{ \text{red} , \text{green} , \text{blue} \}$.  Calculate $| \mathcal{P} ( A \times B \times C ) |$.
I know $|P(A)| = 2^{|A|}$
So am I right in thinking ... $5\times5\times3 = 75 = 2^{75}$ would be my answer?

REPLY [0 votes]: You have the right idea. The only problem is saying that $5\times 5\times 3=75=2^{75}$. Instead, notice that $|A|=5$, $|B|=5$, and $|C|=3$. We know that $|A\times B\times C|=75$ by the definition of Cartesian Product. Thus $|\mathcal{P}(A\times B\times C)|=2^{75}$.


text:
$\norm{\cdot}$ refers to $\ell_2$ unless specified otherwise.
The procedure proposed by~\cite{bora2017compressed} finds a reconstruction $\hat{x} = G(\hat{z})$, where $\hat{z}$ solves:
\[
\wh{z} := \argmin_{z\in\R^k}\norm{AG(z) - y}^2.
\]
This is essentially an ERM-based approach. As is well known from the classical statistics literature, ERM's success relies on strong concentration properties, guaranteed, e.g., if the data are all sub-Gaussian. ERM may fail, however, in the presence of corruption or heavy-tails. Indeed, our experiments demonstrate that in the presence of outliers in $y$ or $A$, or heavy-tailed noise in $y$, \cite{bora2017compressed} fails to recover  $G(z^*)$.

{\bf Remark} {\em Unlike typical problems in $M$-estimation and high dimensional statistics, the optimization problem that defines the recovery procedure here is non-convex, and thus in the worst case, computationally intractable. Interestingly, despite non-convexity, as demonstrated in \cite{bora2017compressed}, (some appropriate version of) gradient descent
is empirically very successful. In this paper, we take this as a computational primitive, thus sidestepping the challenge of proving whether a gradient-descent based method can efficiently provide guaranteed inversion of a generative model. Our theoretical guarantees are therefore statistical but our experiments show empirically excellent performance.}

\subsection{MOM objective}

It is well known that the median of means estimator achieves nearly sub-Gaussian concentration for one dimensional mean estimation of variance bounded random variables \cite{MOM_nemirovsky1983problem,MOM_jerrum1986random,MOM_alon1999space}.
Inspired by the median-of-means algorithm, we propose the following algorithm to handle heavy-tails and outliers in $y$ and $A$. We partition the set $\left[m\right]$ into $M$ disjoint batches $\{B_1, B_2, \cdots, B_M\}$ such that each batch has cardinality $b=\frac{m}{M}$. Without loss of generality, we assume that $M$ exactly divides $m$, so that $b$ is an integer.
For the $j^{th}$ batch $B_j$, define the function
\begin{align}\label{equ:loss}
    \ell_j(z) := \frac{1}{b} \| A_{B_j}G(z) - y_{B_j}\|^2,
\end{align}
where $A_{B_j} \in\R^{b\times n}$ denotes the submatrix of $A$ corresponding to the rows in batch $B_j$. Similarly, $y_{B_j}\in\R^{b}$ denotes the entries of $y$ corresponding to the batch $B_j.$
Our workhorse is a novel variant of median-of-means (MOM) tournament procedure \cite{lugosi2016risk,lecue2017robust}
using the loss function \cref{equ:loss}:
\begin{align}
    \widehat{z} = \arg \min_{z\in\R^k}  \max_{z'\in\R^k}
    \underset{1\leq j \leq M}{\mathrm{median}} (\ell_j(z) - \ell_j(z')).\label{equ:MOM_minmax}
\end{align}
We do not assume that the minimizer is unique, since we only require a reconstruction $G(\wh{z})$ which is close to $G(z^*)$. Any value of $z$ in the set of minimizers will suffice.
The intuition behind this aggregation of batches is that if the inner player $z'$ chooses
a point close to $z^*,$ then the outer player $z$ must also choose a
point close to $z^*$ in order to minimize the objective.
Once this happens, there is no better option for $z'$.
Hence a neighborhood around $z^*$ is almost an equilibrium, and in fact
there can be no neighborhood far from $z^*$ with such an equilibrium.

\paragraph{Computational considerations.}
The objective function \cref{equ:MOM_minmax} is not convex and we use  \Cref{alg:MOM_GAN} as a heuristic to solve \cref{equ:MOM_minmax}.
In \Cref{sec:experiments}, we empirically observe that gradient-based methods are able to minimize this objective and have  good convergence properties. Our main theorem guarantees that a small value of the objective implies a good reconstruction and hence we can certify reconstruction quality
using the obtained final value of the objective.

\begin{algorithm}[t]
\footnotesize
\begin{algorithmic}[1]
\STATE \textbf{Input:} Data samples $\{y_j, a_j\}_{j=1}^m$.
\STATE \textbf{Output:} $G(\widehat{z})$.
\STATE \textbf{Parameters:} Number of batches $M$.\\
{\kern2pt \hrule \kern2pt}
\STATE Initialize $z$ and $z'$.
\FOR {$t=0$ to $T-1$,}
\STATE For each batch $j\in [M]$, calculate
 $\frac{1}{|B_j|} (\ell_j(z) - \ell_j(z'))$ by \cref{equ:loss}.
\STATE Pick the batch with the median loss
$\underset{1\leq j \leq M}{\mathrm{median}} (\ell_j(z) - \ell_j(z'))$, and evaluate the gradient for $z$ and $z'$ using backpropagation on that batch. \\
 (i) perform gradient descent for $z$; \\
 (ii) perform gradient ascent for $z'$.
\ENDFOR
\STATE Output the  $G(\widehat{z}) = G({z})$.

\end{algorithmic}
\caption{\footnotesize Robust compressed sensing of generative models}
\label{alg:MOM_GAN}
\end{algorithm}

config: arxiv


TITLE: Determine $a$ such that $3x\cdot\cos x - ax = 0$ has () solutions...
QUESTION [0 upvotes]: An equation is given $3x\cdot\cos x - ax = 0$, for $x$ in $[0,2\pi]$. I am asked to determine $a$ such that the equation has two and three solutions. It seems that for only one solution $a$ is in the interval $a<-3$ and $a \geqslant 3$. I do not understand this, as I thought that the cosine function cannot go over $[-1,1]$. I reasoned that in that case, $a$ would be in $[-3,3]$. In what case would the equation have only one solution?

REPLY [2 votes]: To answer I do not understand this, as I thought that the cosine function cannot go over [-1,1]. You are correct, the range of $\cos x$ is $[-1, 1]$. But in the given equation, $\cos x$ is being scaled by $3$ in the equation. For example, if $\cos x = 1$, then $3 \cos x = 3$. So $3 \cos x$ can take on any value in the closed interval $[-3, 3]$.


TITLE: Spaces of Killing spinors for different orientation
QUESTION [1 upvotes]: Simply put, I want to understand how a change of orientation on a Riemannian spin manifold can change the space of Killing spinors.
To be more precise:
Let $M$ be a spin manifold (i.e. the first and second stiefel whitney class of $TM$ vanish).
Assume that $M$ is simply connected, so for every Riemannian metric $g$ on $M$ and every orientation $o$ on $M$ we have (up to equivalence) exactly on spin structure. Denote the associated complex spinor bundle by $\Sigma(M,g,o)$.
($\Sigma(M,g,o)=Spin(M,g,o)\times_\rho \Sigma_n$ where $\rho\colon Spin(n)\rightarrow Aut_{\mathbb C}(\Sigma_n)$ is the complex spinor representation and $n=dim(M)$.)
Denote the two orientations on $M$ by $o_1$ and $o_2$. Let $\alpha\in\mathbb{C}$. Are the spaces of $\alpha$-Killing spinors of $\Sigma(M,g,o_1)$ resp. $\Sigma(M,g,o_2)$ related? For example, do they have the same dimension?
Edit: We have an isomorphism $F\colon SO(M,g,o_1)\rightarrow SO(M,g,o_2)$ given by $(b_1,\ldots, b_n)\mapsto (-b_1,b_2,\ldots, b_n)$. (Assuming $M$ is connected.) If the spin structure on $(M,g,o_1)$ is $\eta\colon Spin(M,g,o_1)\rightarrow SO(M,g,o_1)$, then we get a spin structure on $(M,g,o_2)$ by $F\circ \eta\colon Spin(M,g,o_1)\rightarrow SO(M,g,o_2)$. The respective spinor bundles are the same as vector bundles, $\Sigma(M,g,o_1)=\Sigma(M,g,o_2)$. Clifford multiplication changes because of the isomorphism $F$. Namely, if $(b_1,\ldots,b_n)$ is an oriented ON basis of $(M,g,o_1)$ and $\varphi\in\Sigma(M,g,o_1)=\Sigma(M,g,o_2)$, we get $b_1\cdot_1\varphi=-b_1\cdot_2\varphi$ and $b_j\cdot_1\varphi=b_j\cdot_2\varphi$ for $j=2,\ldots, n$ where $\cdot_i$ is the Clifford multiplication in $\Sigma(M,g,o_i)$, $i=1,2$.
For the corresponding connections $\nabla^{1}$ and $\nabla^{2}$ I don't get a relation that seems to help and I can't relate the Killing spinors of $\Sigma(M,g,o_1)$ to those of $\Sigma(M,g,o_2)$.

REPLY [1 votes]: If $M$ is even-dimensional, Clifford multiplication with the Clifford volume element is an isomorphism between the spaces of Killing spinors for $\alpha$ and for $-\alpha$. If you change the orientation, you can actually leave the Clifford multiplication $c\colon TM\to\operatorname{End}\Sigma(M,g,o)$ untouched, or you  replace it by $-c$. Then either the $\alpha$-Killing spinors stay $\alpha$-Killing spinors or become $-\alpha$-Killing spinors.
If $M$ is odd-dimensional and you insist that the Clifford volume element acts by $1$, then you have to replace $c$ by $-c$, and the Killing constant $\alpha$ also changes sign.


TITLE: Geometric interpretation of $\frac {\partial^2} {\partial x \partial y} f(x,y)$
QUESTION [27 upvotes]: Are there any geometric interpretation for the second partial derivative? i.e.
$$f_{xy} = \frac {\partial^2 f} {\partial x \partial y}$$
In particular, I'm trying to understand the determinant from second partial derivative test for determining whether a critical point is a minima/maxima/saddle points:
$$D(a, b) = f_{xx}(a,b) f_{yy}(a,b) - f_{xy}(a,b)^2$$
I have no trouble understanding $f_{xx}(x,y)$ and $f_{yy}(x,y)$ as the of measure of concavity/convexity of f in the direction of x and y axis. But what does $f_{xy}(x,y)$ means?

REPLY [10 votes]: Think of the mixed partial as an abstract tendency of the curve to twist like DNA, (but just because it's positive in absolute value doesn't mean the surface actually twists since other tendencies may overwhelm it), and the straight second derivatives $f_{xx}$ and $f_{yy}$ as an abstract tendency of the curve to bulge up or down in the $xz$- and $yz$- cross-sections.
To tease out the individual roles of the partials, let's assume for the moment that the mixed partials are identically zero, the better to isolate their effect later. If $f_{xx}$ and $f_{yy}$ are of opposite signs, then the curve has a saddle tendency (think of two curves, one in the $yz$-plane and one in the $xz$-plane, intersecting at right angles, one opening up and the other opening down: this will produce a negative intrinsic curvature or saddle shape like a hyperbolic paraboloid). Now think of the same parabolas but both opening say down, with $f_{xx}$ and $f_{yy}$ tending to have the same signs: that will tend to produce an intrinsic positive curvature (bulging) like an ellipsoid. I'm sure you knew this.
Now let's add in the mixed partials to show what their effect is. Think of the mixed partials as a pure twisting factor, also tending to produce a negative or saddle curvature, but rotated $45$ degrees! Yes, a twist is the same as a saddle tendency, but we think of it differently. Imagining your hand riding down along the wall of a saddle shape, like an airplane that dives while rotating, may help you see this.
Now: ever seen a diagram of a saddle showing a kind of "X" shape over it, diagonal lines coming out of the saddle-point, where the tendency to go up in say $y$ is canceled by the tendency to go down in $x$, and the thing just holds steady along the diagonal line, with $f_{xx}$ and $f_{yy}$ both zero here? Well, if you had a properly rotated saddle shape it might not go up or down in the $x$- or $y$- directions at all--and yet it would be negatively curved or twisting nonetheless as would be plainly visible from the other directions. It is THIS twist that the mixed partials measure (just as an $xy$-term rotates a conic, by the way).
If the curvature from the two ordinary second partials is negative, forget it--the mixed partials will make it even more negative.  In other words, if $f_{xx}f_{yy}$ is negative because these differ in sign, the intrinsic curvature is already negative, and subtracting $f_{xy}^2$ will make it even more so. But if the curvature from the straight second partials is positive (bulging up or down), because $f_{xx}$ and $f_{yy}$ agree in sign, then possibly this positive tendency can still be overwhelmed by the independent negative-curvature twisting action of the mixed partials. That is why $f_{xy}$ is squared and subtracted: its sign doesn't matter to the saddle-ness and it is an inherently negatively-curved factor. The contest between these is the discriminant test you mention.


TITLE: Natural deduction vs simply typed lambda calculus
QUESTION [1 upvotes]: In ND , I have propositions as their own things, but in simply typed lambda calculus, I have propositions associated with proof. The question I want to ask is, how do these two different way of treating proposition (as being attached without proof vs with) cause differences between the calculus' in the big picture?

REPLY [2 votes]: The big picture is painted by the Curry-Howard isomorphism.
If you make your question more specific and targeted, a less general answer might be possible.


TITLE: Fixed point of an inverse?
QUESTION [1 upvotes]: According to a problem that I am working on a fixed point is defined as a point $x$ that satisfies $$f(x) = x.$$
A problem is asking me to find the fixed point of the inverse of $f(x)$, and the explanation tells me to find the inverse function first, and later use the definition.
Is this step necessary? I want to say no because the inverse of a function has an image that is reflected about the line $y=x$, so finding the fixed point of the original function should give you the fixed point of the inverse as well.
Is there an exception that I am not aware about?

REPLY [4 votes]: I believe the OP meant to say "if $f: R \rightarrow R$ is a function, then the graph of its inverse is simply the graph of $f$ reflected about the line $y = x$."
I'm going to assume that the original function is bijective (i.e., "one-to-one and onto"), so that it actually has an inverse function, rather than an inverse relation.
Let $g$ be the inverse of the function $f$. Suppose that $x_0$ is a fixed point of $g$. That means that
$g(x_0) = x_0$
Applying the function $f$ to both sides of this equation, you get
$f(g(x_0)) = f(x_0)$
Since $f$ and $g$ are inverses, we know that $f(g(x_0)) = x_0$, so this equation can be rewritten
$x_0 = f(x_0)$.
In other words, I've shown that any fixed point of $g$ is also a fixed point of $f$. (Essentially the same proof shows that fixed points of $f$ are fixed points of $g$ as well.) So if the problem asks you to find fixed points of the inverse of $f$, you might as well just look for fixed points of $f$, i.e., don't bother with trying to invert it.
-John


TITLE: Vectors with minimal Hamming weight in a rational vector space?
QUESTION [7 upvotes]: Suppose given $n\ge 1$ and a subspace $U$ in $\mathbb{Q}^n$. It is given as $\mathbb{Q}$-span of certain known vectors.
For $x \in U$, we let the Hamming weight of $x$ be the number of its nonzero entries.
Is it possible to find an element of minimal Hamming weight in $U\smallsetminus\{0\}$? Is there an algorithm?
(All I could find is concerned with the case of vector spaces over finite fields. Or, on the other hand, with vectors of minimal Euclidean length in lattices.)

REPLY [3 votes]: Here is an Integer Linear Programming approach to this problem.
First, let's multiply given vectors by a suitable integer to make them all having integer components. Second, we notice that if certain rational coefficients deliver the minimum Hamming weight, then by scaling them, we can obtain integer coefficients delivering the same weight. Therefore, we can focus on the problem of finding an integer linear combination of integer vectors with the smallest nonzero number of nonzero components.
Let $v_1,\dots,v_m$ be given integer vectors. Let $c_i$ for $i\in\{1,\dots,m\}$ be integer variables corresponding to the coefficients in a linear combination. For each component $j\in\{1,\dots,n\}$, we further introduce two binary variables $p_j,q_j\in\{0,1\}$ and three inequalities:
$$\sum_{i=1}^m v_{ij} c_i \geq p_j - Mq_j,$$
$$\sum_{i=1}^m v_{ij} c_i \leq -q_j + Mp_j,$$
$$p_j + q_j \leq 1,$$
where $M$ is a large positive constant (chosen empirically). The third inequality here restricts values to three possible cases: $(p_j,q_j)=(1,0)$ when the $j$-th component in the linear combination is positive; $(p_j,q_j)=(0,1)$ when the $j$-th component is negative; and $(p_j,q_j)=(0,0)$ when the $j$-th component is zero. Notice that the large value of $M$ when it comes with a nonzero coefficient makes the corresponding inequality silent (automatically satisfied).
Next, we exclude the zero linear combination by requiring
$$\sum_{j=1}^n p_j + q_j \geq 1.$$
Finally, since $\sum_{j=1}^n p_j + q_j$, in fact, equals the weight of the linear combination, our objective is
$$\text{minimize}\quad \sum_{j=1}^n p_j + q_j.$$


TITLE: Finite subgroups of the General Linear Group
QUESTION [0 upvotes]: Let G be a finite subgroup of GLn(K) where K is an algebraic closure of Q, the rational Field. Prove that every element of G is diagonalisable over K. For solving this, I understand that an element of G is diagonalisable iff its minimal polynomial is square free. I know that all eigen values are in K but how do I ensure that the Arithmetic multiplicity of every eigen value is equal to its Geometric multiplicity? Help please.

REPLY [0 votes]: Note that it suffices to consider finite order $A \in \mathrm{GL}_n(K)$. This being the case, $A^m = I$ for some $m$. Therefore the minimal polynomial for $A$ must divide the square-free polynomial $x^m - 1$, which makes the minimal polynomial square-free as well.


text:
{\bf Problem.} For how many values of $a$ is it true that the line $y=x+a$ passes through the vertex of parabola $y=x^2+a^2$?
{\bf Level.} Level 4
{\bf Type.} Algebra
{\bf Solution.} The given parabola has vertex at $(0,a^2)$. The line $y=x+a$ passes through this point if and only if $a^2=0+a$. Rearranging the equation gives $a^2-a=0$. Factoring an $a$ out of the left hand side yields $a(a-1)=0$, so $a=0$ or $a=1$. Thus, there are $\boxed{2}$ possible values of $a$.

set_name: MATH


TITLE: piecewise potention of Matrix
QUESTION [0 upvotes]: Is there a a name for the piecewise potention of a Matrix. Simular to the Hadamard product for multiplication?
In Matlab code this would be: A.^x

REPLY [0 votes]: Perhaps unsurprisingly, this is called the Hadamard power of a matrix.


TITLE: Solve $x^{18} \equiv 7^{99} - 7, \mod 592$
QUESTION [1 upvotes]: What I tried:
$x^{18} \equiv 7^{99} - 7, \mod 592 \iff \begin{cases} x^{18} \equiv 7^{99}-7 & \mod 7 \\ x^{18} \equiv 7^{99}-7 & \mod 2 \\ x^{18} \equiv 7^{99}-7 & \mod
 3\end{cases} \iff x^{18} \equiv 0, \mod 7,2,3. $
I'm not sure how to proceed: is the last step equivalent to saying $x^{18} \equiv 0, \mod 42 (=7 \cdot 2 \cdot 3)$ or $x^{18} \equiv 0, \mod 592$?

REPLY [2 votes]: Hint $\bmod 37\!:\,\  x^{\large 18}\equiv \color{#c00}{7^{\large 99}}\!-7\equiv -6\,\overset{\rm square}\Longrightarrow\,x^{\large 36}\equiv -1\,$ contra little Fermat
because: $\ \ 7 \equiv 3^{\large 4}\,\Rightarrow\, \color{#c00}{7^{\large 99}}\equiv (3^{\large 4})^{\large 99}\equiv (3^{\large 36})^{\large 11}\equiv 1^{\large 11}\equiv\color{#c00}{\bf 1}$


TITLE: Subgroup of $S_5$ contains cycle of length $5$ and transposition
QUESTION [0 upvotes]: Suppose a subgroup of $S_5$ contains a cycle of length $5$ and a transposition. Must it be all of $S_5$?
Say, it contains the cycle $(1 2 3 4 5)$ and a transposition $(ij)$. Then it contains a product of any number of copies of these two, and also inverses. How to continue?

REPLY [1 votes]: Let $G$ is generated by   $(12345)$ and $(ij)$. The $10\mid |G|$.
From reasons of symmetry it is sufficient to consider two cases:
1) $(12345)$ and $(12)$
2) $(12345)$ and $(13)$
In the first case  $(12345)(12)=(1345)$ has order $4$ and $(12345)^2(12)=(14)(235)$ has order $6$. Hence  $60\mid |G|$ and either $G=A_5$ or $G=S_5$. Since $G$ contains a transposition,  $G\ne A_5$.
The second case is considered similarly.