TITLE: Solve $2^{1+\sin(3x)}-8^{\sin(x)+\frac13}+\sin (x) \cos (2x)=\sin (x)$
QUESTION [2 upvotes]: I want to solve this equation:
$$2^{1+\sin(3x)}-8^{\sin(x)+\frac13}+\sin (x) \cos (2x)=\sin (x)$$

This is what I did: with $\cos(2x)=1-2\sin^2 (x)$:
$2^{1+\sin(3x)}-8^{\sin(x)+\frac13}+\sin (x) (1-2\sin^2 (x))=\sin (x)$
$\implies 2^{1+\sin(3x)}-8^{\sin(x)+\frac13}+\sin (x) (1-2\sin^2 (x))=\sin (x)$
$\implies 2\times 2^{\sin(3x)}-8^{1/3}\times 8^{\sin(x)}=2\sin^2 (x)$
$\implies 2^{\sin(3x)}- 8^{\sin(x)}=\sin^2 (x)$
But here I don't know how to continue.

REPLY [3 votes]: There is a mistake at the second implies. It should be:

$$\implies 2\times 2^{\sin(3x)}-8^{1/3}\times 8^{\sin(x)}=2\sin^{\color{red}{3}} (x)$$

So you should actually arrive at
$$2^{\sin 3x}- 8^{\sin x}=\sin^3 x$$
Using $\sin 3x=3\sin x-4\sin^3 x$, the equation is equivalent with:
$$2^{\sin 3x}+\frac{\sin 3x}{4}=2^{3\sin x}+\frac{3\sin x}{4}$$
Define the function $f:\mathbb{R}\to \mathbb{R}, f(t)=2^t+\frac{t}{4}$, and the equation is equivalent with:
$$f(\sin 3x)=f(3\sin x)$$
$f$ is clearly increasing, and thus injective. This implies $\sin 3x=3\sin x$ and therefore $\sin^3x=0$, for which the solution is $\boxed{x \in \{k\pi,\ k\in \mathbb{Z}\}}$.


TITLE: Finding a system of equations that defines a line $r$
QUESTION [0 upvotes]: I'm trying to get a system of equations that defines the following line $r$. Here is its parametric equation
$r: (1,2,3)+t(3,1,2) \mid t \in \mathbb{R}$
To find the two equations I calculate the nullspace of $(3,1,2)$, this gives me the coefficients of the equations.
(nullspace) $\mathscr{N}(3,1,2)=\mathscr{L}((-2,0,3),(-1,3,0))$
Therefore the two equations should be
$r: \begin{cases} -2(x-1)+3(z-3)=0\\ -(x-1)+3(y-2)=0 \end{cases}$
But if I solve the system I get: $\mathscr{L} ((1,\frac{1}{3},\frac{2}{3})) + (0,\frac{5}{3},\frac{7}{3})=(0,\frac{5}{3},\frac{7}{3})+ t (1,\frac{1}{3},\frac{2}{3}) \mid t \in \mathbb{R}$
Which is not the original equation of $r$.
Where is my mistake?
Thanks a lot in advice

REPLY [1 votes]: What you get is a different representation of the same line.
Compare
\begin{align*}
(1,2,3)+t(3,1,2) &= (0,\tfrac53,\tfrac73)+u(1,\tfrac13,\tfrac23)
\end{align*}
From the first coordinate you can read that $u=1+3t$. If you plug that into the other coordinates, you will find that the equation holds in this case as well. So it's just a different representation of the same line.


text:
\begin{document}

\maketitle

\begin{abstract}
This paper is devoted to the analysis of some uniqueness properties of a classical reaction-diffusion equation of  Fisher-KPP type, coming from  population dynamics in heterogeneous environments. We work in a one-dimensional interval $(a,b)$ and we assume a nonlinear term of the form $u \, (\mu(x)-\gamma u)$ where $\mu$ belongs to a fixed subset of $C^{0}([a,b])$. We prove that the knowledge of $u$ at $t=0$ and of $u$, $u_x$  at a single point $x_0$ and for small times $t\in (0,\varepsilon)$ is sufficient to completely determine the couple $(u(t,x),\mu(x))$ provided $\gamma$ is known. Additionally, if $u_{xx}(t,x_0)$ is also measured for $t\in (0,\varepsilon)$, the triplet $(u(t,x),\mu(x),\gamma)$ is also completely determined. Those analytical results are completed with numerical simulations which show that, in practice, measurements of $u$ and $u_x$ at a single point $x_0$ (and for $t\in (0,\varepsilon)$) are sufficient to obtain a good approximation of the coefficient $\mu(x).$ These numerical simulations also show that the measurement of the derivative $u_x$ is essential in order to accurately determine $\mu(x)$.
\end{abstract}

\noindent{\it Keywords\/}: reaction-diffusion $\cdot$ heterogeneous media $\cdot$ uniqueness $\cdot$
 inverse problem

\section{Introduction and ecological background}

Reaction-diffusion models (hereafter RD models), although they
sometimes bear on simplistic assumptions such as infinite velocity
assumption and completely random motion of animals
\cite{Hol93}, are not in disagreement with certain dispersal
properties of populations observed in natural as well as
experimental ecological systems, at least qualitatively
\cite{ShiKaw97,Tur98,Mur02,OkuLev02}. In fact, since the work of Skellam \cite{Ske51}, RD theory has been the main analytical framework to study spatial spread of biological organisms, partly because it benefits from a well-developed mathematical theory.

The idea of modeling population dynamics with such models has emerged at the beginning of the 20$^{\hbox{th}}$ century, with random walk theories of organisms, introduced by  Pearson and Blakeman \cite{PeaBla06}. Then, Fisher  \cite{Fis37} and   Kolmogorov, Petrovsky, Piskunov \cite{kpp} independently used a reaction-diffusion equation as a model for population genetics.
The corresponding equation is
\begin{equation}\label{eqkpp}
\frac{\partial u}{\partial t}-D  \frac{\partial^2 u}{\partial x^2}=u\, (\mu- \gamma u), \ t>0, \ x\in(a,b)\subset\R,
\end{equation}
where $u=u(t,x)$ is the population density at time $t$ and space
position $x$, $D$ is the diffusion coefficient, and  $\mu$ and
$\gamma$ respectively correspond to the \emph{constant} intrinsic growth
rate and intraspecific competition coefficients. In the 80's, this
model has been extended to heterogeneous environments by Shigesada
et al. \cite{ShiKaw86}. The corresponding model  is of the type: \be\label{eqskt_gale}
\frac{\partial u}{\partial t}- \frac{\partial}{\partial x}\left(D(x)\frac{\partial u}{\partial x}\right)=u\, (\mu(x)-\gamma(x) u), \ t>0, \ x\in(a,b).\ee
The coefficients $\mu(x)$
and $\gamma(x)$ now depend on the space variable $x$ and can
therefore include some effects of environmental heterogeneity.
More recently, this model revealed that the heterogeneous
character of the environment played an essential role on species
persistence and spreading, in the sense that for different spatial
configurations of the environment, a population can survive or
become extinct and spread at different speeds, depending on the habitat spatial structure
(\cite{ShiKaw97}, \cite{BerHamRoq05a}, \cite{CanCos03},\cite{ElsHamRoq09}, \cite{HamFay10} ,\cite{RoqHam07}, \cite{RoqSto07}).
Thus, determining the coefficients in model (\ref{eqskt_gale})  is an important question, even for areas other than ecology (see \cite{Xin00} and references therein).

In this paper, we focus on the case of constant coefficients $D$ and $\gamma$:
\be\label{eqskt}
\frac{\partial u}{\partial t}-D  \frac{\partial^2 u}{\partial x^2}=u\, (\mu(x)-\gamma u), \ t>0, \ x\in(a,b),
\ee
 and
we address the question of the uniqueness of couples $(u,\mu(x))$ and triples $(u,\mu(x),\gamma)$ satisfying (\ref{eqskt_gale}),
given a localized measurement of $u$.

Uniqueness results of this type have been obtained for reaction-diffusion models, through the
Lipschtiz stability of the coefficient with respect to the solution $u$. Lipschtiz  stability is generally obtained
by using the method of Carleman estimates \cite{BukKli81}. Several publications starting from the paper by Isakov \cite{Isa93} and including the recent overview of the method of Carleman estimates applied to inverse coefficients problems \cite{KliTim04} provide results for the case of multiple measurements. The particular problem of the uniqueness of the couple $(u,\mu(x))$  satisfying (\ref{eqskt}) given  such multiple measurements has been investigated, together with Lipschtiz stability, in a previous work \cite{CriRoq08}. Placing ourselves in a bounded domain $\Omega$ of $\R^N$ with Dirichlet boundary conditions, we had to use the following measurements: (i) the density $u(0,x)$ in $\Omega$ at $t=0$;  (ii)  the density $u(t,x)$ for $(t,x)\in (t_0,t_1)\times \omega$, for some times $0<t_0<t_1$ and a subset $\omega \subset \subset \Omega$; (iii) the density $u(\theta,x)$  for all $x\in \Omega$, at some time $\theta\in (t_0,t_1)$.

Although the  result of \cite{CriRoq08} allows to determine $\mu(x)$ using partial measurements of $u(t,x),$ assumption (iii) implies that $u$ has to be known in the whole set $\Omega$. This last measurement (iii) is a key assumption in several other papers  on uniqueness and stability of solutions to     parabolic equations with respect to parameters (see Imanuvilov and Yamamoto \cite{ImmYam98}, Yamamoto and Zou \cite{YamZou01}, Belassoued and Yamamoto \cite{BelYam06} for scalar equations  and   Cristofol, Gaitan and Ramoul \cite{CriGai06} or Benabdallah, Cristofol, Gaitan and Yamamoto \cite{BenCri08} for systems).

Here, contrarily to  previous results obtained for this type of reaction-diffusion models, there are some regions in $(a,b)$ where $u$ is never
measured: we only require to know (i')
the density $u(0,x)$ in $(a,b)$ at $t=0$ and (ii') the density $u(t,x_0)$ and its spatial derivative $\ds{\frac{\partial u}{\partial x}}(t,x_0)$ for $t\in (0,\varepsilon)$ and some point $x_0$ in $(a,b)$ (see Remark  \ref{rem1} for a particular example of hypothesis (ii')). Thus a measurement of type (iii) is no more necessary. Furthermore, we show simultaneous uniqueness of two coefficients $\mu(x)$ and $\gamma$ provided that measurements of the second derivative $\ds{\frac{\partial^2 u}{\partial x^2}}(t,x_0)$ are available.

Our paper is organized as follows: in the next section, we give precise statements of our hypotheses and results; Section \ref{section_proof} is then dedicated to the proof of the results. Section \ref{section_num} is  devoted to the description of numerical examples illustrating how  the coefficient $\mu(x)$ can be approached using measures of the type (i') and (ii'). Those results are further discussed in Section \ref{sec:ccl}.

\section{Hypotheses and main results \label{sec:res}}

Let $(a,b)$ be an interval in $\R$. We consider the problem:
$$\left\{\baa{l}
\frac{\partial \ua}{\partial t}-D  \frac{\partial^2 \ua}{\partial x^2}=\ua\, (\mu(x)-\gamma \ua), \ t\ge 0, \ x\in(a,b),\\
\alpha_1 \ua (t,a) - \beta_1 \frac{\partial \ua}{\partial x} (t,a)=0, t>0, \\ \alpha_2 \ua (t,b) + \beta_2 \frac{\partial \ua}{\partial x} (t,b)=0, \ t>0,\\
\ua(0,x)=u_i(x), \ x\in(a,b).
\eaa
\right. \hspace{1cm} (\mathcal{P}_{\mu,\gamma})
$$
Our hypotheses on the coefficients are the following. Firstly, we assume that:
\be \label{hypmu}
\mu\in M:=\{\psi \in C^{0,\eta}([a,b]) \hbox{ such that }\psi \hbox{ is piecewise analytic on }(a,b)\},
\ee
for some $\eta \in (0,1]$. The space $C^{0,\eta}$ corresponds to H\"older continuous functions with exponent $\eta$ (see e.g. \cite{Fri64}). A function $\psi \in C^{0,\eta}([a,b])$ is called piecewise
analytic if it exists $n>0$ and an increasing sequence $(i_k)_{1\le k\le n}$ such that $i_1=a$, $i_n=b$, and $$\hbox{for all }x\in(a,b), \ \psi(x)=\sum_{j=1}^{n-1} \chi_{[i_j,i_{j+1})}(x)\varphi_j(x),$$for some analytic functions $\varphi_j$, defined on the intervals $[i_j,i_{j+1}]$, and where $\chi_{[i_j,i_{j+1})}$ are the characteristic functions of the intervals $[i_j,i_{j+1})$ for $j=1,\ldots, n-1$.

We also assume that $\gamma$ is a positive constant and that the boundary coefficients satisfy:
 \be \alpha_1,\alpha_2,\beta_1,\beta_2\ge 0 \hbox{ with }\alpha_1+\beta_1>0 \hbox{ and }\alpha_2+\beta_2>0. \label{HypBC}\ee

We furthermore make  the following hypotheses on the initial condition:

 \be u_i\ge 0, \ u_i\not \equiv 0 \hbox{ and }u_i\in C^{2,\eta}([a,b]),\label{HypDI}\ee
 for some $\eta$ in $(0,1)$, that is $u_i$ is a $C^2$ function such that $u_i''$ is H\"older continuous. In addition to that, we assume the following compatibility conditions:
\be\alpha_1 u_i (a) - \beta_1 u_i' (a)=0, \ \alpha_2 u_i (b) + \beta_2 u_i' (b)=0, \ \delta_{\beta_1}u_i''(a)=0, \ \delta_{\beta_2}u_i''(b)=0,\label{HypDI2}\ee
where $\delta_y$ is verifies: $\delta_0=1$ and $\delta_y=0$ if $y\neq 0$. We also need to assume that:
\be \label{hypui} \hbox{measure}(\{x \in (a,b), \ u_i(x)=0\})=0.
\ee

Under the assumptions (\ref{hypmu})-(\ref{HypDI2}), for each $\mu \in M$ and $\gamma>0$, the problem $(\mathcal{P}_{\mu,\gamma})$ has a unique solution $\ua\in C^{2,\eta}_{1,\eta/2}([0,+\infty)\times[a,b])$ (i.e. the derivatives up to order two in $x$ and order one in $t$ are H\"older continuous, see \cite{Fri64,Pao92} for a definition of H\"older continuity). Existence, uniqueness and regularity of the solution $u$ are classical. See e.g.  \cite[Ch. 1]{Pao92}.

\

Let us state our main results:
\begin{theorem}
\label{th:uniq1}
Let $\mu,\tmu \in M,$ and $\gamma>0$, and assume that the solutions $\ua$ and $\ub$ to $(\mathcal{P}_{\mu,\gamma})$ and $(\mathcal{P}_{\tmu,\gamma})$ satisfy, at some $x_0\in (a,b),$  and for some $\varepsilon>0$ and all  $t$ in $(0,\varepsilon)$: \ba  \ua(t,x_0) & = & \ub(t,x_0), \label{hypth1aa} \\ \frac{\partial \ua}{\partial x}(t,x_0) & = & \frac{\partial \ub}{\partial x} (t,x_0) . \label{hypth1ab} \ea Assume furthermore that
\be u_i(x_0)\neq 0 \hbox{ or } \frac{\partial^2 \ua}{\partial x^2}(t,x_0)=\frac{\partial^2 \ub}{\partial x^2} (t,x_0) \hbox{ for } t\in(0,\varepsilon). \label{hypth1b}\ee
 Then, we have $\mu\equiv\tmu$ on $[a,b]$ and consequently $\ua\equiv \ub$ in $[0,+\infty)\times[a,b]$. If $\beta_1>0$ (resp. $\beta_2>0$), this statement remains true when $x_0=a$ (resp. $x_0=b$).
\end{theorem}
\begin{remark}
This result remains valid if $\gamma=\gamma(x)$ is a given, positive function in $C^{0,\eta}([a,b]).$
\end{remark}
However, the conclusion of Theorem \ref{th:uniq1} is not true in general without the assumption  (\ref{hypth1ab}):
\begin{proposition}
\label{prop:uniq1}
Let $\mu \in M$ and $\gamma>0$. Assume that $\alpha_1=\alpha_2$  and $\beta_1=\beta_2$ and that $u_i$ is symmetric with respect to $x=(a+b)/2.$
Let $\tmu:=\mu(b-(x-a))$ for $x\in [a,b].$ Then, the solutions $\ua$ and $\ub$ to $(\mathcal{P}_{\mu,\gamma})$ and $(\mathcal{P}_{\tmu,\gamma})$ satisfy $u(t,\frac{a+b}{2}) = \ub(t,\frac{a+b}{2})$ for all $t\ge 0.$
\end{proposition}

Under an additional assumption on the initial condition $u_i$, we are able to obtain a uniqueness result for triples $(\ua,\mu,\gamma)$:
\begin{theorem}
\label{th:uniq2}
Let $\mu,\tmu \in M,$ and $\gamma,\tg>0$. Assume that, at some $x_0 \in (a,b)$, $u_i(x_0)=0$. Assume furthermore that the solutions $\ua$ and $\uc$ to $(\mathcal{P}_{\mu,\gamma})$ and $(\mathcal{P}_{\tmu,\tg})$ satisfy, for some $\varepsilon>0$ and for all  $t$ in $(0,\varepsilon)$: \ba \ua(t,x_0) & = &\uc(t,x_0), \label{hypth2a} \\ \frac{\partial \ua}{\partial x}(t,x_0)& = & \frac{\partial \uc}{\partial x} (t,x_0), \label{hypth2b} \\ \frac{\partial^2 \ua}{\partial x^2}(t,x_0)&= &\frac{\partial^2 \uc}{\partial x^2} (t,x_0). \label{hypth2c} \ea  Then, we have $\mu\equiv\tmu$ on $[a,b]$ and $\gamma=\tg$. Consequently $\ua\equiv \uc$ in $[0,+\infty)\times[a,b]$. If $\beta_1>0$ (resp. $\beta_2>0$), this statement remains true for $x_0=a$ (resp. $x_0=b$).
\end{theorem}

\begin{remarks}
\begin{itemize}
\item A particular example where hypotheses (\ref{hypth1aa}-\ref{hypth1b}) of Theorem \ref{th:uniq1} (resp. hypotheses (\ref{hypth2a}-\ref{hypth2c}) of Theorem \ref{th:uniq2}) are fulfilled is whenever, for some subset $\omega$ of $(a,b)$, $\ua(t,x)=\ub(t,x)$ for $t\in(0, \varepsilon)$ and all $x\in \omega$ (resp. $x_0\in \omega$ and $\ua(t,x)=\uc(t,x)$ in $(0,\varepsilon)\times \omega$). Note that, under this hypothesis, the previous results  \cite{CriRoq08} did not imply uniqueness; indeed, an additional assumption of type (iii) was required (cf. the introduction  section).

\item The uniqueness result of Theorem \ref{th:uniq2} cannot be adapted to the stationary equation associated to $(\mathcal{P}_{\mu,\gamma})$: $-p''=p\, (\mu(x)-\gamma p)$ (see e.g. \cite{BerHamRoq05a} for the existence and uniqueness of the stationary state $p>0$). Indeed, for any $\tau \in (0,1),$ setting $\tmu=\mu-\tau \gamma p$ and $\tg= (1-\tau)\gamma$, we obtain $-p''=p\, (\tmu(x)-\tg p)$, whereas $\tmu\not \equiv \mu$ and $\tg \not \equiv \gamma$. Thus, a measurement of $p$, even on the whole interval $[a,b]$, does not provide a unique couple $(\mu,\gamma)$.

\item The subset $M$ of $C^{0,\eta}([a,b])$ made of piecewise analytic functions is much larger than the set of analytic functions on $[a,b]$. It indeed contains some functions whose regularity is not higher than $C^{0,\eta}$, and some functions which are constant on some subsets of $[a,b]$. Our results hold true if  $M$ is replaced by any subset $M'$ of $C^{0,\eta}([a,b])$ such that for any couple of elements in $M'$, the subset of $[a,b]$ where these two elements intersect has a finite number of connected components.
\end{itemize}
\label{rem1}
\end{remarks}
\section{Proofs}\label{section_proof}

Let $\mu,\tmu \in M,$ and $\gamma,\tg>0$. Let $\ua$ be the solution to $(\mathcal{P}_{\mu,\gamma})$  and $\uc$ the solution to $(\mathcal{P}_{\tmu,\tg})$. We set $$U:=\ua-\uc \hbox{ and }m:=\mu-\tmu.$$ The function $U$ satisfies:

\begin{equation}
\frac{\partial U}{\partial t}- D  \frac{\partial^2 U}{\partial x^2}=\tmu U- \tg U(\ua+\uc)+\ua( m - \ua (\gamma-\tg)),
\label{eqU}
\end{equation}
for $t\ge 0$ and $x\in(a,b),$ and
\begin{equation}\left\{\baa{l}
\alpha_1 U (t,a) - \beta_1 \frac{\partial U}{\partial x} (t,a)=0, \ \alpha_2 U (t,b) + \beta_2 \frac{\partial U}{\partial x} (t,b)=0, \ t>0,\\
U(0,x)=0, \ x\in(a,b).
\eaa
\right.
\label{eqUb}
\end{equation}

\

\underline{Proof of Theorem \ref{th:uniq1}:} In that case $\gamma=\tg$. Equation (\ref{eqU}) then reduces to
\begin{equation}
\frac{\partial U}{\partial t}- D  \frac{\partial^2 U}{\partial x^2}=\tmu U- \gamma U(\ua+\ub)+\ua \, m.
\label{eqU1}
\end{equation}

\

\textit{Step 1: We prove that $m(x_0)=0.$}

\

It follows from hypothesis (\ref{hypth1aa}) that,  for all $t \in [0,\varepsilon)$, $U(t,x_0)=0$ and thereby, $$\frac{\partial U}{\partial t}(t,x_0)=0\hbox{ for all }t\in[0,\varepsilon).$$  If $u_i(x_0) \neq 0$, then, since $U(0,\cdot)\equiv 0$ we  deduce from (\ref{eqU1}) applied at $t=0$ and $x=x_0$ that $u_i(x_0) m(x_0)=0,$ and therefore $m(x_0)=0$.

If $u_i(x_0) =0$, from (\ref{hypth1b}), we have $\frac{\partial^2 U}{\partial x^2}(t,x_0)=0$ for all $t\in[0,\varepsilon)$. Applying equation (\ref{eqU1}) at $t=\varepsilon/2$ and $x=x_0,$ we get $$\ua\left(\frac{\varepsilon}{2},x_0\right) m(x_0)=0.$$ If $x_0 \in (a,b)$, the strong parabolic maximum principle (Corollary \ref{corPM}) applied to $\ua$ implies that $\ua(\varepsilon/2,x_0)>0$. As a consequence we again get $m(x_0)=0$. Lastly, if $x_0=a$ and $\beta_1>0$ the Hopf's Lemma applied to $\ua$ again implies that $\ua(\varepsilon/2,x_0)>0$. Indeed, assume on the contrary that $\ua(\varepsilon/2,x_0)=\ua(\varepsilon/2,a)=0$. The boundary condition $\alpha_1 \ua (t,a) - \beta_1 \frac{\partial \ua}{\partial x} (t,a)=0$ implies: $$\beta_1 \frac{\partial \ua}{\partial x} \left(\frac{\varepsilon}{2},a\right)=0,$$ which is impossible from Hopf's Lemma (Corollary \ref{corPM} and Theorem \ref{thPM} (b) and (c)). Thus $\ua(\varepsilon/2,x_0)>0$ and, again, $m(x_0)=0$. A similar argument holds for $x_0=b$, whenever $\beta_2>0.$

Under the assumptions of Theorem \ref{th:uniq1}, we therefore always obtain $m(x_0)=0.$

\

\textit{Step 2: We prove that $m\equiv 0$.}

\

Let us now set
$$b_1:=\sup\{x \in [x_0,b] \hbox{ s.t. }m\hbox{ has a constant sign on }[x_0,x]\}.$$By ``constant sign" we mean that either $m\ge0$ on $[x_0,x]$ or
$m\le 0$ on $[x_0,x]$. Then, four possibilities may arise:
\begin{itemize}
\item (i) $m=0$ on $[x_0,b_1]$ and $b_1<b$,\item (ii) $m\ge 0$ on $[x_0,b_1]$ and it exists $x_1 \in (x_0, b_1)$ such that $m(x_1)>0$,
\item (iii) $m\le 0$ on $[x_0,b_1]$ and it exists $x_1 \in (x_0, b_1)$ such that $m(x_1)<0$,
\item (iv) $b_1=b$, and $m=0$ on $[x_0,b]$.
\end{itemize}

Assume (i). Then, by definition of $b_1$, there exists a  decreasing sequence $y_k\to b_1,$ $y_k>b_1$, such that $|m(y_k)|>0$ for all $k  \ge 0$.
Assume that it exists $k_0$ such that $|m(x)|>0$ for all $x\in (b_1,y_{k_0})$. By continuity, $m$ does not change sign in $(b_1,y_{k_0})$, and therefore in $[x_0,y_{k_0}]$. This contradicts the definition of $b_1$. Thus, \be \label{zk}\hbox{ for all }k, \hbox{ it exists }z_k\in (b_1,y_k)\hbox{ such that }m(z_k)=0.\ee
Since $\mu$ and $\tmu$ belong to $M$, the function $m$ also belongs to $M$ and is therefore piecewise analytic on $(a,b)$. Thus, the set $\{x\in(a,b) \hbox{ s.t. }m(x)=0\}$ has a finite number of connected components. This contradicts (\ref{zk}) and rules out possibility (i).

Now assume (ii). By continuity of $m$, and from hypothesis (\ref{hypui}) on $u_i$, we can assume that $u_i(x_1)>0$. Since $m(x_1)>0$ and $U(0,\cdot)\equiv 0$, it follows from (\ref{eqU1})
 that $$\frac{\partial U}{\partial t}(0,x_1)= u_i(x_1) m(x_1)>0.$$ Thus, for $\varepsilon_1>0$ small enough, $U(t,x_1)>0$ for  $t\in(0,\varepsilon_1]$. As a consequence, $U$ satisfies:
\begin{equation}\left\{\baa{l}
\frac{\partial U}{\partial t}- D  \frac{\partial^2 U}{\partial x^2}-(\tmu-\gamma \ua- \gamma \uc) U \ge 0, \ t \in (0, \varepsilon_1], \ x\in (x_0,x_1),
\\
U (t,x_0)=0 \hbox{ and }U(t,x_1)>0 , \ t\in(0,\varepsilon_1], \\
U(0,x)=0, \ x\in (x_0,x_1).
\eaa
\right.
\label{eqU2}
\end{equation}
Moreover,
\begin{lemma}
We have $U(t,x)>0$ in $(0,\varepsilon_1)\times(x_0,x_1)$.
\label{lem1}
\end{lemma}
\textbf{Proof of Lemma \ref{lem1}:}
Set $W=U e^{-\lambda t},$ for some $\lambda>0$ large enough such that $c(t,x):=\tmu-\gamma \ua- \gamma \uc-\lambda \le 0$ in $(x_0,x_1).$ The function $W$ satisfies
$$\frac{\partial W}{\partial t}-D  \frac{\partial^2 W}{\partial x^2}-c(t,x) W \ge 0,  \ t \in (0, \varepsilon_1], \ x\in (x_0,x_1).$$
Assume that it exists a point $(t^*,x^*)$ in $(0,\varepsilon_1)\times (x_0,x_1)$ such that $U(t^*,x^*)< 0$. Then, since $W(t,x_0)=0$ and $W(t,x_1)>0$  for $t\in (0,\varepsilon_1)$, and since $W(0,x)=U(0,x)= 0,$ $W$ admits a minimum $m^*< 0$ in $(0,\varepsilon_1]\times (x_0,x_1)$. Theorem \ref{thPM} (a) applied to $W$ implies that $W\equiv m^*< 0$ on $[0,\varepsilon_1]\times [x_0,x_1]$, which is impossible. Thus $W\ge 0$
in $[0, \varepsilon_1]\times [x_0,x_1].$ Theorem \ref{thPM} (a) and (c) then implies that $W>0$ and consequently $U(t,x)>0$ in $(0,\varepsilon_1)\times(x_0,x_1)$. $\Box$

\

Since $U(t,x_0)=0$, the Hopf's lemma (Theorem \ref{thPM} (b) and (c)) also implies that $\ds{\frac{\partial U}{\partial x}(t,x_0)>0}$ for all $t\in (0,\varepsilon_1).$ This contradicts hypothesis (\ref{hypth1ab}). Possibility (ii) can therefore be ruled out.

Applying the same arguments to $-U$, possibility (iii) can also be rejected.
Finally, only (iv) remains.

Setting $$a_1:=\inf\{x\in [a,x_0] \hbox{ s.t. }m\hbox{ has a constant sign on }[x,x_0]\},$$ the same argument as above shows that $a_1=a$ and $m=0$ on $[a,x_0]$. Thus, finally, $m\equiv 0$ on $[a,b]$ and this concludes the proof of Theorem \ref{th:uniq1}. $\Box$

\

\underline{Proof of Theorem \ref{th:uniq2}:} From the assumptions (\ref{hypth2a}) and (\ref{hypth2c}) of Theorem \ref{th:uniq2},  equation  (\ref{eqU}) at $x=x_0$ reduces to
$$\ua(t,x_0)\, (m(x_0) - \ua(t,x_0) (\gamma-\tg))=0 \hbox{ for }t\in[0,\varepsilon).$$
If $x_0\in (a,b),$  the strong parabolic maximum principle (Corollary \ref{corPM}) implies that $\ua(t,x_0)>0$ for all $t>0$. This remains true if $x_0=a$ (if $\beta_1>0$) or $x_0=b$ (if $\beta_2>0$); cf. the proof of Theorem \ref{th:uniq1}. We therefore get:
\be
\label{eqU3}
m(x_0) = \ua(t,x_0) (\gamma-\tg) \hbox{ for }t\in(0,\varepsilon).
\ee
From the continuity of $t\mapsto \ua(t,x_0)$ up to $t=0$, we have $m(x_0)=u_i(x_0) (\gamma-\tg)$. Thus, $u_i(x_0)=0$ implies that  $m(x_0)=0$ which in turns implies from (\ref{eqU3}), and since $\ua(t,x_0)>0$ for $t>0$, that $\tg=\gamma$. The end of the proof is therefore similar to that of Theorem \ref{th:uniq1}. $\Box$

\begin{remark}
Extension of the arguments used in the previous proof to higher dimensions is not straightforward. Indeed, placing ourselves  in a bounded domain $\Omega$ of $\R^N,$ with $N\ge 2$, we may consider the largest region $\Omega_1$ in $\Omega$, containing $x_0$ and such that $m$ has a constant sign in $\Omega_1$. Consider in the above proof the possibility (ii)$_N$ (instead of (ii)): $m\ge 0$ on $\overline{\Omega_1}$ and it exists $x_1 \in \Omega$ such that $m(x_1)>0$.
    Then it exists a subset $\omega_1$ of $\Omega_1$, such that $x_0 \in \partial \omega_1$ and  $u(t,x)>0$ on a portion of $\partial \omega_1$. However, we cannot assert that $U(t,x)\ge 0$ on $\partial \omega_1$, and (ii)$_N$ can therefore not be ruled out as we did for (ii).
\end{remark}

\

\underline{Proof of Proposition \ref{prop:uniq1}:} Under the assumptions of Proposition \ref{prop:uniq1}, we observe that $\ub(t,b-(x-a))$ is a solution of $(\mathcal{P}_{\mu,\gamma}).$ In particular, by uniqueness, we have $$u(t,x)=\ub(t,b-(x-a)), \hbox{ for all }t\ge 0 \hbox{ and }x\in [a,b].$$It follows that $u(t,\frac{a+b}{2}) = \ub(t,\frac{a+b}{2})$ for all $t\ge 0.$ $\Box$

\section{Numerical computations}\label{section_num}

The purpose  of this section is to verify numerically that the measurements (\ref{hypth1aa}-\ref{hypth1ab}) of Theorem \ref{th:uniq1} allow to obtain a good approximation of the coefficient $\mu(x)$, when $\gamma$ is known.

Assuming that $\mu$ belongs to a finite-dimensional subspace $E\subset M$ and measuring  the distance between the measurements of
the solutions of $(\mathcal{P}_{\mu,\gamma})$ and $(\mathcal{P}_{\tmu,\gamma})$ through the function
$$G_\mu(\tmu)=\|\ua(\cdot ,x_0)-\ub(\cdot,x_0)\|_{L^2(0,\varepsilon)}+\|\frac{\partial \ua}{\partial x}(\cdot,x_0)-\frac{\partial \ub}{\partial x}(\cdot,x_0)\|_{L^2(0,\varepsilon)},$$  we look for  the coefficient $\mu(x)$ as a minimizer of the function $G_\mu$. Indeed, $G_\mu(\mu)=0$ and, from Theorem \ref{th:uniq1}, this is the unique global minimum of $G_\mu$ in $M$.

Solving $(\mathcal{P}_{\mu,\gamma})$ by a numerical method (see Appendix B) gives an approximate solution $u^h$. In our numerical
tests, we therefore replace $G_\mu$ by the discretized functional
$$\widehat{G}_\mu(\tmu):=\|\ua^h(\cdot ,x_0)-\ub^h(\cdot,x_0)\|_{L^2(0,\varepsilon)}+\|\frac{\partial \ua^h}{\partial x}(\cdot,x_0)-\frac{\partial \ub^h}{\partial x}(\cdot,x_0)\|_{L^2(0,\varepsilon)}.$$

\begin{remark}
Since $(\mathcal{P}_{\mu,\gamma})$ and $(\mathcal{P}_{\tmu,\gamma})$ are solved with the same (deterministic) numerical method, we have $\widehat{G}_\mu(\mu)=0$. Thus $\mu$ is a global minimizer of $\widehat{G}_\mu$. However, this minimizer  might not be unique.
\end{remark}

\subsection{State space $E$ \label{subsec_E}}

We fix $(a,b)=(0,1)$ and we assume that the function $\mu$ belongs to a subspace  $E \subset M$ defined by:
$$E:=\left\{\tmu \in  C^{0,\eta}([0,1]) \, | \, \exists \  (h_i)_{0\le i \le n}\in \R^{n+1}, \ \tmu(x)=\sum_{i=0}^{n}h_i \cdot j\left((n-2)\left(x-c_i\right)\right) \hbox{ on }[0,1]\right\},$$ with $c_i=\frac{i-1}{n-2}$ and
$j(x)=\left\{\baa{l} \exp\left(\frac{4 x^2}{x^2-4}\right), \hbox{ if }x\in(-2,2), \\ 0 \hbox{ otherwise.}
\eaa \right.$

\subsection{Minimization of $\widehat{G}_\mu$ in $E$ \label{subsec_minG}}

For the numerical computations,  we fixed  $D=0.1$, $\gamma=1$, $\alpha_1=\alpha_2=0$ and $\beta_1=\beta_2=1$ (Neumann boundary conditions). Besides, we assumed that $u_i\equiv 0.2$, $\varepsilon=0.3$ and $x_0=2/3.$ The integer $n$ was set to $10$ in the definition of $E$.

Numerical computations were carried out for $100$ functions $\mu_k$ in $E:$ $$\mu_k=\sum_{i=0}^{n}h_i^k \cdot j\left[(n-2)\left(x-c_i\right)\right], \ k=1\ldots 100,$$whose components $h_i^k$ were randomly drawn from  a uniform distribution in $(-5,5).$

Minimizations of the functions $\widehat{G}_{\mu_k}$ were performed using MATLAB's$^{\circledR}$ \textit{fminunc} solver \footnote{ MATLAB's$^{\circledR}$ \textit{fminunc} medium-scale optimization algorithm uses a Quasi-Newton method with a mixed quadratic and cubic line search procedure. Our stopping criterion was based on the maximum number of evaluations of the function $\widehat{G}_\mu$, which was set at $2\cdot 10^3.$}. This led to $100$ functions $\mu^*_k$ in $E$, each one corresponding to a
computed approximation for a minimizer of
the function $\widehat{G}_{\mu_k}$. In our numerical tests, we obtained values of $\widehat{G}_{\mu_k}(\mu^*_k)$ in $(5\cdot 10^{-7}, 10^{-5})$, with an average of $5\cdot 10^{-6}$ and a standard deviation of $2\cdot 10^{-6}.$

The values $\|\mu_k-\mu^*_k\|_{L^2([0,1])}/\|\mu_k\|_{L^2([0,1])}$, for $k=1\ldots 100$, are comprised between $5 \cdot 10^{-3}$ and $0.16$, with an average value of $0.04$ and a standard deviation of $0.03$.

\begin{figure}
\centering
\subfigure[$\mu$ (plain line) and $\mu^*$ (dotted line)]{
\includegraphics*[width=7cm]{exple1_rev.eps}}
\subfigure[$\mu$ (plain line) and $\underline{\mu}^*$ (dotted line)]{ \includegraphics*[width=7cm]{exple1H_rev.eps}}
\caption{(a) An example of function $\mu$ in $E$, together with a function $\mu^*$ which was obtained by minimizing $\widehat{G}_{\mu}.$ In this case  $\|\mu-\mu^*\|_{L^2([0,1])}/\|\mu\|_{L^2([0,1])}=0.03$ and $\widehat{G}_{\mu}(\mu^*)=2 \cdot 10^{-6}$. (b) The same function $\mu$ together with the function $\underline{\mu}^*$ obtained by minimizing  $\widehat{H}_{\mu}$. Here, $\|\mu-\underline{\mu}^*\|_{L^2([0,1])}/\|\mu\|_{L^2([0,1])}=0.47$ and $\widehat{H}_{\mu}(\underline{\mu}^*)=2 \cdot 10^{-6}.$}
\label{fig:exple}
\end{figure}

Fig. \ref{fig:exple} (a) depicts an example of function $\mu$ in $E$, together with a function $\mu^*$ which was obtained by minimizing $\widehat{G}_{\mu}.$

\

\subsection{Test of another criterion $H_\mu$ \label{subsec_minH}}

In this section, we illustrate that measurement (\ref{hypth1aa}) alone  cannot be used for reconstructing $\mu$. Replacing $G_\mu$ by:
$$H_\mu(\tmu)=\|\ua(\cdot,x_0)-\ub(\cdot,x_0)\|_{L^2(0,\varepsilon)},$$and setting
$\widehat{H}_\mu(\tmu):=\|\ua^h(\cdot ,x_0)-\ub^h(\cdot,x_0)\|_{L^2(0,\varepsilon)},$
we performed the same analysis as above, with the same samples $\mu_k\in E$ and the same parameters.

The corresponding values of $\widehat{H}_{\mu}(\underline{\mu}^*_k)$ are comparable to those obtained in Section \ref{subsec_minG}.  Namely, these values are included in $(2\cdot 10^{-8}, 10^{-5}),$ with average $2\cdot 10^{-6},$ and standard deviation $3\cdot 10^{-6}.$
However, the corresponding values of the distance $\|\mu_k-\underline{\mu}^*_k\|_{L^2([0,1])}/\|\mu_k\|_{L^2([0,1])}$ are far larger than those obtained in Section \ref{subsec_minG}: these values are comprised between $0.08$ and $1.64$, with an average of $0.56$ and a standard deviation of $0.34$.

Using the same sample $\mu \in E$ as in Fig. \ref{fig:exple} (a), we present in Fig. \ref{fig:exple} (b) the approximation $\underline{\mu}^*$ obtained by minimizing $\widehat{H}_{\mu}$. In this case, the distance $\|\mu-\underline{\mu}^*\|_{L^2([0,1])}/\|\mu\|_{L^2([0,1])}$ is $18$ times larger than $\|\mu-\mu^*\|_{L^2([0,1])}/\|\mu\|_{L^2([0,1])}.$

\section{Discussion \label{sec:ccl}}

Studying the reaction-diffusion problem $(\mathcal{P}_{\mu,\gamma})$ with a nonlinear term of the type $u \, (\mu(x)-\gamma u),$ we have
proved in Section \ref{sec:res} that  knowing  $u$ and its first spatial derivative
at a single point $x_0$ and for small times $t\in (0,\varepsilon)$ is sufficient to completely determine the couple $(u(t,x),\mu(x))$. Additionally, if the second spatial derivative is also measured at $x_0$ for $t\in (0,\varepsilon)$, the triplet $(u(t,x),\mu(x),\gamma)$ is also completely determined.

These uniqueness results  are mainly the consequences of Hopf's Lemma and of an hypothesis on the set $M$ of coefficients which $\mu(x)$ belongs to. This hypothesis implies that two coefficients in $M$ can be equal only over a set having a finite number of connected components.

The theoretical results of Section \ref{sec:res} suggest that the coefficients $\mu(x)$ and $\gamma$ can be numerically determined using only measurements of the solution $u$ of $(\mathcal{P}_{\mu,\gamma})$ and of its spatial derivatives at one point $x_0,$ and for $t\in (0,\varepsilon)$.
Indeed, the numerical computations of Section \ref{section_num} show that, when $\gamma$ is known,
the coefficient $\mu(x)$ can be estimated  by minimizing a function $G_\mu$. The function $\ub$ being the solution of $(\mathcal{P}_{\tmu,\gamma}),$ we defined  $G_\mu(\tmu)$ as the distance between  $(u,\partial u/ \partial x)(\cdot,x_0)$ and $(\ub,\partial \ub/\partial x)(\cdot,x_0),$ in the $L^2(0,\varepsilon)$ sense.

The numerical computations presented in Section \ref{subsec_minG} were carried out on $100$ samples of functions $\mu_k$ chosen in a finite-dimensional subspace of $M$. In each case, a good approximation $\mu^*_k$ of $\mu_k$ was obtained. The average relative $L^2$-error  between $\mu^k$ and $\mu_k^*$ is $30$ times smaller than the average relative $L^2$-error between $\mu^k$ and the constant function $\mu_k(x_0)$.
Thus, a measurement of $u$ and of its first spatial derivative at a point $x_0$ (and for $t\in (0,\varepsilon)$) indirectly gives more information on the global shape of $\mu$ than a direct measure of $\mu$ at $x_0.$
These good results, in spite of the computational error, indicate $L^2$-stability of the coefficient $\mu$ with respect to single-point measurements of the solution $u$ of $(\mathcal{P}_{\mu,\gamma})$ and of its spatial derivative.

Proposition \ref{prop:uniq1} shows that the uniqueness result
of Theorem \ref{th:uniq1} is not true
without the assumption (\ref{hypth1ab}) on the spatial derivatives. This suggests that measurement (\ref{hypth1aa})  alone  cannot be used for reconstructing $\mu.$ In Section
\ref{subsec_minH}, working with the same samples $\mu_k$ as those discussed
above, we obtained approximations $\underline{\mu}^*_k$ of
$\mu_k$ by minimizing a new function $H_\mu$, which measures  the distance between $u(\cdot,x_0)$ and $\ub(\cdot,x_0).$
The  average relative $L^2$-error between $\mu_k$ and $\underline{\mu_k}^*$  was $14$ times larger than the average relative $L^2$-error separating   $\mu_k$ and $\mu^*_k.$ This confirms the usefulness of the spatial derivative measurements for the reconstruction of $\mu.$

\section*{Acknowledgements}

The authors would like to thank two anonymous referees for their valuable comments on an earlier version of this paper.
The first author is supported by the French ``Agence Nationale de la Recherche" within the projects ColonSGS, PREFERED, and URTICLIM.

\section*{Appendix A: maximum principle}

The following version of the parabolic maximum principle can be found in \cite[Ch. 2]{Fri64} and \cite[Ch. 3]{ProWei67}.

\begin{theorem}
Let $u \in C^{2}_{1}((0,T]\times (x_1,x_2))\cap C([0,T]\times [x_1,x_2]),$ for some $T>0$ and $x_1,x_2\in\R.$ Let $c(t,x)\le 0 \in C^{0,\eta}_{0,\eta/2}([0,T]\times [x_1,x_2])$, for some $\eta \in (0,1]$.

Suppose that $\ds{\frac{\partial u}{\partial t}-D  \frac{\partial^2 u}{\partial x^2}-c(x) u \ge 0}$ for  $t\in(0,T]$ and $x\in (x_1,x_2)$.

\

(a) If $u$ attains a minimum $m^* \le 0$ at a point $(t^*,x^*)\in (0,T]\times (x_1,x_2),$ then $u(t,x)\equiv m^*$ on $[0,t^*]\times [x_1,x_2]$.

(b) (Hopf's Lemma) If $u$ attains a minimum $m^* \le 0$ at a point $(t^*,x_1)$ (resp. $(t^*,x_2)$), with $t^*>0$, then either $\frac{\partial u}{\partial x}(t^*,x_1)>0$ (resp. $\frac{\partial u}{\partial x}(t^*,x_2)<0$) or $u(t,x)\equiv m^*$ on $[0,t^*]\times [x_1,x_2]$.

(c) If $u\ge 0,$ the results (a) and (b) remain true without the assumption $c(t,x)\le 0.$
\label{thPM}
\end{theorem}

\noindent An immediate corollary of this theorem is:
\begin{corollary}
The solution $u(t,x)$ of $(\mathcal{P}_{\mu,\gamma})$ is strictly positive in $(0,+\infty)\times(a,b)$.
\label{corPM}
\end{corollary}

\textbf{Proof of Corollary \ref{corPM}:} Assume that it exists $(t^*,x^*)\in (0,+\infty)\times (a,b)$ such that $u(t^*,x^*)<0$.

Set $w(t,x)=u  \, e^{-\lambda t},$ for $\lambda>0$ large enough such that $$c(t,x):=\mu(x) - \gamma u - \lambda\le 0 \hbox{ in } [0,t^*]\times [a,b].$$The function $w$ satisfies:
$$\frac{\partial w}{\partial t}-D  \frac{\partial^2 w}{\partial x^2}-c(t,x) w =0.$$Since $w(0,x)=u_i(x)\ge 0$ in $(a,b)$ and $w(t^*,x^*)<0,$ the function $w$ admits a minimum $m^*<0$ in $(0,t^*]\times [a,b].$ From Theorem \ref{thPM} (a), and since $u_i\not \equiv 0,$ this minimum is attained at a boundary point: it exits $t'\in (0,t^*]$ such that $w(t',a)=m^*<0$ or $w(t',b)=m^*<0$. Without loss of generality, we can assume in the sequel that $w(t',a)=m^*<0.$ From Theorem \ref{thPM} (b), we obtain $\frac{\partial w}{\partial x}(t',a)>0.$ Using the boundary conditions in problem $(\mathcal{P}_{\mu,\gamma})$, we finally get: $$\alpha_1 \, m^* = \beta_1 \, \frac{\partial w}{\partial x}(t',a)>0.$$Using assumption (\ref{HypBC}), we get a contradiction. Thus $u(t,x)\ge 0$ in $(0,+\infty)\times (a,b).$ The conclusion then follows from Theorem \ref{thPM} (c). $\Box$

\

\section*{Appendix B: numerical solutions of $(\mathcal{P}_{\mu,\gamma})$ and $(\mathcal{P}_{\tmu,\gamma})$}

The equations $(\mathcal{P}_{\mu,\gamma})$ and $(\mathcal{P}_{\tmu,\gamma})$ were solved using Comsol Multiphysics$^{\circledR}$ time-dependent solver, using second order finite element method (FEM) with 960 elements. This solver uses a method of lines approach incorporating variable order variable stepsize backward differentiation formulas. Nonlinearities are treated using a Newton's method. The interested reader can get more information in Comsol Multiphysics$^{\circledR}$ user's guide.

\bigskip

\section*{References}

config: arxiv


TITLE: Calculating topological $K(X)$ for complex projective manifolds
QUESTION [2 upvotes]: In the introduction to the book Vector bundles and K-theory
http://pi.math.cornell.edu/~hatcher/VBKT/VBpage.html
two approaches to classification of (topological) vector bundles are discussed - the topological $K$-theory and Characteristic classes. Having algebraic geometry in mind, characteristic classes are omni-present when one deals with complex projective manifolds (Grothendick-Riemann-Roch...). One computes them quite often. However I don't seem to remember calculations of the whole ring $K(X)$ in books on algebraic geometry. So I wonder, do people compute (the topological) $K(X)$ for complex projective manifolds? And if they do, in which circumstances and for which purpose?

REPLY [5 votes]: There is an Atiyah-Hirzebruch spectral sequence $H^*(X;\mathbb{Z}[u,u^{-1}])\Longrightarrow K^*(X)$, in which the differentials are always torsion-valued.  Thus, if $H^*(X;\mathbb{Z})$ is torsion-free, then the spectral sequence collapses, and $K^*(X)$ has a natural filtration whose associated graded ring is isomorphic to $H^*(X;\mathbb{Z}[u,u^{-1}])$.  There are many complex projective varieties $X$ to which this applies.  Moreover, in these cases it is usually not hard to find explicit generators of the $K$-theory.  In particular, any complex vector bundle $V$ over $X$ has Chern classes $c^H_i(V)\in H^{2i}(X;\mathbb{Z})$ and also Chern classes $c^K_i(V)\in K^{2i}(X)$.  If we have a basis for $H^*(X;\mathbb{Z})$ consisting of monomials in cohomological Chern classes, then the corresponding monomials in $K$-theory Chern classes will give a basis for $K^*(X)$ over $\mathbb{Z}[u,u^{-1}]$.


TITLE: Finding roots of a Complex Polynomial
QUESTION [2 upvotes]: Question
Given that x = 3 is a solution to $$ x^3 - (7+3i)x^2 + (16+15i)x - 6(2+3i) = 0 $$ find the other two solutions.

What I have attempted;
If $x = 3$ is a root then $(x-3)$ is a factor
so $$ (x-3)(x^2 + Ax + B) = 0 $$
$$  x^3 + (A-3)x^2 + (B-3A)x - 3B = 0 $$
Equation Coefficients
$$ x^3 - (7+3i)x^2 + (16+15i)x - 6(2+3i) = 0 $$
$$ x^2 :−3+A=−7−3i $$
$$ ⇒ A=−4−3i  $$
$$\text{Constant: } -3B = -6(2+3i) $$
$$ ⇒ B=4+6i $$
$$ (x-3)(x^2 -(4+3i)x + 4+6i) = 0 $$
$$ x = {-b\pm\sqrt{b^2-4ac} \over 2a} $$
$$ x = {4+3i\pm\sqrt{(4+3i)^2-4(4+6i)} \over 2} $$
$$ x = {4+3i\pm\sqrt{-9} \over 2} $$
$$ x = {4+3i±3i\over 2} $$
$$ x_1 = 3 $$
$$ x_2 = 2+3i $$
$$ x_3 = 2 $$
Hopefully this is correct , and if so I was wondering if there is an alternative method in solving this.
I was thinking because we are given x = 3 is a root and (x-3) is a factor we can do polynomial division with complex numbers? Is it possible to do polynomial division with complex  numbers? If so can someone show how to get the same answer by using that method..

REPLY [0 votes]: Call the cubic $p(x).$ $\bullet$ Method 1: We have $p(3)=0.$ We have $$p(x)=p(x)-p(3)=(x-3)p'(3)+(x-3)^2p''(3)/2+(x-3)^3p'''(3)/6=$$ $$=[x-3]\cdot [p'(3)+(x-3)p''(3)/2+(x-3)^2p'''(3)/6].$$ For computation, let $x=y+3$ and find the solutions, in $y$, of $ p'(3)+y p''(3)/2+y^2 p'''(3)/6=0.$ $\bullet$  Method 2. For any cubic $p$ with leading term $A x^3$ we have $p(x)=(x-3) A x^2 +q(x)$ where $q$ is of degree $2$ or less, with leading term $B x^2$ ($B$ may be $0$). We have $q(x)=(x-3)B x+r(x)$ where $r(x)=Cx +D$ with constant $C,D.$ We have $r(x)= (x-3)C +E$ with constant $E.$ If $p(3)=0$ then $E=0,$ and $$p(x)=(x-3)A x^2 +q(x)=(x-3)A x^2+(x-3)B x+r(x)=$$ $$=(x-3)A x^2+(x-3)B x +(x-3)C=(x-3)(A x^2+B x +C).$$ In practice this method is fast and easy.


TITLE: Dimension of the kernel of a linear transformation of an eigenbasis
QUESTION [0 upvotes]: Let V be a vector space of dimension n and let $T: V \to V$ be a linear transformation. Assume
$T$ has eigenvalues $λ_1, λ_2,\dots, λ_n$. For each $j = 1, 2, \dots, n$, let $b_j$ be an eigenvector of $T$ associated to $λ_j$. Assume $B = \{b_1, b_2, \dots, b_n\}$ is a basis of $V$ (one calls $B$ an eigenvector basis for $T$). Therefore, $T(b_j) = λ_jb_j$ for $1 ≤ j ≤ n$. Now, assume $λ_j \neq 0$ for all $j$. Find the dimension of the kernel of $T$. Justify your answer.

I am a little confused with this question. In my understanding, since $b_j$ is a basis vector, it can't be $0$, and since $λ_j \neq 0$, then $λ_jb_j$ cannot equal zero. Does that mean that the null space of $T$ does not exist? In that case, is $\dim(\ker(T))=0$?
Thanks!

REPLY [0 votes]: Suppose that $v\in\ker(T)$. Let $v=\sum_{j=1}^{n}a_jb_j$. Then $$T(v)=T\left(\sum_{j=1}^na_jb_j\right)=\sum_{j=1}^n a_jT(b_j)=\sum_{j=1}^n a_j\lambda_jb_j=\vec{0} $$ Since $B$ is a basis, then it is linearly independent, so the scalars $a_j\lambda_j=0$ for all $1\leq j\leq n$. Since $\lambda_j\neq 0$ for all $1\leq j\leq n$, then $a_j=0$ for all $j$ which implies that $v=\vec{0}$, hence $\dim\ker(T)=0$.


TITLE: Incorrect combinatorial argument- 5 card hand with at least 3 red cards
QUESTION [0 upvotes]: How many 5 card hands can be made with at least three red cards?  Of course, we're using a standard deck of 52.  I know how to answer this, but I frequently see this argument, producing a different answer.  I know it's wrong but I can't explain exactly what's wrong with it?
"First, there are $_{52}C_3$ of choosing three red cards.  Since the other two cards can be black or red, we can choose them from any of the 49 unused cards.  I.e. $_{49}C_2$ ways.  So the final answer should be $_{52}C_3$  x   $_{49}C_2$"

REPLY [3 votes]: This counting argument is incorrect because it will multiple-count configurations for which more than three cards are red; e.g., $$\{10\color{red}\heartsuit, J\color{red}\heartsuit, Q\color{red}\heartsuit, K\color{red}\heartsuit, A\color{red}\heartsuit\} = \{\{10\color{red}\heartsuit, J\color{red}\heartsuit, Q\color{red}\heartsuit \}, \{K\color{red}\heartsuit, A\color{red}\heartsuit\}\} = \{\{10\color{red}\heartsuit, J\color{red}\heartsuit\}, \{ Q\color{red}\heartsuit, K\color{red}\heartsuit, A\color{red}\heartsuit\}\}$$ but under such an enumeration scheme, the middle and right hand expressions are considered distinct.


TITLE: Highly asymmetric regular graph
QUESTION [0 upvotes]: Let $G$ be a regular connected simple graph on $n$ vertices with chromatic number $\chi$ and maximum degree $\Delta$. Then, it is implied that $G$ is $\chi$-partite. Suppose, we remove one of the partite set of vertices. Then, what would  be the maximum degree of the induced subgraph formed by the remaining vertices?
I may say with some  confidence that the induced subgraph would have a maximum degree of $\textit{at least} $ $\chi-2$(as the remaining partite sets must be connected with each other, otherwise the graph would be disconnected). In addition, if the graph be vertex transitive, I think that the maximum degree of the induced subgraph would be $\Delta-1$. Any hints and counterexamples in this case? Thanks beforehand.

REPLY [2 votes]: Consider a complete $k$-partite graph $G$ where all parts have size $n/k >> k$. Then $\Delta = n(k-1)/k$, and even after removing a part the degree would still be $n(k-2)/k$ $=\Delta - n/k$. [I am not sure precisely what you mean by 'highly symmetric but you surely could remove some of the edges so that there are no graph automorphisms, the minimum degree stays high, and there remains in there a copy of a complete $k$-partite graph on $m >>k$ vertices so the chromatic number stays $k$]


TITLE: Do all waves superpose on each other?
QUESTION [1 upvotes]: What would happen if two waves with different frequency were to pass through 1 point in space at the same time? Would they interfere at that point in space? Are superposition and interference the same thing?

REPLY [3 votes]: No.  In general, only linear waves (i.e. only waves described by a linear differential equation.) will superpose (in the usual sense of the word.) By linearity, the sum of two solutions is also a solution.  Besides the common wave equation
$$
\frac{\partial^2 u}{\partial t^2}=v^2 \nabla^2u
$$
the Schrodinger equation is also linear.  The combination of (linear) waves with different frequencies gives rise to beats (accoustic or otherwise).
This does not hold for non-linear waves, since in general the sum of two solutions is NOT a solution to the non-linear wave equation.  A famous example of a non-linear wave equation is the Korteweg-de Vries equation, which will exhibit soliton (or solitary wave) solutions.  In particular, the ``collision'' of two solitons does not result in interference.
Another example of a non-linear wave common in physics is the non-linear Schrodinger equation, which is used for instance in optical fibers.


TITLE: Free electrons in materials with high resisitivity
QUESTION [0 upvotes]: I want to understand why exactly resistors or materials with high resistivity difficult the flow of current. If I'm not mistaken, there are not many free electrons in this materials to move and contribute to the current. But now comes my question, why can't the free electrons that come from conductors (for example a wire that is connected to the resistor, and are moving because of a potential difference) just traverse the resistant material. Or is it that resistance is more than just the lack of free electrons to contribute to the current and is also related to a collision of free electrons due to the structure of the material? I am a bit confused so can someone explain me what happens when current flows through a resistor and why resistors oppose to the flow of current? Thank you!

REPLY [0 votes]: I want to understand why exactly resistors or materials with high
  resistivity difficult the flow of current. If I'm not mistaken, there
  are not many free electrons in this materials to move and contribute
  to the current.

Instead of talking about "resistors" it is better to talk in terms of electrical "resistance". That's because devices can be designed with specific materials so as to have a controlled amount of resistance.
Metals, such as copper, aluminum, silver, gold, etc. have many mobile electrons that can easily move in response to an electric field. This makes these materials very good conductors. At the other extreme, plastics have virtually no free electrons and conduct no current. In order to for current to flow extremely high voltages are needed to pull electrons out of their bonds. This makes plastics very good insulators.
In between these extremes, there are devices specifically designed to provide a controlled  amount of free electrons and therefore a controlled amount of resistance in a circuit. Examples are carbon composition resistors, thermistors, wire wound resistors, metal film resistors, etc. You can look up how these devices are designed.

But now comes my question, why can't the free electrons that come from
  conductors (for example a wire that is connected to the resistor, and
  are moving because of a potential difference) just traverse the
  resistant material.

Free electrons that come from the conductors do traverse the resistant materials, but they collide with atoms in the resistor and make them vibrate. As a consequence the introduction of resistance reduces the flow of current in the circuit. Some of the electrical potential energy given the electrons by the voltage source is dissipated as heat in the resistance.

Or is it that resistance is more than just the lack of free electrons
  to contribute to the current and is also related to a collision of
  free electrons due to the structure of the material?

A combination of both, but primarily it is the result of collisions between the free electrons and the atoms of the resistance materials.

I am a bit confused so can someone explain me what happens when
  current flows through a resistor and why resistors oppose to the flow
  of current?

The electric field has to do work to move the electrons through the resistance which opposes the flow of current. The potential difference, voltage, across the resistor is the work required per unit charge to move the charge between the points.

Yes thanks now it's very clear. I just have a doubt about the
  potential energy that the electrons lose when they collide with the
  atoms of the material. My question is, why is it that they lose
  potential energy and not kinetic energy?

They do lose kinetic energy. The end result is potential energy is converted into heat. The progression is as follows: The electric field exerts a force on the electrons giving them kinetic energy. But each time an electron gains kinetic energy it quickly loses it due to collisions with the atoms and molecules of the material which generate heat. Then it gets kinetic energy again from the field and again loses it due to collisions. The gaining and losing of kinetic energy due to collisions averages out to an overall change in kinetic energy (change in drift velocity) of zero, so that the current is constant.
The progression is therefore electrical potential energy converts to kinetic energy which converts to heat. The net result: Conversion of electrical potential energy to heat.
Hope this helps.


TITLE: Is this the correct way to perform mathematical induction? (re: derivative of $z^n$ is $nz^{n-1}$)
QUESTION [6 upvotes]: Here's a question:
Derive $$\frac{\mathrm{d}}{\mathrm{d}z} z^n = nz^{n-1},$$
when n is a positive integer by using mathematical induction and and the derivative of a product of two functions
$$\frac{\mathrm{d}}{\mathrm{d}z} f(z)g(z) = f(z)g'(z) + f'(z)g(z).$$
Here's what I did. Is this mathematical induction performed correctly?
Base case: n = 1
$$\frac{\mathrm{d}}{\mathrm{d}z} z^1 = 1z^{1-1}$$
$$1 = 1$$
Base case is true.
Inductive step: Assume true for $n = k$, show true for $k + 1$.
So show:
$$\frac{\mathrm{d}}{\mathrm{d}z} z^{(k+1)} = (k+1)z^{(k+1) - 1} = (k+1)z^k$$
$$\frac{\mathrm{d}}{\mathrm{d}z} z^{(k+1)} = \frac{\mathrm{d}}{\mathrm{d}z} z^kz.$$
Using derivative of a product of two functions:
$$\frac{\mathrm{d}}{\mathrm{d}z} z^kz =z^k\cdot 1 + kz^{k-1}\cdot z$$
$$ =z^k + kz^k$$
$$ = (k+1)z^k$$
So as the base case holds and the inductive step holds, this means the original statement is valid?

REPLY [0 votes]: The induction step is obvious if one works with logarithmic derivatives.
$\qquad\ (fg)' =\: f\:'g + fg'\ $ when divided through by $fg$ becomes
$\qquad\dfrac{(fg)'}{fg}\: =\: \dfrac{f\:'}f + \dfrac{g'}g\ $ which, in terms of $\:D(f) := \dfrac{f\:'}f\: $ becomes
$\qquad D(fg)\: =\: D(f) + D(g)\ $ the "logarithm-like" law of the logarithmic derivative $D$
$\  \Rightarrow\ D(x^n)\: =\: n\: D(x)\ $ by an obvious induction (prove it!)
$\  \Rightarrow\ \dfrac{(x^n)'}{x^n}\: =\: n\:\dfrac{1}x $
$\  \Rightarrow\ \: (x^n)' =\: n\ x^{n-1}$


TITLE: Can this reduced version of algebraic K-theory be identified with this direct limit?
QUESTION [2 upvotes]: Let $X$ be a connected smooth scheme over a field and let $VB(X)$ be the exact category of vector bundles (i.e. locally free $\mathcal{O}_X$-module whose rank is finite at every point) over $X$.
Let the abelian group $\tilde K_0(X)$ denote the kernel of the rank morphism from the zeroth algebraic K-theory group $K_0(X)$ to $\mathbb{Z}$.
Let $Vec_k(X)$ be the set of isomorphism classes $[A]$ of rank $k$ vector bundles $A$ over $X$. One gets maps $i_k:Vec_k(X)\to Vec_{k+1}(X)$ defined by $[A]\mapsto [A\oplus \mathbb{A}^1_X]$, i.e. by adding a trivial bundle. The directed colimit $cVec(X)=\operatorname{colim}_k Vec_k(X)$ of this system has the structure of a commutative monoid by $[A]+[B]=[A\oplus B]$.

Is there an isomorphism $cVec(X)\cong\tilde K_0(X)$ of monoids?

This holds for topological K-theory over a connected CW-complex. I am a little unconvinced that this isomorphism holds since $VB(X)$ is not split-exact. However, I cannot find an argument.

REPLY [2 votes]: It's already false for $\mathbb P^1$. Let $L$ be a line bundle with no global sections except zero. Then $L\oplus L^{-1}$ is not a trivial bundle because it is not generated by global sections, and this remains true when you add a trivial bundle to it, but it is trivial in your reduced $K^0$.


TITLE: What is basically the difference between static pressure and dynamic pressure?
QUESTION [8 upvotes]: What is basically the difference between static pressure and dynamic pressure?
While studying Bernoulli's theorem, I came before these terms. The law says:

When the fluid flows through a small area, its pressure energy decreases & kinetic energy increases and vice versa.

Now that's wierd as I know due to having KE, ie. having momentum, one can impart pressure. Then why distinction ? What is then pressure energy??
In order to understand that I went to wikipedia & quora & others; there I found fluid exerts two pressure: Static & dynamic. But really nothing could be understood more than that. What are they actually?

REPLY [2 votes]: Dynamic pressure is not really pressure at all.  It represents the amount that the pressure would increase if all the fluid's kinetic energy per unit volume could be converted to pressure by blocking the flow (say with a pitot tube).  On the other hand, static pressure is another name for just "plain old pressure" exerted by parcels of fluid on adjacent parcels of fluid, or on the walls of the flow channel.  For incompressible flow, it is, more precisely, the isotropic part of the stress tensor.


TITLE: Pre-image of linear operator
QUESTION [1 upvotes]: I'm studying the following proposition but I didn't understand the proof.
If $T: X \rightarrow Y$ is an operator, then the pre-image of a closed linear subspace $B$ of $Y$ is a closed linear subspace $T^{-1}B:=\{x \in X: Tx \in B\}$ of $X$.
Proof: Let $x,\> y, \>x_n \in T^{-1}B$, that is, $Tx,\> Ty,\> Tx_n \in B$ and let $\lambda Tx \in \mathcal{F}$. Then
$$T(x + y) = Tx + Ty \in B$$
$$T(\lambda x) = \lambda Tx \in B$$
$$ x_n \rightarrow a \Rightarrow Ta = T(\lim_{n \rightarrow \infty} x_n) = \lim_{n \rightarrow \infty} Tx_n \in B  $$
show that $T^{-1}B$ is a closed linear subspace.
Question: The above expressions were statements about closed linear subspace $B$ of $Y$ -- such that continuous linear transformation $T$ preserve vector addition, scalar multiplication and convergence. I don't get it how does it show that $T^{-1}B$ is a closed linear subspace.
Thank you!

REPLY [1 votes]: Since $T(x+y)\in B$, $x+y\in T^{-1}B$.  Similarly, the other statements show that $\lambda x\in T^{-1}B$ and $a\in T^{-1}B$.  Together these show that $T^{-1}B$ is a closed subspace of $X$.


text:
\begin{document}

	\title{An Extension of Averaged-Operator-Based Algorithms\\

		\thanks{This work was supported by the Funda\c{c}\~{a}o para a Ci\^{e}ncia e Tecnologia within the Portuguese Ministry for Science, Technology and Higher Education under Project UID/EEA/50008/2013 and Grant BPD/N.º 134 - 16/10/2017.}
	}

	\author{\IEEEauthorblockN{Miguel Sim\~{o}es}
		\IEEEauthorblockA{\textit{Instituto de Telecomunica\c{c}\~{o}es} \\
			\textit{Instituto Superior T\'{e}cnico, Univ. Lisboa}\\
			Lisbon, Portugal \\
			miguel.simoes@lx.it.pt}
		\and
		\IEEEauthorblockN{Jos\'{e} Bioucas-Dias}
		\IEEEauthorblockA{\textit{Instituto de Telecomunica\c{c}\~{o}es} \\
			\textit{Instituto Superior T\'{e}cnico, Univ. Lisboa}\\
			Lisbon, Portugal \\
			bioucas@lx.it.pt}
		\and
		\IEEEauthorblockN{Luis B. Almeida}
		\IEEEauthorblockA{\textit{Instituto de Telecomunica\c{c}\~{o}es} \\
		\textit{Instituto Superior T\'{e}cnico, Univ. Lisboa}\\
		Lisbon, Portugal \\
		luis.almeida@lx.it.pt}

	}

	\maketitle

	\begin{abstract}
		Many of the algorithms used to solve minimization problems with sparsity-inducing regularizers are generic in the sense that they do not take into account the sparsity of the solution in any particular way. However, algorithms known as semismooth Newton are able to take advantage of this sparsity to accelerate their convergence. We show how to extend these algorithms in different directions, and study the convergence of the resulting algorithms by showing that they are a particular case of an extension of the well-known Krasnosel'ski\u{\i}--Mann scheme.
	\end{abstract}

	\begin{IEEEkeywords}
		Convex nonsmooth optimization, primal--dual optimization, semismooth Newton method, forward--backward method, variable metric
	\end{IEEEkeywords}

	\section{Introduction}

	\subsection{Background}

	The objective functions of many signal-processing problems can be formulated as sums of two proper lower-semicontinuous convex functions: one that is smooth, $f: \mathbb{R}^n \to ]-\infty,+\infty]$, and another one that need not be smooth, $g: \mathbb{R}^n \to ]-\infty,+\infty]$. The resulting problem is
	\begin{equation} \label{eq:split}
	\underset{\mathbf{x}  \in \mathbb{R}^n}{\text{minimize}} \quad f (\mathbf{x}) + g (\mathbf{x}).
	\end{equation}
	Such problems are typically large-scale and can be solved by using splitting methods, which convert~\eqref{eq:split} into a sequence of separable subproblems. The (relaxed) \emph{forward--backward} method~\cite{Figueiredo2003, Daubechies2004} is an example of such methods. Its iterations can be broken into a gradient (forward) step on $f$ and a proximal (backward) step on $g$, performed consecutively---see Algorithm~\ref{algo:rfba}, where $\text{prox}_{\tau g}$ denotes the \emph{proximal operator} of function $g$, i.e., $\text{prox}_{\tau g}(\mathbf{x}) \eqdef \text{arg min}_{\mathbf{u} \in \mathbb{R}^n} \left\{ g(\mathbf{u}) + \frac{1}{2 \tau} \| \mathbf{x} - \mathbf{u} \|^2 \right\}$~\cite{Moreau1962}.
	\begin{algorithm} \label{algo:rfba}
		Choose $\mathbf{x}^0 \in \mathbb{R}^n,\ \tau > 0$\;
		$k \leftarrow 1$\;
		\While{stopping criterion is not satisfied}{
			Choose $\lambda^k > 0$\;
			$\mathbf{x}^{k + 1} \leftarrow \mathbf{x}^k + \lambda^k \left( \text{prox}_{\tau g} \left(\mathbf{x}^k - \tau \nabla f \left(\mathbf{x}^k \right)\right) - \mathbf{x}^k \right)$\; \label{eq:iter_rfba}
			$k \leftarrow k + 1$\;
		}
		\caption{Relaxed forward--backward method.}
	\end{algorithm}

	When analyzing the properties of many of these and other algorithms, it can be advantageous to use the theory of monotone operators~\cite{Byrne2004}. Let $2^{\mathbb{R}^n}$ denote the {power} set of $\mathbb{R}^n$. A set-valued operator $A: \mathbb{R}^n \to 2^{\mathbb{R}^n}$ is said to be \emph{monotone} if $\langle \mathbf{u}-\mathbf{v}, \mathbf{x}-\mathbf{y} \rangle \geq 0$ for all $(\mathbf{x},\mathbf{u}) \in \text{gra } A$ and $(\mathbf{y},\mathbf{v}) \in \text{gra } A$, where $\text{gra } A$ denotes the {graph} of A, and it is said to be \emph{maximally monotone} if there exists no other monotone operator whose graph properly contains $\text{gra } A$. Monotone operators are connected to optimization problems as follows. Take, for example, \eqref{eq:split}. According to Fermat's rule, its solutions should satisfy the inclusion $0 \in \nabla f (\mathbf{x}) + \partial g (\mathbf{x})$, where the set-valued operator $\partial g : \mathbb{R}^n \to 2^{\mathbb{R}^n} : \mathbf{x} \to \partial g (\mathbf{x})$ denotes the \emph{subdifferential} of $g$ (in the sense of Moreau and Rockafellar~\cite[Chapter 23]{Rockafellar1970}). The operators $\nabla f$ and $\partial g$ are examples of maximally-monotone operators~\cite[Theorem 20.40]{Bauschke2011}. Problem~\eqref{eq:split} can be seen as a particular case of the problem of finding a zero of the sum of two monotone operators $A$ and $C$, i.e.,
	\begin{equation} \label{eq:inclusion}
	\text{find } \mathbf{x} \in \mathbb{R}^n \quad \text{such that } 0 \in A \left(\mathbf{x}\right) + C \left(\mathbf{x}\right),
	\end{equation}
	if one makes $A=\partial g$ and $C=\nabla f$. Problem~\eqref{eq:inclusion} may be solved using a generalized version of Algorithm~\ref{algo:rfba}, in which Line~\ref{eq:iter_rfba} is replaced with
	\begin{equation} \label{algo:rfba_op}
		\mathbf{x}^{k + 1} \leftarrow \mathbf{x}^k + \lambda^k \left( J_{\tau A} \left( \mathbf{x}^k - \tau C \left(\mathbf{x}^k\right) \right) - \mathbf{x}^k \right),
	\end{equation}
	where $J_{\tau A} \eqdef (\text{Id} + \tau A)^{-1}$ is the \emph{resolvent} of operator $A$ and $\text{Id}$ denotes the \emph{identity} operator. Note that $J_{\tau \partial g} = \text{prox}_{\tau g}$ \cite[Example 23.3]{Bauschke2011}.

	Problem~\eqref{eq:inclusion} can alternatively be written as the problem of finding a fixed point of the operator $R \eqdef J_{\tau A} \circ (\text{Id} - \tau C)$:
	\begin{equation} \label{eq:mon_incl_T}
	\text{find } \varx \in \mathbb{R}^n \quad \text{such that } \neop \left( \varx \right) = \varx.
	\end{equation}
	In general, the solutions of a convex optimization problem correspond to the fixed points of a certain operator, and an iterative optimization algorithm corresponds to a fixed-point method.
	We can rewrite~\eqref{algo:rfba_op} as
	\begin{equation} \label{algo:km}
		\mathbf{x}^{k + 1} \leftarrow T_{\lambda^k} \left( \mathbf{x}^k \right) \eqdef \mathbf{x}^k + \lambda^k (R \left( \mathbf{x}^k \right) - \mathbf{x}^k).
	\end{equation}
	We say that an operator $R: \mathbb{R}^n \to \mathbb{R}^n$ is nonexpansive if $\| \mathbf{u} - \mathbf{v} \| \leq \| \mathbf{x} - \mathbf{y} \|$ for all $(\mathbf{x},\mathbf{u}) \in \text{gra } R$ and $(\mathbf{y},\mathbf{v}) \in \text{gra } R$. Let $R$ be a generic nonexpansive operator and let $\lambda \in \; ]0,1[$. Then the operator $T \eqdef \left(\eye - \lambda \right) + \lambda R$ is said to be $\lambda$-\emph{averaged}. It obeys the following contractive property~\cite[Proposition 4.25]{Bauschke2011}:
	\begin{align}
		&\norm{T \left(\varx\right) - T \left(\vary\right)}{}^2 \nonumber \\
		& \, \leq \norm{\varx - \vary}{}^2 - \frac{1 - \lambda}{\lambda} \norm{\left( \text{Id} - T \right) \left(\varx\right) - \left( \text{Id} - T \right) \left(\vary\right)}{}^2 \label{eq:contract_avop}
	\end{align}
	for all $\varx, \, \vary \in \mathbb{R}^n$. In particular, when $\lambda = 1/2$, $T$ is said to be \emph{firmly nonexpansive}. The resolvents of maximally-monotone operators are firmly-nonexpansive~\cite[Corollary 23.8]{Bauschke2011}. Iteration~\eqref{algo:km} is known as the \emph{Krasnosel'ski\u{\i}--Mann} scheme and is the basis of not only the forward--backward method but also other optimization algorithms, such as the Douglas--Rachford one~\cite{Byrne2004, Bauschke2011}. It can be shown that, under certain conditions, the Krasnosel'ski\u{\i}--Mann scheme converges to $\text{Fix } R$, where $\text{Fix } R$ denotes the set of fixed points of $R$.

	The convergence rate of the forward--backward method (Algorithm~\ref{algo:rfba}) can be shown to be sublinear, or, under certain assumptions, to be linear. This rate can often be improved by incorporating \emph{second-order} information about $f$ if this function is twice-differentiable. The local convergence rate of second-order methods is superlinear or even quadratic. As an example, consider the second-order version of Algorithm~\ref{algo:rfba}, which is given by replacing Line~\ref{eq:iter_rfba} with the iteration $\mathbf{x}^{k + 1} \leftarrow \mathbf{x}^k + \lambda^k \left( \text{prox}_g^{\mathbf{B}^k} \left( \mathbf{x}^k - \left[ \mathbf{B}^k \right]^{-1} \nabla f \left( \mathbf{x}^k \right) \right) - \mathbf{x}^k \right)$~\cite{Schmidt2011, Becker2012, Lee2014}, where $\mathbf{B}^k$ is a \ac{PD} matrix (the Hessian of $f$ or an approximation of it) and $\text{prox}_g^{\mathbf{B}^k}$ denotes the proximal operator of $g$ relative to the norm $\| \cdot \|^2_{\mathbf{B}^k}$, i.e., $\text{prox}_{g}^{\mathbf{B}^k} (\mathbf{x}) \eqdef \text{arg min}_{\mathbf{u} \in \mathbb{R}^n} \left\{ g(\mathbf{u}) + \frac{1}{2} \| \mathbf{x} - \mathbf{u} \|^2_{\mathbf{B}^k} \right\}$. More generally, and from an operator-centric perspective, by using second-order methods such as these, one is actually solving a left-preconditioned version of~\eqref{eq:inclusion}, in the sense that instead of directly tackling that problem we are considering problems that share the same set of solutions but may be more convenient to solve:
	\begin{equation} \label{eq:mon_incl_precond}
	\text{find } \varx \in \mathbb{R}^n \quad \text{such that } 0 \in \fbvm \maxmonresol \left( \varx \right) + \fbvm \cocoercop \left( \varx \right),
	\end{equation}
	where $\fbvm$ is a \ac{PD} operator. In what follows, we denote positive definiteness by $\fbvm \succ 0$ and positive semidefiniteness by $\fbvm \succeq 0$.

	\subsection{Contributions}

	The basis of this work is the study of the following alternative scheme to~\eqref{algo:km}:
	\begin{equation} \label{eq:fixed_point_iter_opwavop}
	\varx^\iite = \avop{\ave^\ite} \left( \varx^\ite \right) \eqdef \varx^\ite + \ave^\ite \left( \neop \left( \varx^\ite \right) - \varx^\ite \right),
	\end{equation}
	where, for every $\ite$, $\ave^\ite$ is a linear operator such that $\eye \succ \ave^\ite \succ 0$. For convenience, we call the operators $\avop{\ave^\ite}$, \emph{operator-weighted averaged operators}. It is clear that if, for all $k$, we make $\ave^\ite = \lambda^\ite \eye$, we recover~\eqref{algo:km}.

	Iteration~\eqref{eq:fixed_point_iter_opwavop} can be interpreted in different ways. For example, if $\ave^\ite$ is fixed, i.e., if, for all $\ite$, $\ave^\ite = \ave$, where $\ave \succ 0$, that iteration can also be seen as a left-preconditioning scheme to solve~\eqref{eq:mon_incl_T}:
	\begin{equation} \label{eq:mon_incl_precond_T}
	\text{find } \varx \in \mathbb{R}^n \quad \text{such that } \ave \neop \left( \varx \right) = \ave \varx.
	\end{equation}

	\subsection{Notation and outline}

	A detailed account of the notions listed in this section can be found in the work of Bauschke and Combettes~\cite{Bauschke2011}. We denote the \emph{scalar product} of a Hilbert space by $\langle \cdot , \cdot \rangle$ and the associated \emph{norm} by $\| \cdot \|$. The \emph{range} of an operator $A$ is denoted by $\text{ran } A$, and the \emph{adjoint} of $A$ by $A^*$. We say that an operator $A : \mathbb{R}^n \to \mathbb{R}^n$ is \emph{Lipschitz continuous} with constant $L > 0$ if $\| \mathbf{u} - \mathbf{v} \| \leq L \| \mathbf{x} - \mathbf{y} \|$, for all $(\mathbf{x},\mathbf{u}) \in \text{gra } A$ and $(\mathbf{y},\mathbf{v}) \in \text{gra } A$. Additionally, let $\Gamma_0 (\mathbb{R}^n)$ denote the class of all proper lower-semicontinuous convex functions from $\mathbb{R}^n$ to $]{-\infty},+\infty]$. Given two functions $f \in \Gamma_0 (\mathbb{R}^n)$ and $g \in \Gamma_0 (\mathbb{R}^n)$, their \emph{infimal convolution} is denoted by  $\infconv{f}{g}$. The Legendre--Fenchel \emph{conjugate} of a function $f$ is denoted by $f^*$. The \emph{indicator function} of a set $C \in \mathbb{R}^{n}$ is defined as $\delta_C(\mathbf{x}) \eqdef 0$ if $\mathbf{x} \in C$, $\delta_C(\mathbf{x}) \eqdef + \infty$ otherwise. We use the notation $\{\mathbf{x}^k\}$ as a shorthand for representing the sequence $\{\mathbf{x}^k\}_{k=1}^{+\infty}$. The space of \emph{absolutely-summable sequences} in $\mathbb{R}$ is denoted by $\spaceseq^1 (\mathbb{N})$; the set of summable sequences in $[0, + \infty [$ is denoted by $\spaceseq^1_+ (\mathbb{N})$. Bold lowercase letters denote vectors and bold uppercase letters denote matrices. $[\mathbf{a}]_i$ denotes the $i$-th element of a vector $\mathbf{a}$, $[\mathbf{A}]_{:j}$ denotes the $j$-th column of a matrix $\mathbf{A}$, and $[\mathbf{A}]_{ij}$ denotes the element in the $i$-th row and $j$-th column of a matrix $\mathbf{A}$. $\mathbf 0$ denotes a \emph{zero} vector or matrix of appropriate size. The maximum and signum operators are denoted by $\text{max}(\cdot)$ and $\text{sgn}(\cdot)$, respectively.

	The structure of this work is as follows. In Section~\ref{sec:ssn}, we briefly discuss a class of algorithms known as semismooth Newton methods. In Section~\ref{sec:extension}, we study the scheme given by~\eqref{eq:fixed_point_iter_opwavop}, and show how it can be used to solve a primal--dual problem first studied by Combettes and Pesquet~\cite{Combettes2011b}. In Section~\ref{sec:apps}, we present a simple application of the proposed method to solve an inverse problem. Section~\ref{sec:conclusions} concludes. Due to space constraints, we omit the proofs of the results discussed in Section~\ref{sec:extension}; these proofs can be consulted elsewhere~\cite[Chapter 5]{Simoes2017}.

	\section{Semismooth Newton methods} \label{sec:ssn}

	\emph{Semismooth Newton} methods were originally developed with the goal of using Newton-like methods to minimize certain nonsmooth functions at a superlinear convergence rate. To illustrate why these methods may be useful when solving problems of the form of~\eqref{eq:split}, consider, as an example, that $f = \| \mathbf{y} - \mathbf{H} \cdot \|^2$, and $g = \mu \| \cdot \|_1$, where $\mathbf{y} \in \mathbb{R}^m$, $\mathbf{H} \in \mathbb{R}^{m \times n}$, and $\mu > 0$. For problems such as these, it was shown by Hinterm\"{u}ller~\cite{Hintermuller2003} that some semismooth Newton methods are equivalent to some active-set methods. As we discuss in Section~\ref{sec:apps}, the fact that these methods can be written as active-set ones allows for significant time savings when solving certain problems, namely the ones involving sparsity-inducing regularizers, as is the case of the $\ell_1$ norm.

	Let $G: \mathbb{R}^n \to \mathbb{R}^n$ be an operator such that $G: \mathbf{x} \to \mathbf{x} - \text{prox}_{\mu \| \mathbf{x} \|_1} \left(\mathbf{x} - 2 \mu \mathbf{H}^* (\mathbf{H} \mathbf{x} - \mathbf{y}) \right)$. The solution of the problem under consideration should satisfy the nonlinear equation $G ({\mathbf{x}}) = \mathbf{0}$, which is nonsmooth, since $\text{prox}_{\mu \| \cdot \|_1}$ is not everywhere differentiable. There are, however, generalizations of the concept of differentiability that are applicable to an operator such as $G$. One of them is the B(ouligand)-differential~\cite[Definition 4.6.2]{Facchinei2003}, which is defined as follows. Suppose that a generic operator $G: D \subset \mathbb{R}^n \to \mathbb{R}^m$ is locally Lipschitz, where $D$ is an open subset. Then by Rademacher's theorem, $G$ is differentiable almost everywhere in $D$. Let $C$ denote the subset of $\mathbb{R}^n$ consisting of the points where $G$ is differentiable (in the sense of Fr\'{e}chet~\cite[Definition 2.45]{Bauschke2011}). The B-differential of $G$ at $\mathbf{x}$ is $\partial_B \, G (\mathbf{x}) \eqdef \left\{ \lim_{\mathbf{x}^j \to \mathbf{x}} \nabla G \left(\mathbf{x}^j \right) \right\}$, where $\{\mathbf{x}^j\}$ is a sequence such that $\mathbf{x}^j \in C$ for all $j$ and $\nabla G(\mathbf{x}^j)$ denotes the Jacobian of $G$ at $\mathbf{x}^j$.

	The B-differential of an operator at a given point may not be unique: for example, take $\text{prox}_{\mu \| \cdot \|_1} (\mathbf{x})$, which can be evaluated element-wise by computing $\text{max} \left\{ \big| [\mathbf{x}]_i \big| - \mu, 0 \right\} \circ \text{sgn} \left([\mathbf{x}]_i \right)$ for $i \in \{1, \cdots, n\}$. A possible $\mathbf{H} \in \partial_B \, \text{prox}_{\mu \| \cdot \|_1} (\mathbf{x})$ is a binary diagonal matrix defined as~\cite[Proposition 3.3]{Griesse2008}
	\begin{equation} \label{eq:partial_B_G}
		[\mathbf{H}]_{ii} = \begin{cases}
		1 & \text{if } \big| [\mathbf{x}]_i \big| > \mu,\\
		0 & \text{otherwise.}
		\end{cases}
	\end{equation}

	This generalization of the concept of differentiability can also be used to formulate the so-called semismooth Newton method, which is characterized by the iteration $\mathbf{x}^{k+1} \leftarrow \mathbf{x}^{k} - [\mathbf{H}^k]^{-1} \, G(\mathbf{x}^k)$, where $\mathbf{H}^k \in \partial_B  \, G (\mathbf{x}^k)$. It can be shown that this method locally converges superlinearly for operators known as semismooth~\cite{Qi1993b}. Let $\mathbf{x} \in D$ and $\mathbf{d} \in \mathbb{R}^n$; semismooth operators are operators that are directionally differentiable at a neighborhood of $\mathbf{x}$ and that, for any $\mathbf{H} \in \partial_B \, G (\mathbf{x}+\mathbf{d})$, satisfy the condition $\mathbf{H} \mathbf{d} - G'(\mathbf{x}; \mathbf{d})=o(\|\mathbf{d}\|)$ for $\mathbf{d} \to \mathbf{0}$, where $G'(\mathbf{x}; \mathbf{d})$ denotes the directional derivative of $G$ at $\mathbf{x}$ along $\mathbf{d}$. Examples of semismooth functions are the Euclidean norm and piecewise-differentiable functions~\cite[Chapter 2]{Ulbrich2011}, $\text{prox}_{\mu \| \cdot \|_1} (\mathbf{x})$ being an example of the latter. Note that the semismooth Newton method is a particular case of~\eqref{eq:fixed_point_iter_opwavop}, although we impose that $\eye \succ \ave^\ite \succ 0$ in the latter equation, which is not necessarily true for this method.

	\section{An extension of averaged-operator-based algorithms} \label{sec:extension}

	In this section, we define operator-weighted averaged operators, and show that they have a contractive property. We also study the asymptotic behavior of fixed-point iterations of these operators. Such iterations can be seen as an extension of the Krasnosel'ski\u{\i}--Mann scheme [cf.~\eqref{algo:km}]. We base our analysis on the fact that these iterations produce a sequence that is variable-metric Fej\'{e}r monotone~\cite{Combettes2013,Combettes2014b}. We then present an algorithm that uses operator-weighted averaged operators, and that solves a primal--dual problem that encapsulates many problem formulations~\cite{Combettes2011b, Combettes2014b}.

	\subsection{An extension of the Krasnosel'ski\u{\i}--Mann scheme} \label{sec:eKM}

	\begin{definition}[Operator-weighted averaged operators]
		Let $\nesubset$ be a nonempty subset of $\mathbb{R}^n$, let $\eps \in \; ]0, 1[$, and let $\ave$ be an operator in $\mathbb{R}^n$ such that
		\begin{equation} \label{eq:ave_ass}
		\Meig \eye \succeq \ave \succeq \meig \eye, \quad \text{where } \Meig, \, \meig \in [\eps, 1-\eps].
		\end{equation}
		We say that an operator $\avop{\ave}: \nesubset \to \mathbb{R}^n$ is an operator-weighted averaged operator if there exists a nonexpansive operator $\neop: \nesubset \to \mathbb{R}^n$ such that
		\begin{equation} \label{eq:aveop}
		\avop{\ave} \define (\eye - \ave) + \ave \neop.
		\end{equation}
	\end{definition}

	We have proved the following results:

	\begin{proposition} \label{th:contractive}
		Let $\nesubset$ be a nonempty subset of $\mathbb{R}^n$, let $\eps \in \; ]0, 1[$, let $\ave$ be an operator in $\mathbb{R}^n$ satisfying~\eqref{eq:ave_ass}, let $\neop: \nesubset \to \mathbb{R}^n$ be a nonexpansive operator, and let $\avop{\ave}: \nesubset \to \mathbb{R}^n$ be an operator as defined in~\eqref{eq:aveop}. Then the operator $\avop{\ave}$ is $\Meig$-averaged in the metric induced by $\inv{\ave}$. In other words, the operator $\avop{\ave}$ verifies
		\begin{align*}
		&\norm{\avop{\ave} \left( \varx \right) - \avop{\ave} \left( \vary \right)}{\inv{\ave}}^2 \\ \nonumber
		&\leq \norm{\varx - \vary}{\inv{\ave}}^2 - \frac{1 - \Meig}{\Meig} \norm{\left( \emph{\eye} - \avop{\ave} \right) \left( \varx \right) - \left( \emph{\eye} - \avop{\ave} \right) \left( \vary \right)}{\inv{\ave}}^2
		\end{align*}
		for all $\varx, \, \vary \in \nesubset$.
	\end{proposition}

	\begin{theorem} \label{th:eKM}
		Let $\nesubset$ be a nonempty closed convex subset of $\mathbb{R}^n$, let $\eps \in \; ]0, 1[$, let $\seq{\seqave^\ite} \in \spaceseq^1_+(\mathbb{N})$, let $\seq{\ave^\ite}$ be a sequence of \ac{PD} operators in $\mathbb{R}^{n \times n}$ such that, for all $\ite \in \mathbb{N}$,
		\begin{equation} \label{eq:seq_ave_ass}
		\begin{cases}
		\Meig^\ite \emph{\eye} \succeq \ave^\ite \succeq \meig^\ite \emph{\eye},\\
		\Meig^\ite, \, \meig^\ite \in [\eps, 1-\eps],\\
		\left( 1 + \seqave^\ite \right) \ave^\iite \succeq \ave^\ite,
		\end{cases}
		\end{equation}
		and let $\neop: \nesubset \to \nesubset$ be a nonexpansive operator such that $\emph{\fix} \neop \neq \emptyset$. Additionally, let $\varx^0 \in \nesubset$ and let, for all $\ite$, $\seq{\varx^\ite}$ be a sequence generated by~\eqref{eq:fixed_point_iter_opwavop}. Then $\seq{\varx^\ite}$ converges to a point in $\emph{\fix} \neop$.

	\end{theorem}

	\subsection{Primal--dual optimization algorithms} \label{sec:pdprob}

	Combettes and Pesquet studied a primal--dual problem that generalizes many problems~\cite[Problem 4.1]{Combettes2011b}. By being able to devise an algorithm to solve this problem, we are effectively tackling a large number of problems simultaneously (problem~\eqref{eq:split} is one of these). Let $m$, $n$, and $\dimr$ be strictly-positive integers, let $\cvxone \in \lsc(\mathbb{R}^n)$, let $\coco \in \; ]0, + \infty[$, let $\smooth: \mathbb{R}^n \to ]{-\infty},+\infty]$ be convex and differentiable with a $\inv{\coco}$-Lipschitzian gradient, and let $\biasvar \in \mathbb{R}^n$. For every $\itr \in \{ 1, \dots, \dimr \}$, let $\biasvarlnop_\itr \in \mathbb{R}^{m_\itr}$, let $\cvxtwo_\itr \in \lsc(\mathbb{R}^{m_\itr})$, let $\strmaxmonopparam_\itr \in \; ]0, +\infty[$, let $\strong_\itr \in \lsc(\mathbb{R}^{m_\itr})$ be $\strmaxmonopparam_\itr$-strongly convex,\footnote{A function $\strong$ is said to be $\strmaxmonopparam$-\emph{strongly convex} if $\strong - \frac{\strmaxmonopparam}{2} \langle \mathbf{x}, \mathbf{x} \rangle$ is convex, for some $\strmaxmonopparam > 0$.} let $\lnop_\itr \in \mathbb{R}^{m_\itr \times n}$ such that $\lnop_\itr \neq 0$, and let $\pdomega_\itr$ be real numbers in $]0, 1]$ such that $\sum_{\itr = 1}^{\dimr} \pdomega_\itr = 1$. The problem is as follows:

	\begin{problem} \label{th:problem}

		Solve the primal minimization problem,
		\begin{equation*} \label{eq:primalproblem2}
			\underset{\pr \in \mathbb{R}^n}{\text{{minimize}}} \, \cvxone (\pr) + \sum_{\itr=1}^{\dimr} \pdomega_\itr \left(\infconv{\cvxtwo_\itr}{\strong_\itr} \right) \left(\lnop_\itr \pr - \biasvarlnop_\itr \right) + \smooth (\pr) - \innerpro{\pr}{\biasvar}{},
		\end{equation*}
		together with its corresponding dual minimization problem,
		\begin{align*}
			\underset{\du_1 \in \mathbb{R}^{m_1}, \cdots, \du_\itr \in \mathbb{R}^{m_\itr}}{\text{{minimize}}} &\, \left( \infconv{\conj{\cvxone}}{\conj{\cvxtwo}} \right) \left( \biasvar - \sum_{\itr=1}^{\dimr} \pdomega_\itr  \conj{\lnop_\itr} \du_\itr \right) \\
			&\, + \sum_{\itr=1}^{\dimr} \pdomega_\itr \left( \conj{\cvxtwo_\itr} (\du_\itr) + \conj{\strong_\itr} (\du_\itr) + \innerpro{\du_\itr}{\biasvarlnop_\itr}{} \right). \label{eq:dualproblem2}
		\end{align*}
		The sets of solutions to these primal and dual problems are denoted by $P$ and $D$, respectively.

	\end{problem}

	Consider Algorithm~\ref{algo:stackevmfbapp} to solve Problem~\ref{th:problem}. In what follows, for all $\itr$, $\seq{\vm^\ite}$, $\seq{\ave^\ite}$, $\seq{\vm^\ite_\itr}$, $\seq{\ave^\ite_\itr}$ are sequences of linear operators, and $\seq{\errorpr^\ite}$, $\seq{\errordu^\ite_\itr}$, $\seq{\errorresolpr^\ite}$, $\seq{\errorresoldu^\ite_\itr}$ are absolutely-summable sequences that can be used to model errors. Algorithm~\ref{algo:stackevmfbapp} is an extension of~\cite[Example 6.4]{Combettes2014b}.
	\begin{algorithm} \label{algo:stackevmfbapp}
		Choose $\pr^0 \in \mathbb{R}^n$ and $\du_1^0 \in \mathbb{R}^{m_1}, \cdots, \du_\itr^0 \in \mathbb{R}^{m_\itr}$\;
		$\ite \leftarrow 1$\;
		\While{stopping criterion is not satisfied}{
			\For{$\itr = 1, \dots, \dimr$}{
				Choose $\vm^\ite_\itr, \, \ave^\ite_\itr \succ 0 \text{ s.t. } \ave^\ite_\itr \prec \eye$\;
				$\pdu^\ite_\itr =\prox^{\inv{(\vm_\itr^\ite)}}_{\conj{\cvxtwo}_\itr} \big( \du^\ite_\itr + \vm_\itr^\ite \big( \lnop_\itr \pr^\ite$
					\newline\makebox[3cm]{}$ - \grad{\conj{\strong}_\itr} \left(\du^\ite\right) - \errorresoldu^\ite_\itr - \biasvarlnop_\itr \big) \big) + \errordu^\ite_\itr$\;
				$\duo^\ite_\itr = 2 \pdu^\ite_\itr - \du^\ite_\itr$\;
				$\du^\iite_\itr = \du^\ite_\itr + \ave_\itr^\ite \left( \pdu^\ite_\itr - \du^\ite_\itr \right)$\;
			}
			Choose $\vm^\ite, \, \ave^\ite \succ 0 \text{ s.t. } \ave^\ite \prec \eye$\;
			$\ppr^\ite =$
				$\prox_{\cvxone}^{\inv{(\vm^\ite)}} \big( \pr^\ite - \vm^\ite \big( \sum_{\itr = 1}^{\dimr} \pdomega_\itr \conj{\lnop}_\itr \duo^\ite_\itr$
				\newline\makebox[3cm]{}$+ \grad{\smooth} \left(\pr^\ite\right) + \errorresolpr^\ite - \biasvar \big) \big) + \errorpr^\ite$\;
			$\pr^\iite =  \pr^\ite + \ave^\ite \left(\ppr^\ite - \pr^\ite \right)$\; \label{eq:ssn_in_algo}
			$\ite \leftarrow \iite$\;
		}
		\caption{An application of~\eqref{eq:fixed_point_iter_opwavop} to solve Problem~\ref{th:problem}.}
	\end{algorithm}

	The following corollary establishes some convergence properties of Algorithm~\ref{algo:stackevmfbapp}.

	\begin{corollary} \label{th:stackevmfbapp}
		Suppose that
		\begin{equation*} \label{eq:assumption2}
		\biasvar \in \emph{\ran} \left( \subgrad{\cvxone} + \sum_{\itr=1}^{\dimr} \pdomega_\itr \conj{\lnop_\itr} \left( \infconv{\subgrad{\cvxtwo}_\itr}{\subgrad{\strong}_\itr} \right) \left(\lnop_\itr \cdot - \biasvarlnop_\itr \right) + \grad{\smooth} \right)
		\end{equation*}
		and set $\mincocomon \eqdef \min \{\coco, \strmaxmonopparam_1, \dots, \strmaxmonopparam_\dimr \}$. Let $\seq{\vm^\ite}$ be a sequence of \ac{PD} operators in $\mathbb{R}^{n \times n}$ and, for every $\itr \in \{ 1, \dots, \dimr \}$, let $\seq{\vm^\ite_\itr}$ be a sequence of \ac{PD} operators in $\mathbb{R}^{m_\itr \times m_\itr}$ such that, for all $\ite \in \mathbb{N}$,
		\begin{equation} \label{eq:stackevmfbass1}
		\begin{cases}
		\Meigvm \emph{\eye} \succeq \vm^\ite \succeq \meigvm \emph{\eye},\\
		\Meigvm \emph{\eye} \succeq \vm^\ite_\itr \succeq \meigvm \emph{\eye},\\
		\Meigvm, \, \meigvm \in \ ]0, + \infty[,
		\end{cases}
		\end{equation}
		let $\fbeps \in \;]0, \min \{ 1, \mincocomon \}[$, let $\seq{\ave^\ite}$ be a sequence of \ac{PD} operators in $\mathbb{R}^{n \times n}$, and let $\seq{\ave^\ite_\itr}$ be a sequence of \ac{PD} operators in $\mathbb{R}^{m_\itr \times m_\itr}$ such that, for all $\ite$,
		\begin{equation} \label{eq:stackevmfbassave}
		\begin{cases}
		\ave^\ite \vm^\ite = \vm^\ite \ave^\ite,\\
		\ave^\ite_\itr \vm^\ite_\itr = \vm^\ite_\itr \ave^\ite_\itr,\\
		\Meig \emph{\eye} \succeq \ave^\ite \succeq \meig \emph{\eye},\\
		\Meig \emph{\eye} \succeq \ave^\ite_\itr \succeq \meig \emph{\eye},\\
		\Meig, \, \meig \in [\fbeps, 1],
		\end{cases}
		\text{and }
		\begin{cases}
		\ave^\iite \vm^\iite \succeq \ave^\ite \vm^\ite, \\
		\ave^\iite_\itr \vm^\iite_\itr \succeq \ave^\ite_\itr \vm^\ite_\itr.
		\end{cases}
		\end{equation}

		Let, for all $\itr$, $\seq{\errorpr^\ite}$, $\seq{\errordu^\ite}$, $\seq{\errorresolpr^\ite_\itr}$, $\seq{\errorresoldu^\ite_\itr} \in \spaceseq^1(\mathbb{N})$. For every $\ite$, set $\pddelta^\ite \define \isquareroot{\sum_{\itr = 1}^{\dimr} \pdomega_\itr  \norm{\squareroot{\vm^\ite_\itr} \lnop_\itr \squareroot{\vm^\ite}}{}^2} - 1$ and suppose that $\pdxi^\ite \define \frac{\pddelta^\ite}{(1+\pddelta^\ite) \Meigvm} \geq \frac{1}{2 \mincocomon - \fbeps}$.

		Let $\seq{\pr^\ite}$ be a sequence generated by Algorithm~\ref{algo:stackevmfbapp}. Then $\pr^\ite$ converges to a point in $P$ and $\left(\du^\ite_1, \dots, \du^\ite_\dimr \right)$ converges to a point in $D$.
	\end{corollary}

	\section{Experiment} \label{sec:apps}

	In this section, we give a practical example of a simple problem that can be solved via Algorithm~\ref{algo:stackevmfbapp}. Consider the constrained problem
	\begin{equation} \label{eq:lasso_constraint}
	\underset{\mathbf{x} \in [c,d]^n}{\text{minimize}} \quad \| \mathbf{b} - \mathbf{H} \mathbf{x} \|^2 + \mu \| \mathbf{x} \|_1,
	\end{equation}
	where $\mathbf{b} \in \mathbb{R}^n$, $c \in \mathbb{R}$, $d \in \mathbb{R}$, $\mu>0$, $\mathbf{H} = {{}^{1}\!/_{n}} \widehat{\mathbf{H}}$, and $\widehat{\mathbf{H}} \in \mathbb{R}^{n \times n}$ is a lower-triangular matrix of ones. Griesse and Lorenz studied a non-constrained, and therefore simpler, version of this problem in the context of inverse integration~\cite[Section 4.1]{Griesse2008}. Problem~\eqref{eq:lasso_constraint} can be solved via Algorithm~\ref{algo:stackevmfbapp} if we let $\gamma > 0$, $\tau >0$ and make $m = n$, $\dimr = 1$, $\lnop_1 = \eye$, $\biasvarlnop_1 = \myvec{0}$, $\biasvar = \myvec{0}$, and, for all $\ite$, $\vm^\ite_1 = \gamma \eye$, $\vm^\ite = \tau \eye$, $\errorresoldu^\ite_1 = \myvec{0}$, $\errordu^\ite_1 = \myvec{0}$, $\ave_{1}^\ite = \eye$, $\errorresolpr^\ite = \myvec{0}$, $\errorpr^\ite = \myvec{0}$, $\smooth = \| \mathbf{b} - \mathbf{H} \cdot \|^2$, $\cvxone=\mu \| \cdot \|_1$, $\cvxtwo= \ind{[c,d]^n}{\cdot}$, $\strong_1: \mathbf{u} \to 0$ if $\mathbf{u} = 0$, $\strong_1: \mathbf{u} \to + \infty$ otherwise.

	If we take $\ave^\ite$ to be a sequence of scalars, we recover a version of~\cite[Example 6.4]{Combettes2014b}. However, inspired by the fast convergence properties of the methods discussed in Section~\ref{sec:ssn} and following a similar reasoning to~\cite[Proposition 3.7]{Griesse2008}, we consider the B-differential for the operator $\text{prox}_{\mu \| \cdot \|_1}$ given in~\eqref{eq:partial_B_G} and take $\ave^\ite$ to be the inverse of
	\begin{equation*} \label{eq:op_ssn}
	\inv{\left(\mathbf{P}^\ite\right)} \begin{bmatrix}
	\tau [\mathbf{H}]^*_{:{I}^k} [\mathbf{H}]^{}_{:{I}^k} & \tau [\mathbf{H}]^*_{:{I}^k} [\mathbf{H}]^{}_{:{A}^k} \\
	\mathbf{0} & \eye
	\end{bmatrix} \mathbf{P}^\ite,
	\end{equation*}
	where
	\begin{equation*}
	\begin{aligned}
	{A}^k &\eqdef \{ i \in \mathbb{N} : \big| \left[\pr^\ite - 2 \tau \left( \mathbf{H}^* \left(\mathbf{H} \mathbf{x}^k - \mathbf{b}\right) + \duo^\ite_1 \right)\right]_i \big| \leq \tau \mu \},\\
	{I}^k &\eqdef \{ i \in \mathbb{N} : \big| \left[\pr^\ite - 2 \tau \left( \mathbf{H}^* \left(\mathbf{H} \mathbf{x}^k - \mathbf{b}\right) + \duo^\ite_1 \right)\right]_i \big| > \tau \mu \},
	\end{aligned}
	\end{equation*}
	and $\seq{\mathbf{P}^\ite}$ is a sequence of appropriate permutation matrices such that, given a vector $\mathbf{x}$, the first elements of the vector $\mathbf{P}^\ite \mathbf{x}$ correspond to the indices in ${I}^k$ and the last elements to the indices in ${A}^k$, for all $k$. By again following a similar reasoning to the one of~\cite[Section 3.3]{Griesse2008}, it can be shown that Line~\ref{eq:ssn_in_algo} of Algorithm~\ref{algo:stackevmfbapp} can be rewritten in such a way that this algorithm is easily seen to be equivalent to an active-set method. In fact, that line is given by
	\begin{equation*}
	\pr^\iite \leftarrow \inv{\left(\mathbf{P}^\ite\right)} \begin{bmatrix}
	\left([\mathbf{H}]^*_{:{I}^\ite} [\mathbf{H}]_{:{I}^\ite}^{} \right)^{-1} \left[ \mathbf{H}^* \mathbf{b} - \duo^\ite_1 + \tau \mathbf{e}^\ite_{\pm}  \right]_{{I}^\ite}^{} \\
	\mathbf{0}
	\end{bmatrix},
	\end{equation*}
	where $\mathbf{e}^\ite_{\pm} \eqdef \text{sgn} \left[ \pr^k - 2 \tau \left( \mathbf{H}^* \left(\mathbf{H} \mathbf{x}^k - \mathbf{b}\right) + \duo^\ite_1 \right) \right]$, for every $\ite$. The dimension of the problem to solve at each iteration is given by the cardinality of the set $I^\ite$. Naturally, the sparser the solution is estimated to be, the smaller the dimension of this problem is. In contrast, methods such as the \ac{ADMM}~\cite{Afonso2010} require the solution of a problem involving the full matrix $\mathbf{H}^*\mathbf{H}$. This is the reason why semimooth Newton methods are able to achieve faster convergence rates in practice than others.

	We simulate an example similar to the one studied by Griesse and Lorenz~\cite[Section 4.1]{Griesse2008} but consider the noise to be Gaussian with a \ac{SNR} of 30 dB. We have set $\mu = 3 \times 10^{-3}$, $c=-80$, and $d=52$. We compared Algorithm~\ref{algo:stackevmfbapp} (denoted in what follows as \emph{Proposed}) with \ac{ADMM} and with the \ac{CM} to solve~\eqref{eq:lasso_constraint}. We manually tuned the different parameters of the three methods in order to achieve the fastest convergence results in practice. We arbitrarily chose the result of \ac{ADMM} after $10^7$ iterations as representative of the solution given by the three methods. Fig.~\ref{fig:rmse_vs_time_inv_int} illustrates the behavior of the three methods by showing the \ac{RMSE}

	between the estimates of each method and the representative solution, as a function of time. The three methods were initialized with the zero vector. The experiments were performed using MATLAB on an Intel Core i7 CPU running at 3.20~GHz, with 32~GB of RAM.

	\begin{figure}[!t]
		\begin{center}
			\includegraphics[scale=.45]{rmse_vs_time_inv_int}
			\caption{RMSE, as a function of time, between the estimates of each iteration and the representative solution, for the three methods.}
			\label{fig:rmse_vs_time_inv_int}
		\end{center}
	\end{figure}

	In this example, we did not enforce assumptions~\eqref{eq:stackevmfbassave} but verified in practice that they were satisfied. However, in more complex examples, it may be necessary to devise a strategy that generates a sequence $\seq{\ave^\ite}$ satisfying these assumptions. This is akin to the necessity of devising globalization strategies in other Newton-like methods~\cite[Chapter 8]{Facchinei2003}.

	\subsection{Appraisal}

	It is clear that, for this example, the proposed method has a much faster convergence than either \ac{CM} or \ac{ADMM}. This improvement in convergence is similar to the one observed in the methods discussed in Section~\ref{sec:ssn}. In general, the sparser the solution is, the faster the method is as well. In order to benefit from this property, we must be able to solve the lower-dimensional linear system faster than the full system. This may not always be possible: for example, in problems that involve computations with the \ac{FFT} of a signal, we usually have only modest improvements in speed if we wish to compute only selected elements of the \ac{FFT}.\footnote{See~\url{http://www.fftw.org/pruned.html} for details.} However, for large-scale problems and for highly-sparse signals, methods known as sparse \acp{FFT}~\cite{Gilbert2014} may be useful. We verified in other experiments not detailed here that the proposed method has a comparable convergence speed to ADMM in problems whose solutions are not sparse or where we cannot take advantage of their sparsity.

	\section{Conclusions} \label{sec:conclusions}

	In this work, we defined operator-weighted averaged operators, and showed that they can be used to construct a number of algorithms with good convergence properties. These algorithms have very broad applications, and seem to be particularly suitable to address problems with sparsity-inducing regularizers, as suggested by a simple experiment. Possible future directions to be explored are the possibility of relaxing the assumptions on $\ave^\ite$, and the study of which problems are most suitable to be tackled by these methods.

	\bibliographystyle{IEEEtran}

	\bibliography{refs}


TITLE: What are the odds of picking one outcome out of three, if you have two attempts and the one you pick is removed from the pool?
QUESTION [0 upvotes]: Edited for (hopefully) clarity.
There are three cards on the table facedown, two with the [o] symbol and one with [x]. You must find [x] to "win" and you have two attempts. If you do not find the [x] after your first try, the card you picked is removed and there are now only two cards. One [o] and one [x].
First attempt:
[o] [o] [x]
1/3 chance, 33.3%
Second attempt (assuming first one was unsuccessful):
[o] [x]
1/2 chance, 50%
What is the final probability of picking the [x]?
I thought that Chance AB = Chance A * Chance B, but that would be 1/3 * 1/2 = 1/6, which seems way too low to be correct.
On the other hand 1/3 + 1/2 = 5/6
I also further confused myself by trying to calculate the odds of not picking the [x] using both above methods.
2/3 * 1/2 = 1/3, which is obviously incorrect, since it does not add up to a 1 if you sum the 1/6 from above
But then 2/3 + 1/2 = 7/6 ???? yeah...
Obviously I have no idea what I am doing, can someone please untangle me? Thank you.

REPLY [0 votes]: You could find the complement of failing on both tries,
hence $1 - \frac23\frac12 = \frac23$


TITLE: How to find the value of the following items summed up together?
QUESTION [0 upvotes]: How to find the value of the following items summed up together?
$$U^j_nd^0_n\binom{j}{j}P^j_n(1-P_n)^0+U^{j-1}_nd^1_n\binom{j}{j-1}P^{j-1}_n(1-P_n)^1+U^{j-2}_nd^2_n\binom{j}{j-2}P^{j-2}_n(1-P_n)^2+\dots+U^2_nd^{j-2}_n\binom{j}{2}P^{2}_n(1-P_n)^{j-2}+U^1_nd^{j-1}_n\binom{j}{1}P^{1}_n(1-P_n)^{j-1}+U^0_nd^{j}_n\binom{j}{0}P^{0}_n(1-P_n)^{j}$$

REPLY [1 votes]: This appears to be a direct application of the binomial theorem for $(P_nU_n + (1-P_n)d_n)^j$

Binomial theorem: $$(x+y)^n = \sum\limits_{i=0}^n \binom{n}{i}x^iy^{n-i}$$

To see that, group the terms with like-powers.  (For the term $U_n^{j-1}d_n^1\binom{j}{j-1}P_n^{j-1}(1-P_n)^1$ for example, put the $U$ and the $P$ term together and the $d$ and the $(1-P)$ term together).  You get a sum of powers with one set increasing in power, the other decreasing in power with a binomial coefficient on each, matching the statement of the theorem.
Setting $x= U_nP_n$, $y=d_n(1-P_n)$, and $n=j$ into the above formula gives the result.


TITLE: Deducing formula for nth term in sequence and validate using principles of induction
QUESTION [1 upvotes]: I a working my way through some old exam papers but have come up with a problem. One question on sequences and induction goes:
A sequence of integers $x_1, x_2,\cdots, x_k,\cdots$ is defind recursively as follows: $x_1 = 2$ and $x_{k+1} = 5x_k,$ for $k \geq 1.$
i) calculate $x_2, x_3, x_4$
ii) deduce a formula for the $n$th term i.e. $x_n$ in terms of $n$ and then prove its validity, using the principles of mathematical induction.
It is the last part that is giving me trouble. I think $x_2, x_3$ and $x_4$ are $10, 50$ and $250$ respectively. I also think I managed to work out the formula, it is $f(n) = 2 \cdot 5^{n-1}.$
However I'm not sure how I'm supposed to prove this using induction... induction is only used when you're adding the numbers in a sequence I thought? I've looked everywhere and can't find any answer specific enough to this question to help. Any help appreciated. Thanks.

REPLY [0 votes]: Induction is aplicable in many cases, not just sums. In this case you have a expression for $x_n$, prove (base) that it is valid for $n = 1$ and (induction) if it is valid for $n$ it is valid for $n + 1$.


TITLE: Perpendicular vectors in 3d
QUESTION [1 upvotes]: Suppose a  vector $v$ in $\mathbb{R}^3 $
How can I  find two arbitrary unit vectors $u$ and $u^*$, that are perpendicular to each other and $v$ ?
There are infinitely many solutions, but I cannot hand pick them. I need some function $Q(v)$ = $(u, u^*)$ that deterministically finds a solution, for all non-zero vectors in $\mathbb{R}^3$.
This is probably a quaternion question, but I would prefer notation in terms of linear algebra.

REPLY [1 votes]: First pick vector $w$ which is non-parallel to $v$.
As long as $w\neq r*v$, where $r \in \Bbb R$, $w$ is non-parallel to $v$.
Let $u =w\times v$, this guarantee u is perpendicular to $v$ and $w$ vectors.
Then $u' =v\times u$, this guarantee $u'$ perpendicular to $v$ and $u$.
You have found $u$, $u'$ and $v$ which are mutually perpendicular.


TITLE: Property of pairwise independent but not independent events
QUESTION [1 upvotes]: Let $(\Omega, \mathcal A, P)$ be a probability space and $A,B,C \in \mathcal A$ with the properties
  a) $A,B,C$ are pairwise independent,
  b) $A\cap B \cap C = \emptyset$,
  c) $P(A) = P(B) = P(C) =: p$.
  Then $p \leq \frac{1}{2}$.

I tried to use the standard trick and expand with the inclusion-exclusion principle:
$$0 = P(A\cap B \cap C) = P(A \cup B \cup C)  + P(A\cap C) + P(A\cap B) + P(B\cap C) - P(A) - P(B) - P(C) = P(A\cup B \cup C) + 3p^2 - 3p$$
and hence $P(A\cup B \cup C) = 3p - 3p^2$. Here I got stuck; using $0 \leq P(A \cup B \cup C) \leq 1$ didn't get me anywhere. I am kind of skeptical of the statement but also could not find a counterexample. Any help appreciated...

REPLY [2 votes]: We also know that $P(A\cup B) \le P(A\cup B\cup C)$, which leads to the inequality $2p-p^2 \le 3p-3p^2$; this is equivalent to $2p^2 \le p$, which implies that $p \le \frac12$.


TITLE: Find the rightmost triangle with respect to the diagonal in a four-sided polygon.
QUESTION [1 upvotes]: The goal is to find the right triangle, depicted in red, in a four-sided polygon with respect to the diagonal. The four-sided polygon's vertices are known.

Initial attempts: The angle formed by the diagonal and the positive x-axis is calculated. I used x1 of v1 > x1 of v3 to identify the red triangle if the angle was found within the first quadrant.

REPLY [0 votes]: Draw a line parallel to the given diagonal from both of the other two points, and determine which one has an x-intercept greater than the other.


TITLE: Dimension of the vector space of odd polynomials of degree $n$
QUESTION [1 upvotes]: I was doing some exercises of vector space. Don't know how to handle this question?

A polynomial $p(x)$ is odd if $p(-x)=-p(x)$. Let $O_n$ denote the sets of odd polynomials in $P_n$. Then what is $\dim\,O_n$?

REPLY [4 votes]: We can split functions into odd and even parts via $$f_{\mathrm{odd}}(x)=\frac{f(x)-f(-x)}{2},\qquad f_{\mathrm{even}}(x)=\frac{f(x)+f(-x)}{2}.$$
1: Check that these are odd and even respectively, and that $f=f_{\mathrm{odd}}+f_{\mathrm{even}}$.
2: Check that $(f+g)_{\mathrm{odd}}=f_{\mathrm{odd}}+g_{\mathrm{odd}}$ and $(f+g)_{\mathrm{even}}=f_{\mathrm{even}}+g_{\mathrm{even}}$.
3: Show that $f$ is odd (resp. even) if and only if $f_{\mathrm{even}}$ (resp. $f_{\mathrm{odd}}$) is identically zero.
4: Observe that even powers $x^{2k}$ are even and odd powers $x^{2k-1}$ are odd.
5: Explain why $f\in P_n$ is odd (resp. even) if and only if it contains no even (resp. odd) powers.
6: Observe that $\{x,x^3,x^5,\dots,x^m\}$ is a basis for $O_n $, where $m$ is the largest odd $\le n$.
Now how many elements are in this set?

REPLY [1 votes]: Remember, a polynomial P(x) is odd iff it only contains odd powers of x. So every odd polynomial is of the form:
$a_1x^1 + a_3x^3 + \cdots + a_kx^k$
Assuming $P_n$ means the vector space of polynomials of degree n, you can figure out the number of different coefficients $a_i$ that will show up for a given value of n without too much trouble. That number will be the number of "degrees of freedom" you have in choosing an odd polynomial (equivalently, the number of basis elements), so it will be the dimension of the vector space.