How does weight normalization work?
Your interpretation is quite correct. I could not understand how it would speed up the convergence though. What they are doing is basically re-assigning the magnitude of the weight vector (also called norm of the weight vector).

To put things in the perspective, the conventional approach to any Machine Learning cost function is to not only check the variations of the error with respect to a weight variable (gradient) but also add a normalization term which is $\lambda (w_0^2 + w_1^2 + \dots)$. This has got a few advantages:


The weights will not get exponentially high, even though if you make some mistake (generally bouncing off to exponential costs due to the wrong choice of learning rate).
Also, the convergence is quicker somehow (maybe because you have now 2 ways to control how much weight should be given to a feature. Unimportant features weights are not only getting reduced by normal gradient, but also the gradient of the normalization term $\lambda (w_0^2 + w_1^2 + \dots)$).


In this paper, they have proposed to fix the magnitude of the weight vector. This is a good way, although I am not sure if it is better than feature normalization. By limiting the magnitude of weight to $g$, they are fixing the resource available. The intuition is that, if you have 24 hours, you have to distribute this time among subjects. You'll distribute it in a way such that your grade/knowledge is maximized. So this might be helping in the faster convergence.

Also, another intuition would be, when you are subtracting the gradient from a weight vector you use a learning rate $\alpha$. This decides by how much weight-age of error you want to give which will be subsequently be subtracted from the weights. In this approach, you are not only subtracting the weights but also using another learning rate $g$ to scale the weight. I call this $g$ a learning rate because you can customize it which in turn customizes the value of weights which in turn affects the future reductions of weight gradient descent.

I am sure someone will post a better mathematical explanation of this stuff but this is all the intuition I could think of. I would be grateful if other intuitions and mathematical subtleties are pointed out. Hope this helps!