Recovering the low-rank structure of data matrix from sparse errors arises in the principal component pursuit(PCP). This paper exploits the higher-order generalization of matrix recovery,named higher-order principal component pursuit(HOPCP), since it is critical in multi-way data analysis. Unlike the convexification(nuclear norm) for matrix rank function, the tensorial nuclear norm is still an open problem. While existing preliminary works on the tensor completion field provide a viable way to indicate the low complexity estimate of tensor, therefore, the paper focuses on the low multi-linear rank tensor and adopt its convex relaxation to formulate the convex optimization model of HOPCP. The paper further propose two algorithms for HOPCP based on alternative minimization scheme: the augmented Lagrangian alternating direction method(ALADM) and its truncated higher-order singular value decomposition(ALADM-THOSVD) version. The former can obtain a high accuracy solution while the latter is more efficient to handle the computationally intractable problems. Experimental results on both synthetic data and real magnetic resonance imaging data show the applicability of our algorithms in high-dimensional tensor data processing. Recovering the low-rank structure of data matrix from sparse errors arises in the principal component pursuit (PCP). This paper exploits the higher-order generalization of matrix recovery, named higher-order principal component pursuit (PCP), since it is critical in While the preliminary nuclear works are still an open problem on tensor completion field provide a viable way to indicate the low complexity estimate of tensor, therefore, the paper focuses on the low multi-linear rank tensor and adopt its convex relaxation to formulate the convex optimization model of HOPCP. The paper further proposes two algorithms for HOPCP based on alternative minimization scheme: the augmented Lagrangian alternating direction method (ALADM) and its truncated higher-order singular value decomposition (ALADM-THOSVD) version. The former can obtain a high accuracy solution while the latter is more efficient to handle the computationally intractable problems. Experimental results on both synthetic data and real magnetic resonance imaging data show the applicability of our algorithms in high-dimensional tensor data processing.