Abstract
The nuclear norm (NN) has been widely explored in matrix recovery problems,such as Robust PCA and matrix completion, leveraging the inherent globallow-rank structure of the data. In this study, we introduce a new modifiednuclear norm (MNN) framework, where the MNN family norms are defined byadopting suitable transformations and performing the NN on the transformedmatrix. The MNN framework offers two main advantages: (1) it jointly capturesboth local information and global low-rankness without requiring trade-offparameter tuning; (2) Under mild assumptions on the transformation, we providedexact theoretical recovery guarantees for both Robust PCA and MC tasks-anachievement not shared by existing methods that combine local and globalinformation. Thanks to its general and flexible design, MNN can accommodatevarious proven transformations, enabling a unified and effective approach tostructured low-rank recovery. Extensive experiments demonstrate theeffectiveness of our method. Code and supplementary material are available athttps://github.com/andrew-pengjj/modified_nuclear_norm.