Deconvolution with Unknown Error Distribution Interpreted as Blind Isotonic Regression

Abstract

Deconvolution is a statistical inverse problem to estimate the distribution of a random variable based on its noisy observations. Despite the extensive studies on the topic, deconvolution with unknown noise distribution remains as a notoriously hard problem. We propose a matrix-based viewpoint for collective deconvolution that subsumes the setup with repeated measurements as a special case. As the main result, we describe a simple algorithm that partially utilizes matrix structure to solve deconvolution problem and provide non-asymptotic error analysis for the algorithm. We show that the proposed algorithm achieves the minimax optimal rate for deconvolution in a restricted sense. We also remark the connection between the collective deconvolution and the so-called statistical seriation as a byproduct or our matrix viewpoint. We conjecture that the link suggests that collective deconvolution, as well as deconvolution with repeated measurements, is intrinsically much easier than usual deconvolution of a single distribution.

arXiv comment25 pages + 40 pages (appendix)

References in corpus (9)

• Matrix estimation by Universal Singular Value Thresholding
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Estimation of high-dimensional low-rank matrices
• On deconvolution with repeated measurements
• Nonparametric graphon estimation
• On deconvolution of distribution functions
• Regularized Minimax Conditional Entropy for Crowdsourcing
• Achieving Budget-optimality with Adaptive Schemes in Crowdsourcing
• Estimating network edge probabilities by neighborhood smoothing