Abstract Trace norm based rank regularization techniques have been successfully applied to learn a low-rank recovery for high-dimensional noise data. In many applications, it is desirable to add new samples to previously recovered data which is known as outof-sample data recovery problem. However, traditional trace norm based regularization methods can not naturally cope with new samples and thus fail to deal with out-of-sample data recovery. In this paper, we propose a new robust out-of-sample data recovery (ROSR) model for trace norm based regularization methods. An effective iterative algorithm, with the proof of convergence, is presented to find the optimal solution of ROSR problem. As an application, we apply our ROSR to image classification task. Experimental results on six image datasets demonstrate the effectiveness and benefits of the proposed ROSR method.