Structured sparsity, as an extension of standard sparsity, has shown the outstanding performance when dealing with some highly correlated variables in computer vision and pattern recognition. However, the traditional mixed (L, L) or (L, L) group norm becomes weak in characterizing the internal structure of each group, since they cannot alleviate the correlations between variables. Recently, nuclear norm has been validated to be useful for depicting a spatially structured matrix variable. It considers the global structure of the matrix variable but overlooks the local structure. To combine the advantages of structured sparsity and nuclear norm, this paper presents a tree-structured nuclear norm approximation (TSNA) model assuming that the representation residual with tree-structured prior is a random matrix variable and follows a dependent matrix distribution. The extended alternating direction method of multipliers is utilized to solve the proposed model. An efficient bound condition based on the extended restricted isometry constants is provided to show the exact recovery of the proposed model under the given noisy case. In addition, TSNA is connected with some newest methods, such as sparse representation-based classifier, nuclear-L norm joint regression, and nuclear norm-based matrix regression, which can be regarded as the special cases of TSNA. Experiments with face reconstruction and recognition demonstrate the benefits of TSNA over other approaches.