image processing - quadprog in MATLAB taking lot of time -

my goal classify image using multi class linear svm (with out kernel). write own svm classifier

i using matlab , have trained linear svm using image sets provided.

i have around 20 classes, 5 images in each class (total of 100 images) , using one-versus-all strategy.

each image (112,92) matrix. means 112*92=10304 values.

i using quadprog(h,f,a,c) solve quadratic equation (y=w'x+b) in svm. 1 call quadprog returns w vector of size 10304 1 image. means have call quadprog 100 times.

the problem 1 quadprog call takes 35 secs executed. means 100 images take 3500 secs. might due large size of vectors , matrices involved.

i want reduce execution time of quadprog. there way it?

first of all, when classification using svm, extract feature (like hog) of image, dimensionality of space on svm has operate gets reduced. using raw pixel values, generates 10304-d vector. not good. use standard feature.

secondly, not call quadprog 100 times. call once. concept behind optimization is, want find weight vector w , bias b such satisfies w'x_i+b=y_i images (i.e. x_i). note i go 1 number of examples in training set, w , b stay same. if wanted (w,b) satisfy 1 x, not need fancy optimization. stack x in big matrix of dimension nxd, y vector of nx1, , call quadprog. take longer time 35 seconds, once. called training svm. while testing new image, extract feature, , w*x+b class.

third, unless doing exercise understand svms, quadprog not best way solve problem. need use other techniques work large data, example, sequential minimal optimization.

how can 1 linear hyperplane classify more 2 classes: multi-class classification, svms use 2 popular approaches:

1. one-vs-one svm: c class problem, train c(c-1)/2 classifiers , @ test time, test many classifiers , choose class receives votes.
2. one-vs-all svm: name suggests, train 1 classifier per class positive samples class , negative samples other classes.

from libsvm faqs:

it one-against-one. chose after doing following comparison: c.-w. hsu , c.-j. lin. comparison of methods multi-class support vector machines , ieee transactions on neural networks, 13(2002), 415-425.

"1-against-the rest" method performance comparable "1-against-1." latter because training time shorter.

however, note naive implementation of one-vs-one may not practical large-scale problems. libsvm website lists shortcoming , provides an extension.

liblinear not support one-versus-one multi-classification, provide extension here. if k number of classes, generate k(k-1)/2 models, each of involves 2 classes of training data. according yuan et al. (2012), one-versus-one not practical large-scale linear classification because of huge space needed store k(k-1)/2 models. however, approach may still viable if model vectors (i.e., weight vectors) sparse. our implementation stores models in sparse form , can handle large-scale data.