Multiclass classification machines with the complexity of a single binary classifier

► One-versus-all scheme in multiclass classification. ► We operate a one-versus-all multiclass classifier, without training multiple binary classifiers. ► With the same classification accuracy, the computational complexity is orders of magnitude lower. ► We show that several celebrated coding of the multiclass labels have identical performance.