TITLE: Equivalence classes in a Hilbert space
QUESTION [6 upvotes]: I'm reading something about quantum information/quantum computing theory, and I've run into a wall. I know what is meant by an equivalence class and how something can be partitioned into equivalence classes, but I need help on the following two questions:

How can a partitioning of a Hilbert space be naturally realized?
How a density operator can be seen as a equivalence class representing a range of different possible ensembles?

For the 1. I have no clue, while for the 2. I was thinking it has something to do with the equation for the expectation of some observable $\hat{A}$, $\langle \hat{A }\rangle =tr (\rho \hat{A})$, since the trace is cyclically invariant and so a unitary transformation $|\psi '\rangle \rightarrow \hat{U } |\psi \rangle$, $\hat{A'}\rightarrow \hat{U^{-1}}\hat{A}\hat{U}$, because
$$\langle \hat{A' }\rangle=tr (\rho ' \hat{A'})=tr(\hat{U^{-1}}\rho\hat{U} \hat{U^{-1}}\hat{A}\hat{U})=tr(\hat{U^{-1}}\rho \hat{A}\hat{U})=tr(\rho \hat{A}\hat{U}\hat{U^{-1}})= \langle \hat{A }\rangle$$
But the same argument works for expectation calculated via Ehrenfest's theorem.
I have looked everywhere and found nothing.

REPLY [2 votes]: In the context of physics, there are "natural" equivalence relations motivated by the following notion: mathematical objects that determine the same physics should be considered equivalent.  These equivalence relations lead to partitions of the sets on which they are defined.
Equipped with this idea, let's examine the two points you mention:

Let $\mathcal H$ be a Hilbert space.  The non-zero elements of this space can be viewed as states of a quantum system.  Two such states that differ by a nonzero complex factor should be considered equivalent because they determine the same physics (e.g. yield the same transition probabilities).  As a result, there is a physically natural equivalence relation on $\mathcal H$ defined as follows: a nonzero vector $|\psi_1\rangle$ is said to be equivalent to another nonzero vector $|\psi_2\rangle$ provided there exists a nonzero complex number $c$ for which
\begin{align}
    |\psi_1\rangle = c|\psi_2\rangle.
\end{align}
The equivalence classes determined by this relation are called rays, and the set of all such equivalence classes is called the projective Hilbert space determined by $\mathcal H$.  This set is often denoted $P(\mathcal H)$.
Let $p = (p_1, p_2, \dots)$ be a sequence of non-negative real numbers whose sum is $1$, and let $\Psi = (|\psi_1\rangle, |\psi_2\rangle, \dots)$ be a sequence of vectors of unit length in a Hilbert space $\mathcal H$.  A pair $\mathscr E = (p,\Psi)$ of such sequences is called an ensemble.  This mathematical definition can be thought of as corresponding to $N\gg 1$ quantum systems such that $N_k = p_k N$ of them are prepared in the pure state $|\psi_k\rangle$.  Therefore, each $p_k$ can be thought of as the probability that one of the $N$ systems is prepared in the pure state $|\psi_k\rangle$.  To every ensemble $\mathscr E$, we can associate a density operator as follows:
\begin{align}
    \rho_\mathscr E = \sum_kp_k|\psi_k\rangle\langle\psi_k|.
\end{align}
We say that an ensemble $\mathscr E_1$ is equivalent to an ensemble $\mathscr E_2$ provided they determine the same density operator:
\begin{align}
    \rho_{\mathscr E_1} = \rho_{\mathscr E_2}.
\end{align}
The idea behind this definition is that the density operator associated with each ensemble determines all of the physics associated with it (e.g. ensemble averages of observables), so from a physical point of view, ensembles yielding the same density operator shouldn't be considered distinct.


text:
We generalize the linear manifold learning problem of~\eqref{Eqn:LRA}, as a
nonlinear manifold learning as follows:
For a given data-set lying on the high-dimensional manifold, learn a manifold,
and the corresponding mapping, on which the solution can be expressed as a
low-rank linear decomposition.
The map from the high-dimensional physical manifold to the learned manifold is
denoted by $\mapEultoALEnull$ and the inverse by $\mapALEtoEulnull$.
In the finite-dimension matrix form where
$\mapEultoALEnull: \realsetT{N}{K} \rightarrow \realsetT{N}{K}$ and
$\mapALEtoEulnull: \realsetT{N}{K} \rightarrow \realsetT{N}{K}$,
the minimization problem has the following
form:

\begin{equation}\label{Eqn:LaMIN1}
\begin{aligned}
& \underset{}{\minimize}
& &
\NormF{
	\bm{M} - \mapALEtoEul{\snapshotr}
}.
\end{aligned}
\end{equation}

In this case, $\snapshotr=\sys{U} \sys{V}$ is the linear decomposition the data
on the learned manifold, where $\sys{U} \in \realsetT{N}{\sizeROM_r}$ and
$\sys{V}
\in\realsetT{\sizeROM_r}{K}$.
In principle, the compression of the data on the learned manifold is lossless.
For the compression to be successful $\sizeROM_r \ll N$ and $\sizeROM_r \ll K$,
and it outperforms~\eqref{Eqn:LRA}
if and only if $\sizeROM_r < k$.

In this formulation, both the high-dimensional snapshots and its
low-dimensional representation on the learned manifold (latent variables) are
stored in a matrix.
In contrast to most  machine vision tasks dealing with images, the
data does not necessarily lie on a uniform Cartesian grid.
This is important since many of the PDEs are discretized on unstructured
computational grids, while many of the traditional machine learning tools
are developed for uniform Cartesian grids representing an image.
Often, the snapshot matrix of $\snapshot$ is defined on a constant grid (in
physics: Eulerian framework) and $\snapshotr$, by construct, is associated to
the snapshots of latent variables on a parameter/time-varying grid (in physics:
arbitrary Lagrangian Eulerian framework).
Therefore, \eqref{Eqn:LaMIN1} can be interpreted as a registration task, that
minimizes the Kolmogorov \nwidth\ of the snapshots of the latent variables on
the learned parameter/time-varying grid.

\subsection{Diffeomorphism and interpolation}
\label{sec:diffeomorphism}

We impose diffeomorphism as a condition on the mapping to and from the learned
manifold:
By definition, a map, $\mapEultoALEnull$, is said to be diffeomorphic if
$\mapEultoALEnull$ and $\mapALEtoEulnull$ are
differentiable~\citep{Modersitzki_2009}.
Bijectivity (i.e. one to oneness) and smoothness guarantee diffeomorphism.
Therefore, by enforcing the map to be diffeomorphic, we ensure existence and
uniqueness of $\snapshotr$, given a $\snapshot$ and vice versa.
Bijectivity is achieved by ensuring that volume of all the cells remain
strictly positive.
A negative cell volume leads to the indeterminate derivative of the state
parameter, which can be seen as a ``tear'' in an image.
Smoothness of the grid is maintained by penalizing abrupt changes of
the grid volume, both in space and parameter/time.
Any of the commonly used interpolation schemes between the constant grid and
the learned grid can be utilized in this setting.

\subsection{Low-rank registration}

So far, we only have tied the mapping to a time/parameter-varying grid, and have
suggested that the mapping between the constant and the learned grid is simply
an interpolation between them.
In this section, the construction of the grid in the parameter/time space is
discussed.

There are two general approaches to formulate the grid deformation in a
registration problem.
In the first class of approaches, the grid nodes are controlled as the solution
of the a minimization problem.
Diffeomorphism can then be achieved by enforcing  a constraint on the
determinant of the deformation gradient: be strictly positive for all grid
cells.
This approach leads to a high-dimensional optimization problem which its
nonlinearity and ill-posedness makes it computationally
challenging~\cite{Mang_OE_2018}.
In the second class of approaches, the mapping is the solution of a transport
equation, i.e. flow fields, as in diffeomorphic dimensionality reduction
\citep{Walder_NIPS_2008}.
Interestingly, in some special cases, a similar transport equation arises where
the frame of references is changed from the Eulerian to the Lagrangian
viewpoint, i.e. by solving the hyperbolic PDEs on the corresponding
characteristic lines.
This change of the reference is proven to be efficient in reduced order
modeling  of convection dominated PDEs~\citep{Mojgani_2017, Lu_JCP_2020}.
The existence of a low-rank near-optimal grid for many of the
convection-dominated PDEs are demonstrated; However, the extension of this
change of frame for any arbitrary systems is not straightforward.
We leverage this premise in a data-driven setting.
In our proposed method the coordinates of the  grid at the $n^\textit{th}$
parameter or time-step is constructed as:

\begin{equation}\label{Eqn:grid}
\sysn{x}{\timecounterd} := \basisgridU \basisgridvn,
\end{equation}

where $\basisgridvn \in \realsetO{r}$ is the $n^{\textit{th}}$ column of
$\basisgridV$ and
$\basisgridU \basisgridV$ is a rank-$\sizeGridROM$ matrix,
$\basisgridU \in \realsetT{N}{\sizeGridROM}$ and $\basisgridV \in
\realsetT{\sizeGridROM}{K}$, that represents the evolution of the
parameter/time-varying grid, on which the low-dimensional latent variables lie.
The rank-$\sizeGridROM$ grid is then learned in~\eqref{Eqn:LaMIN1}.
The latent variables can be interpreted as the evolution of the state
parameters on the low-rank approximation of how the information travels, i.e.
characteristic lines of the hyperbolic PDEs.
This is one of the key elements of the proposed method, which greatly
reduces the size of the optimization compared to existing registration-based
methods, such as~\cite{Taddei_SIAM_2020}. More importantly, it results in
unprecedented predictive capabilities, i.e. accuracy beyond the training range.

\subsection{Implementation}
\label{sec:implementation}

In this section, we summarize the elements of the proposed algorithm and make
some clarifications on implementation of the method.
As illustrated in Fig.~\ref{fig:idea}, the procedure is designed to learn a
low-rank grid, $\basisgridU \basisgridV$, on which the snapshot of the data,
$\snapshotr = \mapEultoALE{\snapshot}$, is low-rank.

\input{method_schematic}

The final minimization problem has the following form:

\begin{equation}\label{Eqn:ResMin_ALE_smooth}
\begin{aligned}
& \underset{\basisgridU,
			\basisgridV}{\minimize}
& &
\NormF{
	\bm{M} - \mapALEtoEul{\bm{U}\bm{V}}
} +
\NormF{
	\bm{\Gamma}_1   \basisgridU
} +
\NormF{
	\basisgridV   \ \transpose{\bm{\Gamma}_2}
}, \\
& \text{subject to}
& & \sysn{v}{n}\geq v_{\text{min}}, \text{ for } n=1,\ldots,K, \\
&&& \sysn{x}{n}|_{\partial \Omega} = \bm{x}|_{\partial \Omega}, \text{ for }
n=1,\ldots,K,
\end{aligned}
\end{equation}

where
${\bm{\Gamma}}_1 \in \realsetT{N}{N}$
and
${\bm{\Gamma}}_2 \in \realsetT{K}{K}$
are Tikhonov matrices designed to promote grid smoothness.
Also
$ \sysn{v}{\timecounterd} \in \realsetO{N-1}$
is a vector of cell volumes of the parameter/time-varying grid at the
$n^{\text{th}}$ parameter/time step,
$v_{\min}$ is the minimum admissible cell volume, and
$\sysn{x}{\timecounterd} |_{\partial \Omega}$
and
$\bm{x}|_{\partial \Omega}$
are boundary points of the learned grid and the constant grid, respectively.
The appropriate Tikhonov matrices and the minimum cell volumes are
hyper-parameters and problem dependent.

Moreover, for practical reasons, a weak constraint on the rank reduction is
chosen.
While~\eqref{Eqn:LaMIN1} implies minimizing over the rank of $\snapshotr$, in
many cases, the solution of the minimization for a preset size of the
decomposition is preferred.
We assume $\snapshotr=\sys{U} \sys{V}$, where
$\sys{U} \in \realsetT{N}{\sizeROM_r}$,
$\sys{V} \in\realsetT{\sizeROM_r}{K}$, and
$\sizeROM_r \ll N $ , $\sizeROM_r \ll K $.
Moreover, to reduce the size of the optimization problem, $\basisgridU$ and
$\basisgridV$ are uniformly down-sampled, however, the objective is
evaluated on the fine grid.

To interpolate the snapshots between the two sets of grid, we simply utilize a
$p$-degree polynomial interpolation scheme.
This choice innately incorporates a sparsity pattern into the mapping.
While the latent space representation of a data-point on the learned grid using
a nearest-neighbor interpolation only requires one data-point on the constant
grid, a $p$-degree polynomial interpolation requires $p-1$ entries of the input
vector.
This, in principle, leads to a great reduction in the size the optimization
problem compared to the traditional neural networks, where there is no
\apriori~assumption on the structure of the connectivity between the nodes.

Finally, the proposed mapping can be utilized as an auto-encoder layer in a
neural network (Fig.~\ref{fig:architecture}).
This additional layer, greatly improves accuracy and training cost of neural
network based models.
The algorithm to train the proposed physics-aware registration based
auto-encoder is summarized in Alg.~\ref{alg:alg}.

\input{schematic_autoencoder}

\input{Alg}

config: arxiv


TITLE: Some questions about variations of fixed point method
QUESTION [2 upvotes]: I'm doing some excercises in Fixed Point Iteration methods with Matlab. I have to find roots for $f(x)=e^x -x -1.9\cos x$ by using $x_{n+1}=g(x_n)$. I know how to choose $g(x)$ such that I can find both roots. The following part of the exercise is as follows:
In general we can rewrite $f(x)=0$ to $x=g(x)$ with $g(x)=x+cf(x)$, where $c\neq 0$ is a constant.
I am given the function $f(x)=e^x-x-1.9\cos x$ , and I have to determine values for $x_0$ and $c$ such that the sequences obtained for $x_{n+1}=g(x_n)$ both converge quickly, to  roots $x_{r1}$ and $x_{r_2}$.
I'm told that this can be obtained by picking a point $x_0$ close to the zero and setting $g'(x_0)=0$ by an appropriate choice of $c$.  My question is, what is this all about? What should I do?
Then, another part says

Increase the order of convergence of the fixed point method $x_{n+1}=x_n+cf(x_n)$ by changing $c$ each iteration instead of using a constant value.

How can I do that? What do they mean?

REPLY [2 votes]: A central tenet in calculus is that we can understand the local behavior of a function near a point by examining the linear approximation of the function at that point.  Thus, let's begin by exploring the behavior of iteration near fixed points of linear functions.
To this end, consider the function $\ell(x) = x_f + m(x-x_f)$.  This clearly has a fixed point at $x_f$.  Now, suppose that we iterate this function starting from some point $x_0$.  Note that
$$\ell(\ell(x_0)) = x_f + m((x_f + m(x_0-x_f)) - x_f) = x_f + m^2 (x_0 - x_f).$$
More generally,
$$\ell^p(x_0) = x_f + m^p (x_0 - x_f).$$
As a result, we see quite easily that the orbit of $x_0$ tends towards $x_f$ iff $|m|<1$.  Furthermore, the smaller the value of $m$, the faster the convergence.  The convergence is fastest (instantaneous, in fact) when $m=0$.
Now, let's consider the iteration of a differentiable function $g$ near a fixed point $x_f$, thus $g(x_f)=x_f$. Suppose we iterate $g$ starting from some point $x_0$ near $x_f$.  By analogy with the linear example we just examined, we might expect $x_f$ to be attractive if the slope of $g$ is less than $1$ in absolute value at the point $x_f$.  More precisely, we need $|g'(x_f)|<1$.
Now, in your example, you have a given function $f(x)=e^x-x-1.9\cos(x)$ and you'll generate $g_c$ by setting $g_c(x)=x+c\,f(x)$.  Since you have a computational tool in your hands, I suggest that you examine the graph of $g_c$ together with the graph of $y=x$ to help you choose a good value of $c$.  For example, here's the graph of $y=g_{-1/2}(x)$ together with the graph of $y=x$.

The points of intersection correspond to the roots of $f$.  It appears that one such point is around $0.7$ or so and that iteration of $g_{-1/2}$ starting near there should converge to that fixed point.  It does appear, though, that you could pick a value of $c$ that is better than $-1/2$.  Note that it is important to plot the graph in it's correct aspect ratio to get a good feel for the magnitude of the derivative.
Finally, if you start with a good $c$ value, then refinement should not be necessary.  I guess the idea, though, is choose $c$ at the $i^{\text{th}}$ step so that $g_c'(x_i)=0$.  Since $x_i$ is close to $x_f$, we'd then expect $g_c'(x_f)$ to be close to zero.


TITLE: Find, $\sum_{k=0}^{n}4^k \binom{n}{k}$
QUESTION [3 upvotes]: Reading through my textbook I came across the following problem, and I am looking for some help solving it. I believe I have done the workings correctly but I just wanted to make sure as it seemed a little to easy.  Find,  $$\sum_{k=0}^{n}4^k \binom{n}{k}$$ Consider the expansion $(1+x)^n$ using binomial theorem.  $$(1+x)^n = \sum_{k=0}^{n} x^k \binom{n}{k}$$ Then substitute $x = 4$. That should lead you to the answer $5^n$. Therefore $$\sum^{n}_{k=0}4^k\binom{n}{k} = 5^n$$

REPLY [1 votes]: Yep it's absolutely correct. You could have treated it as
$$\sum_{k=0}^n \binom {n}{k} 4^k=\sum_{k=0}^n \binom {n}{k} 1^{n-k} 4^k=(1+4)^n=5^n$$


TITLE: How this trade-off has been calculated for Regularized least-squares in convex-optimization boyd book
QUESTION [1 upvotes]: I am reading this topic of boyd book from convex optimization, but the following division i-e trade-off least square and l2 norm are difficult to understand for me. If kindly someone can explain equation, that how it has been calculated. Your guidance will be appreciated. Regards,

REPLY [1 votes]: My apologies, please ignore my question. I have solved my problem. I am just posting the answer in case someone needed. In case the question is too irrelevant here, it can be deleted. Regards

REPLY [0 votes]: The solution to this "multi-objective" task is known to be $A^\dagger \,b$ with the Moore-Penrose pseudoinverse $A^\dagger$. If $A$ is injective, we have
$$A^\dagger b = (A^* A)^{-1} A^* b.$$
In case $A$ is surjective, we have
$$A^\dagger b = A^* (A\, A^*)^{-1} b$$
In the general case, one may apply Tikhonov regularization:
$$A^\dagger \,b = \lim_{\lambda \searrow 0} (A^*A + \lambda)^{-1} A^\intercal  b = \lim_{\lambda \searrow 0} A^* (A\, A^* + \lambda)^{-1} b.$$
See also here.


TITLE: f, h cont diff. Find necessary and sufficient conditions for these functions to be first-order approximations of each other at the point (0,0).
QUESTION [0 upvotes]: Suppose that the functions $f: \mathbb R^2 \to \mathbb R$ and $h: \mathbb R^2 \to \mathbb R$ are continuously differentiable. Find necessary and sufficient conditions for these functions to be first-order approximations of each other at the point (0,0).

REPLY [0 votes]: See https://en.wikipedia.org/wiki/Order_of_approximation#First-order.
First-order approximation means coincidence of functions and first derivatives in the point, so
$$f(0,0) = h(0,0)$$
$$\cdots = Df(0,0) = Dh(0,0) = \cdots$$
where you can write $Df(0,0)$, $Dh(0,0)$ using partial derivatives...


TITLE: Question about some properties of combinatorial structures
QUESTION [2 upvotes]: Consider $\mathcal A$ as the set of perfect matchings in the complete bipartite graph $K_{n,n}$ and let  $i$ be an edge of $K_{n,n}$.
Let
$$
B_i=\{a\in \mathcal A: \hbox{matching }a\hbox{ has edge }i\}.
$$
Clearly $\frac{|\mathcal A|}{|B_i|}=\frac{n!}{(n-1)!}=n$, which is $poly(n)$ and which is independent of $i$.
I have the following question: For which combinatorial structures (other than perfect matchings) it holds that $\frac{|\mathcal A|}{|B_i|}$ is independent of $i$? Is there any name for this property?

REPLY [0 votes]: Let $K_{n,n}$ be the complete bipartite graph with left vertex set $a_j, j=1,\ldots,n$ and right vertex set $b_j, j=1, \ldots, n$. There is a 1-1 correspondence between perfect matchings in $K_{n,n}$ and permutations in $S_n$. For example, the set of perfect matchings that contain the edge $(a_i,b_j)$ corresponds to the set of permutations in $S_n$ that map element $i$ to element $j$.  It's clear this set has $(n-1)!$ permutations.
In general if a group $G$ acts transitively on a set $X$ of cardinality $n$, then the set of elements in the group that map an element $i$  to an element $j$ in $X$ has the same cardinality as the set of elements in the group that map the element $i$ to itself, and this cardinality is equal to $|G|/|X|=|G|/n$ due to the orbit-stabilizer lemma.  Thus, $|G|$ divided by $|G|/|X|$ equals $|X|=n$, which happens to be polynomial in $n$.
Since $S_n$ is 2-transitive, the set of permutations in $S_n$ that map $i_1,i_2$ to $j_1,j_2$, respectively, is $(n-2)$!, and the ratio of $|S_n|$ to this quantity is a quadratic, hence also a polynomial in $n$.  This corresponds to the number of perfect matchings in $K_{n,n}$ that contain a chosen set of two independent edges.


TITLE: If $A⊆P_1\cup P_2$, then $A⊆P_1$ or $A⊆P_2$.
QUESTION [2 upvotes]: In a commutative ring $R$, let $A$ be an ideal of $R$ and $P_1$, $P_2$ be prime ideals. If $A⊆P_1\cup P_2$, then $A⊆P_1$ or $A⊆P_2$.
I suppose $x_1\in A-P_1$ and $x_2\in A-P_2$ then $x_1\in P_2$, $x_2\in P_1$, and $x_1x_2\in P_1\cap P_2$. But I don't know what's the contradiction. Any suggestion? Thanks.

REPLY [6 votes]: HINT: Let $x=x_1+x_2$; if $x\in P_1$, then $x_1=x-x_2\in P_1$, so $x\notin P_1$; can you see a contradiction coming?
Added: Note that the suggested argument does not actually use the primality of $P_1$ and $P_2$. The generalization of this result to the union of more than two ideals does require that the ideals be prime, however.


TITLE: Prove that a function from a metric space into [0,1] is continuous and real valued.
QUESTION [0 upvotes]: $(M,d)$ is a metric space and $X$ is a subset of $M$. define $d(x,X) = \inf \{d(x,y)| y \epsilon X\}$
A and B are closed subsets of M such that $A \cap B = \phi$
a. Prove that $$g(x) = \frac{d(x,A)}{d(x,A) + d(x,B)}$$ is continuous from M into [0,1].
b. Also prove that there exists open subsets $U,V$ such that $A \subset U$ and $B \subset V$ and $U \cap V = \phi$
The question had 2 previous parts where I had to prove that $f(x) = d(x,X)$ is continuous, I managed to prove that but am fumbling with these. $\\\\\\\\$

REPLY [0 votes]: Continuity is quite clear one you know that $f(x) = d(x,A)$ is continuous, and so is $f'(x) = d(x,B)$.
Check that $A \cap B = \emptyset$ implies that $d(x,A) + d(x,B) > 0$.
This uses that $x \in \overline{X}$ iff $d(x,X) = 0$ for subsets of $X$.
So we have a quotient of continuous functions (you need that division and addition are continuous on the real numbers), which is continuous.
b) follows from pulling back disjoint neighbourhoods of $0$ and $1$ under this $g$.