NNDSVD to initialize Convex-NMF
I've played before with a library for ("classic") NMF from University of Vienna: libNMF

While it wasn't useful for me at first, since they don't implement Convex-NMF, I had a look at their NNDSVD implementation.
They simply replace all negative values and values smaller than the machine epsilon with zero.

I tried that, but it fails, since the update rules for Convex-NMF are such that I get a division by zero. Since they add 0.2 to all values in their proposed initialization scheme (for "smoothing"), I just did the same here.

It works, the precision is worse than expected (a bit worse than k-means, which is my best approach for now), but I'll tweak it a bit more.