How to implement a gradient based Hough transform
I am a bit confused by your question.  Hough transform is used to detect lines, not edges.

If all you want is an edge map, you should simply threshold the gradient magnitude, or use something more fancy like the Canny edge detector.

If you want to detect straight lines, you would be better off starting with an edge map, and then using the hough function if the Image Processing toolbox, if you have access to it. The problem with doing a Hough transform on the gradient is that edge pixels forming a straight line might have opposite gradient orientations.  For example, consider a checkerboard pattern.  A edge between two rows of squares flips orientation depending on whether you have a black square above and a white square below, or the other way around.

As to your implementation, I think the problem is that the bins in your Hough matrix are too small.  Essentially the bin size in the rho dimension is 1, and the bin size in the theta dimension is less than 2 degrees.  That means that the gradient orientations must alight very precisely to form a line, which rarely happens in practice.  If you caculate rho_idx and theta_idx so that the bins are larger, that will make your line detector more tolerant to errors, and you might get better lines.