text:
\begin{document}
\title{Error bounds for overdetermined and underdetermined generalized centred simplex gradients}
\author{Warren Hare\thanks{Department of Mathematics, University of British Columbia, Okanagan Campus, Kelowna, B.C. V1V 1V7, Canada. Research partially supported by NSERC of Canada Discovery Grant 2018-03865. warren.hare@ubc.ca, ORCID 0000-0002-4240-3903}\and Gabriel Jarry--Bolduc\thanks{Department of Mathematics, University of British Columbia, Okanagan Campus, Kelowna, B.C. V1V 1V7, Canada. Research partially supported by Natural Sciences and Engineering Research Council (NSERC) of Canada Discovery Grant 2018-03865. gabjarry@alumni.ubc.ca }\and Chayne Planiden\thanks{School of Mathematics and Applied Statistics, University of Wollongong, Wollongong, NSW, 2500, Australia. Research supported by University of Wollongong. chayne@uow.edu.au, ORCID 0000-0002-0412-8445}}
\maketitle\author
\begin{abstract}
 Using the Moore--Penrose pseudoinverse, this work generalizes the gradient approximation technique called centred simplex gradient to allow sample sets containing any number of points. This approximation technique  is called the \emph{generalized centred simplex gradient}.  We develop error bounds and, under a full-rank condition, show that the error bounds have order $O(\Delta^2)$, where $\Delta$ is the radius of the  sample set of points used.  We establish calculus rules for generalized centred simplex gradients, introduce a calculus-based generalized centred simplex gradient and confirm that error bounds for this new approach are also order $O(\Delta^2)$.  We provide several examples to illustrate the results and some benefits of these new methods.
\end{abstract}

\section{Introduction}\label{sec:intro}

Derivative-free optimization (DFO) focuses on the study of optimization algorithms that do not use first-order information within the algorithm. Recent advances in their applications, convergence analysis and practical implementations have fuelled a surge in DFO research (see \cite{Audet2014,audet2017derivative,Conn2009,Custodio2017,HareNutiniTesfamariam2013,larson_menickelly_wild_2019} and citations therein).

One of the broad classes of DFO algorithms is model-based DFO methods.  These methods rely on accurately approximating first-order information using only function evaluations and then using the approximations within classical optimization algorithms.  For example, using linear interpolation on function values from $n+1$ well-poised sample points in $\R^n$ creates a linear model of the objective function.  The gradient of this linear model, called the {\em simplex gradient}, provides an approximation of the true gradient \cite{Bortz1998,Kelley1999}.

The error bound comparing the simplex gradient and the true gradient dates back to the late 1990s and is known to be order $O(\Delta)$, where $\Delta$ is the radius of the  sample set of evaluated points \cite{Kelley1999}.   This error bound is critical in showing convergence of many first-order model-based methods
\cite[Ch.\ 10 \& 11]{audet2017derivative}.

Simplex gradients, and their associated error bound, are not limited to the setting where exactly $n+1$ interpolation points are used in $\R^n$. In \cite{Conn2008}, the authors study the construction of simplex gradients consisting of $n+1$ interpolation points in $\R^n$, and in \cite{Conn22008}, they extend those results to the cases of fewer (underdetermined models) and more (overdetermined models) than $n+1$ points.  Most notably, they establish error bounds for these cases and find them to be order $O(\Delta)$.  These results were further elaborated in \cite{Regis2015}.

Many other methods of approximating gradients exist \cite{Billups2013,Oeuvray2007,Powell2004,Regis2005,Schonlau1998,Wild2011}. Central to this work is the {\em centred simplex gradient}, which is created by retaining the original points in the sample set and adding their reflection through the reference point (see Definition \ref{def:GCSG}).  This creates an average of two simplex gradients.  Interestingly, the accuracy of the centred simplex gradient is $O(\Delta^2)$ \cite{Kelley1999}.  However, this error bound is only established for the determined case, using exactly $2n$ function evaluations in $\R^n$.  The primary goal of this paper is to establish the error bound for the centred simplex gradient for the underdetermined and overdetermined cases.  This is accomplished using the Moore--Penrose pseudoinverse to define a \emph{generalized centred simplex gradient (GCSG)}, which allows centred simplex gradients to be constructed using a sample set of any finite size.

Returning briefly to our discussion of the simplex gradient, \cite{hare2020,Regis2015} develop calculus rules for the generalized simplex gradient. A secondary goal of this paper is the extension of these results to the GCSG.  This provides the concept of the \emph{generalized centred simplex calculus gradient (GCSCG)}.  We examine this novel gradient approximation and prove that it retains the $O(\Delta^2)$ accuracy of the centred simplex gradient.  Some benefits of the new techniques are illustrated through examples.

The structure of the paper is the following. In Section \ref{sec:prel}, we introduce notation and basic definitions. In Section \ref{sec:errorbounds}, we show that generalized centred simplex gradients inherit the  order of accuracy $O(\Delta^2)$.  We present two error bounds, depending on the number of points  in the sample set. In Section \ref{sec:calc}, we present the calculus rules for the GCSG. In Section \ref{sec:centredsimplexcalculusgradient}, we define the GCSCG, based on the calculus rules from  the previous section. We prove that each of these new techniques has order of accuracy $O(\Delta^2)$.  We provide examples, showing some benefits of the GCSCG compared to the GCSG in certain situations. Section \ref{sec:conclusion} summarizes the work accomplished and suggests some topics to explore in future research.

\section{Preliminaries} \label{sec:prel}

Unless otherwise stated, we use the standard notation found in \cite{rockwets}. The domain of a function $f$ is denoted by $\dom(f)$. The transpose of a matrix $A$ is denoted by $A^\top$. We work in finite-dimensional space $\R^n$ with inner product $x^\top y=\sum_{i=1}^nx_iy_i$ and induced norm $\|x\|=\sqrt{x^\top x}$. We use angle brackets $\langle\cdots\rangle$ to contain an ordered set of vectors. The identity matrix is denoted by $\Id$. We denote by $B(x,\Delta)$ the open ball centred about $x$ with radius $\Delta$. The set of all linear combinations of the vectors in a set $S$ is denoted by $\Span S$. \medskip\\
We next list some definitions and background results.
\begin{df}[Jacobian]
Given a differentiable function $f: \dom(f) \subseteq \R^n\to\R^p$, the \emph{Jacobian} of $f$,
written $\jf$, is the column matrix of all partial derivatives of $f$:
$$\jf=\left[\begin{array}{c c c}\frac{\partial
f}{\partial x_1}&\cdots&\frac{\partial f}{\partial
x_n}\end{array}\right]=\left[\begin{array}{c c c}
\frac{\partial f_1}{\partial x_1}&\cdots&\frac{\partial f_1}{\partial x_n}\\
\vdots&\ddots&\vdots\\
\frac{\partial f_p}{\partial x_1}&\cdots&\frac{\partial f_p}{\partial
x_n}\end{array}\right].$$
\end{df}
\begin{df}[Lipschitz continuity] A function $f: \dom(f) \subseteq \R^n\to\R$ is said to be \emph{Lipschitz continuous} with Lipschitz constant $L\geq0$ if for all $x,y\in\dom (f)$,
$$|f(y)-f(x)|\leq L\|y-x\|.$$If for every $x\in\dom (f) $ there exists a neighbourhood $U$ of $x$ such that $f$ restricted to $U$ is Lipschitz continuous, then $f$ is said to be \emph{locally Lipschitz continuous} on $U$.
\end{df}

We remind the reader that for nonsquare matrices, a generalization of the matrix inverse is the pseudoinverse. The most well-known type of matrix pseudoinverse, which is central to the results of this work, is the Moore--Penrose pseudoinverse.
\begin{df}[Moore--Penrose pseudoinverse] \label{def:mpinverse}
Let $A\in\R^{n\times m}$. The \emph{Moore--Penrose pseudoinverse} of $A$, denoted by $A^\dagger$, is the unique matrix in $\R^{m \times n}$ that satisfies the following four equations:
\begin{align*}
AA^\dagger A&=A,\\A^\dagger AA^\dagger&=A^\dagger,\\(AA^\dagger)^\top&=AA^\dagger,\\(A^\dagger A)^\top&=A^\dagger A.
\end{align*}
\end{df}
The Moore--Penrose inverse $A^\dagger$ is not always an inverse of $A$, but the following two properties hold.
\begin{itemize}
\item If $A$ has full column rank $m$, then $A^\dagger$ is a left-inverse of $A$, that is, $A^\dagger A=\Id_m$.
\item If $A$ has full row rank $n$, then $A^\dagger$ is a right-inverse of $A$, that is, $AA^\dagger=\Id_n$.
\end{itemize}
In order to define the generalized simplex gradient and the GCSG in the sequel, we use the following sets, matrices and terminology.
\begin{df}[Simplex notation]\label{df:simplex}Given $f:\dom(f)  \subseteq \R^n\to\R$ and an ordered sample set of distinct  points
\begin{align*}
\X&=\langle x^0,x^1,\ldots,x^m\rangle=\langle x^0,x^0+d^1,\ldots,x^0+d^m\rangle\subseteq \dom (f),
\intertext{we define}
\X^-&=\langle x^0,x^0-d^1,\ldots,x^0-d^m\rangle\subseteq \dom (f),\\
\Delta&=\max\limits_{i \,\in\{1,\ldots,m\}}\|d^i\| \mbox{\emph{, the radius of }}\X,\\
S=S(\X)&=[d^1~~\cdots~~d^m]\in\R^{n\times m},\\
\ds=\dsf(\X)&=\left[\begin{array}{c}f(x^1)-f(x^0)\\f(x^2)-f(x^0)\\\vdots\\f(x^m)-f(x^0)\end{array}\right]\in\R^m,\\
\dc=\dcf(\X)&=\frac{1}{2}\left[\begin{array}{c}f(x^0+d^1)-f(x^0-d^1)\\f(x^0+d^2)-f(x^0-d^2)\\\vdots\\f(x^0+d^m)-f(x^0-d^m)\end{array}\right]\in\R^m.
\end{align*}
\end{df}
\begin{df}
Let $\X=\langle x^0, x^0+d^1, \dots, x^0+d^m \rangle \subseteq \dom(f)$  be an ordered set of $m+1$ distinct points in $\R^n.$ Then we classify the set $\X$ in exactly one of the following cases:
\begin{itemize}
\item \emph{overdetermined case} if $m>n$ and $\rank S=n$;
\item\emph{determined case} if $m=n$ and $\rank S=n$;
\item\emph{underdetermined case} if $m<n$ and $\rank S=m$;
\item\emph{undetermined case} if S is not full rank.
\end{itemize}
\end{df}

Note that the points in $\X$ are assumed to be distinct for the rest of this paper.
\begin{df}[Generalized simplex gradient] Let $f:\dom(f) \subseteq \R^n\to\R$ and let $\X$ be an ordered set in $\dom(f).$ The \emph{generalized simplex gradient} (GSG) of $f$ over $\X$ is denoted by $\nabla^sf(\X)$ and defined by
\begin{equation*}\label{eq:simplex}\ns f(\X)=(S^\top)^\dagger\ds.\end{equation*}
\end{df}
\begin{df}[Generalized centred simplex gradient]\label{def:GCSG}
Let $f:\dom(f) \subseteq \R^n\to\R$ and let $\X$ be an ordered set such that $\X \cup \X^{-}$ is in  $\dom(f)$. The \emph{generalized centred simplex gradient} (GCSG) of $f$ over $\X$ is denoted by $\nabla^cf(\X)$ and defined by
\begin{equation*}\label{eq:centred}\nc f(\X)=(S^\top)^\dagger\dc.\end{equation*}
\end{df}
It is easy to show that an equivalent way to compute the GCSG is by using the average of two GSGs:
\begin{equation}\label{eq:altcentred}\nc f(\X)=\frac{1}{2}(\ns f(\X)+\ns f(\X^-)).\end{equation}
Next, we introduce a proposition that clarifies the relation between the GSG and the GCSG and provides a case where both approaches are equal. We require the following two lemmas first.
\begin{lem}
Let $A \in \R^{n \times m}$. Then $(A^\top)^\dagger=(A^\dagger)^\top.$
\end{lem}
\begin{proof}
Since $(A^\dagger)^\top$ and $(A^\top)^\dagger$ satisfy the same four properties in Definition \ref{def:mpinverse}, it follows that they are equal.
\end{proof}
\begin{lem} Let  $A \in \R^{n \times m}$ have full  row rank. Then $\bbm A&-A\ebm^\dagger=\frac{1}{2}\bbm A^\dagger\\-A^\dagger\ebm.$
\end{lem}
\begin{proof}
Since $\bbm A &-A\ebm$ has full row rank, we have
\begin{align*}
    \bbm A&-A\ebm^\dagger&=\bbm A&-A \ebm^\top \left ( \bbm A&-A\ebm \bbm A&-A \ebm^\top \right )^{-1}\\
    &=\bbm A^\top\\-A^\top \ebm \left ( \bbm A&-A \ebm \bbm A^\top\\-A^\top \ebm \right )^{-1}\\
    &=\bbm A^\top\\-A^\top \ebm \left ( 2 \bbm AA^\top \ebm \right )^{-1}\\
    &=\frac{1}{2}\bbm A^\top (AA^\top)^{-1}\\-A^\top (AA^\top)^{-1}   \ebm\\
    &=\frac{1}{2}\bbm A^\dagger\\-A^\dagger \ebm.\qedhere
\end{align*}
\end{proof}
\begin{prop}
Let $f:\dom(f) \subseteq \R^n \to \R$ and let $\X=\langle x^0, x^0+d^1, \dots, x^0+d^m \rangle$ be an ordered set such that $\X \cup \X^{-} \subseteq \dom(f)$ and $S$ has full row rank (determined and overdetermined cases). Let $\mathcal{Y}=\left \langle x^0, x^0+d^1, \dots, x^0+d^m, x^0-d^1, \dots, x^0-d^m \right \rangle$. Then
\begin{align*}
    \ns f(\y)&=\nc f(\X).
\end{align*}
\end{prop}
\begin{proof}
We have
\begin{align*}
    \ns f(\y)&=(S(\y)^\top)^\dagger \dsf (\y)\\
    &=\left (\bbm S(\X) &-S(\X)\ebm^\top\right )^\dagger \bbm \dsf(\X)\\\dsf(\xm)\ebm=\left (\bbm S(\X) &-S(\X)\ebm^\dagger\right )^\top \bbm \dsf(\X)\\\dsf(\xm)\ebm\\
    &=\frac{1}{2}\bbm S(\X)^\dagger\\-S(\X)^\dagger\ebm^\top \bbm \dsf(\X)\\\dsf(\xm)\ebm=\frac{1}{2}\bbm (S(\X)^\top)^\dagger& -(S(\X)^\top)^\dagger  \ebm\bbm \dsf(\X)\\\dsf(\xm)\ebm\\
    &=\frac{1}{2}\left ( (S(\X)^\top)^\dagger \dsf(\X) -(S(\X)^\top)^\dagger \dsf(\xm) \right )\\
    &=\frac{1}{2}\left ( (S(\X)^\top)^\dagger \dsf(\X) +(S(\xm)^\top)^\dagger \dsf(\xm) \right )=\nc f(\X).\qedhere
\end{align*}
\end{proof}
Notice that the GCSG uses an ordered set of points. The reason is that if the position of the reference point $x^0$  is changed in the overdetermined case, then we do not necessarily get the same value. The following example illustrates this situation.
\begin{ex} Consider the sets $\X=\langle -1, 0, 1 \rangle$ and $\X_\alpha=\langle 0, 1, -1 \rangle,$ and the function $f: \R \to \R: y \mapsto y^4.$ Then
\begin{align*}
    \nc f(\X)&=(S(\X)^\top)^\dagger \dcf(\X)\\
    &=\bbm1\\2\ebm^\dagger \frac{1}{2} \bbm 0 -16\\1-81\ebm=-17.6
    \intertext{and}
    \nc f(\X_\alpha)&=\bbm 1 \\-1 \ebm^\dagger \frac{1}{2} \bbm 1 - 1\\ 1 -1 \ebm =0.
\end{align*}
\end{ex}

\section{Error bounds for the GCSG} \label{sec:errorbounds}

This section is dedicated to developing the $O(\Delta^2)$ upper bounds on the error for the GCSG. There are two instances to consider separately; first we look at the determined and overdetermined cases, then the underdetermined case. These two settings have different results, as the number of linearly independent vectors in the simplex differs.

\subsection{Determined and overdetermined cases}

An error bound for the determined case of the GCSG is established in \cite[Theorem 9.13]{ audet2017derivative}, the accuracy of which is measured in terms of $\Delta$. The GCSG error bound in the determined case has order $O(\Delta^2)$. We show that this error bound can be extended to the overdetermined case. To that end, we present Lemma \ref{lem1}, which relies on the multidimensional  second-order Taylor theorem below.

\begin{thm}\emph{\cite[Section 4.3]{Lax2017}}\label{thm:Taylor} Suppose $f:\dom(f)\subseteq \R^n\to\R$ is a $\mathcal{C}^{3}$ function on the open ball $B(x^0,\overline{\Delta}).$  Then for $x^0+d$ in the ball,
\begin{align*}
    f(x^0+d)&=f(x^0)+\nabla f(x^0)^\top d+ \frac{1}{2} d^\top \nabla^2 f(x^0) d+R_2(x^0, d).
\end{align*}
Moreover,
\begin{align*}
    \vert R_2(x^0, d) \vert \leq \frac{L}{6} \Vert d \Vert^3,
\end{align*}
where $L$ is the Lipschitz constant of the Hessian $\nabla^2 f.$
\end{thm}
\begin{lem}\label{lem1}
Let $f:\dom(f) \subseteq \R^n\to\R$ be $\mathcal{C}^{3}$ on $B(x^0,\overline{\Delta})$ and denote by $L$ the Lipschitz constant of $\nabla^2f$. Then for any $d\in B(x^0,\overline{\Delta})$, we have
\begin{equation}\label{eq1}|f(x^0+d)-f(x^0-d)-2\nabla f(x^0)^\top d|\leq\frac{L}{3}\|d\|^3.\end{equation}
\end{lem}
\begin{proof}
From Theorem \ref{thm:Taylor}, we know that
\begin{align}f(x^0+d)&=f(x^0)+\nabla f(x^0)^\top d+\frac{1}{2}d^\top\nabla^2f(x^0)d+R_2(x^0, d),\label{eq2}\\
f(x^0-d)&=f(x^0)-\nabla f(x^0)^\top d+\frac{1}{2}d^\top\nabla^2f(x^0)d+R_2(x^0, -d).\label{eq3}
\end{align}
Subtracting \eqref{eq3} from \eqref{eq2}, we find
\begin{align*}
f(x^0+d)-f(x^0-d)-2\nabla f(x^0)^\top d&=R_2(x^0, d)-R_2(x^0, -d)\\
\Rightarrow |f(x^0+d)-f(x^0-d)-2\nabla f(x^0)^\top d|&=|R_2(x^0, d)-R_2(x^0, -d)|.
\end{align*}
Also from Theorem \ref{thm:Taylor}, we know that
\begin{equation}\label{eq6}|R_2(x^0, \pm d)|\leq\frac{L\|d\|^3}{6}.\end{equation}
Therefore, by \eqref{eq6} and the triangle inequality, we obtain \eqref{eq1}.
\end{proof}
Now we are ready for our first error bound result, for the determined and overdetermined cases.
\begin{thm}\label{thm:det}
Let $f:\dom(f) \subseteq \R^n\to\R$ be $\mathcal{C}^{3}$ on $B(x^0,\overline{\Delta}),$ and denote by $L$ the Lipschitz constant of $\nabla^2f$. Let $\X=\left \langle x^0, x^1, \dots, x^m \right \rangle$ be an ordered set with radius $\Delta<\overline{\Delta}$ and let $\rank S=n$ (determined and overdetermined cases).
 Then
\begin{equation*}\label{eq:determinederror}\|\nc f(\X)-\nabla f(x^0)\|\leq\frac{L\sqrt m}{6}\left\|(\widehat{S}^\top)^\dagger\right\|\Delta^2,\end{equation*}
where $\widehat{S}=S/\Delta$.
\end{thm}
\begin{proof}
 We have
\begin{align*}
    \|\dcf-S^\top\nabla f(x^0)\|&=\sqrt{\sum\limits_{i=1}^m\left(\frac{f(x^0+d^i)-f(x^0-d^i)}{2}-(d^i)^\top\nabla f(x^0)\right)^2}\\
    &\leq \sum\limits_{i=1}^m\left\vert \frac{f(x^0+d^i)-f(x^0-d^i)}{2}-(d^i)^\top\nabla f(x^0)\right \vert.
\end{align*}
Now using Lemma \ref{lem1} and the definition of $\Delta$, we have
\begin{equation*}\label{eq7}\|\dcf-S^\top\nabla f(x^0)\|\leq\frac{L\sqrt m\Delta^3}{6}.\end{equation*}
Since $S^\top$ has full column rank, $(S^\top)^\dagger$ is a left inverse of $S^\top$. Thus,
\begin{align*}
\|\nc f(\X)-\nabla f(x^0)\|&=\left\|(S^\top)^\dagger\dcf-(S^\top)^\dagger S^\top\nabla f(x^0)\right\|\\
&\leq\left\|(S^\top)^\dagger\right\|\|\dcf-S^\top\nabla f(x^0)\|\\
&\leq\left\|(S^\top)^\dagger\right\|\frac{L\sqrt m\Delta^3}{6}\\
&=\left\|(\widehat{S}^\top)^\dagger\right\|\frac{L\sqrt m\Delta^2}{6}.\qedhere
\end{align*}
\end{proof}

\subsection{Underdetermined case}

When developing the underdetermined case, we obtain the error bound by considering $f$ not on all of $\R^n$, but on a subspace that is dependent on the linearly independent vectors in $S$. Suppose $\uu=\Span S\neq\R^n$ (i.e.\ $\rank S<n$). Note that $\uu+x^0$ is the affine hull of $\X$, which we denote by $\aff\X$. Since all of our sample points lie in $\uu+x^0$, it is unreasonable to expect the ability to estimate gradients accurately outside of this affine hull. The following example demonstrates this problem.
\begin{ex}\label{ex:proj}
Let $f:\R^3\to\R: y\mapsto ay_1+(a+1)y_2+(4-a)y_3$, $a\in\R$. Consider the sample set$$\X=\left\langle x^0,x^1,x^2\right\rangle=\left\langle\left[\begin{array}{c}0\\0\\0\end{array}\right],\left[\begin{array}{c}1\\0\\1\end{array}\right],\left[\begin{array}{c}0\\1\\1\end{array}\right]\right\rangle.$$Then regardless of the value of $a$, we have
$$f(x^0)=0,\qquad f(x^1)=a+4-a=4,\qquad f(x^2)=a+1+4-a=5.$$
Therefore, it is impossible to determine $\nabla f$ using $\X$.
\end{ex}
We wish to create an approximate gradient that is accurate on the subspace $\uu$. Note that $\uu=\{y :y_3=y_1+y_2\}$. Define $\Proj_{\uu}$ as the projection operator onto $\uu\subseteq\R^n$. We restrict $f$ to the domain $\uu$ by defining the following function:
$$f_{\uu}(y)=f(x^0+\Proj_{\uu}(y-x^0)).$$Then by \cite[Lemma 4.2]{hare2019chain}, we have the following useful relationship between the projection of the gradient of $f$ onto $\uu$ and the so-called $\U$-gradient of $f$ denoted by $\nabla f_{\uu}$:
$$\nabla f_{\uu}=\Proj_{\uu}\nabla f.$$
The function $f_{\uu}$ effectively restricts the domain of $f$ to the subspace $\uu$ and provides us with gradient information on $\aff\X$.

\begin{ex} Let $f:\R^3\to\R:y \mapsto a^\top y=a_1y_1+a_2y_2+a_3y_3$ and$$\X=\left\langle x^0,x^1,x^2\right\rangle=\left\langle\left[\begin{array}{c}0\\0\\0\end{array}\right],
\left[\begin{array}{c}1\\0\\1\end{array}\right],\left[\begin{array}{c}0\\1\\1\end{array}\right]\right\rangle.$$We have $$S=\left[\begin{array}{c c}1&0\\0&1\\1&1\end{array}\right].$$

By \emph{\cite[\S 2.2 eq. (3)]{vusmoothness} (see \eqref{eq:projsum2} below)}, the projection of $y$ onto $\uu$ is given by
$$\Proj_{\uu}y=\frac{1}{3} \bbm 2&-1&1\\-1&2&1\\1&1&2\ebm \bbm y_1\\y_2\\y_3 \ebm=\frac{1}{3}\left[\begin{array}{c}2y_1-y_2+y_3\\-y_1+2y_2+y_3\\y_1+y_2+2y_3\end{array}\right].$$
Thus,
\begin{align*}f_{\uu}(y)=f(x^0+\Proj_{\uu}(y))&=a_1\frac{2y_1-y_2+y_3}{3}+a_2\frac{-y_1+2y_2+y_3}{3}+a_3\frac{y_1+y_2+2y_3}{3}\\
&=\frac{2a_1-a_2+a_3}{3}y_1+\frac{-a_1+2a_2+a_3}{3}y_2+\frac{a_1+a_2+2a_3}{3}y_3\end{align*}
and $$\nabla f_{\uu}(y)=\frac{1}{3}\left[\begin{array}{c}2a_1-a_2+a_3\\-a_1+2 a_2+a_3\\a_1+a_2+2a_3\end{array}\right].$$
On the other hand, we have
\begin{align*}
\Proj_{\uu}\nabla f(y)=\Proj_{\uu}a=\frac{1}{3} \bbm 2&-1&1\\-1&2&1\\1&1&2\ebm \left[\begin{array}{c}a_1\\a_2\\a_3\end{array}\right]=\frac{1}{2}\left[\begin{array}{c}2a_1-a_2+a_3\\-a_1+2 a_2+a_3\\a_1+a_2+2a_3\end{array}\right].
\end{align*}
\end{ex}
In the underdetermined case below, we will work with the Moore--Penrose inverse $S^\dagger$.  By \cite[\S 2.2 eq. (3)]{vusmoothness}, if $S$ has full column rank, then
\begin{equation}\label{eq:projsum2}
\Proj_{\uu}y=S(S^\top S)^{-1}S^\top y=(S^\top)^\dagger S^\top y.
\end{equation}
With this in mind, we are ready to provide an error bound for the underdetermined case.
\begin{thm} \label{thm:under}
Let $f:\dom(f) \subseteq \R^n\to\R$ be $\mathcal{C}^{3}$ on $B(x^0,\overline{\Delta})$ and denote by $L$ the Lipschitz constant of $\nabla^2f$.
Let $\X=\langle x^1,\ldots,x^m\rangle$ be an ordered set   with radius $\Delta<\overline{\Delta}$. Let $\rank S=m<n$ (underdetermined case) and let $\uu=\Span S.$  Define $\widehat{S}=S/\Delta$. Then
$$
\|\nabla^c f (\X) - \nabla f_{\uu}(x^0)\| =
\|\Proj_{\uu}\nabla^c f(\X)-\Proj_{\uu}\nabla f(x^0)\|
\leq \frac{L\sqrt m}{6}\left\|(\widehat{S}^\top)^\dagger\right\|\Delta^2.$$
\end{thm}
\begin{proof}  By definition, $\nabla f_{\uu}(x^0)=\Proj_{\uu}\nabla f(x^0)$. Also, note that for all $i \in \{0, 1, \dots, m\}$, we have $f(x^i)=f_{\uu}(x^i)$. So $\nc f(\X)=\nc f_{\uu} (\X),$ and by definition, $\nc f_{\uu}(\X)= \Proj_{\uu} \nabla^c f(\X).$ Thus, the first equality holds.

From the definition of Lipschitz continuity, restricting $f$ to $\uu=\Span S\subseteq\R^n$ does not alter $\nabla^2f$ from being $L$-Lipschitz. The projection of a point onto $\uu$ is given by \eqref{eq:projsum2}, which yields
\begin{align*}
\|\Proj_{\uu}\nabla^cf(\X)-\Proj_{\uu}\nabla f(x^0)\|&=\|(S^\top)^\dagger S^\top(S^\top)^\dagger\delta^c_f-(S^\top)^\dagger S^\top\nabla f(x^0)\|.
\end{align*}
Since $S$ has full column rank, $S^\top$ has full row rank, which yields $S^\top (S^\top)^\dagger =\Id_m$. Hence,
\begin{align*}
\|\Proj_{\uu}\nabla^cf(\X)-\Proj_{\uu}\nabla f(x^0)\|&=\|(S^\top)^\dagger\delta^c_f-(S^\top)^\dagger  S^\top\nabla f(x^0)\|\\
&\leq\|(S^\top)^\dagger\|\|\delta^c_f-S^\top\nabla f(x^0)\|.
\end{align*}
Using Lemma \ref{lem1}, we have
\begin{align*}
\|\Proj_{\uu}\nabla^cf(\X)-\Proj_{\uu}\nabla f(x^0)\|&\leq \|(S^\top)^\dagger\|\frac{L\sqrt m}{6}\Delta^3\\
&\leq\|(\widehat{S}^\top)^\dagger\|\frac{L\sqrt m}{6}\Delta^2.\qedhere
\end{align*}
\end{proof}
We observe that this result is almost identical to the Theorem \ref{thm:det} result, except that it is in the reduced space rather than in $\R^n$. With only $m<n$ linearly independent vectors in $S$, this is the best result possible for the underdetermined case.

\section{Calculus rules}\label{sec:calc}

In this section, we provide calculus rules for the GCSG. Throughout this section, all  functions have a domain contained in $\R^n$  and map to $\R$. The calculus formulae for the GCSG follow directly from the calculus rules for the GSG  presented in \cite{hare2020} by using \eqref{eq:altcentred}.  Before introducing the calculus rules for the GSCG, let us recall the definition of the \emph{product difference vector} and the calculus rules for the GSG (Table  \ref{tab:calcrulesgsg}) introduced in \cite{hare2020}.

\begin{df}[Product difference vector]
Let $\X=\langle x^0, x^0+d^1, \dots, x^0+d^m \rangle$ be an ordered set of $m+1$ distinct points contained in $\dom(f)$ and $\dom(g)$. The \emph{product difference vector} of $f$ and $g$  over $\X$ is denoted by $\delta^s_{f|g}(\X)$ and defined by
\[
\dfxg (\X)=\begin{bmatrix}(f(x^0+d^1)-f(x^0))(g(x^0+d^1)-g(x^0))\\(f(x^0+d^2)-f(x^0))(g(x^0+d^2)-g(x^0)) \\\vdots\\(f(x^0+d^m)-f(x^0))(g(x^0+d^m)-g(x^0))\end{bmatrix}.
\]
\end{df}
\begin{table}[ht]
\caption{\textbf{Calculus rules for the GSG}}\label{tab:calcrulesgsg}
\center{
\begin{tabular}{ |p{1.5cm}||p{6.8cm}|p{7.1cm}| }

 \hline
\textbf{Rule}& \textbf{Formula} &\textbf{$E^s$}\\
 \hline
 Product of $2$ & $f(x^0)\ns g(\X)+g(x^0)\ns f(\X)+E^s_{fg}$&$\left (S^\top\right )^\dagger \dfxg$\\
 Product of $k$&$\sum_{i=1}^{k}\left(\prod_{j\neq i}f_j (x^0) \right)\ns f_i(\X)+ E^s_{f_1\cdots f_n}$ &$\sxtd \left ( \delta^s_{f_1\cdots f_n} -
 \sumdk \right )$\\
 Positive power &$n[f(x^0)]^{n-1}\ns f(\X)+E^s_{f^n}$ & $\sxtd\left ( \sum_{i=1}^{n-1}[f(x^0)]^{n-1-i}\dfftothei \right )$\\
 Negative power &$-n[f(x^0)]^{-n-1} \ns f(\X)-E_{f^{-n}}$&$\frac{\sxtd}{[f(x^0)]^n}\left ( n \doneoverff - \sum_{i=1}^{n-1}[f(x^0)]^{1+i} \dfminusonefminusi \right )$\\
 Quotient&$\frac{g(x^0)\ns f(\X)-f(x^0)\ns g(\X)}{[g(x^0)]^2} -E_{\frac{f}{g}}$ &$\frac{\sxtd}{g(x^0)} \dfovergg$ \\

 \hline
\end{tabular}}
\end{table}

Note that the GCSG is a linear operator. Indeed, this follows from the facts that the GSG is a linear operator \cite[Proposition 9] {Regis2015} and the GCSG is the average of two GSGs.  Using this, we can adjust the product rule for the GSG to a product rule for the GCSG.

\begin{prop}[GCSG product rule]\label{prop:productrule} Let $\X=\langle x^0,x^0+d^1,\ldots,x^0+d^m\rangle$ be an ordered set of $m+1$ points such that $\X \cup \X^{-}$ is in $\dom(f)$ and $\dom(g)$. Then
\begin{equation*}\nc(fg)(\X)=f(x^0)\nc g(\X)+g(x^0)\nc f(\X)+\ecfg(\X),\end{equation*}
where $\ecfg(\X)=\frac{1}{2}\left(\esfg(\X)+\esfg (\X^-)\right)$.
\end{prop}
\begin{proof}
We have
\footnotesize\begin{align*}
\nc (fg)(\X)&=\frac{1}{2}(\ns(fg)(\X)+\ns (fg)(\X^-))\\
&=\frac{1}{2}(f(x^0)\ns g(\X)+g(x^0)\ns f(\X)+\esfg(\X)+f(x^0)\ns g(\X^-)+g(x^0)\ns f(\X^-)+\esfg(\X^-))\\
&=f(x^0)\frac{1}{2}(\ns g(\X)+\ns g(\X^-))+g(x^0)\frac{1}{2}(\ns f(\X)+\ns f(\X^-))+\frac{1}{2}(\esfg (\X)+\esfg (\X^-))\\
&=f(x^0)\nc g(\X)+g(x^0)\nc f(\X)+\ecfg(\X).\qedhere
\end{align*}
\normalsize
\end{proof}

The averaging technique used in Proposition \ref{prop:productrule} can be used to create calculus rules for the product of $k$ functions, positive powers, and negative powers.  We omit proofs for the next three results, as they are straightforward.

\begin{cor}[GCSG product rule, $k$ functions]
Let $f_i:\dom(f_i) \subseteq \R^n\to\R$ for all $i\in\{1,2,\ldots,k\}$, $k\geq 2$ and let $\X=\langle x^0,x^0+d^1,\ldots,x^0+d^m\rangle$ be an ordered set of $m+1$ points such that $\X \cup \X^{-}$ is in $\dom(f_i)$ for all $i$. Then
\begin{equation*}\nc(f_1\cdots f_k)(\X)=\sum\limits_{i=1}^k\prod\limits_{j\neq i}f_j(x^0)\nc f_i(\X)+\ecfonefk(\X),\end{equation*}
where
\begin{equation*}\ecfonefk (\X)=\frac{1}{2}\left(\esfonefk (\X)+\esfonefk (\X^-)\right).\end{equation*}
\end{cor}
\begin{cor}[GCSG power rule]
Let $\X=\langle x^0,x^0+d^1,\ldots,x^0+d^m\rangle$ be an ordered set of $m+1$ points such that $\X \cup \X^{-}$ is in $\dom(f)$. Let  $k\in\N$. Then
\begin{equation*}\nc f^k(\X)=k(f(x^0))^{k-1}\nc f(\X)+\ecfk(\X),\end{equation*}
where
\begin{equation*}\ecfk(\X)=\frac{1}{2}\big(\esfk(\X)+\esfk(\X^-)\big).\end{equation*}
\end{cor}
\begin{prop}[GCSG quotient rule] \label{prop:gcsgquotient}
Let $\X=\langle x^0,x^0+d^1,\ldots,x^0+d^m\rangle$ be an ordered set of $m+1$ points such that $\X \cup \X^-$ is in $\dom(f) \cap \dom(g)$ and  for which $g(x^0)$, $g(x^0\pm d^1)$, $\ldots$, $g(x^0\pm d^m)$ are all nonzero. Then
\begin{equation*}\nc\left(\frac{f}{g}\right)(\X)=\frac{g(x^0)\nc f(\X)-f(x^0)\nc g(\X)}{g^2(x^0)}-\ecfoverg (\X),\end{equation*}
where
\begin{equation*}\ecfoverg (\X)=\frac{1}{2}\Big(\esfoverg (\X)+\esfoverg (\X^-)\Big).\end{equation*}
\end{prop}
\begin{cor}[GCSG power rule, negative exponent] \label{cor:gcsgpowerneg}
Let $\X=\langle x^0,x^0+d^1,\ldots,x^0+d^m\rangle$ be an ordered set of $m+1$ points such that $\X \cup \X^-$ is in $\dom(f)$   and for which $f(x^0)$, $f(x^0\pm d^1), \ldots, f(x^0\pm d^m)$ are all nonzero. Let $k\in\N$. Then
\begin{equation*}\nc f^{-k}(\X)=-k f^{-k-1}(x^0)\nc f(\X)-\ecfminusk (\X),\end{equation*}
where
\begin{equation*}\ecfminusk (\X)=\frac{1}{2}\left(\esfminusk(\X)+\esfminusk (\X^-)\right).\end{equation*}
\end{cor}
\noindent Our final calculus rule for the GCSG is the chain rule. For this, we require some additional notation. Let $f:\dom(f) \subseteq \R^p\to\R$ and $g: \dom(g) \subseteq \R^n\to\R^p$, where
\begin{equation*}g(y)=\left[\begin{array}{c}g_1(y)\\g_2(y)\\\vdots\\g_p(y)\end{array}\right]\in\R^p.\end{equation*}
Let $\X=\langle x^0,x^0+d^1,\ldots,x^0+d^m\rangle$ be an ordered set of $m+1$ distinct points such that $\X \cup \X^-$ is in $\dom(g)$ and define
\begin{align*}
g(\X)&=\langle g(x^0),g(x^0+d^1),\ldots,g(x^0+d^m)\rangle\\
&=\langle g(x^0),g(x^0)+h^1,\ldots,g(x^0)+h^m\rangle,\\
g(\X)^{-}&= \langle g(x^0), g(x^0)-h^1, \ldots, g(x^0)-h^m \rangle
\end{align*}
where $h^i=g(x^0+d^i)-g(x^0)$ for all $i\in\{1,2,\ldots,m\}$, to be ordered sets of $m+1$ points such that $g(\X) \cup g(\X)^-$ is in $\dom(f)$. Denote
\begin{align*}
\sg=S(g(\X))&=[g(x^0+d^1)-g(x^0)~~\cdots~~g(x^0+d^m)-g(x^0)]\\
&=[h^1~~\cdots~~h^m]\in\R^{p\times m}.
\end{align*}
Now we introduce the generalized centred simplex Jacobian of $g$ over $\X$.
\begin{df}[Generalized centred simplex Jacobian] Define the function $g: \dom(g) \subseteq \R^n\to\R^p$, $y\mapsto[g_1(y)~~g_2(y)~~\cdots~~g_p(y)]^\top$. Let $\X$ be an ordered set of $m+1$ points such that $\X \cup \X^-$ is in $\dom(g)$. Then the \emph{generalized centred simplex Jacobian} of $g$ over $\X$, denoted by $\jcg(\X)$, is the $p\times n$ real matrix defined by
 \begin{equation*}
\jcg (\X)=\left[\begin{array}{c}\nc g_1(\X)^\top\\\nc g_2(\X)^\top\\\vdots\\\nc g_p(\X)^\top\end{array}\right].
\end{equation*}
\end{df}
\noindent With these terms defined, we are ready to present the GCSG chain rule. Note that
\begin{align*}
\dcf (g(\X))&=\frac{1}{2}\left[\begin{array}{c}f(g(x^0)+h^1)-f(g(x^0)-h^1)\\\vdots\\f(g(x^0)+h^m)-f(g(x^0)-h^m)\end{array}\right].\\
\neq \dcfcircg (\X)&=\frac{1}{2}\left[\begin{array}{c}f(g(x^0+d^1))-f(g(x^0-d^1))\\\vdots\\f(g(x^0+d^m))-f(g(x^0-d^m))\end{array}\right].
\end{align*}
For this reason, the chain rule for the GCSG cannot be obtain using a similar approach to the one for the GSG \cite[Theorem 15]{hare2020}.
\begin{prop}[GCSG chain rule]
Let the functions  $f:\dom(f) \subseteq \R^p\to\R$, $g:\dom(g) \subseteq \R^n\to\R^p$ and let $\X=\langle x^0,x^0+d^1,\ldots,x^0+d^m\rangle$ be an ordered set of $m+1$ points  such that $\X \cup \X^-$ is in $\dom(g)$ and $g(\X) \cup g(\X)^-$ is in $\dom(f)$. Then
\begin{equation*}
\nc (f\circ g)(\X)=\jcg (\X)^\top\nc f(g(\X))-E,
\end{equation*}
where
\begin{align*}
E&=(S^\top)^\dagger\dcg(\X)(\sg^\top)^\dagger\widetilde{E}+(S^\top)^\dagger\widehat{E}\dcf(g(\X))-(S^\top)^\dagger\widetilde{E}\widehat{E},\\
\widetilde{E}&=\dcf(g(\X))-\dcfcircg(\X),\\
\widehat{E}&=\dcg(\X)(\sg^\top)^\dagger-\Id.
\end{align*}
\end{prop}
\begin{proof}
We have
\begin{align*}
\nc (f\circ g)(\X)&=(S^\top)^\dagger\dcfcircg(\X)\\
&=(S^\top)^\dagger\big(\dcg(\X)(\sg^\top)^\dagger-\widehat{E}\big)\dcfcircg(\X).
\end{align*}Thus,
\begin{equation*}
\nc(f\circ g)(\X)=(S^\top)^\dagger\big(\dcg(\X)(\sg^\top)^\dagger-\widehat{E}\big)\big(\dcf(g(\X))-\widetilde{E}\big).
\end{equation*}
Expanding the left-hand side, we obtain
\small\begin{align*}
\nc (f\circ g)(\X)&=(S^\top)^\dagger\left[\dcg(\X)(\sg^\top)^\dagger\dcf (g(\X))-\dcg(\X)(\sg^\top)^\dagger\widetilde{E}-\widehat{E}\dcf(g(\X))+\widetilde{E}\widehat{E}\right]\\
&=\jcg(\X)^\top\nc f(g(\X))-(S^\top)^\dagger\dcg(\X)(\sg^\top)^\dagger\widetilde{E}-(S^\top)^\dagger\widehat{E}\dcf(g(\X))+(S^\top)^\dagger\widetilde{E}\widehat{E}\\
&=\jcg(\X)^\top\nc f(g(\X))-E.\qedhere
\end{align*}\normalsize
\end{proof}

\section{The generalized centred simplex calculus gradient} \label{sec:centredsimplexcalculusgradient}

In the previous section, we developed calculus rules for the GCSG that involve basic calculus rules plus a term $E$.  In this section, we see that we can eliminate the $E$ terms in all the calculus rules to create new gradient approximation techniques.  The error bounds for these new techniques remain $O(\Delta^2)$. We name these techniques the \emph{generalized centred simplex calculus gradient (GCSCG)}.

Table \ref{tab1} below summarizes the calculus results of Section \ref{sec:calc}.
\begin{table}[H]
\caption{Calculus rules for the GCSG}\label{tab1}
\begin{tabular}{|l||l|l|l|}\hline
Rule&Formula&$E^c$&$E^s$\\\hline
\scriptsize\pbox{2cm}{Product\\$fg$}&\scriptsize $f(x^0)\nc g+g(x^0)\nc f+\ecfg$&\scriptsize $\frac{1}{2}\left(\esfg(\X)+\esfg(\X^-)\right)$&\scriptsize $(S^\top)^\dagger\delta^s_{f|g}$\\\hline
\scriptsize\pbox{2cm}{Product\\ $f_1\Compactcdots f_k$}&\scriptsize $\sum\limits_{i=1}^k\prod\limits_{j\neq i}f_j(x^0)\nc f_i+\ecfonefk$&\scriptsize $\frac{1}{2}\left(\esfonefk(\X)+\esfonefk(\X^-)\right)$&\scriptsize $(S^\top)^\dagger\left(\dsfonefk-\sum\limits_{i=1}^k\prod\limits_{j\neq i}f_j(x^0)\dsf \right)$\\\hline
\scriptsize Power&\scriptsize $kf^{k-1}(x^0)\nc f+\ecfk$&\scriptsize $\frac{1}{2}\left(\esfk(\X)+\esfk (\X^-)\right)$&\scriptsize$(S^\top)^\dagger\left(\sum\limits_{i-1}^{k-1}f^{k-1-i}(x^0)\delta_{f|f^{-i}}^s\right)$ \\\hline
\scriptsize Quotient&\scriptsize $\frac{g(x^0)\nc f-f(x^0)\nc g}{g^2(x^0)}-\ecfoverg$&\scriptsize $\frac{1}{2}\left(\esfoverg(\X)+\esfoverg (\X^-)\right)$&\scriptsize$\frac{(S^\top)^\dagger}{g(x^0)}\delta_{\frac{f}{g}|g}^s$ \\\hline
\scriptsize\pbox{2cm}{Negative\\power}&\scriptsize$-kf^{-k-1}(x^0)\nc f-\ecfminusk$&\scriptsize$\frac{1}{2}\left(\esfminusk(\X)+\esfminusk (\X^-)\right)$&\scriptsize$\frac{(S^\top)^\dagger}{f^k(x^0)}\left(k\delta_{\frac{1}{f}|f}^s-\sum\limits_{i=1}^{k-1}f^{1+i}(x^0)\delta_{f^{-1}|f^{-i}}^s\right)$\\\hline
\scriptsize Chain&\scriptsize $(\jcg)^\top\nc f(g(\X))-\ecfcircg$&\scriptsize\pbox{4cm}{$(S^\top)^\dagger\dcg (\X)(\sg^\top)^\dagger\widetilde{E}+$\\$(S^\top)^\dagger\widehat{E}\dcf (g(\X))-(S^\top)^\dagger\widetilde{E}\widehat{E}$} &\scriptsize$(S^\top)^\dagger\left(\sg^\top(\sg^\top)^\dagger-\Id\right)\dsf (g(\X))$ \\\hline
\end{tabular}
\end{table}
\noindent We introduce the notation $\ncc$ to represent the GCSCG. In the sequel, we formalize the formulae.
\begin{df}[GCSCG]Let $f:\dom(f) \subseteq \R^n\to\R, g: \dom(g)\subseteq \R^n \to \R$ and let $\X=\langle x^0,x^0+d^1,\ldots,x^0+d^m\rangle$ be an ordered set such that $\X \cup \X^-$ is in $\dom(f) \cap \dom(g)$.
The GCSCG of $fg$ over $\X$ is
\begin{equation}\label{eq:cc1}\ncc (fg)(\X)=f(x^0)\nc g(\X)+g(x^0)\nc f(\X).\end{equation}
Let $f_i:\R^n\to\R$ for all $i\in\{1,\ldots,k\}$, $k\geq 2,$ and let $\X$ be an ordered set  such that $\X \cup \X^-$ is in $\dom(f_i)$ for all $i$. The GCSCG of $f_1\cdots f_k$ over $\X$ is
\begin{equation}\label{eq:cc2}\ncc (f_1\cdots f_k)(\X)=\sum\limits_{i=1}^k\prod\limits_{j\neq i}f_j(x^0)\nc f_i(\X).\end{equation}
The GCSCG of $f^k$ over $\X$ is
\begin{equation}\label{eq:cc3}\ncc f^k(\X)=kf^{k-1}(x^0)\nc f(\X),\end{equation}where $f(x^0)$ is nonzero whenever $k-1<0$.\medskip\\
Let $g(x^0)\neq0$. The GCSCG of $\frac{f}{g}$ over $\X$ is
\begin{equation}\label{eq:cc4}\ncc \left(\frac{f}{g}\right)(\X)=\frac{g(x^0)\nc f(\X)-f(x^0)\nc  g(\X)}{g^2(x^0)}.\end{equation}
Let $a\in (0, \infty)$. The GCSCG of $a^f$ over $\X$ is
\begin{equation}\label{eq:cc6}\ncc a^{f(\X)}=a^{f(x^0)}\nc f(\X)\ln a.\end{equation}
Let $f(x^0)\neq0$ and $a\in (0, \infty)$. The GCSCG of $\log_af$ over $\X$ is
\begin{equation}\label{eq:cc7}\ncc \log_af(\X)=\frac{1}{f(x^0)\ln a}\nc f(\X).\end{equation}
Let $f:\dom(f) \subseteq \R^p\to\R$ and $g:\dom(g)\subseteq\R^n\to\R^p$. Let $\X$ be an ordered set such that $\X \cup \X^-$ is in $\dom(g)$ and $g(\X) \cup g(\X)^-$ is in $\dom(f).$ The GCSCG of $f\circ g$ over $\X$ is
\begin{equation}\label{eq:cc5}\ncc (f\circ g)(\X)=\jcg (\X)^\top\nc f(g(\X)).\end{equation}
\end{df}
We point out that the GCSCG is less restrictive than the GCSG. For instance, \eqref{eq:cc3} only requires $f(x^0)$ to be nonzero when $k-1<0$, which is not sufficient in Corollary \ref{cor:gcsgpowerneg}. The quotient rule presented in \eqref{eq:cc4} requires only $g(x^0)$ to be nonzero, whereas Proposition \ref{prop:gcsgquotient} requires all of $g(x^0), g(x^0\pm d^1), \dots, g(x^0\pm d^m)$ to be nonzero. Lastly, the GCSG $\nc\ln f(\X)$ requires $f$ to be positive for all points in $\X$ and $\X^-$, so that $\delta_{\ln f}^c(\X)$ is well-defined. However, only $f(x^0)$ must be nonzero in \eqref{eq:cc7} and $f$ is not restricted at any other point in $\X$ or $\X^-$.\par The preceding seven equations of approximate gradients are summarized in Table \ref{tab2} below for quick reference.
\begin{table}[H]\centering
\caption{Calculus rules for the GCSCG}\label{tab2}
\begin{tabular}{|l||l l|}\hline
Rule&Formula $\ncc$&\\\hline
Product $fg$&$f(x^0)\nc g(\X)+g(x^0)\nc f(\X)$&\eqref{eq:cc1}\\\hline
Product $f_1\Compactcdots f_k$&$\sum\limits_{i=1}^k\prod\limits_{j\neq i}f_j(x^0)\nc f_i(\X)$&\eqref{eq:cc2}\\\hline
Power&$kf^{k-1}(x^0)\nc f(\X)$&\eqref{eq:cc3}\\\hline
Quotient&$\frac{g(x^0)\nc f(\X)-f(x^0)\nc g(\X)}{g^2(x^0)}$&\eqref{eq:cc4}\\\hline
Exponential&$a^{f(x^0)}\nc f(\X)\ln a$&\eqref{eq:cc6}\\\hline
Logarithmic&$\frac{1}{f(x^0)\ln a}\nc f(\X)$&\eqref{eq:cc7}\\\hline
Chain&$\jcg (\X)^\top\nc f(g(\X))$&\eqref{eq:cc5}\\\hline
\end{tabular}
\end{table}
\noindent The next step is to show that GCSCG has controlled error.

\subsection{Error bounds for the GCSCG}

In this section, we demonstrate that the GCSCG is a valid approximation method, in the sense that we can define an error bound between the approximations and the true values of the gradients at $x^0$. Furthermore, we show that the error bounds are all $O(\Delta^2)$. We provide some examples along the way, to show the accuracy gain that can be made by using the GCSCG. The four propositions below follow from applying Theorems \ref{thm:det} and \ref{thm:under} to the appropriate results from Section \ref{sec:calc}. We provide the proof for Proposition \ref{prop:nccfgerrorbound} as a demonstration and omit proofs for the other three results. In the following propositions, we  use $\uu=\Span S \subseteq \R^n.$ Note that if $S$ has full row rank, then $\uu=\R^n$ and $f_\uu=f.$

\begin{prop}[$\ncc (fg)$ error bound] \label{prop:nccfgerrorbound}
 Let $f:\dom(f) \subseteq \R^n\to\R, g:\dom(g) \subseteq \R^n \to \R$ be $\mathcal{C}^{3}$ on $B(x^0, \overline{\Delta})$ and denote by $L_f$ and $L_g$ the Lipschitz constants  of $\nabla^2 f$ and $\nabla^2 g$.
Let $\X=\langle x^0, x^1, \ldots, x^m \rangle$ be an ordered set  with radius $\Delta<\overline{\Delta}$ such that $S$ has full rank. Let $\uu=\Span S$. Then
\begin{equation*}
\|\ncc (fg)(\X)-\nabla(fg)_{\uu}(x^0)\|\leq\frac{\sqrt m}{6}\big(L_g|f(x^0)|+L_f|g(x^0)|\big)\big\|(\widehat{S}^\top)^\dagger\big\|\Delta^2.
\end{equation*}
\end{prop}
\begin{proof}
Note  that $f(x^i)=f_{\uu}(x^i)$ and $g(x^i)=g_{\uu}(x^i)$ for all $i \in \{0, 1, \ldots, m\}.$ We have
\begin{align*}
&\|\ncc(fg)(\X)-\nabla(fg)_{\uu}(x^0)\|\\
=&\|f(x^0)\nc g(\X)+g(x^0)\nc f(\X)-f_{\uu}(x^0)\nabla g_{\uu}(x^0)-g_{\uu}(x^0)\nabla f_{\uu}(x^0)\|\\
\leq&|f(x^0)|\|\nc g(\X)-\nabla g_{\uu}(x^0)\|+|g(x^0)|\|\nc f(\X)-\nabla f_\uu(x^0)\|\\
\leq&\frac{\sqrt m}{6}\left(L_g|f(x^0)|+L_f|g(x^0)|\right)\big\|(\widehat{S}^\top)^\dagger\big\|\Delta^2
\end{align*}
by Theorem \ref{thm:det} or Theorem \ref{thm:under} as appropriate.
\end{proof}
\begin{prop}[$\ncc (f_1\Compactcdots f_k)$ error bound]\label{prop:ccproduct}
Let $f_i:\dom(f_i) \subseteq \R^n\to\R$ be $\mathcal{C}^{3}$ on $B(x^0, \overline{\Delta})$ and denote by $L_i$ the Lipschitz constants  of $\nabla^2 f_i$ for each $i$.
Let $\X=\langle x^0, x^1, \ldots, x^m \rangle$ be an ordered set with radius $\Delta<\overline{\Delta}$ such that $S$ has full rank. Let $\uu= \Span S.$  Then
\begin{equation*}\|\ncc (f_1\Compactcdots f_k)(\X)-\nabla(f_1\Compactcdots f_k)_\uu(x^0)\|\leq\frac{\sqrt m}{6}\sum\limits_{i=1}^k\prod\limits_{j\neq i}|f_j(x^0)|L_i\big\|(\widehat{S}^\top)^\dagger\big\|\Delta^2.\end{equation*}
\end{prop}
\noindent In some situations, the error bound above is zero. Corollary \ref{cor:ccproduct} below gives sufficient conditions for the GCSCG $\nabla_{cc}(f_1\Compactcdots f_k)$ to be perfectly accurate.
\begin{cor}\label{cor:ccproduct}Let the assumptions of Proposition \ref{prop:ccproduct} hold. If any of the following holds:
\begin{itemize}
\item[(a)]$f_i(x^0)=f_j(x^0)=0$ for some $i,j\in\{1,\ldots,k\}, i\neq j$;
\item[(b)]$f_i$ is a polynomial of order less than three for all $i\in\{1,\ldots,k\}$;
\item[(c)]$f_i$ is a polynomial of order less than three and $f_i(x^0)=0$ for some $i\in\{1,\ldots,k\}$,
\end{itemize}then
\begin{equation*}
\ncc (f_1\Compactcdots f_k)(\X)=\nabla(f_1\Compactcdots f_k)_\uu(x^0).
\end{equation*}
\end{cor}
\noindent When $S$ has full  rank,  Corollary \ref{cor:ccproduct} tells us that if just one of the $k$ functions is linear or quadratic and is equal to zero at $x^0$, then $\ncc (f_1\Compactcdots f_k)(\X)$ is equal to $\nabla (f_1\Compactcdots f_k)_\uu(x^0),$ regardless of the nature of the other $k-1$ functions. The same result is obtained if just two of the $k$ functions are equal to zero at $x^0$, no matter the form of the other functions.

\begin{prop}[$\ncc f^k$ error bound]\label{prop:power}
Let $f:\dom(f) \subseteq \R^n\to\R$ be $\mathcal{C}^3$  on $B(x^0, \overline{\Delta})$ and denote by $L$ the  Lipschitz constant of $\nabla^2 f$.  Let $f(x^0)\neq0$ whenever $k-1<0$.
Let $\X=\langle x^0, x^1, \ldots, x^m \rangle$ be an ordered set with radius $\Delta<\overline{\Delta}$ such that $S$ has full rank. Let $\uu=\Span S$ and $k \in \R$. Then
\begin{equation*}
\|\ncc (f^k)(\X)-\nabla (f^k)_\uu(x^0)\|\leq\frac{L\sqrt m}{6}|k||f(x^0)|^{k-1}\big\|(\widehat{S}^\top)^\dagger\big\|\Delta^2.
\end{equation*}
\end{prop}
\begin{prop}[$\ncc \left(\frac{f}{g}\right)$ error bound]\label{prop:quotient}
Let $f:\dom(f) \subseteq \R^n\to\R, g:\dom(g)\subseteq \R^n \to \R$ be $\mathcal{C}^{3}$ on $B(x^0,\overline{\Delta})$  and denote by  $L_f, L_g$ the Lipschitz constants of $\nabla^2 f, \nabla^2 g$ respectively.
Let $\X=\langle x^0, x^1, \ldots, x^m \rangle$ be an ordered set with radius $\Delta<\overline{\Delta}$ such that $S$ has full rank. Let $\uu=\Span S$.  Assume $g(x^0)\neq0$. Then
\begin{equation*}
\left\|\ncc \left(\frac{f}{g}\right)(\X)-\nabla\left(\frac{f}{g}\right)_\uu(x^0)\right\|\leq\frac{\sqrt m}{6}\left(L_f\left|\frac{1}{g(x^0)}\right|+L_g\left|\frac{f(x^0)}{g^2(x^0)}\right|\right)\big\|(\widehat{S}^\top)^\dagger\big\|\Delta^2.
\end{equation*}
\end{prop}
The error bound involving the chain rule ($\ncc (f\circ g)$) requires new techniques, so we include the proof of Proposition \ref{prop:cccomp}.
\begin{prop}[error bound for $\ncc (f\circ g)$]\label{prop:cccomp}
Let $g:\dom(g) \subseteq \R^n \to \R^p$,  $f: \dom(f) \subseteq \R^p \to \R$  be $\mathcal{C}^{3}$ on  $B(g(x^0),\overline{\Delta}_g)$ and $B(x^0,\overline{\Delta})$ respectively  and denote by $L_{\nabla^2 f} , L_{\nabla^2 g}$ the Lipschitz constants of  $\nabla^2 f$ and $\nabla^2 g$. Denote by $L_{g_i}$ the Lipschitz constant of $g_i$ on  $B(x^0,\overline{\Delta})$ for each  $i \in \{1,2, \dots, p\}.$ Let $\X=\langle x^0, x^1, \ldots, x^m \rangle$ be an ordered set with radius $\Delta<\overline{\Delta}$ and let $g(\X)=\langle g(x^0), g(x^1), \ldots, g(x^m) \rangle$ be an ordered set with radius $\Delta_g<\overline{\Delta}_g$. Assume that $S$ and $\sg$ have full rank. Let $\uu=\Span S \subseteq \R^n$ and $\vv= \Span \sg \subseteq \R^p.$  Then
\footnotesize\begin{equation*}
\|\ncc (f\circ g)(\X)-\nabla(f\circ g)_\uu (x^0)\|\leq \frac{\sqrt{m}\;p}{6}\big(\sqrt{m} \; L_{g_*} \;L_{\nabla^2 f}\big\|(\widehat{S}_g^\top)^\dagger\big\|+ \Vert \nabla f(g(x^0)) \Vert  L_{\nabla^2 g_*} \big)\big\|(\widehat{S}^\top)^\dagger\big\|\Delta^2_{*},\\
\end{equation*}\normalsize
where
\begin{align*}
\Delta_{*}&= \max\left \{ \Delta, \Delta_g \right\},\\
L_{g_{*}}&= \max \{L_{ g_i}: i=1, \dots, p\},\\
 L_{ \nabla^2 g_{*}}&= \max \{L_{\nabla^2 g_i}: i=1, \dots, p\}.
 \end{align*}
\end{prop}
\begin{proof}
We have
\begin{align*}
\Vert  \ncc (f \circ g)(\X)-\nabla(f\circ g)_\uu(x^0)\Vert&=\Vert \cjt \nc f(g(\X)) - \jtw \nabla f_\vv \left ( g_\uu \left ( x^0\right ) \right )\Vert.
\end{align*}
Note that $g_\uu(x^0)=g(x^0+\Proj_\uu(x^0-x^0))=g(x^0).$ We obtain
\begin{align*}
&\Vert  \ncc (f \circ g)(\X)-\nabla(f\circ g)_\uu(x^0)\Vert\\
=&\Vert \cjt \nc f(g(\X)) - \jtw \nabla f_\vv \left ( g \left ( x^0\right ) \right )\Vert\\
=&\Vert \cjt \cgfy - \cjt \gradfvg\\
\quad&+\cjt \gradfvg - \jtw \nabla f_{\vv} \left ( g\left ( x^0\right ) \right )\Vert\\
\leq&\Vert \cjt \Vert \Vert \cgfy -\gradfvg \Vert + \Vert \gradfvg \Vert \Vert \left ( \cj- \jacw \right )^\top \Vert.
\end{align*}
Let us find a bound for $\Vert \cgfy-\gradfvg \Vert.$ If $\sg$ has full column rank, then
\begin{align*}
\Vert \cgfy-\gradfvg \Vert &\leq \frac{\sqrt{m}}{6} L_{\nabla^2 f}\big\|(\widehat{S}_g^\top)^\dagger\big\|\Delta^2_g
\end{align*}
by Theorem \ref{thm:under}. If $\sg$ has full row rank, then
\begin{align*}
    \gradfvg&=\Proj_\vv \nabla f (g(x^0))\\
    &=(\sg^\top)^\dagger \sg^\top \nabla f (g(x^0))\\
    &=\nabla f (g(x^0)).
\end{align*}
Hence
\begin{align*}
    \Vert \cgfy-\gradfvg \Vert &= \Vert \cgfy -\nabla f (g(x^0)) \Vert\\
    &\leq \frac{\sqrt{m}}{6} L_{\nabla^2 f}\big\|(\widehat{S}_g^\top)^\dagger\big\|\Delta^2_g
\end{align*}
by Theorem \ref{thm:det}. Next we find a bound for $\Vert \left (\cj-\jacw \right )^\top \Vert.$ We have
\begin{align*}
\Vert \left (\cj-\jacw \right )^\top \Vert &= \left \Vert \begin{bmatrix}\left (\nc g_1(\X)-\nabla (g_1)_{\uu}(x^0) \right )^\top\\ \vdots \\ \left ( \nc g_p(\X) -\nabla (g_p)_{\uu} (x^0) \right )^\top \end{bmatrix}^\top \right \Vert\\
&\leq \Vert \nc g_1(\X)-\nabla (g_1)_{\uu}(x^0) \Vert + \dots + \Vert \nc g_p(\X)-\nabla (g_p)_{\uu} (x^0) \Vert.\\
\end{align*}
If $S$ has full row rank, then $\nabla (g_i){_\uu}(x^0)=\nabla (g_i)(x^0)$ for all $i \in \{1, 2, \dots, p\}.$ By Theorem \ref{thm:det}, we obtain
\begin{align}
    &\Vert \nc g_1(\X)-\nabla (g_1)_{\uu}(x^0) \Vert + \dots + \Vert \nc g_p(\X)-\nabla (g_p)_{\uu} (x^0) \Vert \notag\\
    &\leq  \frac{\sqrt{m}}{6} \Delta\big\|(\widehat{S}^\top)^\dagger\big\|\left ( L_{\nabla^2 g_1} +\dots +L_{\nabla^2 g_p} \right ) \notag\\
    &\leq \frac{\sqrt{m}\;p}{6} L_{ \nabla^2 g_*}\big\|(\widehat{S}^\top)^\dagger\big\|\Delta^2. \label{eq:bound}
\end{align}
If $S$ has full column rank, then \eqref{eq:bound} is obtained by Theorem \ref{thm:under}. Finally, let us find a bound for  $\Vert \cjt \Vert$. We have
\begin{align*}
    \Vert \cjt \Vert&=\left \Vert \begin{bmatrix}\nc g_1(\X)^\top\\ \vdots \\ \nc g_p(\X)^\top \end{bmatrix}^\top \right \Vert\\
&\leq \Vert \nc g_1(\X) \Vert + \dots + \Vert \nc g_p(\X)\Vert\\
&\leq \big\|(\widehat{S}^\top)^\dagger\big\|\left \Vert \frac{\delta^c_{g_1}(\X)}{\Delta} \right \Vert+ \dots +  \big\|(\widehat{S}^\top)^\dagger\big\|\left \Vert \frac{\delta^c_{g_p}(\X)}{\Delta} \right \Vert\\
&\leq\big\|(\widehat{S}^\top)^\dagger\big\|\sqrt{m} \; L_{g_1}+ \dots +\big\|(\widehat{S}^\top)^\dagger\big\|\sqrt{m} \; L_{g_p}\\
&\leq \sqrt{m}\;p \; L_{g_*}\big\|(\widehat{S}^\top)^\dagger\big\|.
\end{align*}
All together,
\begin{align*}
&\Vert \nc (f \circ g)(\X)-\nabla(f\circ g)_\uu(x^0)\Vert\\
\leq&\sqrt{m}\;p \; L_{ g_*}\big\|(\widehat{S}^\top)^\dagger\big\|\frac{\sqrt{m}}{6} L_{\nabla^2 f}\big\|(\widehat{S}_g^\top)^\dagger\big\|\Delta_g^2+ \Vert \nabla f_{\vv}(g(x^0)) \Vert \frac{\sqrt{m}\;p}{6} L_{ \nabla^2 g_*} \big\|(\widehat{S}^\top)^\dagger\big\|\Delta^2\\
\leq&\frac{\sqrt{m}\;p}{6}\big(\sqrt{m} \; L_{g_*} \;L_{\nabla^2 f}\big\|(\widehat{S}_g^\top)^\dagger\big\|+ \Vert \nabla f_{\vv}(g(x^0)) \Vert  L_{\nabla^2 g_*} \big)\big\|(\widehat{S}^\top)^\dagger\big\|\Delta^2_{*}.
\end{align*}
Since $\Vert \nabla f_{\vv}(g(x^0)) \Vert \leq \Vert \nabla f (g(x^0)) \Vert,$ we obtain the final result. \qedhere

\end{proof}
\noindent Analysing the error bound of Proposition \ref{prop:cccomp}, we find two cases where it is zero. Corollary \ref{cor:cccomp} presents these cases.
\begin{cor}\label{cor:cccomp}
Let the assumptions of Proposition \ref{prop:cccomp} hold. If either of the following holds:
\begin{itemize}
\item[(a)]$g$ is a constant function;
\item[(b)]$f$ and $g$ are polynomials of order less than three,
\end{itemize}then
\begin{equation*}
\ncc (f\circ g)(\X)=\nabla(f\circ g)_\uu(x^0).
\end{equation*}
\end{cor}
\begin{ex}
Consider $f:\R\to\R:y\mapsto y^2$, $g:\R\to\R:y\mapsto y^2+1$ and $\X=\langle2,3\rangle$. We compute the absolute error for $\ncc (f \circ g)(\X)$ and the value of $\nc (f \circ g)(\X).$ Note that $S$ and $\sg$ have full row rank. Hence, $\nabla (f \circ g)_\uu (x^0)=\nabla (f \circ g)(x^0).$ We have
\begin{align*}
\ncc (f\circ g)(\X)&=\jcg (\X)^\top\nc f(g(\X))\\
&=(S^\top)^\dagger\dcg (\X)(\sg^\top)^\dagger\dcf (g(\X))\\
&=1\cdot\frac{1}{2}(10-2)\frac{1}{5}\cdot\frac{1}{2}(100-0)\\
&=40
\end{align*}and the true derivative $\nabla (f \circ g)(x^0)$ is
\begin{equation*}
\frac{d}{dy}(y^2+1)^2\Big\vert_{y=2}=40.
\end{equation*}
Therefore, the absolute error $\| \ncc (f \circ g)(\X)-\nabla (f \circ g)(\X)\|=0.$ The error bound in Proposition \ref{prop:cccomp} is also equal to zero since $f$ and $g$ are quadratic functions. The GCSG $\nc(f\circ g)(\X)$ does not return the exact value of the derivative. Indeed, we have
\begin{align*}
\nc(f\circ g)(\X)&=(S^\top)^\dagger\dcfcircg(\X)\\
&=1\cdot\frac{1}{2}(9+1)^2-(1+1)^2)=48.
\end{align*}
\end{ex}

The next example demonstrates Corollary \ref{cor:cccomp}.

\begin{ex}
Consider $f:\R^3 \to \R:y \mapsto \alpha(y_1^2+y_2^2+y_3^2),$ $\alpha \in \R,$  $g:\R^3 \to \R^2:y \mapsto \bbm y_2-2y_1&y_1+y_2&y_1y_2+y_2\ebm^\top$ and the sample set $\X=\left \langle \bbm 1\\2\ebm, \bbm 2\\2 \ebm, \bbm 1\\3 \ebm\right \rangle.$ We compute the absolute error for $\ncc (f \circ g)(\X).$ Note that $g(\X)=\left \langle \bbm 0\\3\\4\ebm, \bbm -2\\4\\6\ebm, \bbm 1\\4\\6\ebm\right \rangle$ and
\begin{align*}
    S&=\bbm 1&0\\0&1 \ebm, \quad \sg=\bbm -2&1\\1&1\\2&2\ebm.
\end{align*}
We see that $S$ has full row rank and $\sg$ has full column rank, so $\nabla (f \circ g)_\uu(x^0)=\nabla (f \circ g)(x^0)$. We obtain
\begin{align*}
    \ncc (f \circ g)(\X)&=(\jcg(\X))^\top \nc f(g(\X))\\
    &=\bbm -2&1&2\\1&1&2\ebm\bbm 0\\ 4.4\alpha \\8.8\alpha \ebm\\
    &=\alpha\bbm 22\\22\ebm,
\end{align*}
and
\begin{align*}
    \nabla (f \circ g)(x^0)&=(\jac)^\top \nabla f(g(x^0))\\
    &=\bbm -2&1&2\\1&1&2\ebm \bbm 0\\ 6\alpha \\ 8\alpha \ebm\\
    &=\alpha \bbm 22\\ 22\ebm.
\end{align*}
Therefore, the absolute error is
\begin{align*}
\|\ncc (f\circ g)(\X)-\nabla(f\circ g)_\uu(x^0)\|&=\|\ncc (f\circ g)(\X)-\nabla(f\circ g)(x^0)\|=0.
\end{align*}
The error bound in Proposition \ref{prop:cccomp} is also equal to zero since $f$ and $g$ are quadratic functions.
\end{ex}
The next two propositions are proved using the same technique as Proposition \ref{prop:nccfgerrorbound}.
\begin{prop}[$\ncc a^f$ error bound]\label{prop:ccexp}
Let $f:\dom(f)\subseteq \R^n\to\R$ be $\mathcal{C}^{3}$ on $B(x^0,\overline{\Delta})$ and denote by $L$ the Lipschitz constant of $\nabla^2 f.$
Let $\X=\langle x^0, x^1, \ldots, x^m \rangle$ be an ordered set  with radius  $\Delta<\overline{\Delta}$ such that $S$ has full rank. Let $\uu=\Span S$ and $a>0$. Then
\begin{equation*}
\big\|\ncc a^{f(\X)}-\nabla a^{f_\uu(x^0)}\big\|\leq\big|a^{f(x^0)}\ln a\big|\frac{L\sqrt m}{6}\big\|(\widehat{S}^\top)^\dagger\big\|\Delta^2.
\end{equation*}
\end{prop}
\noindent Examining the error bounds of Proposition \ref{prop:ccexp}, we see that it is zero whenever $L=0$. This is the case when $f$ is a polynomial of order less than three. The following examples illustrate this for both cases.
\begin{ex}
Consider $f:\R^2\to\R:y\mapsto y_1^2+y_2^2$ and $\X=\left\langle\left[\begin{array}{c}1\\1\end{array}\right],\left[\begin{array}{c}2\\1\end{array}\right],\left[\begin{array}{c}1\\2\end{array}\right]\right\rangle$. We compute the absolute error for $\ncc e^{f(\X)}$ and the value of $\nc e^f(\X).$ Note that $S$ has full row rank, hence, $\nabla e^{f_\uu(x^0)}=\nabla e^{f(x^0)}.$ We have
\begin{align*}
\ncc e^{f(\X)}&=e^{f(x^0)}\nc f(\X)\\
&=e^2(S(\X)^\top)^\dagger\delta_f^c(\X)\\
&=e^2\left[\begin{array}{c c}1&0\\0&1\end{array}\right]\frac{1}{2}\left[\begin{array}{c}5-1\\5-1\end{array}\right]\\
&=\left[\begin{array}{c}2e^2\\2e^2\end{array}\right]\approx\left[\begin{array}{c}14.78\\14.78\end{array}\right],
\end{align*}
and
\begin{align*}
\nabla e^{f(x^0)}&=\nabla e^{y_1^2+y_2^2}=[2e^2~~2e^2]^\top.
\end{align*}
So the absolute error is equal to zero. The error bound in Proposition \ref{prop:ccexp} is also equal to zero since $f$ is a quadratic function. Also,
\begin{align*}
\nc e^{f(\X)}&=\left(\widehat{S}^\top\right)^\dagger\delta_{e^f}^c(\X)\\
&=\left[\begin{array}{c c}1&0\\0&1\end{array}\right]\frac{1}{2}\left[\begin{array}{c}e^5-e^1\\e^5-e^1\end{array}\right]\approx\left[\begin{array}{c}72.85\\72.85\end{array}\right].
\end{align*}
\end{ex}
\begin{ex}
Consider $f:\R^2\to\R:y\mapsto y_1^2+y_2^2$ and $\X=\left\langle\left[\begin{array}{c}1\\1\end{array}\right],\left[\begin{array}{c}2\\1\end{array}\right] \right\rangle$. We compute the absolute error for $\ncc e^{f(\X)}.$ Note that $S$ has full column rank. We obtain
\begin{align*}
\ncc e^{f(\X)}&=e^{f(x^0)}\nc f(\X)\\
&=\begin{bmatrix}2e^2\\0\end{bmatrix}
\end{align*}
Also,
\begin{align*}
    \nabla e^{f_\uu (x_0)}&=e^{f_\uu(x^0)}\nabla f_\uu(\X)\\
    &=e^{f(x^0)} \Proj_\uu \nabla f(x_0)\\
    &=e^2 \bbm 1&0\ebm^\dagger \bbm1&0 \ebm \bbm 2\\2\ebm=\bbm 2e^2\\0\ebm,
\end{align*}
so the absolute error is
\begin{equation*}
\left\|\ncc e^{f(\X)}-\nabla e^{f_\uu(x^0)}\right\|=0.
\end{equation*}
The error bound in Proposition \ref{prop:ccexp} is also zero since $f$ is a quadratic function.
\end{ex}
\begin{prop}[$\ncc \log_af(\X)$ error bound]\label{prop:cclog}
 Let $f:\dom(f) \subseteq \R^n\to\R$ be $\mathcal{C}^{3}$ on $B(x^0, \overline{\Delta})$  with $f(x^0)\neq0$, and denote by $L$ the Lipschitz constant  of $\nabla^2 f$ on $B(x^0, \overline{\Delta}).$ Let $\X=\langle x^0, x^1, \ldots, x^m \rangle $ be an ordered set with radius $\Delta<\overline{\Delta}$ such that $S$ has full rank. Let $\uu=\Span S$ and $a>0$. Then
\begin{equation*}
\|\ncc \log_af(\X)-\nabla\log_af_\uu(x^0)\| \leq \left|\frac{1}{f(x^0)\ln a}\right|\frac{L\sqrt m}{6}\big\|(\widehat{S}^\top)^\dagger\big\|\Delta^2.
\end{equation*}
\end{prop}
\noindent Examining the error bounds of Proposition \ref{prop:cclog}, we see that it is zero whenever $f$ is a polynomial of order less than three. The example below illustrates this situation.
\begin{ex}
Consider $f:\R^2\to\R:y\mapsto y_1^2+2y_2^2-3$ and $\X=\left\langle\left[\begin{array}{c}2\\2\end{array}\right],\left[\begin{array}{c}3\\2\end{array}\right],\left[\begin{array}{c}2\\3\end{array}\right]\right\rangle$. We compute the error bound for $\ncc \ln f(\X)$ and $\nc \ln f(\X).$  Note that $S$ has full row rank, so $\nabla \ln f_\uu (x^0)=\nabla \ln f(x^0).$ We have
\begin{align*}
\ncc \ln f(\X)&=\frac{1}{9}\left[\begin{array}{c c}1&0\\0&1\end{array}\right]\frac{1}{2}\left[\begin{array}{c}14-6\\19-3\end{array}\right]\\
&=\left[\begin{array}{c}\frac{4}{9}\\\frac{8}{9}\end{array}\right],
\end{align*}and the true gradient is
\begin{equation*}
\nabla\ln f(x^0)=\left[\begin{array}{c}\frac{1}{9}\cdot4\\\frac{1}{9}\cdot8\end{array}\right]=\left[\begin{array}{c}\frac{4}{9}\\\frac{8}{9}\end{array}\right].
\end{equation*}
Therefore, the absolute error is equal to zero. The error bound in Proposition \ref{prop:cclog} is also zero since $f$ is a quadratic function. The GCSG is
\begin{align*}
\nc \ln f(\X)&=\left[\begin{array}{c c}1&0\\0&1\end{array}\right]\frac{1}{2}\left[\begin{array}{c}\ln14-\ln6\\\ln19-\ln3\end{array}\right]\\
&\approx\left[\begin{array}{c}0.4236\\0.9229\end{array}\right].
\end{align*}
\end{ex}

\begin{comment}
\section{Numerical experiment} \label{sec:numericalexperiment}

In this section, we investigate the numerical accuracy of the GCSCG using the functions defined in \cite{more1981testing}. Four different gradient approximation techniques are employed for comparison: the GSG $\ns$, generalized simplex calculus gradient $\nabla^{sc}$, GCSG $\nc$ and GCSCG $\ncc$.\par First, we test the chain rule. We recall the definitions of these four gradient approximations for the composition $f\circ g$:
\begin{align*}
\ns (f\circ g)(\X)&=(S^\top)^\dagger\dsfcircg (\X),\\
\nabla^{sc}(f\circ g)(\X)&=\jsg(\X)^\top\ns f(g(\X)),\\
\nc (f\circ g)(\X)&=(S^\top)^\dagger\dcfcircg(\X),\\
\ncc (f\circ g)(\X)&=\jcg (\X)^\top\nc f(g(\X)).
\end{align*}
Second, we test the product rule. The four approximations for the product of $k$ functions are:
\begin{align*}
\ns (f_1\Compactcdots f_k)(\X)&=(S^\top)^\dagger\dsfonefk (\X),\\
\nabla^{sc}(f_1\Compactcdots f_k)(\X)&=\sum\limits_{i=1}^k\prod\limits_{j\neq i}f_j(x^0)\ns f_i(\X),\\
\nc (f_1\Compactcdots f_k)(\X)&=(S^\top)^\dagger \dcfonefk (\X),\\
\ncc (f_1\Compactcdots f_k)(\X)&=\sum\limits_{i=1}^k\prod\limits_{j\neq i}f_j(x^0)\nc f_i(\X).
\end{align*}
The sample set of points used on every problem is $\X=\langle x^0,x^0+e_1,\ldots,x^0+e_n\rangle$, where $x^0$ is the starting point defined in \cite{more1981testing}. The parameter $\beta$ is defined to be a real number in the interval $(0,1]$. The role of $\beta$ is to shrink the matrix $S=[e_1~~e_2~~\cdots~~e_n]$. Our goal is to determine the largest value of $\beta$ necessary to obtain a relative error less than $10^{-3}$. To achieve this goal, we do the following for all four gradient approximations.
\begin{enumerate}
\item Let $\beta=1$. Compute the approximate gradient and the resulting relative error. If the relative error is less than $10^{-3}$, stop and return $\beta=1$.
\item Compute the approximate gradient using $\beta\in\{10^{-1},10^{-2},\ldots,10^{-8}\}$ and the resulting relative errors, until a value is found that gives a relative error less than $10^{-3}$. If none of these values provides such a relative error, return {\tt error}.
\item Apply a bisection method with a tolerance of $10^{-7}$ to find the highest value of $\beta$ that returns a relative error less than $10^{-3}$.
\end{enumerate}
We present our findings in Tables \ref{tab3} and \ref{tab4}. In the tables, a number is boldfaced if no other method does better on that particular problem. A boldfaced and underlined number means that not only does no other method do better, but also the value of $\beta$ is at least one order of magnitude higher than the second-best method.\par Table \ref{tab3} displays our results regarding the chain rule. The outer function used is $f:\R^k\to\R:y\mapsto\sum_{i=1}^k\|y_1\|^2$. In the table, the dimension of the domain of the inner function $g$ is given by $n$ and the dimension of the codomain by $k$.
\begin{table}[H]\centering
\caption{Values of $\beta$ that obtain relative error $<10^{-3}$}\label{tab3}
\begin{tabular}{|l|l l|l|l|l|l|}\hline
Function&$n$&$k$&$\ns (f\circ g)$&$\nabla^{sc}(f\circ g)$&$\nc (f\circ g)$&$\ncc (f\circ g)$\\\hline\hline
1. Rosenbrock&2&2&3.46e-04&3.46e-04&2.20e-02&\textbf{\underline{1}}\\
2. Freudenstein&2&2&7.64e-04&7.64e-04&4.16e-02&\textbf{\underline{1.63e-01}}\\
3. PowellBS&2&2&2.00e-07&2.00e-07&\textbf{\underline{1}}&\textbf{\underline{1}}\\
4. BrownBS&2&3&\textbf{\underline{1}}&\textbf{\underline{1}}&\textbf{\underline{1}}&\textbf{\underline{1}}\\
5. Beale&2&3&8.10e-04&8.10e-04&\textbf{3.19e-2}&1.87e-02\\
6. Jenrich&2&4&5.38e-04&5.38e-04&9.56e-03&\textbf{\underline{2.27e-02}}\\
7. Helical&3&3&6.69e-03&6.69e-03&\textbf{\underline{6.65e-02}}&\textbf{\underline{6.65e-02}}\\
8. Bard&3&15&1.28e-03&1.28e-03&4.27e-02&\textbf{6.77e-02}\\
9. Gaussian&3&15&2.09e-06&2.09e-06&7.48e-03&\textbf{\underline{3.04e-01}}\\
10. Meyer&3&16&7.73e-05&7.73e-05&\textbf{\underline{1}}&\textbf{\underline{1}}\\
11. Gulf&3&20&4.72e-04&4.72e-04&8.01e-03&\textbf{\underline{1.11e-02}}\\
12. Box3D&3&3&2.37e-02&2.37e-02&\textbf{6.41e-01}&5.61e-01\\
13. PowellS&4&4&1.27e-03&1.27e-03&6.24e-02&\textbf{\underline{1}}\\
14. Wood&4&6&2.18e-03&2.18e-03&1.01e-01&\textbf{\underline{1}}\\
15. Kowalik&4&11&4.75e-05&4.75e-05&2.66e-02&\textbf{4.80e-02}\\
16. Brown&4&4&1.85e-02&1.85e-02&8.84e-01&\textbf{\underline{1}}\\
17. Osborne1&5&33&4.88e-06&4.88e-06&2.09e-04&\textbf{4.48e-04}\\
18. Biggs&6&6&7.78e-04&7.78e-04&1.30e-01&\textbf{4.42e-01}\\
19. Osborne2&11&65&2.50e-04&2.50e-04&\textbf{\underline{1.27e-02}}&6.45e-03\\
20. Watson&31&31&1.44e-04&1.44e-04&4.26e-02&\textbf{\underline{1}}\\
21. RosenbrockE&4&4&4.52e-04&4.52e-04&2.53e-02&\textbf{\underline{1}}\\
22. PowellExt&8&8&1.28e-03&1.28e-03&6.29e-02&\textbf{\underline{1}}\\
23. Penalty1&4&5&2.56e-03&2.56e-03&1.47e-01&\textbf{\underline{1}}\\
24. Penalty2&6&12&6.33e-04&6.33e-04&2.92e-02&\textbf{\underline{1}}\\
25. VariablyDim&7&9&2.31e-03&2.31e-03&1.05e-01&\textbf{\underline{1}}\\
26. Trigonometric&7&7&2.49e-04&2.49e-04&6.45e-03&\textbf{\underline{7.75e-02}}\\
27. BrownAlm&9&9&1.41e-01&1.41e-01&\textbf{\underline{1}}&\textbf{\underline{1}}\\
28. DiscreteBnd&5&5&9.47e-06&9.47e-06&1.56e-02&\textbf{\underline{2.65e-01}}\\
29. DiscreteInt&3&3&1.29e-04&1.29e-04&2.13e-02&\textbf{\underline{1.47e-01}}\\
30. BroydenTri&5&5&3.54e-04&3.54e-04&2.74e-02&\textbf{\underline{1}}\\
31. BroydenBan&8&8&4.73e-04&4.73e-04&2.05e-02&\textbf{6.68e-02}\\
32. LinearFR&10&13&4.00e-03&4.00e-03&\textbf{\underline{1}}&\textbf{\underline{1}}\\
33. LinearR1&10&10&1.35e-02&1.35e-02&\textbf{\underline{1}}&\textbf{\underline{1}}\\
34. LinearR1W0&10&10&1.19e-02&1.19e-02&\textbf{\underline{1}}&\textbf{\underline{1}}\\
35. Chebyquad&4&5&1.31e-04&1.31e-04&5.48e-03&\textbf{\underline{1}}\\\hline\hline
\textbf{Average}&4.8&9.7&3.53e-02&3.53e-02&2.74e-01&\textbf{6.08e-01}\\
\textbf{Median}&4&6&6.33e-04&6.33e-04&4.26e-02&\textbf{\underline{1}}\\\hline
\end{tabular}
\end{table}
\begin{table}[H]\centering
\caption{Values of $\beta$ that obtain relative error $<10^{-3}$}\label{tab4}
\begin{tabular}{|l|l l|l|l|l|l|}\hline
Function&$n$&$k$&$\ns (f_1\Compactcdots f_k)$&$\nabla^{sc}(f_1\Compactcdots f_k)$&$\nc(f_1\Compactcdots f_k)$&$\ncc (f_1\Compactcdots f_k)$\\\hline\hline
1. Rosenbrock&2&2&1.33e-03&2.79e-03&7.83e-02&\textbf{\underline{1}}\\
2. Freudenstein&2&2&6.83e-04&2.65e-04&1.75e-02&\textbf{4.03e-02}\\
3. PowellBS&2&2&3.68e-04&\textbf{\underline{1}}&2.71e-02&\textbf{\underline{1}}\\
4. BrownBS&2&3&9.99e-04&\textbf{\underline{1}}&\textbf{\underline{1}}&\textbf{\underline{1}}\\
5. Beale&2&3&6.81e-04&1.70e-03&2.72e-02&\textbf{8.42e-02}\\
6. Jenrich&2&4&2.75e-04&6.04e-04&1.68e-02&\textbf{2.25e-02}\\
7. Helical&3&3&5.00e-03&\textbf{\underline{1}}&\textbf{\underline{1}}&\textbf{\underline{1}}\\
8. Bard&3&15&1.97e-04&3.93e-03&7.65e-03&\textbf{\underline{8.51e-02}}\\
9. Gaussian&3&15&2.33e-07&1.90e-03&9.23e-06&\textbf{\underline{5.27e-02}}\\
10. Meyer&3&16&5.71e-06&\textbf{\underline{1}}&2.29e-04&\textbf{\underline{1}}\\
11. Gulf&3&3&1.87e-04&8.77e-04&1.04e-02&\textbf{1.10e-02}\\
12. Box3D&3&3&1.71e-02&3.01e-02&\textbf{6.91e-01}&5.96e-01\\
13. PowellS&4&4&1.18e-03&1.12e-03&3.30e-02&\textbf{\underline{1}}\\
14. Wood&4&6&2.86e-03&\textbf{\underline{1}}&2.00e-01&\textbf{\underline{1}}\\
15. Kowalik&4&11&3.49e-05&6.24e-04&9.03e-04&\textbf{\underline{1.69e-02}}\\
16. Brown&4&4&8.47e-03&4.04e-02&3.43e-01&\textbf{\underline{1}}\\
17. Osborne1&5&33&2.69e-07&1.39e-05&1.04e-05&\textbf{\underline{4.65e-04}}\\
18. Biggs&6&6&7.05e-05&8.23e-03&3.39e-03&\textbf{\underline{2.06e-01}}\\
19. Osborne2&11&65&7.59e-06&1.43e-03&3.28e-04&\textbf{\underline{3.81e-02}}\\
20. Watson&2&31&5.77e-03&\textbf{\underline{1}}&5.77e-03&\textbf{\underline{1}}\\
21. RosenbrockE&4&4&1.35e-03&2.83e-03&7.89e-02&\textbf{\underline{1}}\\
22. PowellExt&8&8&1.18e-03&1.12e-03&3.30e-02&\textbf{\underline{1}}\\
23. Penalty1&4&5&1.48e-02&\textbf{\underline{1}}&1.72e-01&\textbf{\underline{1}}\\
24. Penalty2&6&12&1.17e-03&2.20e-03&5.24e-02&\textbf{\underline{1}}\\
25. VariablyDim&7&9&3.01e-03&5.61e-02&1.20e-01&\textbf{\underline{1}}\\
26. Trigonometric&7&7&5.81e-05&8.79e-05&1.73e-03&\textbf{\underline{7.75e-02}}\\
27. BrownAlm&9&9&2.11e-02&\textbf{\underline{1}}&8.78e-01&\textbf{\underline{1}}\\
28. DiscreteBnd&5&5&2.16e-05&4.12e-02&8.26e-04&\textbf{\underline{4.36e-01}}\\
29. DiscreteInt&3&3&5.17e-04&5.00e-03&3.38e-02&\textbf{\underline{1.39e-01}}\\
30. BroydenTri&5&5&3.34e-04&2.27e-03&3.09e-02&\textbf{\underline{1}}\\
31. BroydenBan&8&8&6.19e-04&1.10e-03&2.30e-02&\textbf{6.68e-02}\\
32. LinearFR&10&13&8.65e-03&\textbf{\underline{1}}&6.29e-02&\textbf{\underline{1}}\\
33. LinearR1&10&10&1.50e-03&\textbf{\underline{1}}&5.90e-02&\textbf{\underline{1}}\\
34. LinearR1W0&10&10&1.70e-03&\textbf{\underline{1}}&6.81e-02&\textbf{\underline{1}}\\
35. Chebyquad&2&2&3.33e-04&\textbf{\underline{1}}&1.05e-02&\textbf{\underline{1}}\\\hline\hline
\textbf{Average}&4.8&9.7&2.90e-03&3.49e-01&1.45e-01&\textbf{6.24e-01}\\
\textbf{Median}&4&6&6.83e-04&5.00e-03&3.09e-02&\textbf{\underline{1}}\\\hline
\end{tabular}
\end{table}
\hilight{Interpret the tables.} \hilight{Explain why $\nabla_s$ and $\nabla_{sc}$ are identical for composition.}
\end{comment}
\section{Conclusion} \label{sec:conclusion}
Generalized centred simplex gradients provide a formula to approximate gradients regardless of the number of points in the sample set. In the underdetermined case, an error bound with order $O(\Delta^2)$ is defined by restricting the function to a subspace of $\R^n.$ In the overdetermined case, the error bound remains order $O(\Delta^2)$. Thereafter, we showed that calculus rules for generalized centred simplex gradients can be  written in a way similar to those for the true gradients plus a term $E.$ Removing the term $E$ from the calculus rules leads to new approaches to approximate gradients that also have error bounds of order $O(\Delta^2)$. If the true objective functions are linear or quadratic, then the new approaches result in perfect accuracy.  Corollaries \ref{cor:ccproduct} and \ref{cor:cccomp} provide several cases where the product rule and the chain rule are perfectly accurate.

Recent work has been done in the reduction of calculation time and storage space needed to use simplex gradients.  In \cite{Coope2019Efficient}, Coope and Tappenden start with the knowledge that a simplex gradient in $\R^n$ can require $O(n^3)$ operations and $O(n^2)$ storage units, and then reduces both of them to $O(n)$ under reasonable conditions.  A valuable next step would be to confirm if these techniques also work for generalized centred simplex gradients. Another future research direction would be to investigate error bounds when the matrix $S$ does not have full rank (the undetermined case).

\def\cprime{$'$}


TITLE: Square divided by absolute value
QUESTION [0 upvotes]: First time posting on Math SE, with kind of a basic algebra question.
Question
Does the relation:
$$\dfrac{(ab)^2}{|ab|} = \left|ab\right|$$
with $a,b \in \mathbb{R_{\ne 0}}$ always hold?
It seems trivial to me, but Wolfram Alpha gives me a strange answer because it specifies that this is True assuming $a,b$ are positive.
Reasoning
No matter what sign $a,b$ have, we have that $(ab)^2 > 0$ and $\left|ab\right| > 0$. Thus their ratio is greater than zero, and the magnitude of that ratio is exactly $ab$ with a positive sign, so $\left|ab\right|$.
Is what I said correct? If so, is this question a completely useless one? Sorry for the occasionally bad English!
Edit: formatted equations as suggested by Frentos

REPLY [1 votes]: Your statement about Wolfram is not quite correct. It gives various alternate forms for this expression, two of which are:

$ab$ assuming $a$ and $b$ are positive
$ab\,sgn(a)\,sgn(b)$

(2) is equivalent to $|ab|$
See here


TITLE: Find the values of a solution of Burgers' equation, given its value at one point
QUESTION [1 upvotes]: So I have the PDE:
$$u_t+u\cdot u_x=0$$With auxiliary condition $u(1,1)=5$. The question asks if one can find the value of the points at $(2,1), (2,2), (6,2), (4,3), (10,3), (11,3)$. The way I went about it is that my professor went through the solution of Burgers' Equation and reached a solution:
$$u(x,t) = \frac{x-x_0}{t} = g(x_0)$$
Now, I plugged in $(1,1)$ into $u$ to find that $x_0=-4$. Now noting that $g$ is supposed to be increasing, I found that every point is not possible to find a value for except the first point $(2,1)$, and the value there is $6$. Did I approach this question right? Or is there something lacking from my explanation?

REPLY [1 votes]: The solution of Burgers' equation is constant on characteristic lines. Each characteristic line is of the form $x= x_0+ vt$ where $v$ is the value of solution on that line. Specifically, from $u(1,1)=5$ we get the line $x = 1 + 5(t-1)$, or simply $x=5t-4$.
Out of the given points $(x,t)$, namely $(2,1),(2,2),(6,2),(4,3),(10,3),(11,3)$, only $(6,2)$ and $(11,3)$ lie on the above line.  So we know that $u$ is equal to $5$ at those two points, and we don't know about the rest.
All of this is assuming that the line $x=5t-4$ does not hit a shock wave (at which characteristic lines terminate).


TITLE: How to calculate complicated geometrical series?
QUESTION [1 upvotes]: I have a geometrical series (I don't know if its geometrical series or not):
$$
\sum_{n=1}^{\infty }n\rho ^{n}(1-\rho)
$$
how can I simplify it ? ( assume that $ 0 \le \rho \le 1$ )
The last answer in my calculatio should be $\frac{\rho}{1-\rho}$. But I really don't know how ?

REPLY [1 votes]: Using Arithmetico-geometric sequence,  $$\sum_{n=1}^\infty\left[a+(n-1)d\right]r^{n-1}=\frac a{1-r}+\frac{rd}{(1-r)^2}\text{  for } |r|<1$$
We have $$\sum_{n=1}^{\infty}n\rho^n(1-\rho)=(1-\rho)\rho\left(\sum_{n=1}^{\infty}n \rho^{n-1}\right)$$
Here,  we have $\displaystyle a=d=1,r=\rho$


TITLE: Proving sets to be independent
QUESTION [4 upvotes]: I know that I can use P(AB)=P(A)P(B) to prove whether sets are independent. But how can I use this to say that P(A)=0.3 and P(B)=0.4 and P(AUB)=0.6 are or aren't independent?
It's fine not to give an outright solution, an explanation would be much more helpful!

REPLY [3 votes]: Use the fact that $P(A\cup B)=P(A)+P(B)-P(A\cap B)$.


TITLE: Proving with induction a recursive function executes n instructions
QUESTION [0 upvotes]: Suppose that you have a recursive function which accepts an array as input. When its called with an array of length $n$, it executes a total of $8n + 64$ instructions, two of which are recursive function calls with an array of size $n-1$, and when called with an array of length $0$, it executes $8$ instructions. Prove that the function executes $88(2^n)-8n-80$ instructions when its input has length $n$, for all $n \geq 0$ .
I understand the steps in an inductive proof. First, the base case is proven. Then the inductive hypothesis is stated and assumed to be true for the constraints $P(k)$. Then we use this to show in our inductive step that our $P(k+1)$ is also true.
In the case of this problem, since it's recursive I assume we will be using strong induction. In which case, we essentially work backwards in our proof. However, I don't know where to take it after I've proven the base case. Maybe it's the wording that's throwing me off, but I can't figure out how to go about this. Thanks.

REPLY [1 votes]: When you say "$8n+64$ instructions two of which are recursive function calls with an array of size $n-1$", I'll assume you mean $8n+64$ instructions as well as two recursive $n-1$ calls.
In this case, no strong induction is necessary. All we need for a base case in $n=0$, which can be verified algebraically.
Now we assume $P(k)$ holds, and consider $P(k+1)$. We know that for $n=k+1$, the function call executes $8(k+1)+64$ instructions as well as two recursive calls with $n=k$. From $P(k)$, we know the total is thus $8(k+1)+64+2[88(2^k)-8k-80]$, which we can rearrange into $88(2^{k+1})-8(k+1)-80$. This implies $P(k+1)$ holds. We can therefore claim proof by simple induction.


TITLE: Solving recurrence relation with each term defined in terms of the 2 preceding terms
QUESTION [2 upvotes]: $$\{ X_n \} := X_0 = 1 , X_1 = 1 , x_{n+1} = X_n + 2X_{n-1}$$
$$\{Y_n\} := Y_0 = 1, Y_1 = 7, Y_{n+1} = 2Y_n + 3 Y_{n-1}$$
How would one solve these recurrence relations?
For the first one I tried telescoping by dividing $X_n$ by $2^{n-2}$ in an attempt to cancel across 2 lines (I hope you get what I mean, I don't have the Latex skill to show this). But this got pretty ugly because even after most terms had cancelled, I was left with an instance of $X_{n-1}$.
Even with this I tried to "fall backwards spirally" coming up with expression for $X_k$ in terms of $X_{k-1}$ and so on until I hit rock bottom, but this got reallly ugly.

Motivation
I'm trying to solve this problem.

Let $ \{X_n\}$ and $ \{Y_n\}$ denote two sequences of integers defined as follows:
  $X_0 = 1,\ X_1 = 1,\ X_{n + 1} = X_n + 2X_{n - 1} \quad (n = 1,2,3,\ldots)$,
  $Y_0 = 1,\ Y_1 = 7,\ Y_{n + 1} = 2Y_n + 3Y_{n - 1} \quad (n = 1,2,3,\ldots)$.
  Prove that, except for the "1", there is no term which occurs in both sequences.

My idea is to try and come up with closed forms for each recurrence and equate them using 'k' and 'm' as place-holders, and show that there are no integer solutions for either apart from 1.

REPLY [3 votes]: The characteristic equation of the first linear reccurence relation is: $x^2 - x - 2 = (x-2)(x+1)=0$. Therefore we have $x_n = A\cdot 2^n + B \cdot (-1)^n$. Plug in the first two values for $n=0,1$ and you will find the values of $A$ and $B$. Similarly do the same for $Y_n$.


TITLE: If $v+U=x+W$, with $U, W$ subspaces of $V$ then $0+U=x-v+W$?
QUESTION [2 upvotes]: Let $x,v \in V$, with $U, W$ subspaces of $V$. If we have the following equality for affine spaces $v+U=x+W$, then do we have $0+U=x-v+W$?
I would say so, since we have $\forall_{u}\exists_w v+u=x+w$, which implies that $\forall_{u}\exists_w 0+u=x-v+w$, i.e. $0+U\subseteq x-v+W$, and similarly we could have derived $\forall_{w}\exists_u 0+u=x-v+w$, i.e. $0+U\supseteq x-v+W$, giving us the equality $0+U=x-v+W$.
Am I right?

REPLY [2 votes]: Suppose $v+U=x+W$; in particular, $x\in v+U$, so $x-v\in U$. Then
$$
v+U=v+(x-v)+U=x+U
$$
and from $x+U=x+W$ we deduce $U=W$, therefore $v+U=v+W=x+W=x+U$. The equality $0+U=x-v+W$ is now obvious.


TITLE: If $x$ is algebraic over $K$, show that $K[x]$ is a field.
QUESTION [0 upvotes]: Let $L/K$ an extension field (and $K$ a domain). $x$ is algebraic over $K$ if there is a polynomial $P(X)\in K[X]\backslash \{0\}$ such that $P(x)=0$. I want to show that $K[x]$ is a field.
I know that $P(x)=\prod_i P_i(x)^{v_i}=0$ where $P_i(X)$ are irreducible and thus, since $K$ is a domain, there is an $i$ such that $P_i(x)=0$.
I don't understand what follow
$K[x]$ is the range of the ring homomorphism
\begin{align*}
\text{eval}_x:K[X]&\longrightarrow L\\
P(X)&\longmapsto P(x),
\end{align*}
therefore it's kernel is a principal ideal that contain $(P_i)$ which is an ideal maximal.
Q1) Why $K[x]=\text{Im}(\text{eval}_x)$ ? To me we only have $\text{Im}(\text{eval}_x)\subset K[x]$.
Q2) Why $\ker(\text{eval}_x)$ is a principal ideal ? (I know that it's an ideal, but why is it principal ?)
Q3) Why $(P_i)$ is maximal ? And why $\ker(\text{eval}_x)\supset (P_i)$
May be my question are obvious for the most part of you, but I'm starting this course, and I didn't do algebra before, that's why it's complicate to me.

REPLY [0 votes]: I denote $e_x$ for $eval_x$. $$P(X)\in\ker(e_x)\iff e_x(P(X))=0\iff P(x)=0\iff P_i(x)\mid P(x)\iff P(x)=P_i(x)Q(x)\iff P(x)\in (P_i) $$
therefore $\ker(e_x)=(P_i)$.
The maximality of $P_i$ is obvious since every polynomial $Q(X)\in K[X]$ such that $Q(x)=0$ is in $(P_i)$.


TITLE: $\mathbb{R}^n \setminus C_r(0)$, $r>0$ connected for n>1
QUESTION [0 upvotes]: I want to prove that $\mathbb{R}^n \setminus C_r(0)$, $r>0$ is connected for n>1 where $C_r(0)$ denotes the ball around $0$ with radius $r$.
What's the easiest way to show this? Directly or via path connected?
I thought about working with the following:
For $n>2$ the $n-1$ sphere $S^{n-1}$ is connected and
$R^n\setminus C_r(0) \longrightarrow\ S^{n-1}: x \mapsto\ \frac{x}{||x||},$
is continuous and surjective.
Is it correct to say that therefore $\mathbb{R}^n \setminus C_r(0)$ has to be connected? Because usually the lemma goes the other way: a continuous image of a connected set is connected.
Or are there other, simpler ways to prove ths?

REPLY [1 votes]: Let $n \ge 1$ and define ${E_n}^{*} = \mathbb{R}^n \setminus \{\vec 0\}$. It is not difficult to show that the punctured Euclidean space ${E_n}^{*}$ is connected,
Define the unit sphere as $S_{n-1} = \{v \in \mathbb{R}^n \, | \; \; \lVert v \rVert = 1 \}$. The mapping $v \mapsto\ \frac{v}{\lVert v \rVert}$ is a continuous surjection of ${E_n}^{*}$ onto $S_{n-1}$, so the unit sphere is connected.
Recall that if $D$ is a clopen of a topological space $X$ that contains a point $x$ belonging to a connected subspace $G$ of $X$, then $G \subset D$. This is used implicitly several times in what follows.
Exercise: If $B_r(0)$ is a closed ball about the zero vector $\vec 0$ in $\mathbb{R}^n$, show that
$\tag 1 M = \mathbb{R}^n \setminus B_r(0)$
is connected.
Sketch
The sphere $G$ of radius $r + 1$ is a connected subspace of $M$.
$M$ is the union of lines with each one intersecting $G$ in exactly one point (c.f. the polar representation of vectors). Any clopen of $M$ must contain all lines (and line segments/rays) emanating from any point belonging to it.
Let $D$ be any nonempty clopen of $M$ with $\vec v \in M$. By using a scalar factor on $\vec v$, it must be true that $D$ contains a point belonging to $G$. Then it must be true that $G \subset D$. Then it must be true that $M \subset D$. Then it must be true that there is no nontrivial decomposition of $M$ into two clopens. So $M$ is connected.


TITLE: What is the meaning of the particle horizon in conformal diagrams?
QUESTION [4 upvotes]: I'm reading "Physical Foundations of Cosmology" (Mukhanov) and in Chapter 2.3 conformal diagrams get introduced. They seem to be a (graphical) tool to understand the causal structure of the universe. In these diagramms two things seem to be important: 1. the particle horizon and 2. the event horizon.
I understand the region that is seperated by the event horizon. Stuff inside can not talk to stuff outside of that region.
I do not understand what is so special about the particle horizon. I think I can talk to people outside the horizon (while I am inside). If I do not move in space/position (position = comoving distance) than I can leave the particle horizon (if I start inside of it).
I read that the particle horizon is the edge of the observable universe. Since I can leave this region this statement does not make sense to me.

REPLY [3 votes]: In short: The particle horizon is the extent of our future light cone at $t=0$, and the event horizon is the extent of our past light cone at $t=\infty$. It is important to be clear that these horizons are horizons only to an observer at this place in Space and Time. They do not mark physical boundaries between different regions in Space; rather, they describe boundaries for regions in Space and Time observable to us, on Earth, at this particular time. An observer somewhere in the Virgo cluster will see different horizons, spherical, at the same distances as we see them, and with themselves in the exact centre.
Particle horizon:
This is the distance from which light emitted at t=0 can have reached us today. In all practicality, this is marked by the Cosmic Microwave Background at a redshift $z \approx 1100$, before which the Universe was opaque, so we cannot see further back when looking at electromagnetic radiation. There is hope, though, that neutrino and Gravitational Wave observatories in the not too far future can push us closer to the $z = \infty$ limit at the Big Bang. The Particle horizon is always expanding, in all cosmological models. In our currently favoured cosmological model, it is around 43 billion light years away.
Event horizon:
This is the distance, inside of which photons emitted in our direction today will reach us in a finite time in the future. When light in distant parts of the Universe is emitted towards us, their journey is a race between their velocity towards us and the cosmological expansion of Space. The expansion of Space is homogeneous, which means that the recession velocity of a region is proportional to its distance. There is a distance, at which the recession velocity equals the speed of light; this is the distance we call the Hubble Sphere. However, in most cosmological models, the Hubble Sphere is not a horizon; it is perfectly possible to observe galaxies that are currently and have always been receding from us at superluminal speed; we have been doing this routinely for decades. This is because even though these photons are initially moving away from us, they are moving into regions of Space which are receding more slowly from us, until the "catch up" with our Hubble Sphere and start approaching us.
However, if the expansion is fast enough, it will "win" over the expansion of the Hubble sphere at some distance. This means that beyond this distance, photons will never get to our Hubble Sphere and thus never reach our telescopes, because the Universe expands so rapidly that the "crawl" towards our cosmic neighbourhood is too slow. Unlike the Particle Horizon, not all cosmological models have an event horizon - but the one which seems to describe our Universe does, and it is at a redshift of around $z\sim 2$.
But... But...
Yes, we routinely observe objects at distances far beyond that of the event horizon. The Event Horizon is a horizon in Time, not only in Space. What we observe at those distances is all in the past, though. As the Universe expands, these objects cross our event horizon at a given time in their history. From Earth, when we look at a galaxy at these distances, we will see the light from this galaxy being increasingly redshifted as we observe epochs closer and closer to this point in time. This also means a slowing down of the perceived time; on top of the increasing redshift, we will see the galaxy's history slow down and grind to a complete halt as we come asymptotically closer to this point in its history - this event - beyond which we can never get more information. We can easily observe galaxies at $z = 2$, but what happens at these galaxies right now, we will never be able to know.
Remember that an event in relativity is a point in Spacetime. the Event Horizon is aptly named - it is not a geometrical horizon made up of points in Space, but made up of events; of points in Spacetime.


TITLE: Min-cut and Min-$k$-cuts
QUESTION [1 upvotes]: Given an undirected weighted graph $G= \langle V,E \rangle$, the min-cut algorithm is polynomial and cuts the graph to at least 2 connected components such that the sum of the weights of the edges removed is minimal.
Now min-$k$-cut asks the same thing but the result is at least $k$ connected components, this is NP complete problem!
My question is it seems intuitive to try to implement the min-cut algorithm at most $k$ times achieve at least $k$ connected components while with every new cut we choose the component that gives the least sum of weights at each step (basically greedy algorithm), so why does this not work? could you give a counter-example where the min-$k$-cut is less than $k$ iterations of min-cut?
Thanks.

REPLY [1 votes]: Here is a situation where your strategy does not work optimally even when $k=3$. Imagine that the shaded circles are very large complete graphs:

The greedy strategy will first cut the $3$ edges on the left. Then, the left component is just a large clique (with no small cuts) and the right component has three $4$-edge cuts. If we choose any one of these, we'll separate the graph into $3$ components by deleting $7$ edges.
However, deleting all $6$ edges between the middle clique and the two cliques on the right will also create $3$ components, and it is more efficient.


TITLE: Bilinear form and notation
QUESTION [1 upvotes]: When I read about the bilinear form, i see this notation:
$$
f: V \times V \to \mathbb{F}
$$ is a bilinear form on $V$ if .....
Can anybody explain to me what this expression is actually saying in maybe language that newbs would understand. I now we are using these expression to be more precise, but can anyone explain what this expression is saying?
Thanks.

REPLY [1 votes]: This notation means "a function from $V\times V$ to $F$."
Generally you can say that $f$ is a function from $X$ to $Y$ by writing $f:X\to Y$. Here $X$ is the set $V\times V=\{(v,w)\mid v,w\in V\}$.
Then, as you say, it goes on further to specify some properties the function must satisfy. That's all.


TITLE: Indicial equation in Differential equation.
QUESTION [0 upvotes]: The Indicial equation of $$t^2y''+ty'+(t^2-2)y=0$$ at $t=0$ is

What i try::
Let $y=t^r$ for $t>0$
Then $$r(r-1)t^r+rt^r+t^{r+2}-t^r=0$$
$$\bigg[r(r-1)+r-1\bigg]t^r+t^{r+2}=0$$
If $t^{r+2}$ not present in above equation. Then indicial equation is
$r(r-1)+r-1=0$.
But Here $t^{r+2}$ is present. So i did not understand How
can i find indicial equation in above question.
Help me please. Thanks

REPLY [1 votes]: For finding indicial roots in an ODE, put $y=t^m$ and set the co-efficient of the least power of $t$ equal to zero.
$$t^2y''+ty'+(t^2-2)y=0 $$
$$ \implies m(m-1)t^m+mt^m+t^{m+2}-2t^m=0$$
The least powe of $t$ in above is $t^m$, let us set its coefficient equal to 0:
$m(m-1)=m-2=0 \implies m^2-2=0$. So for this ODE $m=\pm \sqrt{2},$
there are the indicial roots.

REPLY [1 votes]: I imagine you're trying to use the Frobenius method. You have to use $$y = \sum_{n=0}^{\infty} a_nt^{t+r}$$ and equate the coefficients of each power of t.


TITLE: Finding the mean and variance of random variables (discrete and continuous, specifically of indicators) and their properties.
QUESTION [1 upvotes]: I was just wondering if someone can help me understand the steps required to finding the mean and variance of random variables (discrete and continuous, specifically of indicators) and their properties. I know that the mean of a discrete random variable X is a weighted average of the possible values that the random variable can take. Also the Variance of a discrete random variable X measure the spread or variability of the distribution.

REPLY [2 votes]: Let $X$ be a random variable with distribution $P(X)$. If $P(X)$ has an associated density $f(X)$, the mean is given by:
$$\langle X\rangle=\int_{-\infty}^{+\infty}xf(x)\,dx$$
For a discrete distribution you can use: $$\langle X\rangle=\sum_{k=0}^{+\infty}kP(k)$$
The variance is defined by the expression $$\mathrm{Var}(X):=\langle (X-\langle X\rangle)^2\rangle,$$ where $\langle X \rangle$ is the mean as defined above.


TITLE: Probability of being dealt two cards of given ranks from the same suit in a 13 card hand?
QUESTION [0 upvotes]: A 13 card hand is randomly-drawn from a standard playing card deck. What is the probability that a 3 and 6 of the same suit is in the 13 card hand? What is the probability that all four suits of some rank are in the 13 card hand?
For the first part of the question, my reasoning was that we are interested in choosing two ranks of the same suit among the 13 possible, and given the four suits the probability should be
$$\frac{{13 \choose 2}{4 \choose 1}}{52 \choose 13}$$
but this gives an estimate in the order of $10^{-10}$, which seems unreasonably low.

REPLY [1 votes]: There are $4$ suits from which the $3$ and $6$ can come, and then you have $50$ cards from which to choose the remaining $11$.  That gives $4{50\choose11}$.  However, any hand containing both $3$ and $6$ of two different suits has been counted twice, so we need to subtract ${4\choose2}{48\choose9}$.  But now hands containing the $3$ and $6$ of three different suits have been added in three times (once fo each suit) and subtracted out three times (once for each pair of suits) so we have to add back in ${4\choose3}{46\choose7}$.  Finally hands with the $3$ and $6$ of each suit have been counted a net two times (check this), so we have to subtract ${44\choose5}.$
The probability is $$
{4{50\choose11}-{4\choose2}{48\choose9}+{4\choose3}{46\choose7}-{44\choose5}\over{52\choose13}}\approx21.978\%$$


TITLE: Proportion of domain in which convex function is small
QUESTION [1 upvotes]: Let $K \subseteq \mathbb R^n$ be a compact convex set with volume $V$, and let $f: K \to [0,1]$ be a convex function with domain $K$. Assume that $\min_{x \in K} f(x) = 0$. I claim that, for every $\epsilon \in [0,1]$, the volume of $\{x \in K : f(x) \leq \epsilon\}$ is at least $\epsilon V$. In other words, the function $f$ is small on a large proportion of its domain.
Is the above true? I think I have a very simple proof, but I'm skeptical of myself because I can't seem to find a reference, and it would simplify some proof of a well-known fact. If it is true, could anyone provide a reference?
UPDATE: HTFB exhibited a nice counter-example, with $K$ the unit ball and $f$ the distance from the origin. There, the volume of $\{x \in K : f(x) \leq \epsilon\}$ is $\epsilon^n V$. I wonder if that is the worst case? I.e. if we can guarantee that the volume of the region in question is at least  $\epsilon^n V$.

REPLY [1 votes]: As pointed out by HTFB, the original conjecture is false. My revised conjecture is that the volume of $\{ x \in K : f(x) \leq \epsilon\}$ is at least $\epsilon^n V$, matching HTFB's example. Here is a proposed proof sketch, in which I am only mildly confident.
Assume without loss of generality that $K$ includes the origin, and moreover that the minimum of $f$ is attained there --- i.e. $f(0) = 0$. Let $\epsilon K$ be the result of scaling down $K$ by a factor of $\epsilon$ (i.e. apply the linear tranformation $\epsilon I$ to $K$). The volume of $\epsilon K$ is $\epsilon^n V$. I claim that $f(x) \leq \epsilon$ for every $x \in \epsilon K$. Take $x \in \epsilon K$ and $y \in K$ such that $x = \epsilon y$. Clearly, $x= \epsilon y + (1-\epsilon) 0$. By Jensen's inequality:
$f(x) \leq \epsilon f(y) + (1-\epsilon) f(0) = \epsilon f(y) \leq \epsilon$.
Assuming I'm not missing anything, this should complete the proof.


TITLE: if $A=\{z\in \mathbb{Z}^+: z= 6xy +x-y; x\in \mathbb{Z}^+ , y \in \mathbb{Z}^+\} $ what is $A^c$?
QUESTION [1 upvotes]: if $A=\{z\in \mathbb{Z}^+:z= 6xy +x-y; x\in \mathbb{Z}^+ ,y \in \mathbb{Z}^+\}$ what is $A^c$ in $\mathbb{Z}^+$?
$A^c$ should have an equation form, without $\neq$ sign.
I make a transformation
$6x(x+k)+k=6x^2+(6x+1)k$ and
$6x(x-k)-k=6x^2+(6x-1)k$. But couldn't make to much progress. If you can help, I will be glad thanks.

REPLY [1 votes]: $z=6xy+x-y\iff 6z-1=(6x-1)(6y+1). $
Now if $x,y\in \Bbb Z^+$ then $6x-1\ge 5$ and $6y+1\ge 7$ so $6z-1$ cannot be prime.
But if $6z-1$ is composite then it has a factor $a\equiv -1 \mod 6$ with $1<a<6z-1.$ So let $a=6x-1$ with $x\in \Bbb Z^+.$ Then $1<(6z-1)/a=b\in \Bbb Z^+$ with $b\equiv 1 \mod 6.$ So let $b=6y+1 $ with $y\in Z^+.$ Then $6z-1=(6x-1)(6y+1)$ so $z\in A.$
So $A=\{z\in \Bbb Z^+: 6z-1 \text { is not prime}\}.$


TITLE: Simple statistical question. What are the odds that two people share a common interest?
QUESTION [1 upvotes]: This should be easy but I can't figure it out for some reason.  Let's say there are X clubs that people can become members of.  However, a single person has time for exactly N of them (where N is less than X.  So if X = 10, a person has time for N = 3 of them).  If you have two people, what are the odds that they share at least one club in terms of X and N.
Thanks

REPLY [0 votes]: Hint: The complementary event to "These people share at least one interest" is "These people have no interests in common".  It might be easier to compute the probability of the latter, then use that to find the former.


TITLE: Constrained Minimization Problem derived from a Directed Graph
QUESTION [1 upvotes]: I'm looking for a solution the following graph problem for data analysis purposes.
Basically, I have a directed graph of $N$ nodes where I know the following:

The sum of the weights of the out-edges for each node ($O_i = \Sigma_{j=1}^N e_{i,j}$ where $i$ is a node and $e_{i,j}$ represents the weight of an edge directed from node $i$ to node $j$)
The sum of the weights of the in-edges for each node ($I_i = \Sigma_{j=1}^N e_{j,i}$ where $i$ is a node and $e_{i,j}$ represents the weight of an edge directed from node $j$ to node $i$).
Following from the above, $\Sigma O_i = \Sigma I_i$
No nodes have edges with themselves ($e_{i,i} = 0$)
All $e_{i,j}$ are positive

Represented as a weighted adjacency matrix, I know the column sums and row sums but not the value of the edges themselves. I've realized that there is not a unique solution to this problem. However, I'm hoping that I can at least arrive at a solution to this problem that minimizes the sum of the edge weights or maximizes the number of 0 edge weights or something along those lines (Basically, out of infinite choices, I'd like the most 'simple' graph).
I've thought about representing it as:
Min $\Sigma e_{i,j}$ s.t. $O_i = \Sigma_{j=1}^N e_{i,j} $, $I_i = \Sigma_{j=1}^N e_{j,i}$ and $e_{i,j} \ge 0$
I'm primarily using this for data analysis in Scipy and Numpy. However, using their constrained minimization techniques, I'll end up with approximately $2N^2-N$ constraints which I'm worried will be unfeasible for large data sets. Is there an analytic solution to this that I'm missing? Any way to simplify the minimization so I don't need that many constraints?

REPLY [0 votes]: I can suggest a solution that gives a graph with $2N-1$ or less edges.
1) Take any pair of vertices $v_i$ and $v_j$ with $O_i>0$ and $I_j>0$ and create a directed edge $(v_i, v_j)$ between them.
2) Let the weight of the edge be $min(O_i, I_j)$. If $O_i < I_j$ then $v_i$ should have no other out-edges and $v_j$ should have additional in-edges with total weight $I_j-O_i$. Let now $O_i=0$ and $I_j=I_j-O_i$ (residual total weights of the out-edges for $v_i$ and of in-edges for $v_j$).
Do similarly for the case $O_i > I_j$.
So now we reduced the quantity of vertices with non-zero total out-edge (or in-edge) weight by 1.
3) Repeat steps 1 and 2 until there is only one vertex with non-zero residual total out-edge weight (or non-zero residual total in-edge weight). Connect it with all remaining vertices with non-zero residual total in-edge weight.
Now you have a graph with $2N-1$ edges at most. It can be not the most 'simple' graph but at least it's quite simple/sparse. (A possible simple and obvious optimization is to try to pair vertices with $O_i = I_j$ every time.)
It seems the algorithm can be implemented in linear time.


TITLE: Is the 4-norm of the orthogonal projection of a vector into a subspace less than or equal to the 4-norm of the vector itself?
QUESTION [3 upvotes]: To simplify the question, suppose $V\subseteq \mathbb{R}^n$ is a subspace and $P$ is the projection matrix. Is it true that $\forall x \in \mathbb{R}^n, \|Px\|_4 \le \|x\|_4$. I guess it is true for any $k$-norm if $k\ge 2$, but I don't know how to prove it.

REPLY [3 votes]: As was concisely pointed out by user1551, the answer is negative, but perhaps the following could shed some more light as to why it is negative, and why $k>2$ is important.
Note first that for every symmetric orthonormal matrix $U$ in $\mathbb{R}^n$, the matrix $P=(U+I)/2$ is a symmetric projection matrix, as can be easily verified. (It is symmetric and $P^2=P$). This, together with the following lemma, allows us to construct orthogonal projections with large $||\cdot ||_k$ norm.
Lemma. Fix a positive integer $m>2$. Let $v_0\in R^{2m}$ denote the vector whose $m$ last coordinates are $1$ and the $m$ first coordinates are zero. Let $u_0\in R^{2m}$ denote the vector whose $m+1$'st coordinate is $\sqrt{m}$ and all the rest are zero. Then there exists an orthonormal symmetric $2m\times 2m$ matrix $U$ such that $Uv_0=u_0$.
Before I prove the lemma, let me show how it is used to answer the question. Let $P={U+I\over 2}$ with $U$ from the lemma and $I$ the identity in $R^{2m}$. Then:
$$||v_0||_k=m^{1/k},\enspace\hbox{but}\enspace ||Pv_0||_k=||{\sqrt{m}e_{m+1}+v_0\over 2}||_k>{\sqrt{m}\over 2}$$
Here $e_{m+1}$ denotes the corresponding unit vector. Consequently, the norm of the projection as an operator from $R^{2m}$ to $R^{2m}$ is larger than ${1\over 2}m^{1/2-1/k}$, which tends to infinity as $m\to\infty$ when $k>2$.
It remains to prove the lemma.
Proof of lemma. Let $Q:R^{2m}\to R^m$ denote the projection which leaves untouched the last $m$ coordinates and deletes the first $m$ coordinates. There exists an orthonormal matrix $V$ in $R^m$ that maps $Qv_0$ to $Qu_0$, because both have the same Euclidean norm, namely $\sqrt{m}$, and the orthogonal group acts transitively on spheres. Consider the $2m\times 2m$ block matrix:
$$U=\begin{bmatrix}
    0 & V  \\
    V^t &0 \\
  \end{bmatrix}$$
$U$ has the desired properties: it is orthonormal (all columns have norm $1$ and are mutually orthogonal), it is symmetric, and $Uv_0=u_0$. Q.E.D.


TITLE: Interpretation and clarification of the inf/max of a function in 1-dimension
QUESTION [1 upvotes]: Consider the following proposition: Let $x_1<x_3<x_2$ be distinct real numbers and $f\in\mathcal{C}^1(\mathbb{R};\mathbb{R})$. If
\begin{equation}\max\{f(x_1),f(x_2)\}<f(x_3),\end{equation}
then there is a critical point $\xi$ of $f$ in $(x_1,x_2)$ characterized by \begin{equation}f(\xi)=\max\limits_{x\in[x_1,x_2]}f(x)=\inf\limits_{[a,b]\in\Gamma}\max\limits_{x\in[a,b]}f(x),\end{equation}
where
\begin{equation}\Gamma=\{[a,b]:a\leq x_1<x_2\leq b\}.\end{equation}
Question and Remarks: From calculus 1, it clear to me why there is a critical point $\xi\in(x_1,x_2)$ such that $f(\xi)=\max\limits_{x\in[x_1,x_2]}f(x)$. However, I am unable to give a simple interpretation or just picture what is being claimed with the characterization $f(\xi)=\inf\limits_{[a,b]\in\Gamma}\max\limits_{x\in[a,b]}f(x)$.
I am aware that such a proposition is used to illustrate the duality geometry and compactness of the Mountain pass theorem used in nonlinear analysis.

REPLY [0 votes]: It's simpler than it seems: the relevant observation is that if $[a,b]$ is a superset of $[x_1,x_2]$, then $\mathop{\max}\limits_{x \in [a,b]} f(x) \geq \mathop{\max}\limits_{x \in [x_1,x_2]} f(x)$. Since the maxes over all intervals containing $[a,b]$ are greater, the max over $[x_1,x_2]$ must be the infimum.