With increasing public demands for timely and accurate air pollution reporting, more air quality monitoring stations have been deployed by the governments in urban metropolises to increase the coverage of urban air pollution monitoring. However, due to systematic or accidental failures, some air pollution measurements obtained from these stations are found to have missing values, which will adversely affect the accuracy of any follow-up air pollution analyses and the quality of environmental decisionmakings. In this study, the mathematical property of air quality measurements is investigated to recover the missing air pollution values. A new algorithm, which matches meteorology data with air pollution data from different locations, to reconstruct the data matrix and recover missing entries, is proposed. Next, a Low Rank Matrix Completion problem is used to reconstruct the missing values, by transforming the data recovery problem to a sub-gradient primal-dual problem, based on the duality theory, with Singular Value Thresholding (SVT) employed to develop sub-optimal solutions. Next, an Interpolation-SVT (ISVT) approach is adopted to handle the sparsity of observed measurements. Comprehensive case studies are conducted to evaluate the performance of the proposed methods. The simulation results have demonstrated that the proposed SVT and ISVT methods can effectively recover the missing air pollution data and outperform existing interpolation methods and data imputation techniques. The proposed study can improve air pollution estimation and prediction whenever the low-rank data types that are used as proxies for air pollution estimation contain a lot of missing values and require data recovery.