The nuclear norm, denoted $\|\cdot\|_*$ is a good surrogate for the $rank$ when minimizing problems like $$\label{pb1}\tag{1} \min_X rank(X) : AX = B $$ Here, we're trying to find an matrix X with low rank such that $AX=B$. If I recall correctly, when the singular values of $X$ are bounded above by 1, you can replace $rank$ by $\|\cdot\|_*$ in the problem \eqref{pb1}.

What about the Frobenius norm ? Can the Frobenius norm be a good surrogate to the nuclear norm ? Under which assumptions ?

Since we have $\|X\|_* = \min_{X=UV^\top} \|U\|_F\|V\|_F$, in particular we have $\|XX^\top\|_* = \|X\|_F^2$.

Then, because $\|X\|_1\le 1$, we also have $\|XX^\top\|_1\le 1$.

So, this is pretty direct, no ? Frobenius norm is also a good surrogate ?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.