This solution is the one that finally fixed the GPS on my Note 4.
I had tried all the other options I could find on the internet (clearing cache, removing SD card, removing/reinserting SIM, calibrating compass, changing location modes, clearing AGPS data, etc., etc., etc.). None of them...