Clock synchronization has been a challenging task in the design of wireless networks because the synchronization accuracy suffers from uncertain transmission delay and/or packet loss due to poor wireless channel conditions. To address this problem, this paper develops a robust clock synchronization schemes based on matrix completion theory to improve the accuracy in presence of random transmission delay and packet loss. We propose a matrix completion based maximum likelihood estimator (MC-MLE) to estimate the clock offset and clock skew under Gaussian transmission delay model. Thanks to the denoise feature of matrix completion, the proposed schemes outperform the maximum likelihood estimator (MLE) in the presence of packet loss and random transmission delay. That is, the proposed schemes are closer to the Cramer-Rao lower bound (CRLB) than the MLE when the timestamp packets are randomly corrupted. The robustness and accuracy of the proposed schemes are validated by numerical results.