To achieve the robust tracking for a visual object under challenging conditions in the noisy, occlusion and the deformation, a novel visual object tracking method is proposed in this paper. By combining the Kernel Sparse Representation Classification (KSRC) and adaptive dictionary updating method under Normal Hedge framework, this method can handle tough situations like high inter-class similarities and drastically target appearance variations. Although the KSRC enhances classification performance, standard convex optimization is not fast enough for tracking in real time. Thus an efficient Kernel Random Coordinate Descent(KRCD) method is proposed to calculate the sparse coefficient vector, and the KRCD-SRC classification method is taken to calculate the loss value of each particle. In order to avoid the template drifting, the adaptive dictionary updating method is also given. At last, the states of the target are estimated by the Normal Hedge. Experiments show that the average computing frame rate of the proposed method is 14 frame/s when 50 particles are used. Extensive test results suggest that the proposed method outperforms several state-of-art tracking methods in many complex conditions.