NOISY LINEAR INVERSE PROBLEMS UNDER CONVEX CONSTRAINTS: EXACT RISK ASYMPTOTICS IN HIGH DIMENSIONS

• 成果类型: Article
• 署名作者: Han, Qiyang
• 署名单位: Rutgers University System; Rutgers University New Brunswick
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• DOI: 10.1214/23-AOS2301
• 发表日期: 2023
• 页码: 1611-1638
• 关键词: least-squares; isotonic regression; robust regression; signal recovery; state evolution; bounds; MONOTONICITY; inequalities; estimators; geometry

摘要

In the standard Gaussian linear measurement model Y = X mu 0 + xi is an element of Rm with a fixed noise level sigma > 0, we consider the problem of estimating the unknown signal mu 0 under a convex constraint mu 0 is an element of K , where K is a closed convex set in Rn. We show that the risk of the natural convex constrained least squares estimator (LSE) mu?(sigma) can be characterized exactly in high dimensional limits, by that of the convex constrained LSE mu ?seQ K in the corresponding Gaussian sequence model at a different noise level. Formally, we show that II mu?(sigma) - mu 02/(nr2) -> 1 in probability, n where rn2 > 0 solves the fixed-point equation EII mu ?seQ(/(rn2+ sigma 2)/(m/n))-mu 02 =nr2 K n. This characterization holds (uniformly) for risks rn2 in the maximal regime that ranges from constant order all the way down to essentially the parametric rate, as long as certain necessary nondegeneracy condition is satisfied for mu?(sigma ). The precise risk characterization reveals a fundamental difference between noiseless (or low noise limit) and noisy linear inverse problems in terms of the sample complexity for signal recovery. A concrete example is given by the isotonic regression problem: While exact recovery of a general monotone signal requires m >> n1/3 samples in the noiseless setting, consistent signal recovery in the noisy setting requires as few as m >> log n samples. Such a discrepancy occurs when the low and high noise risk behavior of mu ?seQ K differ significantly. In statistical languages, this occurs when mu ?seQ K estimates 0 at a faster adaptation rate than the slower worst-case rate for general signals. Several other examples, including nonnegative least squares and generalized Lasso (in constrained forms), are also worked out to demonstrate the concrete applicability of the theory in problems of different types. The proof relies on a collection of new analytic and probabilistic results concerning estimation error, log likelihood ratio test statistics and degree-of freedom associated with mu ?seQ K , regarded as stochastic processes indexed by the noise level. These results are of independent interest in and of themselves.