Nesting-structured nuclear norm minimization for spatially correlated matrix variate

Integrating the structure prior in modeling has achieved considerable attention in pattern recognition and computer vision. Most current state-of-the-art methods (such as low rank representation and structured sparsity) search for a structured metric to fit the structure of the estimated variate, which either bear high time complexity (e.g., compute singular value decomposition for large-scale matrices), or cannot effectively exploit structure information of a matrix variate. In this work, we introduce a nesting-structured nuclear norm to characterize the matrix variate with structure prior and provide a unified framework for solving nesting-structured nuclear norm minimization (NSNM) problem by resorting to an improved sub-gradient method. This not only takes local and global structures of the matrix variate into joint consideration, but also enjoys the lower time complexity than traditional nuclear norm minimization. The revealed statistical meaning explains the rationality of the proposed method. Moreover, we apply NSNM to matrix regression and completion problems, respectively. The extensive experiments for face recognition and large-scale matrix completion clearly demonstrate the superiority of NSNM over some existing methods.