2.1 Minimizing Quadratic Forms

A quadratic form is any function $f:{\mathbb{R}}^n \to {\mathbb{R}}$ of the form

$$f(\ensuremath{\mathbf{x}}) = \frac{1}{2} \ensuremath{\mathbf{x}}^... ...} \ensuremath{\mathbf{x}} - \ensuremath{\mathbf{b}} \ensuremath{\mathbf{x}} + c$$ (2.1)

where $\mathbf{A}$ is an $n \times n$ matrix, $\mathbf{x}$ and $\mathbf{b}$ are vectors of length $n$, and $c$ is a scalar. We will assume $\mathbf{A}$ is symmetric and positive semidefinite, that is

$$\ensuremath{\mathbf{x}}^T \ensuremath{\mathbf{A}} \ensuremath{\mathbf{x}} \ge 0,  \forall x \in {\mathbb{R}^n}$$ (2.2)

Any quadratic form with a symmetric positive semidefinite $\mathbf{A}$ will have a global minimum, where the minimum value is achieved on a point, line or plane. Furthermore there will be no local minima. The gradient and Hessian of the quadratic form $f$ in Equation 2.1 are

$$f'(\ensuremath{\mathbf{x}}) = \ensuremath{\mathbf{A}}\ensuremath{... ...nsuremath{\mathbf{b}},  f''(\ensuremath{\mathbf{x}}) = \ensuremath{\mathbf{A}}$$ (2.3)

Therefore algorithms which find the minimum of a quadratic form are also useful for solving linear systems $\ensuremath{\mathbf{A}}\ensuremath{\mathbf{x}} = \ensuremath{\mathbf{b}}$.

The minimum of a quadratic form $f$ can be found by setting $f'(x) = 0$, which is equivalent to solving $\ensuremath{\mathbf{A}}\ensuremath{\mathbf{x}} = \ensuremath{\mathbf{b}}$ for $\mathbf{x}$. Therefore, one may use Gaussian elimination or compute the inverse or left pseudo-inverse of $\mathbf{A}$ [44,23]. The time complexity of these methods is O$\left( n^3 \right)$, which is infeasible for large values of $n$. Several possibilities exist for inverting a matrix asymptotically faster than O$\left( n^3 \right)$, with complexities as low as approximately O$\left( n^{2.376} \right)$ [37,21]. Due to constant factors not evident in the asymptotic complexity of these methods, $n$ must be very large before they outperform standard techniques such as an LU decomposition or Cholesky factorization [44,37]. However, for very large $n$ even O$\left( n^2 \right)$ is infeasible, and hence these approaches are not practical. An alternative is to find an approximate solution $\mathbf{x}$ using an iterative method.