This work considers the exploitation of unmanned aerial vehicles (UAVs) as flying relays to provide a capacity boost to ground users, which suffer from shadowing due to the complex, and usually irregular, terrain structure. To optimize the position of the flying relay, we propose to learn a detailed air-to-ground radio map based on insufficient measurement samples. This is challenging because even the exact user location may not be available. We establish the connection between radio map reconstruction and non-parametric source localization based on matrix decomposition techniques. We study a tensor decomposition method to help localize a target user, and a joint clustering-and-regression algorithm to classify the shadowing status. We demonstrate the efficiency of optimizing the UAV position over complex terrain.