Report it and get it fixed. It'll be sorted under warranty, and it'll likely be a new motherboard (i.e. new phone internals). They'll switch out the existing internals for a new everything. It does mean you need to do a full complete backup.
It's a hardware issue, not software. Download GPS Status & Toolbox. The app will confirm it, and then it'll be a clear process to fix it. If you're not getting any GPS fixes, then your GPS module is busted and they'll either replace it or replace the whole mobo as explained above. o point waiting for a fix as it wont come.
It's likely your WiFi and other nearby WiFi and/or bluetooth devices are what cause the location to update - so it looks like it's working but it's not the GPS giving you location updates- so you never really "lose signal", because you dont have signal to begin with.
If you disable WiFi/bluetooth scanning (which they say "improves the accuracy of your location"), then it'll be pretty obvious. By enabling the wifi/bt scanning, you might be masking what's otherwise a pretty obvious problem - as was the case with me.
Samsung's troubleshooting steps suggests to enabling the setting, which causes some users to stop asking questions (especially if you live in a very densely populated city like London where there's a WiFi or bluetooth hotspot or device for every sq.ft of the city!) - it'll just look like your location works until you go for a drive at night somewhere remote and end up driving south thinking you're heading north.
