A method called "Robust PCA" solves the matrix decomposition problem
$$L^*, S^* = \arg \min_{L, S} \|L\|_* + \|S\|_1 \quad \text{s.t. } L + S = X$$
as a surrogate for the actual problem
$$L^*, S^* = \arg \min_{L, S} rank(L) + \|S\|_0 \quad \text{s.t. } L + S = X,$$ i.e. the actual goal is to decompose the data matrix $X$ into a low-rank signal matrix $L$ and a sparse noise matrix $S$. In this context: why is the nuclear norm a good approximation for the rank of a matrix? I can think of matrices with low nuclear norm but high rank and vice-versa. Is there any intuition one can appeal to?