Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
Consider this question: Why is the $\ell_1$ norm a surrogate for $\ell_0$? –  p.s. Jun 28 '12 at 16:33
    
You write "low-rank" but the formula has $\arg \max$... –  user31373 Jun 28 '12 at 23:01
    
@LeonidKovalev: Oops. Of course I meant $\min$. –  blubb Jun 29 '12 at 7:26

2 Answers 2

up vote 1 down vote accepted

Why does compressed sensing work? Because the $\ell_1$ ball in high dimensions is extremely "pointy" -- the extreme values of a linear function on this ball are very likely to be attained on the faces of low dimensions, those that consist of sparse vectors. When applied to matrices, the sparseness of the set of eigenvalues means low rank, as @mrig wrote before me.

share|improve this answer
    
Thank you, the reduction to sparse coding of eigenvalues was indeed the link I was looking for! –  blubb Jun 29 '12 at 7:39

The nuclear norm can be thought of as a convex relaxation of the number of non-zero eigenvalues (i.e. the rank).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.