\documentclass[11pt]{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}

\newcommand{\norm}[1]{\|#1\|}
\newcommand{\infnorm}[1]{\norm{#1}_\infty}
\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}

\newcommand{\qed}{\ensuremath{\blacksquare}}
\newenvironment{proof}{\noindent{\bf Proof}\hspace*{1em}}{\qed\bigskip}


\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{5}{2/26/2002}{Dan Spielman}{Nitin Thaper}
\section*{Smoothed Complexity of Gaussian Elimination}
Today we will show that the smoothed complexity of
solving an $n\,$x$\,n$ linear system to $t$ bits of accuracy, using 
Gaussian Elimination without pivoting, is $O(n^3(\log (n/\sigma) + t))$.

More formally, we want to prove the following result.

\begin{theorem}
Let $\bar{A}$ be any matrix with $\infnorm{\bar{A}} \leq 1$ and let
$A = \bar{A} + G$ where $G$ is a Gaussian random matrix with variance $\sigma^2 \le 1$.
Then the expected number of digits needed to solve $Ax = b$ to $t$ bits of accuracy is
$O(log(n/\sigma) + t)$.
\end{theorem}

We will prove this theorem via a sequence of lemmas.

Recall that if we run Gaussian Elimination with $\epsilon_{mach}$ precision then we get $\hat{x}$ s.t. \\
$(A + \delta A)\hat{x} = b$ and
$$ 
\frac{\infnorm{\delta A}}{\infnorm{A}} \leq n \epsilon_{mach}
   \left(3 + \frac{5 \infnorm{L} \infnorm{U}}{\infnorm{A}}\right) 
$$

Also,
$$  
\frac{\norm{\hat{x}- x}}{\norm{x}} \leq \kappa(A)\frac{\infnorm{\delta A}}{\infnorm{A}}
$$

In the  last class, we showed that
$$ \frac{\infnorm{U}}{\infnorm{A}} \le \max_k \frac{\infnorm{A^{(k)}}}{\infnorm{A}}
$$

where $A^{(k)}$ is the $(n-k-1)$x$(n-k-1)$ matrix after first $k$ eliminations.\\
We also proved that 
$$
\frac{\infnorm{A^{(k)}}}{\infnorm{A}} \le n \norm{A_{1:k,1:k}^{-1}} \max(\infnorm{A_{1:k,(k+1):n}},\infnorm{A_{(k+1):n,1:k}})
$$

and
\begin{equation}
Pr[\norm{A_{1:k,1:k}^{-1}} > x] \le \frac{k^{3/2}}{x} 
\end{equation}

\textbf{Fact:} For a Gaussian random variable, $G$, with mean $0$ and variance $1$, $ Pr[G > x] \le \frac{e^{-x^2/2}}{\sqrt{2\pi}x} $

Using this fact together with the union bound, we get:

\begin{equation}
Pr[\max(\infnorm{A_{1:k,(k+1):n}},\infnorm{A_{(k+1):n,1:k}}) > x] \le 
\frac{n^2}{2} \frac{e^{-x^2/2}}{\sqrt{2\pi}x}
\end{equation}

In order to combine the probability bounds from (1) and (2) we use
the following combination lemma.

\begin{lemma}[Combination Lemma 1]
Let $A$ and $B$ be independent random variables s.t.
$$ Pr[A > x] \le \frac{\alpha}{x} $$
$$ Pr[B > x] \le \frac{\beta e^{-x^2/2}}{x} $$
Then, 
$$ Pr[AB > x] \le \frac{\alpha(\sqrt{2 \log (\beta)})}{x} $$
\end{lemma}
\begin{proof}
$AB > x$ $\Rightarrow$ $A > x/\sqrt{2\log{\beta}}$ or 
$\exists i \ge \sqrt{2\log{\beta}} \,$  s.t. $\,i \le B \le i+1$ and $A \ge x/i+1$

Therefore,
\begin{eqnarray*}
Pr[AB > x] & \le & Pr[A \ge x/\sqrt{2\log (\beta)}] + \sum_{i\ge\sqrt{2\log (\beta)}} Pr[A \ge x/i+1]Pr[B \ge i] \\
& \le & \frac{\alpha \sqrt{2 \log (\beta)}}{x} 
\end{eqnarray*}
\end{proof}

Since the random variables in $A_{1:k,1:k}^{-1}$ and $A_{1:k,k+1:n},A_{k+1:n,1:k}$
are independent we can use the combination lemma to get the following bound:

\begin{equation}
Pr[\frac{\infnorm{A^{(k)}}}{\infnorm{A}} \ge n x] \le \frac{n^{3/2}}{x}(2\sqrt{\log n} + 4)
\end{equation}

Finally, the union bound lets us get the following bound on the tail 
probability of the growth factor, $\frac{\infnorm{U}}{\infnorm{A}}$

\begin{equation}
Pr[\frac{\infnorm{U}}{\infnorm{A}} \ge x] \le \frac{n^{7/2}}{x}(2\sqrt{\log n} + 4)
\end{equation}

Next we need to bound $\infnorm{L}$.

%\begin{lemma}
%$$Pr[\infnorm{L} \ge x] \le \frac{5n^{7/2}(\sqrt{\log n + 1})\log x}{x}$$
%\end{lemma}

\textbf{Exercise:} For $j > k$,
$ L_{j,k} = \frac{a^{k-1}_{j,k}}{a^{k-1}_{k,k}} $

Now,
$$ a^{(k-1)}_{k,k} = \bar{a}_{k,k} + g_{k,k} - a_{k,1:k-1}A^{-1}_{1:k-1,1:k-1}a_{1:k-1,k} $$

And since the $g_{k,k}$ are chosen independently,
$$ Pr[|a_{k,k}^{(k-1)}| < \epsilon] \le \epsilon/\sigma $$

Equivalently, since the $g_{k,k}$ do not appear in $a_{j,k}^{(k-1)}, j>k$
$$ Pr[|a_{k,k}^{(k-1)}| < \epsilon\,| \{a_{j,k}^{k-1}\}, j>k] \le \epsilon/\sigma $$

which can be rewritten as:
\begin{equation}
Pr[\frac{1}{|a_{k,k}^{(k-1)}|} > x\mid {a_{j,k}^{k-1}}, j>k] \le \frac{1}/\sigma x
\end{equation}
\textbf{Exercise:} Show that
\begin{equation}
Pr[\exists j: |a_{j,k}^{(k-1)} > x] \le \frac{n^{5/2}(2 \sqrt{\log n} + 4)}{x}
\end{equation}

\begin{lemma}[Combination Lemma 2]
Let $A$ and $B$ be random variables satisfying:
$$ Pr[A > x] \le \alpha/x $$
$$ Pr[B > x|A ] \le \beta/x $$

Then
$$Pr[AB > x] \le \frac{2\alpha \beta \lceil \log x \rceil + \alpha + \beta}{x}$$

\end{lemma}
\begin{proof}

$AB > x$ $\Rightarrow$  either $A > x$ or $B > x$ 
or $\exists i, 1 \le i \le \lceil\log x \rceil s.t. A \ge 2^{i-1}\, and \, B \ge x/2^i $


It follows that:
\begin{eqnarray*}
Pr[AB > x] & \le & Pr[A > x] + Pr[B > x] + \sum_{i=1}^{\lceil\log x \rceil} Pr[A \ge 2^{i-1} \, and \, B \ge x/2^i] \\
& \le & \alpha/x + \beta/x + \sum_{i} Pr[A \ge 2^{i-1}]Pr[B \ge x/2^i | A \ge 2^{i-1}] \\
& \le & \frac{\alpha + \beta}{x} + \sum_{i}\frac{\alpha}{2^i}\frac{\beta 2^i}{x} \\
& \le & \frac{\alpha + \beta + 2 \alpha \beta \lceil \log x \rceil}{x}
\end{eqnarray*}

\end{proof}

The above combination lemma let's us combine the bounds in (5) and (6)
to get the following bound on $\infnorm{L}$:
$$ Pr[\infnorm{L} \ge 5n^{7/2}(\sqrt{\log n} + 1)x \log x/\sigma] \le 1/x $$

So far we've proved the following:
$$ Pr[\infnorm{L} \ge 5n^{7/2}(\sqrt{\log n} + 1)x \log x/\sigma] \le 1/x $$
$$ Pr[\frac{\infnorm{U}}{\infnorm{A}} \ge 2n^{7/2}(\sqrt{\log n} + 1)x/\sigma] \le 1/x $$
$$ Pr[\norm{A} \ge n^{1/2}(1 + \sqrt{4 \log x/n}] \le 1/x $$
$$ Pr[\norm{A^{-1}} \ge n^{3/2}x/\sigma] \le 1/x $$

Combining everything, we get:
$$ Pr[\frac{\kappa(A)\infnorm{L}\infnorm{U}}{\infnorm{A}} \ge 10 n^9(\sqrt{\log n} + 1)^2(1+\sqrt{4\log x/n})x^3/\sigma^3] \le 4/x $$

In order to get an estimate of the digits we need a statment about the $\log$ of
$\frac{\kappa(A)\infnorm{L}\infnorm{U}}{\infnorm{A}}$.

\textbf{Exercise:} If $Pr[a > \alpha x^k] \le 1/x$ then 
$ E[\log (a)] \le k \log(\alpha) + f(k) $
where $ f(k) \le (\frac{1}{1 - 2^{-1/k}})^2 $


Using this fact let's us claim the desired result, viz.,

$$ E[\log (\frac{\kappa(A)\infnorm{L}\infnorm{U}}{\infnorm{A}})] \le O(\log (n/\sigma)) $$

\section*{Drawbacks of this analysis}
This analysis is limited to the case when no pivoting is done. It would
be desirable to prove something about partial pivoting. It seems
that we should be able to get a high probability result
with exponentially instead of polynomially small probability for this case.
Experiments seem to validate this hypothesis too.

\end{document}