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

arXiv: https://arxiv.org/abs/2507.18327 · HTML: https://mlsanity.com/paper/2507.18327/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 32 references that are in the map.
- First posted on arXiv 24 Jul 2025.

## Builds on (most cited first, 9 of 9)

- [Tensor Robust Principal Component Analysis with A New Tensor Nuclear Norm](https://mlsanity.com/paper/1804.03728/) (2018)
- [Hyperspectral Image Restoration via Total Variation Regularized Low-rank Tensor Decomposition](https://mlsanity.com/paper/1707.02477/) (2017)
- [Guaranteed Tensor Recovery Fused Low-rankness and Smoothness](https://mlsanity.com/paper/2302.02155/) (2023)
- [Framelet Representation of Tensor Nuclear Norm for Third-Order Tensor Completion](https://mlsanity.com/paper/1909.06982/) (2019)
- [Incoherence-Optimal Matrix Completion](https://mlsanity.com/paper/1310.0154/) (2013)
- [Exact Decomposition of Joint Low Rankness and Local Smoothness Plus Sparse Matrices](https://mlsanity.com/paper/2201.12592/) (2022)
- [Fast Noise Removal in Hyperspectral Images via Representative Coefficient Total Variation](https://mlsanity.com/paper/2211.01825/) (2022)
- [Robust Principal Component Analysis on Graphs](https://mlsanity.com/paper/1504.06151/) (2015)
- [Tensor Q-Rank: New Data Dependent Definition of Tensor Rank](https://mlsanity.com/paper/1910.12016/) (2019)

## Abstract (arXiv)

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 provided exact 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.