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 (L1, L2) or (L1, L∞) group norm becomes weak in characterizing the internal structure of each group since they cannot alleviate the correla-tions between variables. Recently, nuclear norm has been vali-dated 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 as-suming that the representation residual with tree-structured prior is a random matrix variable and follows a dependent matrix dis-tribution. The Extended Alternating Direction Method of Multi-pliers (EADMM) is utilized to solve the proposed model. An effi-cient 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 (SRC), nuclear-L1 norm joint regression (NL1R) and nuclear norm based matrix regression (NMR), which can be re-garded as the special cases of TSNA. Experiments with face re-construction and recognition demonstrate the benefits of TSNA over other approaches.