Millimeter-wave (mmWave) communication is the rising technology for next-generation wireless transmission. Benefited by its abundant bandwidth and short wavelength, mmWave is advanced in multi-gigabit transmittability and beamforming. In contrast, the short wavelength also makes mmWave easily blocked by obstacles. In order to bypass these obstacles, relays are widely needed in mmWave communications. Unmanned autonomous vehicles (UAVs), such as drones and self-driving robots, enable the mobile relays in real applications. Nevertheless, it is challenging for a UAV to find its optimal relay location automatically. On the one hand, it is difficult to find the location accurately due to the complex and dynamic wireless environment; on the other hand, most applications require the relay to forward data immediately, so the autonomous process should be fast. To tackle this challenge, we propose a novel method AutoRelay specialized for mmWave communications. In AutoRelay, the UAV samples the link qualities of mmWave beams while moving. Based on the real-time sampling, the UAV gradually adjusts its path to approach the optimal location by leveraging compressive sensing theory to estimate the link qualities in candidate space, which increases the accuracy and save the time. Performance results demonstrate that AutoRelay outperforms existing methods in achieving an accurate and efficient relay strategy.