TITLE: Classical analog of state vector
QUESTION [1 upvotes]: I can’t believe I don’t know the answer to this question. What is the classical analog of the state vector of quantum mechanics?

REPLY [1 votes]: The state vector represents a complete (as complete as quantum theory allows) specification of the system's physical state. So the classical analog of the state vector would be a point in phase space, or any other type of data that suffices to specify a unique solution of the classical equations of motion.
By the way, classical physics can be regarded as a special case of quantum physics in which all observables commute with each other and in which the state is always an eigenstate of all of the observables. In this sense, states in classical physics are always orthogonal to each other (cf What makes a theory "Quantum"?).$^\dagger$
$^\dagger$ Minor technicality: In quantum physics, we normally require that the Hilbert space be separable, which means that it must admit a countable basis of mutually orthogonal state vectors. An obstacle to treating classical physics as a special case of quantum physics is that the Hilbert space (state space) of classical physics would typically be non-separable. The significance of this is emphasized, in a different context, in the paper String quantization: Fock vs. LQG Representations.


TITLE: 2 and/or 4 belongs to f(x) image?
QUESTION [0 upvotes]: $$f(x) = \frac{x}{x^ 2+x}+4$$
How can I now if 2 and or 4 belongs to the image of the function? (in a General Way so I can apply it to other functions)

REPLY [0 votes]: Well, try setting $f(x)$ equal to $2$, and seeing if the equation is consistent. Do the same for $f(x)=4$.

REPLY [0 votes]: To decide whether a number $a$ is in the image of that $f$, set $f(x)=a$ and solve for $x$. You'll get a quadratic equation (with the restriction $x^2+x\ne0$). If it as real solutions, then $a$ is in the image. Otherwise, no.
However, since  $x^2+x\ne0$, we must have $x\ne0$ and so $f(x)$ simplifies to $f(x) = \frac{1}{x+1}+4$, which makes $f(x)=a$ much easier to solve.


TITLE: Roots of Unity are distinct
QUESTION [1 upvotes]: Let $F$ be a field and $p, q\in \mathbb Z$ be distinct positive primes. Show that if $x \in F$ is such that $x^p=x^q=1$ then $x=1$.
I tried to suppose $x \neq 1$ and to do something with the least p and q satisfying the preceding property, but had no success.

REPLY [2 votes]: More generally, if $m$ and $n$ are relative prime integers and $x^m=x^n=1$, then $x=1$ because for some $a,b\in\mathbb Z$ we have $1=am+bn$, so $x=x^1=(x^m)^a(x^n)^b$.


TITLE: Swapping supremums and integrals
QUESTION [0 upvotes]: Let $f \in H^{-1}(S)$, where $S \subset \mathbb{R}^n$ is some nice set in space.
Can I exchange supremums and integrals over time here:
$$\sup_{g \in H^1(S)}\int_0^T \langle f, g \rangle_{H^{-1}(S), H^1(S)}\;dt =\int_0^T \sup_{g \in H^1(S)} \langle f, g \rangle_{H^{-1}(S), H^1(S)}\;dt$$
I think so. But what if $g$ has some dependence on $t$? Or is that not allowed?

REPLY [1 votes]: If $f$ depends on $t$ and supremum on the right is computed for each $t$, the two sides are not equal, even if $g$ does not depend on $t$.
A simple counterexample can be constructed by taking $T = 2 \pi, f(t) = \sin t \phi$, where $\phi$ is an arbitrary element in $H^{-1}(\Omega)$. Then if $g \in H^1(\Omega)$, the left hand side is zero, but the right hand side is positive.
If $g$ is allowed to depend on $t$, equality holds, I think.


TITLE: Matrix multiplication for quadratic constraint
QUESTION [0 upvotes]: With two $N$-vectors $x$ and $y$, I calculate $z := x - y$. I also have an $N \times N$ covariance matrix $Q$ and calculate the following:
\begin{align*}
x^\top Qx &= a\\
y^\top Qy &= b\\
z^\top Qz &= c
\end{align*}
Is there any way to calculate a new matrix $K$ such that $x^\top Kx = c$?
I have an optimization problem where I want to solve for $x$, but implement a constraint on $z$ which I haven't been able to setup. So I am hoping to be able to have the constraint on $x$ too but using a different matrix in it.
As $x$ isn't known prior to the optimization solution I think $K$ would need to be calculated using only $y$ and $Q$ which are both known.
I'm not sure if what I'm trying to achieve is possible but any help would be appreciated.

REPLY [0 votes]: Observe that $c = x'Qx - 2x'Qy + b$. So let $x,y\in\mathbb R^N$, and $Q\in\mathbb R^{N\times N}$. Put $$ W := \begin{bmatrix} Q & -2Qy \\ 0 & b \end{bmatrix}\qquad\text{and}\qquad \tilde x:= \begin{bmatrix} x \\ 1 \end{bmatrix}.$$ Then $$\begin{align*} \tilde x'W\tilde x &= \begin{bmatrix} x' & 1 \end{bmatrix}\begin{bmatrix} Q & -2Qy \\ 0 & b \end{bmatrix}\begin{bmatrix} x \\ 1 \end{bmatrix} \\ &=\begin{bmatrix} x'Q + 0 &-2x'Qy+b\end{bmatrix}\begin{bmatrix} x \\ 1 \end{bmatrix} \\ &=x'Qx -2x'Qy + b \\ &= c.\end{align*}$$ So there exists a matrix such that $\tilde x W\tilde x = c$. However, note that you need to modify your $x$ by concatenating a $1$ to the vector (that is, $\tilde x$ is a linear-affine transformation).
Edit: So what you can do is the following. $W$ is the matrix you are looking for. So let's call it $K$. Then optimize the objective function $$\mathcal L(\tilde x, \lambda) = \tilde x' K\tilde x + \lambda (\iota'x - 1)$$ over $\mathbb R^{N+1}$, where $\iota$ is a vector of zeros except for the last, i. e. the $(N+1)$th, component where there is a one.


TITLE: Derivatives of multivariate normal CDF in terms of lower-dimension PDFs and CDFs
QUESTION [0 upvotes]: Suppose I have a standardized multivariate normal distribution of dimensionality $m$, parameterized either by the correlation matrix $\mathbf{\Sigma}$:
$$
X_m \sim N_c(\mathbf{0}, \mathbf{\mathbf{\Sigma}})
$$
or by the precision matrix (inverse of the correlation matrix) $\Lambda = \mathbf{\mathbf{\Sigma}}^{-1}$:
$$
X_m \sim N_p(\mathbf{0}, \mathbf{\mathbf{\Lambda}})
$$
(whichever is most convenient for the solution)
I am interested in the derivative of the CDF (cumulative distribution function)
$$
\mathbf{\Phi}_m(\mathbf{x}, \mathbf{\Sigma}) = P(\mathbf{y}_m \sim N(\mathbf{0}_m, \mathbf{\Sigma}_{m \times m}) \geq \mathbf{x}_m)
$$
with respect to each entry in $\mathbf{x}$ - that is:
$$
\frac{\partial}{\partial x_1} \mathbf{\Phi}_m(\mathbf{x}, \mathbf{\Sigma}), \:\:
\frac{\partial}{\partial x_2} \mathbf{\Phi}_m(\mathbf{x}, \mathbf{\Sigma}), \:\:
... \:\:, \:\:
\frac{\partial}{\partial x_m} \mathbf{\Phi}_m(\mathbf{x}, \mathbf{\Sigma})
$$
From this other question: https://stats.stackexchange.com/questions/71976/partial-derivative-of-bivariate-normal-cdf-and-pdf
When $m=2$, if the upper triangular part of $\mathbf{\Sigma}$ is expressed as a vector $(\rho_{12} \:\: \rho_{13} \:\: ... \:\: \rho_{23} \:\: \rho_{24} \:\: ...  \:\:\rho_{mm})$ and we denote as $\phi_m(\mathbf{x}, \mathbf{\Sigma})$ the PDF of an $m$-dimensional MVN distribution, we have:
$$
\frac{\partial}{\partial x_1} \mathbf{\Phi}_2(x_1, x_2, \rho_{12}) =
\phi_1(x_1)
\mathbf{\Phi}_1(\frac{x_2 - \rho_{12} x_1}{\sqrt{1 - \rho_{12}^2}})
$$
And:
$$
\frac{\partial}{\partial x_2} \mathbf{\Phi}_2(x_1, x_2, \rho_{12}) =
\phi_1(x_2)
\mathbf{\Phi}_1(\frac{x_1 - \rho_{12} x_2}{\sqrt{1 - \rho_{12}^2}})
$$

Can an arbitrary-dimension multivariate normal CDF be expressed in terms of the PDFs and CDFs of lower-dimensional multivariate normal distributions?
I suspect the formula might be something like this:
$$
\frac{\partial}{\partial x_p} \mathbf{\Phi}_m(\mathbf{x}, \mathbf{\Sigma}) =
\phi_{1}(x_p)
\mathbf{\Phi}_{m-1}(
    \frac{x_1 - \rho_{1p} x_p}{\sqrt{1 - \rho_{1p}^2}},
    \frac{x_2 - \rho_{2p} x_p}{\sqrt{1 - \rho_{2p}^2}},
    \:\: ... \:\:;
    \Lambda_{1p},
    \Lambda_{2p},
    ...
)
$$
But I am very unsure about it.
What would be the correct formula?

REPLY [0 votes]: I'll answer myself after finding a book called "Stochastic Programming" by András Prékopa (https://link.springer.com/book/10.1007/978-94-017-3087-7) plus this other question: https://stats.stackexchange.com/questions/330966/derivative-of-the-joint-distribution-interpretation
Given a multivariate CDF $\text{CDF}_m(x_1, x_2, \: ... \:, x_m)$, we have:
$$
\frac{\partial}{\partial x_1} \text{CDF}_m(x_1, x_2, \: ... \:, x_m) =
    \text{PDF}_1(x1) \:\:
    \text{CDF}_{m-1}(x_2, \: ... \: , x_m \:|\: x_1)
$$
For MVN, denoting $\mathbf{x}_{-1} = (x_2 \:,\: ... \:,\: x_m)$ and
$$
\mathbf{S} =
\begin{bmatrix}
    \mathbf{S}_{11} & \mathbf{S}_{12} \\
    \mathbf{S}_{21} & \mathbf{S}_{22} \\
\end{bmatrix}
    =
\begin{bmatrix}
    1 & \mathbf{\Sigma}_{1, 2..m} \\
    \mathbf{\Sigma}_{1, 2..m} & \mathbf{\Sigma}_{2..m, 2..m} \\
\end{bmatrix}
$$
We have:
$$
\phi_{m-1}(x_2, \: ... \: , x_m \:|\: x_1 = c) =
\phi_{m-1}(
    x_1 + \mathbf{S}_{12} \mathbf{S}_{22}^{-1} (c - \mathbf{x}_{-1}), \:\:
    1 - \mathbf{S}_{12} \mathbf{S}_{22}^{-1} \mathbf{S}_{21}
)
$$
Then, as defined by Henrion's "GRADIENT ESTIMATES FOR GAUSSIAN DISTRIBUTION FUNCTIONS: APPLICATION TO PROBABILISTICALLY CONSTRAINED OPTIMIZATION PROBLEMS" paper:
$$
\frac{\partial}{\partial x_1} \mathbf{\Phi}_{m}(\mathbf{x}, \mathbf{\Sigma}) =
    \phi_{1}(x_1, 1) \:
    \mathbf{\Phi}_{m-1}(
        \mathbf{\widetilde{x}}, \:
        \mathbf{\widetilde{\Sigma}}
    )
$$
With:
$$
\mathbf{\widetilde{x}} = \left(
    \frac{x_2 - \Sigma_{2,1} x_1}{\sqrt{1 - \Sigma_{2,1}^2}} \:,\:
    ... \:,\:
    \frac{x_m - \Sigma_{m,1} x_1}{\sqrt{1 - \Sigma_{m,1}^2}}
\right)
$$
and
$$
\mathbf{\widetilde{\Sigma}} =
\begin{bmatrix}
    1 & \frac{\Sigma_{2,3} - \Sigma_{2,1} \Sigma_{3,1}}{\sqrt{1 - \Sigma_{2,1}^2} \sqrt{1 - \Sigma_{3,1}^2}}
    & \: ... & \: &
    \frac{ \Sigma_{2,m} - \Sigma_{2,1} \Sigma_{m,1}  }{ \sqrt{1 - \Sigma_{2,1}^2}  \sqrt{1 - \Sigma_{m,1}^2}}   \\
    & 1 &
    \frac{ \Sigma_{3,4} - \Sigma_{3,1} \Sigma_{4,1} }{ \sqrt{1 - \Sigma_{3,1}^2}   \sqrt{1 - \Sigma_{4,1}^2} } &
    \: ... \: &
    \frac{ \Sigma_{3,m} - \Sigma_{3,1} \Sigma_{m,1} }{ \sqrt{1 - \Sigma_{3,1}^2}   \sqrt{1 - \Sigma_{m,1}^2} } \\
    & & \: ... \: & &
\end{bmatrix}
$$


TITLE: How do we prove this inequality?
QUESTION [2 upvotes]: Suppose $a,b,c > 0$. Prove that
$$\frac{a^2}{b^2} +\frac{b^2}{c^2} + \frac{c^2}{a^2} \geq \frac ab + \frac bc + \frac ca.$$
I've tried multiplying everything by the denominator and then I tried to use the rearrangement inequality, but it didn't yield the result I was looking for. I couldn't really think of anything else to do.

REPLY [4 votes]: Just another way:
Let $x = a/b, y = b/c, z=c/a$, so that $xyz=1$.  Then we need to show $x^2+y^2+z^2\geqslant x+y+z$.  It is enough to show that $f(t)=t^2-t-\log t \geqslant 0$, which is easy as its only minimum is when $f(t=1)=0$.


TITLE: $\lim_{n \to \infty} \frac{1}{\sqrt{n^k}} (1 + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}} + \cdots + \frac{1}{\sqrt{n}})^k$ by Stolz–Cesàro
QUESTION [3 upvotes]: $$\lim_{n \to \infty} \frac{1}{\sqrt{n^k}} (1 + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}} + \cdots + \frac{1}{\sqrt{n}})^k, k \in \mathbb{N}$$
Putting $\sqrt{n^k}$ in denominator, we get:
$$\lim_{n \to \infty} \frac{(1 + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}} + \cdots + \frac{1}{\sqrt{n}})^k}{\sqrt{n^k}}$$
Apllying Stolz–Cesàro theorem:
$$\lim_{n \to \infty} \frac{(1 + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}} + \cdots + \frac{1}{\sqrt{n}})^k - (1 + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}} + \cdots + \frac{1}{\sqrt{n-1}})^k }{\sqrt{n^k} - \sqrt{(n-1)^k}}$$
I don't know how to use properly multinomial formula, but the biggest number in numerator among denominators in first brackets with $k$ degree is $\sqrt{n^k}$, in second brackets $\sqrt{(n-1)^k}$, their coefficients are $1$
$$\lim_{n \to \infty} \frac{ \frac{1}{\sqrt{n^k}} - \frac{1}{\sqrt{(n-1)^k}} + \frac{1}{\sqrt{(n-1)^k}} - \cdots + 1 - 1 + \cdots}{\sqrt{n^k} - \sqrt{(n-1)^k}}$$
Multiplying numbers in first brackets by $\frac{1}{\sqrt{n}}$ gives us $\frac{1}{\sqrt{2^{k-1} \times n}} + \frac{1}{\sqrt{3^{k-1} \times n}} + \cdots + \frac{1}{\sqrt{(n-1)^{k-1} \times n}}$ etc., but I suspect we can't get same numbers in second brackets.
My guess, after evaluating sum (or difference) in numerator, we need to divide each number of our expression by $\sqrt{n^k}$.
In denominator we get 0, because $$\sqrt{\frac{n^k}{n^k}} - \sqrt{\frac{(n-1)^k}{n^k}} = 1 - \sqrt{(\frac{n-1}{n})^k} = 1 - 1 = 0, n \to \infty$$
Multiplication and division of denominator by conjugate ($\sqrt{n^k} + \sqrt{(n-1)^k}$) gives "slightly" different picture (unless I've done several big mistakes in a row):
$$\frac{ n^k - (n-1)^k }{ \sqrt{n^k} + \sqrt{(n-1)^k} } = \frac{ n^k - n^k + kn^{k-1} - \cdots }{ \sqrt{n^k} + \sqrt{(n-1)^k} } = \frac{kn^{k-1} - {k\choose 2}n^{k-2} +\cdots }{ \sqrt{n^k} + \sqrt{(n-1)^k} }, n \to \infty$$
Dividing by $n^{k-1}$:
$$\frac{k - 0 + 0}{ \sqrt{\frac{n^k}{n^{2(k-1)}  } } + \sqrt{ \frac{(n-1)^k}{n^{2(k-1)}}  }} = \frac{k - 0 + 0 - \cdots}{0 + 0}$$
So my guess was a bad guess.
Unfortunately, by this point I'm pretty much lost. Hence, I need some help... Thank you!

REPLY [1 votes]: There is a nice proof already provided by iskander using Stolz–Cesàro.
Also, using definite integrals it can be shown the limit is $2^k$
$\left( \lim_{n \to \infty} \frac{1}{\sqrt{n}}\sum_{i=1}^{n}\frac{1}{\sqrt{i}} \right)^k=\left( \lim_{n \to \infty} \frac{1}{n}\sum_{i=1}^{n}\sqrt{\frac{n}{i}} \right)^k=\left( \int_{0}^{1}\frac{dx}{\sqrt
{x}} \right)^k=2^k$


text:
To start with, consider the problem of detection $K = 2$ communities.   Many community detection methods rely on maximizing an objective function $f(A, e) \equiv f_A(e)$ over the set of node labels $e$, which can take values in, say, $\{-1, 1\}$.
Since $A$ can be thought of as a noisy realization of $\mathbb{E}[A]$, the ``ideal'' solution corresponds to maximizing $f_{\mathbb{E}[A]}(e)$ instead of maximizing $f_A(e)$. For a natural class of functions $f$ described below, $f_{\mathbb{E}[A]}(e)$ is essentially a function over the set of projections of labels $e$ onto the subspace spanned by eigenvectors of $\mathbb{E}[A]$ and possibly some other constant vectors.  In many cases $\mathbb{E}[A]$ is a low-rank matrix, which makes $f_{\mathbb{E}[A]}(e)$ a function of only a few variables. It is then much easier to investigate the behavior of $f_{\mathbb{E}[A]}(e)$, which typically achieves its maximum on the set of extreme points of the convex hull generated by the projection of the label set $e$.    Further, most of the $2^n$ possible label assignments $e$ become interior points after the projection, and in fact the number of extreme points is at most polynomial in $n$ (see Remark \ref{Remark:TwoComComplxty} below);  in particular, when projecting onto a two-dimensional subspace, the number of extreme points is of order $O(n)$. Therefore, we can find the maximum simply by performing an exhaustive search over the labels corresponding to the extreme points. Section~\ref{Sec:LabelEst} provides an alternative method to the exhaustive search, which is faster but approximate.

In reality, we do not know $\mathbb{E}[A]$, so we need to approximate its columns space using the data $A$ instead.    Let $U_A$ be an $m\times n$ matrix computed from $A$  such that the row space of $U_A$ approximates the column space of $\mathbb{E}[A]$ (the choice of $m \times n$ rather than $n \times m$ is for notational convenience that will become apparent below).   Existing work on spectral clustering gives us multiple option for how to compute this matrix, e.g., using the eigenvectors of $A$ itself, of its Laplacian, or of their various regularizations  -- see Section~\ref{Subsec:ApproxAdMat} for further discussion of this issue.  The algoritm works as follows:

\begin{enumerate}
  \item Compute the approximation $U_A$ from $A$.
  \item Find the labels $e$ associated with the extreme points of the projection $U_A[-1,1]^n$.
  \item Find the maximum of $f_A(e)$ by performing an exhaustive search over the set of labels found in step 2.
\end{enumerate}
Note that the first step of replacing eigenvectors of $\mathbb{E}[A]$ with certain vectors computed from $A$ is very similar to spectral clustering.   Like in spectral clustering, the output of the algorithm does not change if we replace $U_A$ with $U_A R$ for any orthogonal matrix $R$.   However, this is where the similarity ends, because instead of following the dimension reduction by an ad-hoc clustering algorithm like $K$-means, we maximize the original objective function.   The problem is made feasible by reducing the set of labels over which to maximize, to a particular subset found by taking into account the specific behavior of $f_{\mathbb{E}[A]}(e)$ and $f_A(e)$.

While our goal in the context of community detection is to compare $f_A(e)$ to $f_{\mathbb{E}[A]}(e)$, the results and the algorithm in this section apply in a general settingwhere $A$ may be any deterministic symmetric matrix.   To emphasize this generality, we write all the results in this section for a generic matrix $A$ and a generic low-rank matrix $B$, even though we will later apply them to the adjacency matrix $A$ and $B = \mathbb{E}[A]$.

Let $A$ and $B$ be $n\times n$ symmetric matrices with entries bounded by an absolute constant, and assume $B$ has rank $m\ll n$.   Assume that $f_A(e)$ has the general form
\begin{equation}\label{Eq:GenFuncType}
  f_A(e)=\sum_{j=1}^\kappa g_j(h_{A,j}(e)),
\end{equation}
where $g_j$ are scalar functions on $\mathbb{R}$ and $h_{A,j}(e)$ are quadratic forms of $A$ and $e$, namely
\begin{equation}\label{Eq:QuadrFun}
  h_{A,j}(e) = (e+s_{j1})^T A (e+s_{j2}).
\end{equation}
Here $\kappa$ is a fixed number, $s_{j1}$ and $s_{j2}$ are constant vectors in $\{-1,1\}^n$.
Note that by \eqref{eq: Okl explicit form}, the number of edges between communities has the form \eqref{Eq:QuadrFun},
and by \eqref{eq: QDCBM explicit form}, the log-likelihood of the degree-corrected block model $Q_{DC}$ is a special case of \eqref{Eq:GenFuncType} with $g_j(x)=\pm x\log x$, $x>0$.

We similarly define $f_B$ and $h_{B,j}$,  by replacing $A$ with $B$ in \eqref{Eq:GenFuncType} and \eqref{Eq:QuadrFun}.
By allowing $e$ to take values on the cube $[-1,1]^n$, we can treat $h$ and $f$ as functions over $[-1,1]^n$.

Let $U_B$ be the $m\times n$ matrix whose rows are the $m$ leading eigenvectors of $B$. For any $e\in[-1,1]^n$, $U_Ae$ and $U_Be$ are the coordinates of the projections of $e$ onto the row spaces of
$U_A$ and $U_B$, respectively.   Since $h_{B,j}$ are quadratic forms of $B$ and $e$ and $B$ is of rank $m$, $h_{B,j}$'s depend on $e$ through $U_Be$ only, and therefore $f_B$ also depends on $e$ only through $U_B e$. In a slight abuse of notation, we also use $h_{B,j}$ and $f_B$ to denote the corresponding induced functions on $U_B[-1,1]^n$.

Let $\mathcal{E}_A$ and $\mathcal{E}_B$ denote the subsets of labels $e\in\{-1,1\}^n$ corresponding to the sets of extreme points of $U_A[-1,1]^n$ and $U_B[-1,1]^n$, respectively. The output of our algorithm is
\begin{equation}\label{Eq:GenMethOutp}
  e^*=\mathrm{argmax}\big\{f_A(e),e\in \mathcal{E}_A\big\}.
\end{equation}

Our goal is to get a bound on the difference between the maxima of $f_A$ and $f_B$ that can be expressed through some measure of difference between $A$ and $B$ themselves.  In order to do this, we make the following assumptions.
\begin{description}
  \item[($1$)] Functions $g_j$ are continuously differentiable and there exists $M_1>0$ such that
  $|g_j^\prime(t)|\leq M_1\log(t+2)$ for $t\geq 0$.
  \item[($2$)] Function $f_B$ is convex on $U_B[-1,1]^n$.
\end{description}
Assumption (1) essentially means that Lipschitz constants of $g_j$ do not grow faster than $\log(t+2)$. The convexity of $f_B$ in assumption (2) ensures that $f_B$ achieves its maximum on $U_B\mathcal{E}_B$. In some cases (see Section~\ref{Sec:AppToComDet}), the convexity of $f_B$ can be replaced with a weaker condition, namely the convexity along a certain direction.

Let $c\in\{-1,1\}^n$ be the maximizer of $f_B$ over the set of label vectors $\{-1,1\}^n$. As a function on $U_B[-1,1]^n$, $f_B$ achieves its maximum at $U_B(c)$, which is an extreme point of $U_B[-1,1]^n$ by assumption (2). Lemma \ref{Lem:MaxFuncEst}  provides a upper bound for $f_A(c)-f_A(e^*)$.

Throughout the paper, we write $\|\cdot\|$ for the $l_2$ norm (i.e., Euclidean norm on vectors and the spectral norm on matrices), and $\|\cdot\|_F$ for the Frobenius norm on matrices. Note that for label vectors $e, c \in\{-1,1\}^n$, $\|e-c\|^2$ is four times the number of nodes on which $e$ and $c$ differ.

\begin{lemma}\label{Lem:MaxFuncEst}
If assumptions (1) and (2) hold then there exists a constant $M_2>0$ such that
\begin{equation}\label{Ineq:MaxFuncEst}
  f_T(c)-f_T(e^*)\leq M_2 n\log(n)\big( \|B\| \cdot \|U_A-U_B\|+ \|A-B\|\big),
\end{equation}
where $T$ is either $A$ or $B$.
\end{lemma}
The proof of Lemma~\ref{Lem:MaxFuncEst} is given in Appendix~\ref{AppendixA}.
To get a bound on $\|c-e^*\|$, we need further assumptions on $B$ and $f_B$.
\begin{description}
  \item[($3$)] There exists $M_3>0$ such that for any $e\in\{-1,1\}^n$, $$\|c-e\|^2\leq M_3\sqrt{n}\|U_B(c)-U_B(e)\|.$$
  \item[($4$)] There exists $M_4>0$ such that for any $x\in U_B[-1,1]^n$
  $$\frac{f_B(U_B (c))-f_B(x)}{\|U_B(c)-x\|}\geq\frac{\max f_B-\min f_B}{M_4\sqrt{n}}.$$
\end{description}

Assumption (3) rules out the existence of multiple label vectors with the same projection $U_B(c)$. Assumption (4) implies that the slope of the line connecting two points on the graph of $f_B$ at $U_B(c)$ and at any $x\in U_B[-1,1]^n$ is bounded from below. Thus, if $f_B(x)$ is close to $f_B(U_B(c))$ then $x$ is also close to $U_B(c)$. These assumptions are satisfied for all functions considered in Section~\ref{Sec:AppToComDet}.

\begin{theorem}\label{Thm:GenMetdCons}
If assumptions (1)--(4) hold, then there exists a constant $M_5$ such that
$$\frac{1}{n} \|e^*-c\|^2 \leq \frac{M_5 n \log n\big( \|B\| \cdot \|U_A-U_B\|+ \|A-B\|\big)}{\max f_B-\min f_B}.$$
\end{theorem}

Theorem~\ref{Thm:GenMetdCons} follows directly from Lemma~\ref{Lem:MaxFuncEst} and Assumptions (3) and (4). When $A$ is a random matrix,  $B=\mathbb{E}[A]$,  and $U_A$ contains the leading eigenvectors of $A$, a standard bound on $\|A-B\|$ can be applied (see Lemma~\ref{Lem:OlivRest}), which in turn yields a bound on $\|U_A-U_B\|$ by the Davis-Kahan Theorem. Under certain conditions, the upper bound in Theorem~\ref{Thm:GenMetdCons} is of order $o(n)$ (see Section~\ref{Sec:AppToComDet}), which shows consistency of $e^*$ as an estimator of $c$ (i.e., the fraction of mislabeled nodes goes to 0 as $n \rightarrow \infty$).

\subsection{The choice of low rank approximation}\label{Subsec:ApproxAdMat}
An important step of our method is replacing the ``population'' space $U_B$ with the ``data'' approximation $U_A$. As a motivating example, consider the case of the SBM,  with $A$ the network adjacency matrix and $B=\mathbb{E}[A]$.
When the network is relatively dense, eigenvectors of $A$ are good estimates of the eigenvectors of $B=\mathbb{E}[A]$ (see \cite{O'Rourke.et.al.2013} and \cite{Lei&Rinaldo2015} for recent improved error bounds).  Thus, $U_A$ can just be taken to be the leading eigenvectors of $A$.
However, when the network is sparse, this is not necessarily the best choice, since the leading eigenvectors of $A$ tend to localize around high degree nodes, while leading eigenvectors of the Laplacian of $A$ tend to localize around small connected components \cite{Mihail&Papadimitriou2002, Chaudhuri&Chung&Tsiatas2012, qin2013regularized, Le&Levina&Vershynin2015}.  This can be avoided by regularizing the Laplacian in some form;   we follow the algorithm of \cite{Amini.et.al.2013}; see also \cite{Joseph&Yu2013, Le&Levina&Vershynin2015} for theoretical analysis.    This works for both dense and sparse networks.

The regularization works as follows.  We first add a small constant $\tau$ to each entry of $A$, and then approximate $U_B$ through the Laplacian of $A+\tau\mathbf{1}\mathbf{1}^T$ as follows.
Let $D_\tau$ be the diagonal matrix whose diagonal entries are sums of entries of columns of $A+\tau\mathbf{1}\mathbf{1}^T$, $L_{\tau} = D_\tau^{-1/2} (A+\tau\mathbf{1}\mathbf{1}^T) D_\tau^{-1/2}$, and $u_i$ be leading eigenvectors of $L_{\tau}$, $1\leq i\leq K$.    Since $A+\tau\mathbf{1}\mathbf{1}^T = D_\tau ^{1/2}L_{\tau}D^{1/2}_\tau$, we set the appoximation $U_A$ the be the basis of the span of $\{D^{1/2}u_i:1\leq i\leq K\}$.  Following \cite{Amini.et.al.2013},  we set $\tau=\varepsilon(\lambda_n/n)$, where $\lambda_n$ is the node expected degree of the network and $\varepsilon\in (0,1)$ is a constant which has little impact on the performance \cite{Amini.et.al.2013}.

\subsection{Computational complexity}\label{Remark:TwoComComplxty}

Since we propose an exhaustive search over the projected set of extreme points, the computational feasibility of this is a concern.    A projection of the unit cube  $U_A[-1,1]^n$ is the Minkowski sum of $n$ segments in $\mathbb{R}^m$, which, by \cite{Gritzmann1993}, implies that it has $O(n^{m-1})$ vertices of $U_A[-1,1]^n$ and they can be found in $O(n^m)$ arithmetic operations.     When $m=2$, which is the primary focus of our paper,  there exists an algorithm that can find the vertices of $U_A[-1,1]^n$ in $O(n\log n)$ arithmetic operations \cite{Gritzmann1993}.     Informally, the algorithm first sorts the angles between the $x$-axis and column vectors of $U_A$ and $-U_A$. It then starts at a vertex of $U_A[-1,1]^n$ with the smallest $y$-coordinate, and based on the order of the angles,  finds neighbor vertices of $U_A[-1,1]^n$ in a counter-clockwise order.  If the angles are distinct (which occurs with high probability), moving from one vertex to the next causes exactly one entry of the corresponding label vector to change the sign, and therefore the values of $h_{A,j}(e)$ in \eqref{Eq:QuadrFun} can be updated efficiently. In particular, if $A$ is the adjacency matrix of a network with average degree $\lambda_n$, then on avarage, each update takes $O(\lambda_n)$ arithmetic operations, and given $U_A$, it only takes $O(n\lambda_n \log n)$ arithmetic operations to find $e^*$ in \eqref{Eq:GenMethOutp}.    Thus the computational complexity of this search for two communities is not at all prohibitive -- compare to the computational complexity of finding $U_A$ itself, which is at least $O(n\lambda_n \log n)$ for $m=2$.

\subsection{Extension to more than two communities}\label{Subsec:MultiCom}

Let $K$ be the number of communities and $S$ be an $n\times K$ label matrix: for $1\leq i\leq n$, if node $i$ belongs to community $k$ then $S_{ik}=1$ and $S_{il}=0$ for all $l\neq k$. The numbers of edges between communities defined by \eqref{Eq:Omatr} are entries of $S^TAS$. Let $B = \sum_{i=1}^K \rho_i\bar{u}_i \bar{u}_i^T$ define the eigendecomposition of $B$. The population version of $S^TAS$ is
\begin{equation*}
  S^TBS = S^T\left(\sum_{j=1}^K \rho_j \bar{u}_j \bar{u}_j^T\right)S = \sum_{j=1}^K\rho_j \left(S^T\bar{u}_j\right)\left(S^T\bar{u}_j\right)^T.
\end{equation*}
Let $U_B$ be the $K\times n$ matrix whose rows are $\bar{u}_j^T$. Then $S^TBS$ is a function of $U_B S$.   We approximate $U_B$ by $U_A$ described in Section~\ref{Subsec:ApproxAdMat}. Let $\tilde{S}$ be the the first $K-1$ columns of $S$. Note that the rows of $S$ sum to one, therefore $U_AS$ can be recovered from $U_A\tilde{S}$. Now relax the entries of $\tilde{S}$ to take values in $[0,1]$, with the row sums of at most one. For $1\leq i\leq n$ and $1\leq j\leq K-1$, denote by $V_{ij}$ the $K\times (K-1)$ matrix such that the $j$-th column of $V_{ij}$ is the $i$-th column of $U_A$ and all other columns are zero.
Then
\begin{equation*}
  U_A\tilde{S} = \sum_{i=1}^n \sum_{j=1}^{K-1} \tilde{S}_{ij} V_{ij}.
\end{equation*}
Since $\sum_{j=1}^{K-1} \tilde{S}_{ij}\leq 1$, $\sum_{j=1}^{K-1} \tilde{S}_{ij} V_{ij}$ is a convex set in $\mathbb{R}^{K\times (K-1)}$, isomorphic to a $K-1$ simplex. Thus, $U_A\tilde{S}$ is a Minkowski sum of $n$ convex sets in $\mathbb{R}^{K\times(K-1)}$. Similar to the case $K=2$, we can first find the set of label matrices $\tilde{S}$ corresponding to the extreme points of $U_A\tilde{S}$ and then perform the exhaustive search over that set.

A bound on the number of vertices of $U_A\tilde{S}$ and a polynomial algorithm to find them are derived by \cite{Gritzmann1993}.   If $d=K(K-1)$, then the number of vertices of $U_A\tilde{S}$ is at most $O\left(n^{(d-1)} K^{2(d-1)}\right)$, and they can be found in $O\left(n^d K^{(2d-1)}\right)$ arithmetic operations. presents An implementation of the reverse-search algorithm of \cite{Fukuda2004} for computing the Minkowski sum of polytopes was presented in \cite{Weibel2010} , who  showed that the algorithm can be parallelized efficiently.   We do not pursue these improvements here, since our main focus in this paper is the case $K = 2$.

config: arxiv


TITLE: How to show that $\Bbb C/(-\infty ,0]$ is simply connected space
QUESTION [0 upvotes]: I need to show that for $\Bbb C/(-\infty ,0]$ that if I have arbitrary different pathes $\gamma , \eta :[0,1] \to\Bbb C/(-\infty ,0]$ such that $\gamma(0)=\eta(0)=\alpha $ and $\gamma(1)=\eta(1)=\beta $ I have continuous homotopy $H:[0,1]^2 \to \Bbb C/(-\infty ,0]$ such that: $H(0,t) = \gamma (t),H(1,t) = \eta (t),H(s,0) = \alpha,H(s,1) = \beta$
unfortunatily my space isn`t a convex,so how do I define a proper Homotopy and proving it's continuous?

REPLY [5 votes]: The simplest way is probably to use that your domain is starshaped with respect to 1. This makes it possible to shrink any closed curve in the domain to the point 1.