The goal of deconvolution is in estimating the distribution of a random variable based on its noisy observations. The goal of matrix estimation is in estimating the entries of a large matrix from observed entries, which are noisy versions of entries in a small fraction of the entire matrix. We study the rate of convergence for estimation of matrices with a certain monotonicity property. It turns out to be equivalent to solving a robust version of the deconvolution problem. As the main result of this paper, we provide a simple, intuitive algorithm for matrix estimation which extends the works by Fan (1991) and Delaigle et al. (2008). We show that our computationally efficient method achieves near optimal minimax rate for the matrix estimation as well as robust deconvolution. This rate is within a constant factor to the rate achieved by the kernel deconvolution estimator in the classical setup.
Monotone Matrix Estimation via Robust Deconvolution
The goal of deconvolution is in estimating the distribution of a random variable based on its noisy observations. The goal of matrix estimation is in estimating the entries of a large matrix from observed entries, which are noisy versions of entries in a small fraction of the entire matrix. We study the rate of convergence for estimation of matrices with a certain monotonicity property. It turns out to be equivalent to solving a robust version of the deconvolution problem. As the main result of this paper, we provide a simple, intuitive algorithm for matrix estimation which extends the works by Fan (1991) and Delaigle et al. (2008). We show that our computationally efficient method achieves near optimal minimax rate for the matrix estimation as well as robust deconvolution. This rate is within a constant factor to the rate achieved by the kernel deconvolution estimator in the classical setup.