Beyond Low-rankness: Guaranteed Matrix Recovery via Modified Nuclear Norm

Peng, Jiangjun; Luo, Yisi; Cao, Xiangyong; Xu, Shuang; Meng, Deyu

doi:10.24963/ijcai.2025/675

Beyond Low-rankness: Guaranteed Matrix Recovery via Modified Nuclear Norm

Jiangjun Peng, Yisi Luo, Xiangyong Cao, Shuang Xu, Deyu Meng

Download BibTeX Cite

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 6066-6074.

https://doi.org/10.24963/ijcai.2025/675

Keywords

Machine Learning: ML: Matrix/tensor methods
Computer Vision: CV: Low-level Vision
Data Mining: DM: Theoretical foundations of data mining
Computer Vision: CV: Machine learning for vision

Abstract

The nuclear norm (NN) has been widely explored in matrix recovery problems, such as Robust PCA and matrix completion, leveraging the inherent global low-rank structure of the data. In this study, we introduce a new modified nuclear norm (MNN) framework, where the MNN family norms are defined by adopting suitable transformations and performing the NN on the transformed matrix. The MNN framework offers two main advantages: (1) it jointly captures both local information and global low-rankness without requiring trade-off parameter tuning; (2) under mild assumptions on the transformation, we provide theoretical recovery guarantees for both Robust PCA and MC tasks—an achievement not shared by existing methods that combine local and global information. Thanks to its general and flexible design, MNN can accommodate various proven transformations, enabling a unified and effective approach to structured low-rank recovery. Extensive experiments demonstrate the effectiveness of our method. Code and supplementary material are available at https://github.com/andrew-pengjj/modified_nuclear_norm.

Jiangjun Peng, Yisi Luo, Xiangyong Cao, Shuang Xu, and Deyu Meng. 2025. Beyond Low-rankness: Guaranteed Matrix Recovery via Modified Nuclear Norm. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. IJCAI, 6066–6074. https://doi.org/10.24963/ijcai.2025/675

@inproceedings{ijcai2025p675,
  title     = {Beyond Low-rankness: Guaranteed Matrix Recovery via Modified Nuclear Norm},
  author    = {Peng, Jiangjun and Luo, Yisi and Cao, Xiangyong and Xu, Shuang and Meng, Deyu},
  booktitle = {Proceedings of the Thirty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-25}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {James Kwok},
  pages     = {6066--6074},
  year      = {2025},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2025/675},
  url       = {https://doi.org/10.24963/ijcai.2025/675},
}

TY  - CPAPER
TI  - Beyond Low-rankness: Guaranteed Matrix Recovery via Modified Nuclear Norm
AU  - Peng, Jiangjun
AU  - Luo, Yisi
AU  - Cao, Xiangyong
AU  - Xu, Shuang
AU  - Meng, Deyu
T2  - Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2025
SP  - 6066
EP  - 6074
DO  - 10.24963/ijcai.2025/675
UR  - https://doi.org/10.24963/ijcai.2025/675
ER  -