Taking into account Stratis's suggestions.

1 files changed, 25 insertions, 30 deletions

diff --git a/notes.tex b/notes.tex
index 77ec645..cd07a10 100644
--- a/notes.tex
+++ b/notes.tex
@@ -7,6 +7,7 @@
 \newcommand{\expt}[1]{\mathop{\mathbb{E}}\left[#1\right]}
 \newcommand{\norm}[1]{\lVert#1\rVert}
 \newcommand{\tr}[1]{#1^*}
+\newcommand{\ip}[2]{\langle #1, #2 \rangle}
 \newcommand{\mse}{\mathop{\mathrm{MSE}}}
 \begin{document}
 
@@ -102,10 +103,10 @@ verification). For any invertible matrix $A$:
 \end{equation}
 
 $A^{-1}$ is the inverse of a positive semidefinite matrix. Hence it is
-also positive semidefinite. We will denote by $x\cdot y$ the scalar product defined by $A^{-1}$,
+also positive semidefinite. We will denote by $\ip{x}{y}$ the scalar product defined by $A^{-1}$,
 that is:
 \begin{displaymath}
-  x\cdot y = \tr x A^{-1} y = \tr y A^{-1} x
+  \ip{x}{y} = \tr x A^{-1} y = \tr y A^{-1} x
 \end{displaymath}
 
 Using \eqref{eq:inverse} we get:
@@ -113,13 +114,13 @@ Using \eqref{eq:inverse} we get:
 \begin{split}
   \tr x (A + x_0\tr x_0)^{-1} x & = \tr x A^{-1} x - \frac{\tr x
   A^{-1}x_0\tr x_0A^{-1} x}{1+\tr x_0 A^{-1}x_0 }\\
-& = \tr x A^{-1} x - \frac{(x\cdot x_0)^2}{1+\norm{x_0}^2} 
+& = \tr x A^{-1} x - \frac{\ip{x}{x_0}^2}{1+\norm{x_0}^2} 
 \end{split}
 \end{displaymath}
 
 Thus:
 \begin{equation}\label{eq:decrease}
-\mse(D_n\cup\{x_0\}) = \mse(D_n) - \frac{\sigma^2(x\cdot x_0)^2}{1+\norm{x_0}^2}
+\mse(D_n\cup\{x_0\}) = \mse(D_n) - \frac{\sigma^2\ip{x}{x_0}^2}{1+\norm{x_0}^2}
 \end{equation}
 
 \emph{Adding one observation to the database decreases the MSE.}
@@ -147,58 +148,52 @@ the database is:
   \frac{\sigma^2(\tr x A^{-1} x_0)^2}{1+\tr x_0 A^{-1} x_0}
 \end{displaymath}
 
-If we denote by $y$ the additional observation present in $D_m$ and
+If we denote by $z$ the additional observation present in $D_m$ and
 not in $D_n$, then we would like to prove that:
 \begin{displaymath}
   \frac{\sigma^2(\tr x A^{-1} x_0)^2}{1+\tr x_0 A^{-1} x_0}
-\geq   \frac{\sigma^2\left(\tr x (A+y\tr y)^{-1} x_0\right)^2}{1+\tr x_0 (A+y\tr y)^{-1} x_0}
+\geq   \frac{\sigma^2\left(\tr x (A+z\tr z)^{-1} x_0\right)^2}{1+\tr x_0 (A+z\tr z)^{-1} x_0}
 \end{displaymath}
 
 Using the same notations as before, this is equivalent
 to:
 \begin{displaymath}
-  \frac{(x\cdot x_0)^2}{1+\norm{x_0}^2}
-\geq \frac{\left(\left(1+\norm{y}^2\right)(x\cdot x_0)-(x\cdot
-  y)(y\cdot x_0)\right)^2}
-{\left(1+\norm{y}^2\right)\big((1+\norm{y}^2)(1+\norm{x_0}^2)-(x_0\cdot
-y)^2\big)}
+  \frac{\ip{x}{x_0}^2}{1+\norm{x_0}^2}
+\geq \frac{\left(\left(1+\norm{z}^2\right)\ip{x}{x_0}-\ip{x}{z}\ip{z}{x_0}\right)^2}
+{\left(1+\norm{z}^2\right)\big((1+\norm{z}^2)(1+\norm{x_0}^2)-\ip{x_0}{z}^2\big)}
 \end{displaymath}
 
 By the Cauchy-Schwarz inequality:
 \begin{displaymath}
- (1+\norm{y}^2)(1+\norm{x_0}^2)-(x_0\cdot
-y)^2 > 0 
+ (1+\norm{z}^2)(1+\norm{x_0}^2)-\ip{x_0}{z}^2 > 0 
 \end{displaymath}
 
-Thus the previous inequality is consecutively equivalent to:
+Thus the previous inequality is consequently equivalent to:
 \begin{multline*}
-  \left(1+\norm{y}^2\right)^2\left(1+\norm{x_0}^2\right)(x\cdot x_0)^2
--\left(1+\norm{y}^2\right)(x_0\cdot y)^2(x\cdot x_0)^2\\
-\geq \left(1+\norm{x_0}^2\right)\left(1+\norm{y}^2\right)^2(x\cdot
-x_0)^2
-+ \left(1+\norm{x_0}^2\right)(x\cdot y)^2(y\cdot x_0)^2\\
--2\left(1+\norm{x_0}^2\right)\left(1+\norm{y}^2\right)(x\cdot
-x_0)(x\cdot  y)(y\cdot x_0)
+  \left(1+\norm{z}^2\right)^2\left(1+\norm{x_0}^2\right)\ip{x}{x_0}^2
+-\left(1+\norm{z}^2\right)\ip{x_0}{z}^2\ip{x}{x_0}^2\\
+\geq \left(1+\norm{x_0}^2\right)\left(1+\norm{y}^2\right)^2\ip{x}{x_0}^2
++ \left(1+\norm{x_0}^2\right)\ip{x}{z}^2\ip{z}{x_0}^2\\
+-2\left(1+\norm{x_0}^2\right)\left(1+\norm{z}^2\right)\ip{x}{x_0}\ip{x}{z}\ip{z}{x_0}
 \end{multline*}
 
 \begin{multline*}
-2\left(1+\norm{x_0}^2\right)\left(1+\norm{y}^2\right)(x\cdot
-x_0)(x\cdot  y)(y\cdot x_0)\\
-\geq \left(1+\norm{x_0}^2\right)(x\cdot y)^2(y\cdot x_0)^2
-+ \left(1+\norm{y}^2\right)(x_0\cdot y)^2(x\cdot x_0)^2
+2\left(1+\norm{x_0}^2\right)\left(1+\norm{z}^2\right)\ip{x}{x_0}\ip{x}{z}\ip{z}{x_0}\\
+\geq \left(1+\norm{x_0}^2\right)\ip{x}{z}^2\ip{z}{x_0}^2
++ \left(1+\norm{z}^2\right)\ip{x_0}{z}^2\ip{x}{x_0}^2
 \end{multline*}
 
-This last inequality is not true in general. As soon as $x$, $y$ and
+This last inequality is not true in general. As soon as $x$, $x_0$ and
 $z$ span a 2-dimensional space, it is possible that for example
-$(x\cdot x_0)$ and $(x\cdot y)$ are positive and $(y\cdot x_0)$
+$\ip{x}{x_0}$ and $\ip{x}{z}$ are positive and $\ip{z}{x_0}$
 negative. Then the left term of the inequality will be negative and
 cannot be greater than the right term which is always positive.
 
-In the one-dimensional case, the inner product $(x\cdot y)$ can be
-written as $\lambda xy$ for some positive $\lambda$. Then the last
+In the one-dimensional case, the inner product $\ip{x}{z}$ can be
+written as $\lambda xz$ for some positive $\lambda$. Then the last
 inequality becomes:
 \begin{displaymath}
-  2\geq \frac{\lambda y^2}{1+\lambda y^2} 
+  2\geq \frac{\lambda z^2}{1+\lambda z^2} 
 + \frac{\lambda x_0^2}{1+\lambda x_0^2}
 \end{displaymath}
 which is trivially true (a more direct proof for the one-dimensional