text:
\chapter{The Zakai Equation}

\noindent Let $X_t\in\mathcal S$ be a Markov process with generator $Q$. Let the domain of $Q$ be denoted by $\mathcal B(Q)$, and let $\mathcal B_b(Q)$ denote the subset of bounded functions in $\mathcal B(Q)$. For any function $g(x)\in\mathcal B_b(Q)$ we have the following limit:
\[\frac{\mathbb E[g(X_{t+\Delta t})|X_t=x]-g(x)}{\Delta t} \rightarrow Qg(x)\]
as $\Delta t\searrow 0$, for any $x\in\mathcal S$. If $Q$ is densely-defined and its resolvent set includes all positive real numbers, then the Hille-Yosida theorem applies, allowing us to write the the distribution of $X_t$ with a contraction semi-group. In these notes we assume that such conditions hold and that the transition density/mass is generated by an operator semigroup denoted by $e^{Q^*t}$.

A standard nonlinear filtering problem in SDE theory assumes that $X_t$ is unobserved and that a process $Y_t$ is given by an SDE
\begin{eqnarray}
\label{eq:dY}
dY_t&=&h(t,X_t)dt+\gamma dW_t\qquad\hbox{observed}
\end{eqnarray}
where $W_t$ is an independent Wiener process, $\gamma>0$ and we assume that $h(t,\cdot)$ is bounded for all $t<\infty$.

The pair $(X_t,Y_t)$ is an HMM for which filtering can be used to find the posterior distribution. Let $\mathcal F_t^Y = \sigma\{Y_s:s\leq t\}$, and for any measurable function $g(x)$ let
\[\hat g_t = \mathbb E[g(X_t)|\mathcal F_t^Y].\]
The posterior expectation of $\hat g_t$ is ultimately what is desired from filtering, but the methods for obtaining the posterior distribution are quite involved. The discrete Bayesian tools that we've used in earlier lectures cannot be used here because we are in a continuum that does not allow us to break apart the layers of the HMM. Instead, we will exploit well-known ideas from SDE theory to obtain the differentials for the filtering distribution. In particular, we will use the Girsanov theorem to obtain the Zakai equation.

\section{Discrete Motivation from Bayesian Perspective}
\label{eq:discreteZakai}
In their book, Karatzas and Shreve \cite{K-S} give a discrete motivation for how the Girsanov theorem works. In a similar fashion, we consider a discrete problem and then construct a change of measure from the ratio of the appropriate densities. We then show how it is analogous to its continuous-time counterpart, and leads to a discrete approximation of the Zakai equation.

To do so, we start by considering a discrete-time analogue of (\ref{eq:dY}),
\[Y_n=Y_{n-1}+h(t_{n-1},X_{n-1})\Delta t+\gamma\Delta W_{n-1},\]
and assume that the unconditional distribution of $X_t$ is a density for all $t\geq 0$ (the same idea will be applicable when $X_t$'s distribution has a mass function). We can easily apply Bayes theorem to obtain the filtering distribution on a Borel set $\mathcal A$:
\[\pi_n(\mathcal A) = \frac{1}{c_n}\int\psi_n(v)e^{Q^*\Delta t}(\mathcal A|v)\pi_{n-1}(dv)\]
where $e^{Q^*\Delta t}$ represents kernel of $X_t$'s transition densities, the likelihood function is
\[\psi_n(v) = \exp\left\{-.5\left(\frac{\Delta Y_{n-1}-h(t_{n-1},v)\Delta t}{\gamma\sqrt{\Delta t}}\right)^2\right\},\qquad\hbox{with }\Delta Y_{n-1}=Y_n-Y_{n-1},\]
and $c_n$ is a normalizing constant. The Lebesgue differentiation theorem can be applied to obtain the density of the posterior,
\[\frac{1}{|\mathcal A|}\pi_n(\mathcal A)\rightarrow \pi_n(dx) = \frac{1}{c_n}\int\psi_n(v)e^{Q^*\Delta t}(dx|v)\pi_{n-1}(dv)\]
when $\mathcal A$ shrinks nicely to $\{x\}$.

Keeping this discrete model and filter in mind, let's shift our attention to a joint density function of all observations and a possible path $(x_0,x_1,\dots,x_n)$ taken by $(X_0,X_1,\dots,X_n)$,
\[dp_n\doteq\mathbb P(Y_0,Y_1,\dots,Y_n;dx_0,dx_1,\dots,dx_n)\]

\[ = \mathbb P(Y_0,Y_1,\dots,Y_n|x_0,x_1,\dots,x_n)\mathbb P(dx_0,dx_1,\dots,dx_n)\]

\[=\left(\prod_{\ell=0}^{n-1}\psi_\ell(x_\ell)\right)\times \mathbb P(dx_0,dx_1,\dots,dx_n)=\left(\prod_{\ell=0}^{n-1}e^{-.5\left(\frac{\Delta Y_\ell-h(t_\ell,x_\ell)\Delta t}{\gamma\sqrt{\Delta t}}\right)^2}\right)\times \mathbb P(dx_0,dx_1,\dots,dx_n)\]

\[=e^{-.5\sum_{\ell=0}^{n-1}\left(\frac{\Delta Y_\ell-h(t_\ell,x_\ell)\Delta t}{\gamma\sqrt{\Delta t}}\right)^2}\times \mathbb P(dx_0,dx_1,\dots,dx_n)\]
where $\mathbb P(dx_0,dx_1,\dots,dx_n)$ can be obtained using the exponential of $Q^*$.

Next, consider an equivalent measure in $\tilde{\mathbb P}$ where $\Delta Y_n/\gamma$ is Brownian motion independent of $X_n$, and the law of $X_n$ remains the same. Under this new measure the joint density function is
\[d\tilde p_n\doteq\tilde{\mathbb P}(Y_0,Y_1,\dots,Y_n;dx_0,dx_1,\dots,dx_n) = \tilde{\mathbb P}(Y_0,Y_1,\dots,Y_n)\tilde{\mathbb P}(dx_0,dx_1,\dots,dx_n)\]

\[=\left(\prod_{\ell=0}^{n-1}e^{-.5\left(\frac{\Delta Y_\ell}{\gamma\sqrt{\Delta t}}\right)^2}\right)\times \mathbb P(dx_0,dx_1,\dots,dx_n)\]

\[=e^{-.5\sum_{\ell=0}^{n-1}\left(\frac{\Delta Y_\ell}{\gamma\sqrt{\Delta t}}\right)^2}\times \mathbb P(dx_0,dx_1,\dots,dx_n).\]
The ratio of these densities is written follows:
\[\frac{dp_n}{d\tilde p_n} \doteq M_n\Big|_{\mathcal F_n^Y} = \exp\left\{\sum_{\ell=0}^{n-1}\frac{h(t_\ell,x_\ell)\Delta Y_\ell}{\gamma^2}-\frac{1}{2}\sum_{\ell=0}^{n-1}\frac{h^2(t_\ell,x_\ell)\Delta t}{\gamma^2}\right\}\]
which is the likelihood ratio of any path for the discrete observation model. It is also the discrete analog of the exponential martingale that we use in the Girsanov theorem. Furthermore, we can use $M_n$ to rewrite the filtering expectation in terms of the alternative measure,
\[\mathbb E[g(X_n)|\mathcal F_n^Y] = \frac{\int g(x_n)dp_n}{\int dp_n}=\frac{\int g(x_n)M_nd\tilde p_n}{\int M_nd\tilde p_n}=\frac{\tilde{\mathbb E}[g(X_n)M_n|\mathcal F_n^Y]}{\tilde{\mathbb E}[M_n|\mathcal F_n^Y]},\]
and if we define $\phi_n[g] = \tilde{\mathbb E}[g(X_n)M_n|\mathcal F_n^Y]$ we can write the filtering expectation as
\[\hat g_n=\mathbb E[g(X_n)|\mathcal F_n^Y] = \frac{\phi_n[g]}{\phi_n[1]}\]
for any function $g(x)\in\mathcal B_b(Q)$.

It turns out to be advantageous to analyze under $\tilde{\mathbb P}$-measure because the dynamics $\phi_n$ are linear when we move to a continuum of observations. To get a sense of the linearity, consider the following discrete expansion for small $\Delta t$,
\[\phi_{n+1}[g] = \tilde{\mathbb E}[g(X_{n+1})M_{n+1}|\mathcal F_{n+1}^Y]\]

\[=\tilde{\mathbb E}\left[g(X_{n+1})\left(1+\frac{h(t_n,X_n)}{\gamma^2}\Delta Y_n\right)M_n\Big|\mathcal F_{n+1}^Y\right]+o(\Delta t)\]

\[=\tilde{\mathbb E}\left[g(X_{n+1})M_n\Big|\mathcal F_{n+1}^Y\right]+\tilde{\mathbb E}\left[g(X_{n+1})\left(\frac{h(t_n,X_n)}{\gamma^2}\right)M_n\Big|\mathcal F_{n+1}^Y\right]\Delta Y_n+o(\Delta t)\]
because $M_{n+1}=\left(1+\frac{h(t_n,X_n)}{\gamma^2}\Delta Y_n\right)M_n+o(\Delta t)$ by a discrete interpretation of It\^o's lemma, and $\Delta Y_n$ is $\mathcal F_{n+1}^Y$-measurable. Now, because $X$ is independent of $Y$ under $\tilde{\mathbb P}$, the conditioning up to time $n+1$ is superfluous and we can reduce it down to time $n$,
\[=\tilde{\mathbb E}\left[g(X_{n+1})M_n\Big|\mathcal F_n^Y\right]+\tilde{\mathbb E}\left[g(X_{n+1})\left(\frac{h(t_n,X_n)}{\gamma^2}\right)M_n\Big|\mathcal F_n^Y\right]\Delta Y_n+o(\Delta t).\]
Then we can again exploit the independence of $X$ from $Y$ under $\tilde{\mathbb P}$ and use an approximation of $X$'s backwards operator.

\[=\tilde{\mathbb E}\left\{\tilde{\mathbb E}\left[g(X_{n+1})M_n\Big|\mathcal F_n^Y\vee X_n\right]\Bigg|\mathcal F_n^Y\right\}\qquad\qquad\qquad\qquad\qquad\qquad\qquad\]

\[\qquad\qquad\qquad\qquad\qquad+\tilde{\mathbb E}\left\{\tilde{\mathbb E}\left[g(X_{n+1})\left(\frac{h(t_n,X_n)}{\gamma^2}\right)M_n\Big|\mathcal F_n^Y\vee X_n\right]\Bigg|\mathcal F_n^Y\right\}\Delta Y_n+o(\Delta t)\]

\[=\tilde{\mathbb E}\left\{(I+Q\Delta t)\tilde{\mathbb E}\left[g(X_n)M_n\Big|\mathcal F_n^Y\vee X_n\right]\Bigg|\mathcal F_n^Y\right\}\qquad\qquad\qquad\qquad\qquad\qquad\qquad\]

\[\qquad\qquad\qquad+\tilde{\mathbb E}\left\{(I+Q\Delta t)\tilde{\mathbb E}\left[g(X_n)\left(\frac{h(t_n,X_n)}{\gamma^2}\right)M_n\Big|\mathcal F_n^Y\vee X_n\right]\Bigg|\mathcal F_n^Y\right\}\Delta Y_n+o(\Delta t)\]

\[=\tilde{\mathbb E}\left[(I+Q\Delta t)g(X_n)M_n\Big|\mathcal F_n^Y\right]+\tilde{\mathbb E}\left[(I+Q\Delta t)g(X_n)\left(\frac{h(t_n,X_n)}{\gamma^2}\right)M_n\Big|\mathcal F_n^Y\right]\Delta Y_n+o(\Delta t)\]
and then using the fact that $\Delta Y_n\cdot \Delta t=o(\Delta t)$, we have

\[=\tilde{\mathbb E}[g(X_n)M_n|\mathcal F_n^Y]+\tilde{\mathbb E}[Qg(X_n)M_n|\mathcal F_n^Y]\Delta t+\tilde{\mathbb E}\left[g(X_n)\frac{h(t_n,X_n)}{\gamma^2}M_n\Big|\mathcal F_n^Y\right]\Delta Y_n+o(\Delta t)\]

\[=\phi_n[g]+\phi[Qg]\Delta t+\phi\left[g\frac{h}{\gamma^2}\right]\Delta Y_n+o(\Delta t)\]
which foreshadows the Zakai equation in a discrete setting,
\[\Delta \phi_n[g] = \phi[Qg]\Delta t+\phi\left[g\frac{h}{\gamma^2}\right]\Delta Y_n+o(\Delta t).\]

\section{Derivation of the Zakai Equation}
In this section we use the Girsanov theorem as the main tool in a formal derivation of the nonlinear filtering equations in continuous time. For ease in notation we let $h(t,x) = h(x)$, but this does change the results because the would merely need to be rewritten to include the time dependence in $h(~)$.

We start by considering the finite interval $[0,T]$ and defining the following exponential,
\[M_t \doteq \exp\left\{\frac{1}{2\gamma^2}\int_0^th^2(X_s)ds+\frac{1}{\gamma}\int_0^th(X_s)dW_s   \right\}\]

\[= \exp\left\{-\frac{1}{2\gamma^2}\int_0^th^2(X_s)ds+\frac{1}{\gamma^2}\int_0^th(X_s)dY_s   \right\}\]
for all $t\in[0,T]$. Since it was initially assumed that $W_t$ was independent, we can define an equivalent measure $\tilde{\mathbb P}$ by
\[d\tilde{\mathbb P} = M_T^{-1}d\mathbb P.\]
By the Girsanov theorem we know that
\begin{enumerate}
\item $\tilde{\mathbb P}$ is a probability measure, and
\item $Y_t/\gamma$ is $\tilde{\mathbb P}$-Brownian motion for $t\in[0,T]$, conditioned on $X$.
\end{enumerate}
It is easy to show with moment generating functions that $\tilde{\mathbb P}(X_t\leq x) = \mathbb P(X_t\leq x)$. We can also easily show that $M_t$ is a true $\tilde{\mathbb P}$-martingale,
\[
\tilde{\mathbb E}M_t = \int M_t(\omega)d\tilde{\mathbb P}(\omega) =  \int M_t(\omega)M_T^{-1}(\omega)d\mathbb P(\omega)  = \mathbb E[M_t/M_T]
\]
\[
= \mathbb E\left[\exp\left\{-\frac{1}{2\gamma^2}\int_t^Th^2(X_s)ds-\frac{1}{\gamma}\int_t^Th(X_s)dW_s   \right\} \right]
\]
\[=1\ .\]
Lastly, a simple lemma shows that $X$ and $Y$ are path-wise independent under $\tilde{\mathbb P}$:

\begin{lemma} $X$ and $Y$ are path-wise independent under $\tilde{\mathbb P}$.\end{lemma}
\begin{proof}
For an arbitrary path-wise function $f_1$ we have
\[\tilde {\mathbb E}f_1(Y/\gamma) = \tilde {\mathbb E}[\tilde{\mathbb E}[f_1(Y/\gamma)|X]] = \tilde {\mathbb E}[\mathbb Ef_1(W)] = \mathbb Ef_1(W)\]
showing that $Y/\gamma$ is $\tilde{\mathbb P}$-Brownian motion unconditional on $X$. Then for another arbitrary path-wise function $f_2$ we have
\[\tilde {\mathbb E}f_1(Y/\gamma)f_2(X) = \tilde {\mathbb E}[f_2(X)\tilde {\mathbb E}[f_1(Y/\gamma)|X]]=\tilde {\mathbb E}[f_2(X)\mathbb Ef_1(W)]\]

\[=\mathbb Ef_1(W)\tilde{\mathbb  E}f_2(X)=\tilde{\mathbb E}f_1(Y/\gamma)\tilde{\mathbb E}f_2(X)\]
and so $X$ and $Y$ are $\tilde{\mathbb P}$-independent.
\end{proof}

From here forward, define the measure $\phi_t$ on $\mathcal B_b(Q)$ as
\[\phi_t[g]\doteq\tilde{\mathbb E}[g(X_t)M_t|\mathcal F_t^Y].\]
With this new measure we can express another important result regarding the Girsanov change of measure, namely the Kallianpur-Streibel formula:
\begin{lemma}\textbf{Kallianpur-Streibel Formula:}
\[\mathbb E[g(X_t)|\mathcal F_t^Y] = \frac{\phi_t[g]}{\phi_t[1]}\]
for any $g(x)\in\mathcal B(Q)$.
\end{lemma}
\begin{proof} For any $ A\in\mathcal F_t^Y$ we have
\[\mathbb E\left\{\mathbf 1_A\mathbb E[g(X_t)|\mathcal F_t^Y]\right\}=\mathbb E[\mathbf 1_Ag(X_t)]=\tilde{\mathbb E}[\mathbf 1_Ag(X_t)M_t]\]

\[=\tilde{\mathbb E}\left\{\mathbf 1_A\tilde{\mathbb E}[g(X_t)M_t|\mathcal F_t^Y]\right\}=\tilde{\mathbb E}\left\{\mathbf 1_A\frac{\tilde{\mathbb E}[g(X_t)M_t|\mathcal F_t^Y]}{\tilde{\mathbb E}[M_t|\mathcal F_t^Y]}\tilde{\mathbb E}[M_t|\mathcal F_t^Y]\right\}=\tilde{\mathbb E}\left\{\mathbf 1_A\frac{\phi_t[g]}{\phi_t[1]}\tilde{\mathbb E}[M_t|\mathcal F_t^Y]\right\}\]

\[=\tilde{\mathbb E}\left\{\tilde{\mathbb E}\left[\mathbf 1_A\frac{\phi_t[g]}{\phi_t[1]}M_t\Big|\mathcal F_t^Y\right]\right\}=\tilde{\mathbb E}\left[\mathbf 1_A\frac{\phi_t[g]}{\phi_t[1]}M_t\right]=\mathbb E\left[\mathbf 1_A\frac{\phi_t[g]}{\phi_t[1]}\right]\]
and since $A$ was an arbitrary set, this shows that the result holds wp1.
\end{proof}

Now, for any $t\in[0,T]$, we use Fubini's theorem to bring the differential inside the expectation, and from there we apply It\^o's lemma, which gives us the following differential,
\[d\tilde{\mathbb E}[g(X_t)M_t|\mathcal F_T^Y] = \tilde{\mathbb E}[Qg(X_t)M_t|\mathcal F_T^Y]dt+ \tilde{\mathbb E}\left[g(X_t)\frac{h(X_t)}{\gamma^2}M_t\Big|\mathcal F_T^Y\right]dY_t\]
for any $g(x)\in\mathcal B_b(Q)$. From this we can construct the integrated form of the differential,
\[\tilde{\mathbb E}[g(X_t)M_t|\mathcal F_T^Y] \]

\[=\tilde{\mathbb E}[g(X_0)|\mathcal F_T^Y]+\int_0^t\tilde{\mathbb E}[Qg(X_s)M_s|\mathcal F_T^Y]ds+ \int_0^t\tilde{\mathbb E}\left[g(X_s)\frac{h(X_s)}{\gamma^2}M_s\Big|\mathcal F_T^Y\right]dY_s\]
and since $X$ is independent of $Y$ under the $\tilde{\mathbb P}$-measure, we can reduce the filtrations from $\mathcal F_T^Y$ to $\mathcal F_s^Y$ for all $s\leq T$, giving us,
\begin{equation}
\label{eq:intZakai}
\tilde{\mathbb E}[g(X_t)M_t|\mathcal F_t^Y] =\mathbb E[g(X_0)]+\int_0^t\tilde{\mathbb E}[Qg(X_s)M_s|\mathcal F_s^Y]ds+ \int_0^t\tilde{\mathbb E}\left[g(X_s)\frac{h(X_s)}{\gamma^2}M_s\Big|\mathcal F_s^Y\right]dY_s
\end{equation}
for all $t\leq T$. Inserting $\phi_s[\cdot]$ in (\ref{eq:intZakai}) wherever possible and then taking the differential with respect to $t$, we have \textbf{the Zakai equation:}
\begin{equation}
\label{eq:zakai}
d\phi_t[g] = \phi_t[Qg]dt+\phi_t\left[g\frac{h}{\gamma^2}\right]dY_t
\end{equation}
for all $t\leq T$. The Zakai equation can also be considered for general unbounded functions $g(x)\in\mathcal B(Q)$, but we have restricted ourselves to the bounded case in order to insure that $\phi_t[g]$ is finite almost surely. Existence of solutions to (\ref{eq:zakai}) is straight-forward because we have derived it by differentiating $\tilde{\mathbb E}[g(X_t)M_t|\mathcal F_t^Y]$. Uniqueness of measure-valued solutions to (\ref{eq:zakai}) has been shown by Kurtz and Ocone \cite{kurtzOcone1988} using a filtered martingale problem, and by Rozovsky \cite{rozovsky1992} using a Radon measure representation of $\phi_t$.

\subsection{The Adjoint Zakai Equation}
Depending on the nature of the filtering problem, the unnormalized probability measure $\phi_t[~\cdot~]$  may have a density/mass function. For example, suppose that $X_t\in\mathbb R$ is a diffusion process satisfying the SDE
\[dX_t= a(X_t)dt+\sigma dB_t\]
where $B_t\perp W_t$. Then the generator is $Q=\mathcal L = \frac{\sigma^2}{2}\frac{\partial^2}{\partial x^2}\cdot~+a(x)\frac{\partial}{\partial x}\cdot~$ and the Zakai equation is
\[d\phi_t[g] = \phi_t[\mathcal Lg]dt+\frac{1}{\gamma^2}\phi_t[gh]dY_t\]

\[=\frac{\sigma^2}{2}\phi_t\left[\frac{\partial^2}{\partial x^2}g\right]dt+\phi_t\left[a\frac{\partial}{\partial x}g\right]dt+\frac{1}{\gamma^2}\phi_t[gh]dY_t\]
for any bounded function $g(x)$ with a 2nd derivative. Depending on $a(x),\sigma$ and the initial conditions, $\tilde\pi_t$ may be a density so that
\[\phi_t[g] = \int g(x)\tilde\pi_t(x)dx,\]
and provided that certain regularity conditions are met, the adjoint of the Zakai equation gives us an SPDE for $\tilde\pi_t$,
\begin{equation}
\label{eq:adjointZakai}
d\tilde\pi_t(x) = \mathcal L^*\tilde\pi_t(x)dt+\frac{h(x)}{\gamma^2}\tilde\pi_t(x)dY_t
\end{equation}
with the initial condition $\tilde\pi_0(x)= \mathbb P(X_0\in dx)$, and with the adjoint operator given by $\mathcal L^* =\frac{\sigma^2}{2}\frac{\partial^2}{\partial x^2}\cdot~-\frac{\partial}{\partial x}\left(a(x)~\cdot~\right)$. Existence and uniqueness of such densities is beyond the scope of these notes. Readers who are interested in regularity of solutions should read the book by Pardoux \cite{pardoux}.

In the case of filtering distributions that are composed of mass functions, the adjoint equation is similar. For instance, if $X_t\in\{x_1,\dots,x_m\}$ is a finite-state Markov chain with generator $Q$, the adjoint equation holds without any regularity conditions,
\[d\tilde\pi_t(x_i) = Q^*\tilde\pi_t(x_i)dt+\frac{h(x_i)}{\gamma^2}\tilde\pi_t(x_i)dY_t\]

\[= \sum_{j=1}^mQ_{ji}\tilde\pi_t(x_j)dt+\frac{h(x_i)}{\gamma^2}\tilde\pi_t(x_i)dY_t.\]
General existence and uniqueness for $\tilde{\pi}_t$ in this discrete case was shown by Rozovsky \cite{rozovsky1972}.

\subsection{Kushner-Stratonovich Equation}
Using the Zakai equation of (\ref{eq:zakai}) and observing that our assumption that $h$ is bounded implies $\mathbb P(\phi_t[1]<\infty)=1$ for all $t\in [0,T]$, we can apply It\^o's lemma to obtain
\begin{equation}
\label{eq:kushner}
d\hat g_t = d\left(\frac{\phi_t[g]}{\phi_t[1]}\right) = \widehat{Qg}_tdt+ \frac{\widehat{gh}_t-\hat g_t\hat h_t}{\gamma^2}\left(dY_t-\hat h_tdt\right).
\end{equation}
However, it should be mentioned that (\ref{eq:kushner}) was originally obtain a few years before the Zakai equation using other methods. Under the appropriate regularity conditions, the Kushner-Stratonovich equation is the adjoint (\ref{eq:kushner}) and is the nonlinear equation for the filtering distribution,
\begin{equation}
\nonumber
d\pi_t(x) = Q^*\pi_t(x)dt+\frac{h(x)-\hat h_t}{\gamma^2}\pi_t(x)\left(dY_t-\hat h_tdt\right)
\end{equation}
where $\pi_t(x)$ is either a density or a mass function (depending on the type of problem).

\subsection{Smoothing}
The smoothing filter has been derived in \cite{bobrovskyZeitouni}, but in the case of regularized processes where the adjoint Zakai equation holds. In this section we derive a similar results but for the general case of functions in $\mathcal B_b(\mathcal S)$, and we'll also derive the backward SPDE for smoothing in the regularized case.

Consider the times $\tau$ and $t$ such that $0\leq \tau\leq t$. The filtering expectation of $g(X_\tau)$ is
\[\mathbb E[g(X_\tau)|\mathcal F_t^Y] = \frac{\tilde{\mathbb E}[M_tg(X_\tau)|\mathcal F_t^Y] }{\tilde{\mathbb E}[M_t|\mathcal F_t^Y] }= \frac{\tilde{\mathbb E}[M_tg(X_\tau)|\mathcal F_t^Y] }{\phi_t[1]}.\]
For $\tau$ fixed and for $t$ increasing, the Zakai equation is
\begin{eqnarray*}
d\tilde{\mathbb E}[M_tg(X_\tau)|\mathcal F_t^Y] &=&\frac{1}{\gamma^2}\tilde{\mathbb E}[M_th(X_t)g(X_\tau)|\mathcal F_t^Y] dY_t\qquad\hbox{for }t>\tau,\\
\tilde{\mathbb E}[M_\tau g(X_\tau)|\mathcal F_\tau^Y] &=&\phi_\tau[g].
\end{eqnarray*}
This equation can be solved to obtain the smoothing distribution, but lacks a differential formula for changes in $\tau$. However, in the regular case there is a backward SPDE that will provide a differential for changes in $\tau$. This backward SDE will provide improved efficiency for coding and analysis.

Suppose there is sufficient regularity so that $\tilde\pi_t(x)\doteq\phi_t[\delta_x] $ satisfies the adjoint Zakai equation (see equation (\ref{eq:adjointZakai})). Given $\mathcal F_t^Y$, the smoothing filter for any time $\tau\in[0,t]$ is
\[\frac{d}{dx}\mathbb P(X_\tau\leq x|\mathcal F_t^Y)= \frac{\tilde{\mathbb E}[M_t\delta_x(X_\tau)|\mathcal F_t^Y]}{\tilde{\mathbb E}[M_t|\mathcal F_t^Y]}\]

\[= \frac{\tilde{\mathbb E}[M_\tau\delta_x(X_\tau)\tilde{\mathbb E}[M_t/M_\tau|\mathcal F_t^Y\vee\mathcal F_\tau^X]|\mathcal F_t^Y]}{\tilde{\mathbb E}[M_t|\mathcal F_t^Y]}\]

\[= \frac{\tilde{\mathbb E}[M_\tau\delta_x(X_\tau)\tilde{\mathbb E}[M_t/M_\tau|\mathcal F_t^Y\vee \{X_\tau=x\}]|\mathcal F_t^Y]}{\tilde{\mathbb E}[M_t|\mathcal F_t^Y]}\]

\[=\frac{\tilde{\mathbb E}[M_\tau\delta_x(X_\tau)|\mathcal F_t^Y] \cdot\tilde{\mathbb E}[M_t/M_\tau|\mathcal F_t^Y\vee \{X_\tau=x\}]}{\tilde{\mathbb E}[M_t|\mathcal F_t^Y]}\]

\[=\frac{\tilde{\mathbb E}[M_\tau\delta_x(X_\tau)|\mathcal F_\tau^Y]\cdot \tilde{\mathbb E}[M_t/M_\tau|\mathcal F_t^Y\vee \{X_\tau=x\}]}{\tilde{\mathbb E}[M_t|\mathcal F_t^Y]}\]

\[=\frac{\tilde\pi_\tau(x)\alpha_{\tau,t}(x)}{\phi_t[1]},\]
where $\alpha_{\tau,t}$ is define as

\[\alpha_{\tau,t}(x) \doteq \tilde{\mathbb E}\left[M_t/M_\tau\Big|\mathcal F_t^Y\vee\{X_\tau=x\}\right]\]

\[=\tilde{\mathbb E}\left[\exp\left\{-\frac{1}{2\gamma^2}\int_\tau^th^2(X_s)ds+\frac{1}{\gamma^2}\int_\tau^th(X_s)dY_s   \right\}\Big|\mathcal F_t^Y\vee\{X_\tau=x\}\right].\]
The function $\alpha_{\tau,t}(x)$ is the smoothing component and satisfies the following backward SPDE
\begin{eqnarray*}
d\alpha_{\tau,t}(x) &=& Q\alpha_{\tau,t}(x)d\tau-\frac{1}{\gamma^2} h(x)\alpha_{\tau,t}(x)dY_\tau\qquad\hbox{for }\tau\leq t,\\
\alpha_{t,t}&\equiv&1,
\end{eqnarray*}
or in integrated form
\[\alpha_{\tau,t}(x) = 1-\int_\tau^tQ\alpha_{s,t}(x)ds + \frac{1}{\gamma^2}\int_\tau^t h(x)\alpha_{s,t}(x)dY_s.\]


TITLE: $T(f(t))$ from "the space of all polynomials"
QUESTION [0 upvotes]: Let $T(f(t)) = (f(0), f(1), f(2), f(3),\cdots)$ from $P$ to $V$, where $P$ denotes the space of all polynomials. Is $T$ linear and if so, is $T$ an isomorphism?
I feel like a counterexample is feasible, but I'm not sure if I should arbitrarily pick some polynomial of any degree. Suggestions?
EDIT:
$V$ denotes the space of infinite sequences of real numbers. Apologies for not clarifying earlier.

REPLY [1 votes]: It's clear that T is linear :
$$T(f+\lambda g) = ((f+\lambda g)(0),(f+\lambda g)(1),(f+\lambda g)(2),\cdots) $$
$$= (f(0)+\lambda g(0),f(1)+\lambda g(1),f(2)+\lambda g(2),\cdots)$$
$$= (f(0),f(1),f(2),\cdots)+\lambda (g(0),g(1),g(2),\cdots)=T(f)+\lambda T(g)$$
Now is T bijective?
Take the sequence $(e^0,e^1,e^2,\cdots)$
If this was the image by T of a polynomial P, you would have
$$\lim_{n\to +\infty} \frac{P(n)}{e^n} \neq 0 $$
But this limit is 0 for all polynomial. Hence T is not bijective.
Edit : notice that T is injective, because if $T(f-g)=0$, $f-g$ has an infinite number of roots, so it's null


text:
\section{Overview of Techniques}
\label{sec:overview}
\paragraph{The LeakyRelu loss.} All of our algorithms use the LeakyRelu loss $\ell_{\lambda}$ in a central way, similarly to  \cite{diakonikolas2019distribution}. See the definition in Section~\ref{sec:notation}. We briefly explain why this is natural, and in the process explain some important connections to the literature on learning generalized linear models \cite{auer1996exponentially,kivinen1998relative,kalai2009isotron,kakade2011efficient}. First, it is easy to see that the problem of learning a halfspace where the labels are flipped with probability $\eta$ (i.e. under RCN) is equivalent to learning a generalized linear model $\E{Y \mid \rvx} = (1 - 2\eta) \sgn(\langle \vw^*, \rvx \rangle)$. Auer et al. \cite{auer1996exponentially} defined the notion of a {\em matching loss} which constructs a loss function, assuming the link function is monotonically increasing, that is convex and so has no bad local minima; if the link function is also Lipschitz then minimizing this loss provably recovers the GLM. In particular, this works to learn halfspaces with margin under RCN \cite{auer1996exponentially,kalai2009isotron,kakade2011efficient,kanade8}.
We see that $\LR_{\eta}$ is a matching loss from the integral representation
\[ \ell_{\eta}(\vw,\rvx) = \frac{1}{2} \int_0^{\langle \vw, \rvx \rangle} ((1 - 2\eta) \sgn(r) - Y)dr. \]
In fact, this integral representation is used implicitly in \cite{diakonikolas2019distribution} (i.e. Lemma~\ref{lem:rounding} below) and also in our proof of Lemma~\ref{lem:01-to-leakyreluslab} below.

\subsection{Separation Oracles and Proper-to-Improper Reduction}
\paragraph{An idealized zero-sum game.}
Our proper learning algorithms are all based on the framework of finding approximately optimal strategies in the following zero-sum game:
\begin{equation}\label{eqn:idealized-game}
\min_{\|\vw\| \le 1} \max_{c} \E{c(\rvx) \ell_{\lambda}(\vw,\rvx)}
\end{equation}
where $\lambda$ is a fixed parameter chosen slightly larger than $\eta$,
and $c(\rvx)$ is any measurable function such that $c(\rvx) \ge 0$ and $\E{c(\rvx)} = 1$. It is helpful to think of $c(\rvx)$ as a \emph{generalized filter}, and we will often consider functions of the form $c_S(\rvx) = \frac{\bone{\rvx \in S}}{\Pr{\rvx \in S}}$, which implement conditioning on $\rvx \in S$. Because the LeakyRelu is homogenous ($\ell_{\lambda}(\vw,c\rvx) = c \cdot \ell_{\lambda}(\vw,\rvx)$ for $c \ge 0$), we sometimes reinterpret $c(\rvx)$ as a rescaling of $\rvx$.

In this game, we can think of the $\min$ player as the classifier, whose goal is to output a hyperplane $\vw$ with loss almost as small as the ground truth hyperplane $\vw^*$. On the other hand, the $\max$ player is a special kind of \emph{discriminator} whose goal is to prove that $\vw$ has inferior predictive power compared to $\vw^*$, by finding a reweighting of the data such that $\vw$ performs very poorly in the LeakyRelu loss. This is based on the fact that in the Massart model, for \emph{any} reweighting $c(\rvx)$ of the data, $\vw^*$ performs well in the sense that $\E{c(\rvx) \ell_{\lambda}(\vw^*,\rvx)} < 0$. This follows from Lemma~\ref{lem:wstar-massart}.

In fact, it turns out that this class of discriminators is so powerful that $\vw$ having optimal zero-one loss is \emph{equivalent} to having value less than zero in the minimax game. We will show this in Section~\ref{sec:proper-to-improper}. Furthermore, the outer optimization problem is convex, so if we could find a good strategy for the $\max$ player, we could then optimize $\vw$. Unfortunately, this is impossible because the $\max$ player's strategies in this game range over \emph{all possible reweightings} of the distribution over $\rvx$, so it is both statistically and computationally intractable to compute the best response $c$ given $\vw$. For example, if $c$ is supported on a set $S$ with extremely low probability, we may never even see a datapoint with $c(\rvx) > 0$, so it will be impossible to estimate the value of the expectation.

The key to our approach is to fix alternative strategies for the $\max$ player which are computationally and statistically efficient. Then we will analyze the resulting dynamics when the $\vw$ player plays against this adversary and updates their strategy in a natural way (e.g. gradient descent). Thus our framework naturally yields simple and practical learning algorithms.

\paragraph{Comparison to previous approach and no-go results.} We briefly explain the approach of \cite{diakonikolas2019distribution} in the context of \eqref{eqn:idealized-game} and why their approach only yields an improper learner. In the first step of the algorithm, they minimize the LeakyRelu loss over the entire space (i.e. taking $c(\rvx) = 1$). They show this generates a $\vw$ with good zero-one loss on a subset of space $S$. They fix this hypothesis on $S$, and then restrict to $\mathbb{R}^d \setminus S$ (i.e., take $c(\rvx) = \frac{\bone{\rvx \notin S}}{\Pr{\rvx \notin S}}$) and restart their algorithm. Because they fix $c$ before minimizing over $\vw$, their first step is minimizing a fixed convex surrogate loss. However, Theorem 3.1 of \cite{diakonikolas2019distribution} establishes that no proper learner based on minimizing a fixed surrogate loss will succeed in the Massart setting. In contrast, our algorithms choose $c$ adversarially based on $\vw$. For this reason, we evade the lower bound of \cite{diakonikolas2019distribution} and successfully solve the proper learning problem.

\paragraph{Proper learner for halfspaces with margin.} Our proper learner for learning halfspaces with margin is based upon the following upper bound on \eqref{eqn:idealized-game}:
\begin{equation}\label{eqn:margin-game}
\min_{\|\vw\| \le 1} \max_{r > 0} \E{\ell_{\lambda}(\vw,\rvx) \mid |\langle \vw, \rvx \rangle| \le r},
\end{equation}
where $r$ will be restricted so that $\Pr{|\langle \vw, \rvx \rangle| \le r} \ge \epsilon$ for some small $\epsilon > 0$. By (greatly) restricting the possible strategies for the discriminator to ``slabs'' along the direction of $\vw$, we completely fix the problem of computational and statistical intractability for the $\max$-player. In particular, the optimization problem over $r > 0$ is one-dimensional, and the expectation can be accurately estimated from samples using rejection sampling.

However, by doing this we are faced with two new problems: First, computing the optimal $\vw$ is a non-convex optimization problem, so it may be difficult to find its global minimum. Second, the value of \eqref{eqn:margin-game} is only an upper bound on \eqref{eqn:idealized-game}, so we need a new analysis to show the optimal $\vw$ actually has good prediction accuracy. To solve the latter issue, we prove in Lemma~\ref{lem:01-to-leakyreluslab} that any $\vw$ with value $< 0$ for the game \eqref{eqn:margin-game} achieves prediction error at most $\lambda + O(\epsilon)$ and,  since we can take $\lambda = \eta + O(\epsilon)$, we get a proper predictor matching the guarantees for the improper learner of \cite{diakonikolas2019distribution}.

Also knowing that it suffices to find a $\vw$ with negative value for \eqref{eqn:margin-game}, we can resolve the issue of optimizing the non-convex objective over $\vw$. If gradient descent fails to find a point $\vw$ with negative LeakyRelu loss, this means the $\max$ player has been very successful in finding convex losses where the current iterate $\vw_t$ performs poorly compared to $\vw^*$, which achieves negative loss. This cannot go on for too long, because gradient descent is a provably low regret algorithm for online convex optimization \cite{zinkevich2003online}.

\paragraph{Proper learner for general halfspaces.} The above argument based on low regret fails when the margin is allowed to be exponentially small in the dimension. The reason is that the optimal value of \eqref{eqn:margin-game} can be too close to zero. In order to deal with this issue, we need an algorithm which can ``zoom in'' on points very close to the halfspace, as in earlier algorithms \cite{blum1998polynomial,cohen1997learning,dunagan2008simple} for learning halfspaces under RCN. This becomes somewhat technically involved, as concentration of measure can fail when random variables of different size are summed. Ultimately, we show how to build upon some of the techniques in \cite{cohen1997learning} to construct the needed rescaling $c$, giving us a separation oracle. By doing this, we give a variant of the algorithm of \cite{cohen1997learning} that is robust to Massart noise.

\paragraph{Proper to improper reduction.} Suppose that we are given black-box access to a hypothesis $h$ (possibly improper) achieving good prediction error in the Massart halfspace setting. In the context of \eqref{eqn:idealized-game}, this serves as valuable advice for the $\min$ player, because it enables efficient sampling from the \emph{disagreement set} $\{ \vx : h(\vx) \ne \sgn(\langle \vw, \rvx \rangle) \}$. If $h$ has significantly better performance than $\vw$ overall, this means that $\vw$ has very poor performance on the disagreement set \--- otherwise, the zero-one loss of $h(\rvx)$ and $\sgn(\langle \vw, \rvx \rangle)$ would be close.

Using this idea, we can ``boost'' our proper learners to output a $\vw$ whose performance almost matches $h$, by running the same algorithms as before but having the $\max$ player always restrict to the disagreement set before generating its generalized filter $c$. In light of the SQ lower bound we observe for achieving optimal error (discussed later in the overview), this has an appealing consequence \--- it means that in the Massart setting, the power of SQ algorithms with blackbox access to a good teacher can be much more powerful than ordinary SQ algorithms. The fact that blackbox access suffices is also surprising, since most popular approaches to knowledge distillation are not blackbox (see e.g. \cite{hinton2015distilling}).

\subsection{Learning Misspecified GLMs}
We now proceed to the more challenging problem of learning misspecified GLMs. In this case, when $\zeta > 0$, it could be that achieving negative value in \eqref{eqn:idealized-game} is actually impossible; to deal with this, we do not attempt to learn a proper classifier in the general misspecified setting except when $\zeta = 0$.

Similar to \cite{diakonikolas2019distribution}, our algorithm breaks the domain $\calX$ into disjoint regions $\brc{\calX^{(i)}}$ and assigns a constant label $s^{(i)}\in\brc{\pm 1}$ to each. This setting poses a host of new challenges, and the partitions induced by our algorithm will need to be far richer in structure than those of \cite{diakonikolas2019distribution}.

\paragraph{Key issue: target error varies across regions}

As a thought experiment, consider what it takes for an improper hypothesis $\hypo$ to compete with $\sgn(\iprod{\vw^*,\cdot})$. Let $\calD$ be the distribution over $(\rvx,Y)$ arising from a misspecified GLM (see Definition~\ref{defn:glm_massart}).
Now take an improper classifier $\hypo$ which breaks $\calX$ into regions $\brc{\calX^{(i)}}$. A natural way to ensure $\hypo$ competes with $\vw^*$ over all of $\calX$ is to ensure that it competes with it over every region $\calX^{(i)}$. For any $i$, note that the zero-one error of $\sgn(\iprod{\vw^*,\cdot})$ with respect to $\calD$ restricted to $\calX^{(i)}$ satisfies \begin{equation}
    \err_{\calX^{(i)}}(\vw^*) \le \frac{1 - \E[\calD]{\sigma(\abs{\iprod{\vw^*,\rvx}})\mid \rvx\in\calX^{(i)}}}{2} \triangleq \lambda(\calX^{(i)}).
\end{equation} Now we can see the issue that for learning Massart halfspaces, $\lambda(\calX^{(i)})$ is always $\eta$. But for general misspecified GLMs, $\lambda(\calX^{(i)})$ can vary wildly with $i$. For this reason, iteratively breaking off regions like in \cite{diakonikolas2019distribution} could be catastrophic if, for instance, one of these regions $\calR$ has $\lambda(\calR)$ significantly less than $\lambda(\calX)$ and yet our error guarantee on $\calR$ is only in terms of some global quantity like in \cite{diakonikolas2019distribution}. Without the ability to go back and revise our predictions on $\calR$, we cannot hope to achieve the target error claimed in Theorem~\ref{thm:glm_informal}.

\paragraph{Removing regions conservatively}
In light of this, we should only ever try to recurse on the complement of a region $\calR$ when we have certified that our classifier achieves zero-one error $\lambda(\calR) + O(\epsilon)$ over that region. Here is one extreme way to achieve this. Consider running SGD on the LeakyRelu loss and finding some direction $\vw$ and annulus $\calR$ on which the zero-one error of $\sgn(\iprod{\vw,\cdot})$ is $O(\epsilon)$-close to $\lambda(\calX)$ (henceforth we will refer to this as ``running SGD plus filtering''). Firstly, it is possible to show that $\err_{\calR}(\vw) \le \lambda(\calX) + O(\epsilon)$ (see Lemma~\ref{lem:leakyrelubound} and Lemma~\ref{lem:rounding}). There are two possibilities. First, it could be that $\lambda(\calR) \ge \lambda(\calX) - \epsilon$, in which case we can safely recurse on the complement of $\calR$. Alternatively we could have $\lambda(\calR) < \lambda(\calX) - \epsilon$.\footnote{Crucially, we can \emph{distinguish} which case we are in without knowing these quantities (see Lemma~\ref{lem:find_split_main}).} But if this happens, we can recurse by running SGD plus filtering on $\calR$. Moreover this recursion must terminate at depth $O(1/\epsilon)$ because $\lambda(\calR')\ge 0$ for any region $\calR'$, so we can only reach the second case $O(1/\epsilon)$ times in succession, at which point we have found a hypothesis and region on which the hypothesis is certified to be competitive with $\vw^*$.
The only issue is that after $O(1/\epsilon)$ levels of recursion, this region might only have mass $\exp(-\Omega(1/\epsilon))$, and we would need to take too many samples to get any samples from this region.

\paragraph{Our algorithm}
The workaround is to only ever run SGD plus filtering on regions with non-negligible mass. At a high level, our algorithm maintains a constantly updating partition $\brc{\calX^{(i)}}$ of the space into a \emph{bounded} number of regions, each equipped with a $\pm 1$ label, and only ever runs SGD plus filtering on the largest region at the time. Every time SGD plus filtering is run, some region of the partition $\calX'$ might get refined into two pieces $\tilde{\calX}$ and $\calX'\backslash\tilde{\calX}$, and their new labels might be updated to differ. To ensure the number of regions in the partition remains bounded, the algorithm will occasionally merge regions of the partition on which their respective labels have zero-one error differing by at most some $\delta$. And if running SGD plus filtering ever puts us into the first case above for some region $\calR$, we can safely remove $\calR$ from future consideration.

The key difficulty is to prove that the above procedure does not go on forever, which we do via a careful potential argument.
We remark that the partitions this algorithm produces are inherently richer in structure than those output by that of \cite{diakonikolas2019distribution}. Whereas their overall classifier can be thought of as a decision tree, the one we output is a general \emph{threshold circuit} (see Remark~\ref{remark:circuit}), whose structure records the history of splitting and merging regions over time.

\subsection{Statistical Query Lower Bounds}

To prove Theorem~\ref{thm:sq_informal}, we establish a surprisingly missed connection between learning under Massart noise and Valiant's notion of evolvability \cite{valiant2009evolvability}.

Feldman \cite{feldman2008evolvability} showed that a concept $f$ is \emph{evolvable} with respect to Boolean loss if and only if it can be efficiently learned by a \emph{correlational SQ} (CSQ) algorithm, i.e. one that only gets access to the data in the following form. Rather than directly getting samples, it is allowed to make noisy queries to statistics of the form $\E[(\rvx,Y)\sim\calD]{Y\cdot G(\rvx)}$ for any $G:\calX\to\brc{\pm 1}$. See Section~\ref{subsec:csq_defs} for the precise definitions. Note that unlike SQ algorithms, CSQ algorithms do not get access to statistics like $\E[(\rvx)\sim\calDx]{G(\rvx)}$, and when $\calDx$ is unknown, this can be a significant disadvantage \cite{feldman2011distribution}.

At a high level, the connection between learning under Massart noise and learning with CSQs (without label noise) stems from the following simple observation. For any function $G:\calX\to\brc{\pm 1}$, concept $f$, and distribution $\calD$ arising from $f$ with $\eta$-Massart noise \begin{equation}
    \E[(\rvx,Y)\sim\calD]{Y\cdot G(\rvx)} = \E[(\rvx,Y)\sim\calD]{f(\rvx)G(\rvx)(1 - 2\eta(\rvx))}.
\end{equation}
One can think of the factor $1 - 2\eta(\rvx)$ as, up to a normalization factor $Z$, \emph{tilting} the original distribution $\calDx$ to some other distribution $\calDx'$. If we consider the noise-free distribution $\calD'$ over $(\rvx,Y)$ where $\rvx\sim \calDx'$ and $Y = f(\rvx)$, then the statistic $\E[(\rvx,Y)\sim\calD]{Y\cdot G(\rvx)}$ is equal, up to a factor of $Z$, to the statistic $\E[(\rvx,Y)\sim\calD']{Y\cdot G(\rvx)}$. See Fact~\ref{fact:trivial_csq}.

This key fact can be used to show that distribution-independent CSQ algorithms that learn without label noise yield distribution-independent algorithms that learn under Massart noise (see Theorem~\ref{thm:csq_to_massart}). It turns out a partial converse holds, and we use this in conjunction with known CSQ lower bounds for learning halfspaces \cite{feldman2011distribution} to establish Theorem~\ref{thm:sq_informal}.

config: arxiv


TITLE: find all solutions of $a^b=b^{a-3}$ over integers.
QUESTION [2 upvotes]: find all solutions of $a^b=b^{a-3}$ over integers.
I used the method of taking $\gcd(a,b)=d$ and simplifying the equation(this method is usually useful in this kind of questions a similar question in IMO is proved in this way.).I also tried the method of solving with factorization in that method we can prove if $a>b$ then $a \mid b$ but non of them worked.

REPLY [2 votes]: $b=0$ leads to $a^0=0^{a-3}$ with only solution $a=3$.
$b=1$ leads to $a=1$
$b=-1$ leads to $\frac 1a=(-1)^{a-3}=\pm1$, but only $a=1$ works.

In all other cases, $b$ is divisible by at least one prime.
Also, we may assume $a\ne 3$ (because $a=3$ leads to $b=0$ again).
Let $p$ be a prime dividing $b$ and occuring in $b$ to the $k$th power (i.e., $p^k\mid b$, $p^{k+1}\nmid b$) with $k\ge 1$.
Then $p$ occurs in $b^{a-3}$ to the $(a-3)k$th power, hence in $a$ to the $\frac{(a-3)k}{b}$th power. In particular, $p\mid a$.
For $p\ne 3$, the pact that $\frac{(a-3)k}{b}$ is an integer and $\gcd(a-3,p)=1$ implies that $p^k\mid k$, which is absurd.
We conclude that $b$ is $\pm$ a power of $3$, $b=\pm3^k$, in particular, $b$ is odd.
On the other hand, if $q$ is a prime dividing $a$, we similarly find that $q\mid b$, hence $q=3$.
Then $3$ occurs in $a-3$ at most to first power. As $\frac{(a-3)k}{3^k}$ must still be an integer, $3^{k-1}\mid k$, we conclude $k=1$, so $b=\pm3$. So $a^3=3^{a-3}$, and with $a=3^m$,
$ 3^{3m}=3^{3^m-3}$, $m=2$, $a=9$.
$$ (a,b)=(3,0), (1,1), (1,-1), (9,3).$$

REPLY [1 votes]: Clearly $p\mid a\Longleftrightarrow p\mid b$, so we can write the prime factorizations of $a$ and $b$ as
$$\begin{array}{c}
a=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_m^{\alpha_m} \\
b=p_1^{\beta_1}p_2^{\beta_2}\dots p_m^{\beta_m}
\end{array}$$
With this we see that $a$ and $b$ are solutions if and only if $\alpha_i b=\beta_i(a-3)$ for all $1\le i\le m$. This gives that
$$\frac{b}{\gcd(b,a-3)}\mid \beta_i$$
However this requires $b\le \beta_i\gcd(b,a-3)$. If $3\nmid a$ then $\gcd(b,a-3)=1$ and this clearly does not hold if $b\neq 1$. If $b=1$ then the pair $a=1,b=1$ works. If $3\mid a$ then $\gcd(b,a-3)=3$ and $b\le 3\beta_i$, however this clearly doesn't hold if $b$ has more than two distinct prime factors, so in this case $b=3^{\beta}$. However we still must have $3^{\beta}\le 3\beta$ which restricts $\beta$ to $1$. So $b=3$ at which point we see $a=9$ satisfies $a^3=3^{a-3}$. So if $a,b\in\mathbb{N}$ then the solution pairs $(a,b)$ are $(1,1)$ and $(9,3)$.
Extending this to all integers shouldn't be hard by consider different combinations of when $a$ and $b$ are positive and negative. Simply check that both sides are integers or non-integers (for example one side can't be raised to a positive exponent and the other side a negative one). If they are both non-integers take the reciprocals of both sides and apply the same argument as above for when $a,b\in\mathbb{N}$.


TITLE: how to change $\sum_{i=1}^{n}u_i^TAu_i$ to matrix form?
QUESTION [0 upvotes]: I have the following expression:
$\sum_{i=1}^{n}u_i^TAu_i$, where $u_i\in R^{k \times 1}$, $A \in R^{k \times k}$. Here $u_i$ is one row of $U \in R ^ {n \times k}$, I would like to know how to change the following expression to matrix form? what is the trick to change summation format to matrix format, easily?
$$\sum_{i=1}^{n}u_i^TAu_i$$
Thanks.

REPLY [1 votes]: In such situations it is often helpful to use the trace and especially its cyclic property $tr(ABC)=tr(CAB)$.
$$
\sum u_i^TAu_i=\sum tr(u_i^TAu_i)=\sum tr(Au_iu_i^T)=tr(A\sum u_iu_i^T).
$$
Depending on your purpose you then replace the sum by $V$ with the defining property that it is positive semi-definite, or with $UU^T$ where $U$ is the matrix with the $u_i$ as columns.


TITLE: Prove that $a(x+y+z) = x(a+b+c)$
QUESTION [5 upvotes]: If $(a^2+b^2 +c^2)(x^2+y^2 +z^2) = (ax+by+cz)^2$
Then prove that $a(x+y+z) = x(a+b+c)$
I did expansion on both sides and got:
$a^2y^2+a^2z^2+b^2x^2+b^2z^2+c^2x^2+c^2y^2=2(abxy+bcyz+cazx) $
but can't see any way to prove $a(x+y+z) = x(a+b+c)$. How should I proceed?

REPLY [5 votes]: By C-S inequality, $(ax+by+cz)^2\le (a^2+b^2+c^2)(x^2+y^2+z^2)$ with equality iff $(x,y,z)=\lambda(a,b,c)$ for some $\lambda$ or $(a,b,c)=(0,0,0)$. But, if $(a,b,c)=(0,0,0)$, the problem is trivially true. If it not the case, then  $x=\lambda a$, $y=\lambda b$ and $z=\lambda c$.
Then $x+y+z=\lambda(a+b+c)$. Multiplying by $a$ both sides and remembering $x=\lambda a$ yield us the proof.

REPLY [5 votes]: HINT: To do it without linear algebra, expand both sides and subtract like terms to leave
$$a^2y^2+a^2z^2+b^2x^2+b^2z^2+c^2x^2+c^2y^2=2abxy+2acxz+2bcyz\;.$$
Notice that you can rearrange this as
$$(a^2y^2-2abxy+b^2x^2)+(a^2z^2-2acxz+c^2x^2)+(b^2z^2-2bcyz+c^2y^2)=0\;,$$
or
$$(ay-bx)^2+(az-cx)^2+(bz-cy)^2=0\;.$$

What can you conclude about $ay-bx$, $az-cx$, and $bz-cy$?
What can you conclude about $a(x+y+z)$ and $x(a+b+c)$?

REPLY [1 votes]: $$a^2x^2+a^2y^2+a^2z^2+b^2x^2+b^2y^2+b^2z^2+c^2x^2+c^2y^2+c^2z^2=a^2x^2+b^2y^2+c^2z^2+2axby+2axcz+2byxz$$
$$a^2y^2+a^2z^2+b^2x^2+b^2z^2+c^2x^2+c^2y^2=2axby+2axcz+2byxz$$
$$a^2y^2-2axby+b^2x^2+a^2z^2-2axcz+c^2x^2+b^2z^2-2byxz+c^2y^2=0$$
$$(ay-bx)^2+(az-cx)^2+(bz-cy)^2=0$$
From here the answer is clear. All three terms are zero.