\section{Introduction} In the core of the SVM training problem lies a convex optimization problem which scales with the training set size rather than the feature space dimension \citep{BGV92, Vap95}. While this is usually considered to be a desired quality, since it circumvents the well known ``curse of dimensionality'', in large scale problems (which are so common in real world application such as speech, document classification, OCR, etc.) it may actually raise a new concern: Although the training problem is, in principle, solvable, in practice it is intractable by the conventional optimization techniques; e.g., each iteration of a general interior point method (IPM) scales cubically with the size of the training set. Several approaches to handle this problem have been suggested in the past few years which basically build a solution by solving a sequence of small scale subproblems. To mention a few: stochastic gradient ascent algorithms such as the Kernel-Adatron \citep{FCC98} and the SMO \citep{Platt99}, which sequentially update one or two (resp.) Lagrange multipliers at every training step, and active set methods, such as Chunking \citep{BGV92}, Decomposition \citep{OFG97} and Shrinking \citep{Joachims99}, which gradually build the (hopefully) small set of active constraints by feeding a generic optimizer (usually an interior point algorithm) with small scale subproblems. Our current effort is concentrated on the numerical rank of the kernel matrix as a source for further enhancement of the performance of the IPM. To this end we make the following three key observations: \begin{enumerate} \item If the kernel matrix has {\em low rank}, then it is possible to design an efficient interior point method that scales {\em linearly} with the size of data set. \item If the kernel matrix has {\em full rank} (or almost so), it may be possible to approximate it by a low rank positive semidefinite matrix (which in turn can be used to feed the optimizer). \item By using an approximation matrix instead of the original kernel matrix we obtain a perturbed optimization problem, which requires less computational effort to solve. In general, the optimal value of the objective function of the perturbed problem is different than the optimal value of the original problem. However, the size of the difference can be explicitely controlled by the quality of the approximation. \end{enumerate} We assume that the positive semidefinite kernel matrix, $Q_{n\times n}$, is totally dense and too large to handle, however its rank, $k$, is significantly smaller than $n$ (``significantly'' may be defined according to the context). This means that $Q$ can be represented as $Q=VV^{T}$, where $V$ is a matrix with $k$ columns and $n$ rows. The most expensive step at every iteration of an IPM (applied to an SVM problem) is inverting or factorizing a matrix of the form $D+Q$, where $D$ is a diagonal (positive) matrix and $Q$ is as described above. In general, this operation requires $O(n^{2})$ storage space and takes $O(n^{3})$ arithmetic operations, but by handling the linear algebra in a special way we can reduce the complexity to $O(nk^{2})$ and the storage to $O(nk)$. There are two possible approaches that achieve the same complexity. The first approach is based on the Sherman-Morrison-Woodbury formula for a low rank update of an inverse of a matrix. The Sherman-Morrison-Woodbury formula has been used widely in the context of interior point methods for linear programming \citep{ChoiMonmaShanno,Marxen}. In that context, however, the method often runs into numerical difficulties. The second approach is based on product form Cholesky factorization and is described in Section \ref{sec:Low-rank_updates}. This method is somewhat more expensive than the first: its workload is about twice and the storage requirement is three times the storage needed for the first method. On the other hand, the second method was shown to be numerically stable (experimentally and theoretically) in the context of interior point methods for LP and quadratically constrained quadratic problems \citep{GS1}. Some examples that we present in Section \ref{sec:Low-rank_updates} suggest that the first method may also have numerical difficulties in the context of our QP problems. The second method works well numerically for all problems that we tried. In many applications that we considered, a low rank representation $Q=VV^{T}$ may not be available a priori (even if it exists). It may also happen that even though the rank of $Q$ is close to (or equal to) $n$, $Q$ can be approximated by a low rank symmetric positive semidefinite matrix $\tQ$. In this case one can apply incomplete Cholesky factorization method with symmetric pivoting to obtain the desired representation of $Q$ or its approximation. This procedure requires $O(nk^2)$ operations, where $k$ is the number of nonzero pivots in the procedure, which is the same as the rank of matrix $Q$ or of its low rank approximation. The storage requirements reduces to $O(nk)$. It is possible to trace the quality of the approximation and apply an appropriate stopping criteria without an extra effort. This and the overall complexity makes this method compare favorably with other recently suggested approximation techniques \citep{SS00, WS01}. Finally, the last observation leads us to derive a bound on the quality of the solution obtained by solving the perturbed problem using a low rank approximation to $Q$. We show that if the approximation error $Q-\tQ$ is bounded (in some sense) by $\e$, then the difference between the optimal objective function values of the original problem and the perturbed problems is bounded by $lc^2\e$, where $c$ is the penalty (cost) parameter of the training error and $l$ is the number of active points in the training set of the perturbed problem. The rest of this paper is organized as follows: In the next section we present the convex QP that we are interested in solving, and the interior point method that we use. In Section \ref{sec:Low-rank_updates} we describe the Sherman-Morrison-Woodbury method and the product form Cholesky factorization method, as means for low rank updates. Section \ref{sec:Approximating_the_Kernel_Matrix} is devoted to issues related to approximating the kernel matrix by a low-rank positive semidefinite matrix. We present the algorithm to find such an approximation and a theorem in which we derive the above mentioned bound. Experiments, which demonstrate the utility of the suggested method, are presented in Section \ref{sec:Experiments}. We wrap things up in Section \ref{sec:Conclusions} with some concluding remarks and leading directions for further study. \subsection{Notation} In general we denote scalars and vectors in lower case letters (we make an explicit distinction when it is not clear from the context), and we use upper case letters to denote matrices. We use subscript indices to indicate elements of a vector or a matrix and we use superscript to label a whole matrix of a vector with an index. The description in this paper follows the traditional notation used in the optimization literature, which is slightly different from the one used in most SVM papers. The main difference is in the identification of the primal and dual problems (which switch roles) and the convention used to denote the unknowns with $x,y$, while in the SVM literature $x$ and $y$ are used to denote the input vectors and their labels, resp. Hence, the SVM training problem with $1$-norm soft margin is \begin{eqnarray} {\rm min_{\xi,w,b}}&& \frac{1}{2} \left + c\sum_{i=1}^n \xi_i \nonumber\\ \hspace{-1.3in}(SVM)\hspace{0.8in}\qquad {\rm s.t.}&& a_i \left( \left< w,v_i \right> + b \right) \geq 1-\xi_i, \quad i=1,\ldots,n \nonumber\\ \hspace{0.8in}&& \xi_i \geq 0, \qquad i=1,\ldots,n \nonumber \end{eqnarray} where labeled examples are pairs of the form $(v,a)$ such that $v$ is a finite or infinite dimension feature vector, $a \in \left\{ -1,+1 \right\}$ is a label, and $\left< \cdot,\cdot \right>$ is an inner product. We often use $Q$ as a shorthand for the labeled kernel matrix, i.e. \[ Q_{i,j} = a_i a_j K\left( v_i, v_j \right) \] where $K\left( \cdot,\cdot \right)$ is a (Mercer) kernel function representing dot-products in the feature (RKHS) space. We will use an equivalent form of the above problem (with somewhat different notation) which we will refer to as the {\sl dual} problem (see problem ($D$) in the next section). The dual of the ($SVM$) problem is thus called the {\sl primal} problem (see problem ($P$) in the next section).