An incremental least squares algorithm for large scale linear classification

In this work we consider the problem of training a linear classifier by assuming that the number of data is huge (in particular, data may be larger than the memory capacity). We propose to adopt a linear least-squares formulation of the problem and an incremental recursive algorithm which requires to store a square matrix (whose dimension is equal to the number of features of the data). The algorithm (very simple to implement) converges to the solution using each training data once, so that it effectively handles possible memory issues and is a viable method for linear large scale classification and for real time applications, provided that the number of features of the data is not too large (say of the order of thousands). The extensive computational experiments show that the proposed algorithm is at least competitive with the state-of-the-art algorithms for large scale linear classification.

► The training of a linear classifier is cast as a linear least-squares problem. ► An incremental recursive algorithm performing a finite number of steps is used. ► Memory accesses is minimal, being each training data used only once. ► The approach is suitable for (real-time) linear large scale classification. ► Experiments show that the approach is competitive with state-of-the-art algorithms.