\documentclass[11pt,epsf]{article}
\parindent 0in
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{epsfig}

\newcommand{\handout}[5]{
   \noindent
   \begin{center}
   \framebox{
      \vbox{
    \hbox to 5.78in { {\bf 18.409 The Behavior of Algorithms in Practice} \hfill #2 }
       \vspace{4mm}
       \hbox to 5.78in { {\Large \hfill #5  \hfill} }
       \vspace{2mm}
       \hbox to 5.78in { {\it #3 \hfill #4} }
      }
   }
   \end{center}
   \vspace*{4mm}
}

\newcommand{\lecture}[4]{\handout{#1}{#2}{Lecturer: #3}{Scribe: #4}{Lecture #1}}

\newcommand{\Kappa}{\kappa}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{assumption}[theorem]{Assumption}

\setlength{\topmargin}{-0.50in}
\setlength{\textheight}{8.5in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{-0.0in}
\setlength{\textwidth}{6in}
\addtolength{\parskip}{2pt}
\addtolength{\itemsep}{0.1in}
\parskip 1.5ex

\renewcommand{\baselinestretch}{1.25}

\begin{document}

\lecture{2}{2/12/2}{Dan Spielman}{Steve Weis}
\section*{Linear Algebra Review}
A $n$ x $n$ matrix has $n$ \textbf{singular values}. For a matrix $A$,
the largest singular value is denoted as $\sigma_n(A)$. Similarly,
the smallest is denoted as $\sigma_1(A)$. They are defined as follows:
\[\sigma_n(A) = ||A|| = \max_x \frac{||Ax||}{||x||}\] \[\sigma_1(A) =
||A^{-1}||^{-1} = \min_x \frac{||Ax||}{||x||}\] There are several
other equivalent definitions: \[\{\sigma_n(A), \ldots, \sigma_1(A)\} =
\{ \sqrt{\lambda_n(A^TA)}, \ldots, \sqrt{\lambda_1(A^TA)} \}\]
\[\sigma_i(A) = \min_{subspaces S, dim(S) = i} \max_{x\in S}
\frac{||Ax||}{||x||} = \max_{subspaces S, dim(S) = (n-i+1)} \min_{x\in
S} \frac{||Ax||}{||x||} \] 

Another classic definition is to take a unit sphere and apply A to it,
resulting in some hyper-ellipse. $\sigma_n$ will be the length of the
largest axis, $\sigma_{n-1}$ will be the length of the next largest
orthogonal axis, etc..  

\textbf{Exercise:} Prove that every real matrix $A$ has a
\emph{singular-value decompsition} as $A = USV$, where $U$ and $V$
  are orthogonal matrices and $S$ is non-negative diagonal, and all entries in 
  $U$, $S$, and $V$ are real.  


\section*{Condition Numbers}
The singular values define a \textbf{condition number} of a matrix as follows:

$\Kappa(A) := \frac{\sigma_n(A)}{\sigma_1(A)} = \frac{||A||}{||A^{-1}||^{-1}}$

\begin{lemma}\label{first}
If $Ax = b$ and $A(x+\delta x) = b + \delta b$ then
\[\frac{||\delta x||}{||x||} \leq \Kappa(A) \frac{||\delta b||}{||b||}\]
\end{lemma}

\textbf{Proof of Lemma \ref{first}:}
\[A\delta x = \delta b \Rightarrow  \delta x = A^{-1}\delta b \Rightarrow
||b|| \leq ||\delta b||\cdot ||A^{-1}|| = \frac{||\delta b||}{\sigma_1(A)} 
\] \[ Ax = b \Rightarrow ||b|| \leq ||A|| \cdot ||x|| = \sigma_n(A)\cdot||x||
\Rightarrow \frac{1}{||x||}\leq \frac{\sigma_n(A)}{||b||}\]

Lemma \ref{first} follows from these two inequalities. 

\begin{lemma}\label{second}
If $Ax=b$ and $(A+\delta A)(x + \delta x) = b$ then \[\frac{||\delta
x||}{||x + \delta x||} \leq \Kappa(A) \frac{||\delta A||}{||A||}\] \end{lemma}

\textbf{Exercise:} Prove Lemma \ref{second}.

In regards to the condition number, sometimes people state things
like:
 
For any function $f$, the condition number of $f$ at $x$ is defined
as: \[ \lim_{\delta \rightarrow 0} \sup_{||\delta x|| < \delta}
\frac{||f(x) - f(x+\delta x)||}{||\delta x||} \] 

If $f$ is differentiable, this is equivalent to the Jacobian of $f$:
$||J(f)||$. A result of Demmel's is that condition
numbers are related to a problem being ``ill-posed''. A problem $Ax=b$
is ill-posed if the condition number $\Kappa(A)=\infty$, which occurs iff
$\sigma_1(A) = 0$. Letting $V := \{A :\sigma_1(A)=0\}$, we
state the following Lemma:

\begin{lemma}\label{distance}
 $\sigma_1(A) = dist(A,V)$, i.e. the Euclidian distance from A to the set V.
\end{lemma}

\textbf{Proof to Lemma \ref{distance}:}
Consider the singular value decomposition (SVD), $A =
USV^T$, $U,V$ orthogonal. $S$ is defined as the diagonal matrix
composed of singular values, $\sigma_1, \ldots, \sigma_n$.

Construct a matrix $B$ to be the singular
matrix closest to $A$. Then
$A = \sum_{i=1}^n \sigma_i u_i v_i^T$ and $B = \sum_{i=2}^n \sigma_i
u_i v_i^T$. Now consider the Frobenius norm, denoted $||M||_F$ of A
and B: $||A - B||_F = ||\sigma_1 u_1 v_1^{T}||_F = \sigma_1 $. Since
$\sigma_1(B) = 0$ and $B$, $dist(A,V) \leq \sigma _{1} (A)$.

The following claim will help us prove that 
  $dist(A,V) \geq \sigma _{1} (A)$.
For a singular matrix $B$ and let 
  $\delta A = A - B$. 
The following claim implies that $||A-B|| \geq \sigma_1$,
  and Lemma~\ref{lem:frob} implies that 
  $||A-B||_{F} \geq ||A-B||$,

\begin{claim}
If $(A + \delta A)$ is singular, then $||\delta A ||_F \geq \sigma_1$
\end{claim}

\textbf{Proof:}
$\exists v, ||v|| = 1, s.t. (A + \delta A)v = 0$, 

$||Av|| \geq \sigma_1(A) \Rightarrow ||\delta A v || \geq \sigma_1
\Rightarrow \sigma_n(\delta A) \geq \sigma_1$.

by the next lemma, we

\begin{lemma}\label{lem:frob}
$||A||_F \geq \sigma_n(A)$
\end{lemma}
\textbf{Proof:} The Froebinus norm, which is the root of the sum of the squares of
the entries in a matrix, does not change under a change of
basis. That is, if $V$ is an orthonormal matrix, then: $||AV||_F = ||A||_F$.
In particular, if $A = USV$ is the singular-value decomposition of
  $A$, then
\[
||A||_F = ||USV||_F = ||S||_F = \sqrt{\sum \sigma_i^2}.
\]

We now state the main theorem that will be proved in this and the next
lectures.

\begin{theorem}\label{thm:main}
Let $A$ be a $d$-by-$d$ matrix such that $\forall i,j, |a_{ij}| \leq
1$. Let $G$ be a $d$-by-$d$ with Gaussian random variance $\sigma^2
\leq 1$. We will start to prove the following claims:
\begin{enumerate}
\item [a.] $Pr[\sigma_1(A+G) \leq \epsilon] \leq \sqrt{\frac{2}{\pi}}
\frac{d^{3/2}\epsilon}{\sigma}$
\item [b.]$Pr[\Kappa(A) > d^2(1+\sigma
\frac{\sqrt{\log{1/\epsilon}}}{\epsilon\sigma})] \leq 2 \epsilon$
\end{enumerate}
\end{theorem}

To give a geometric characterization of what it means for $\sigma_1$
to be small. Let $a_1,\ldots,a_d$ be the columns of 
$A$. Each $a_i$ is a $d-$element vector. We now define
$height(a_1,\ldots,a_d)$ as the shortest distance from some $a_i$ to
the span of the remaining vectors: \[ height(a_1,\ldots,a_d) = \min_i
dist(a_i, span(a_1, \ldots, a_{i-1},a_{i+1},\ldots, a_d))\]

\begin{lemma}
$height(a_1,\ldots,a_d) \leq \sqrt{d}\sigma_1(A)$
\end{lemma}

\textbf{Proof:} Let $v$ be a vector such that $||v|| = 1$, $||Av|| =
\sigma_1(A) = || \sum_{i=1}^d a_i v_i ||$ Since $v$ is a unit vector,
some coordinate $|v_i| \geq \frac{1}{\sqrt{d}}$. Assume it is
$v_1$. Then: \[||\sum_{i=2}^d a_i \frac{v_i}{v_1} + a_1 || =
\frac{\sigma_1}{v_1} \leq \sqrt{d}\sigma_1(A) \Rightarrow 
dist(a_1, span(a_2, \ldots, a_d)) \leq \sigma_1(A)\sqrt{d} \]

\begin{lemma}
$Pr[height(a_1+g_1, \ldots, a_n+g_n) \leq \epsilon] \leq \frac{d\epsilon}{\sigma}$
\end{lemma}

This lemma follows from the union bound applied to the following Lemma:

\begin{lemma}\label{third}
$Pr[dist(a_1+g_1, span(a_2+g_2, \ldots, a_d+g_d)) \leq \epsilon] \leq \frac{\epsilon}{\sigma}$
\end{lemma}

\textbf{Proof of Lemma \ref{third}:}
This proof will take advantage of the following lemmas regarding
gaussian distributions:
\begin{lemma}
A a Gaussian distribution $g$ has
density:\[(\frac{1}{\sqrt{2\pi}\sigma})^d \cdot
e^{\frac{||g||^2}{2\sigma^2}} \] 
\end{lemma}

\begin{lemma}\label{univar}
A univariate Gaussian $x$ with mean $x_0$ and standard deviation
$\sigma$ has density: \[\frac{1}{\sqrt{2\pi}\sigma} \cdot
e^{\frac{-(x-x_0)^2}{2\sigma^2}} \]
\end{lemma}

\begin{lemma}\label{changevar}
The Gaussian distribution is spherically symmetric.  That is, it is
  invariant under orthogonal changes of basis.
\end{lemma} 

\textbf{Exercise:} Prove Lemma \ref{changevar}.

Returning to the proof, fix $a_2,\ldots,a_d$ and $g_2,
\ldots, g_d$. Let $S = span(a_2+g_2, \ldots, a_d+g_d)$. 
We want to upperbound the distance of the vector $a_1+g_1$ to the
multi-dimensional plane
$S$, which has $dim(S) = d-1$. Since the vector is of higher dimension, the
distance to the span will be bounded by one element. We can then just select
$x$ to be a
univariate Gaussian random variable such that $x = g_{11}$ and $x_0 =
a_{11}$. Using Lemma \ref{univar} and the fact that
$e^{\frac{-g^2}{2\sigma^2}} \leq 1$, we can prove lemma \ref{changevar}:

\[
Pr[|g_{11} - a_{11}| < \epsilon] = 
\int_{a_{11}-\epsilon}^{a_{11}+\epsilon}
\frac{1}{\sqrt{2\pi}\sigma} \cdot
e^{\frac{-g_{11}^2}{2\sigma^2}}  \leq
\frac{2\epsilon}{\sqrt{2\pi}\sigma} =
\sqrt{\frac{2}{\pi}}\frac{\epsilon}{\sigma}\leq \frac{\epsilon}{\sigma}
\]

\vskip 1in

Part (a) of  Theorem~\ref{thm:main} follows from these lemmas and claims.

%\section*{Open Questions}
%
%Letting $G$ be a Gaussian random matrix, Adleman has conjectured that
%$Pr[\sigma_1(G) < \epsilon] \sim \sqrt{d \epsilon}$.
%
%A conjecture following from this is that $Pr[\sigma_1(A+G) < \epsilon]
%\sim \sqrt{d\epsilon}$.
%
%\textbf{Conjecture:}
%If $A$ is a $[0,1]$ matrix with each entry having value $0$ with
%probability $p$, then $Pr[\sigma_1(A) < \epsilon] < f(d) \cdot
%\epsilon$
%
%\textbf{Conjecture:}
%If $P$ is random $\pm 1$ matrix and $A$ is an arbitrary matrix, 
%$Pr[\sigma_1(A+\sigma P) < \epsilon] < \frac{d^{3/2}\epsilon}{\sigma}$


\end{document}












