---
title: "Differentiability of rStress at a Local Minimum"
author: "Jan de Leeuw, Patrick Groenen, Patrick Mair"
date: "Version 003, February 8, 2016"
output:
pdf_document:
keep_tex: yes
number_sections: yes
toc: yes
toc_depth: 3
html_document:
keep_md: yes
number_sections: yes
toc: yes
toc_depth: 3
graphics: yes
fontsize: 12pt
bibliography: rStressDiff.bib
---
Note: This is a working paper which will be expanded/updated frequently. The directory [gifi.stat.ucla.edu/rstressdiff](http://gifi.stat.ucla.edu/rstressdiff) has a pdf copy of this article and the complete Rmd file.
#Problem
We study differentiability of the multidimensional scaling loss function rStress (@deleeuw_E_16a), defined as
\begin{equation}
\sigma_r(x):=\sum_{i=1}^n w_i(\delta_i-(x'A_ix)^r)^2
\end{equation}
for some $r>0$.
Here the $w_i$ are positive weights and the $\delta_i$ are positive dissimilarities. The matrices
$A_i$ are positive semi-definite, and the quantities $x'A_ix$ are squared distances.
Clearly if $x'A_ix>0$ for all $i$ the loss function is differentiable. @deleeuw_A_84f proves directional differentiability for $r=\frac12$ and he shows that at a local minimum we generally have $x'A_ix>0$. We investigate if and how this results generalizes to $\sigma_r$.
#Directional Derivatives
Define the directional derivative
\[
d\sigma_r(x,y):=\lim_{\epsilon\downarrow 0}\frac{\sigma_r(x+\epsilon y)-\sigma_r(x)}{\epsilon}.
\]
For our computations we need
\begin{align*}
I_+(x)&:=\{i\mid x'A_ix>0\},\\
I_0(x)&:=\{i\mid x'A_ix=0\}.
\end{align*}
Then
\begin{multline*}
\frac{\sigma_r(x+\epsilon y)-\sigma_r(x)}{\epsilon}=-4r\sum_{i\in I_+}w_i(\delta_i-(x'A_ix)^r)(x'A_ix)^{r-1}y'A_ix\\
-2\epsilon^{2r-1}\sum_{i\in I_0}w_i\delta_i(y'A_iy)^r+\epsilon^{4r-1}\sum_{i\in I_0}w_i(y'A_iy)^{2r}
+\frac{o(\epsilon)}{\epsilon},
\end{multline*}
and thus
\[
d\sigma_r(x,y)=
\begin{cases}
-4r\sum_{i=1}^nw_i(\delta_i-(x'A_ix)^r)(x'A_ix)^{r-1}y'A_ix&\text { if }r>\frac12,\\
-4r\sum_{i\in I_+}w_i(\delta_i-(x'A_ix)^r)(x'A_ix)^{r-1}y'A_ix-2\sum_{i\in I_0}w_i\delta_i(y'A_iy)^r&\text { if }r=\frac12,\\
+\infty&\text{ if }r<\frac12.
\end{cases}
\]
#Results
From our computations we derive the following results.
**Theorem 1:** If $r>\frac12$ then $\sigma_r$ is differentiable at $x$. If $\sigma_r$ has a local minimum at $x$ then
\[
\sum_{i=1}^nw_i\delta_i(x'A_ix)^{r-1}A_ix=\sum_{i=1}^nw_i(x'A_ix)^{2r-1}A_ix.
\]
**Theorem 2:** If $r=\frac12$ then $\sigma_r$ is directionally differentiable at $x$ in every direction $y$. If $\sigma_r$ has a local minimum at $x$ then
\[
\sum_{i\in I_+(x)}w_i\delta_i(x'A_ix)^{r-1}A_ix=\sum_{i\in I_+(x)}w_i(x'A_ix)^{2r-1}A_ix.
\]
and $I_0(x)=\emptyset$.
**Theorem 3:** If $r<\frac12$ then $\sigma_r$ is directionally differentiable only in those directions $y$ with $y'A_iy=0$ for all $i\in I_0(x)$.
Thus for $r=\frac12$ we have non-zero distances and differentiability at local minima, for $r>\frac12$
it is quite possible that local minima with zero distances exist, and for $r>\frac12$ rStress is not even directionally differentiable at points with zero distances.
#Local Maximum
We can also generalize a result of @deleeuw_R_93c to rStress.
**Theorem 4:** $\sigma_r$ has a local maximum at $x$ if and only if $x=0$.
**Proof:** If $x=0$ then
$$\sigma_r(x+\epsilon y)-\sigma_r(x)=-2\epsilon^{2r}\left\{\sum_{i=1}^nw_i\delta_i(y'Ay)^r-\frac12\epsilon^{2r}\sum_{i=1}^nw_i(y'A_iy)^{2r}\right\}.$$
It follows that if
$$
\frac12\epsilon^{2r}\leq\frac{\sum_{i=1}^nw_i\delta_i(y'Ay)^r}{\sum_{i=1}^nw_i(y'A_iy)^{2r}}
$$
we have $\sigma(x+\epsilon y)-\sigma(x)\leq 0$. So, although $\sigma_r$ may not even directionally differentiable at $x=0$, it does decrease in all directions and is thus a local minimum.
Converse, suppose $\sigma_r$ has a local maximum at $x\not= 0$. Then
$$
\sigma_r(\epsilon x)=\sum_{i=1}^nw_i\delta_i^2-2\theta\sum_{i=1}^nw_i\delta_i(x'Ax)^r+\theta^2\sum_{i=1}^nw_i(x'A_ix)^{2r},
$$
with $\theta:=\epsilon^{2r}$. Thus $\sigma_r$ is a convex quadratic in $\theta$ and it cannot have a local maximum on the ray through $x$.
**QED**
$$
#NEWS
001 01/14/16
-- First upload
002 01/15/16
-- Added local maximum result
003 02/08/16
-- Corrected some typos
#References