Noisy linear inverse problems under convex constraints: exact risk asymptotics in high dimensions

DOI10.1214/23-AOS2301OpenAlexW4387819051MaRDI QIDQ6183752FDOQ6183752

Authors: Qiyang Han 

Publication date: 4 January 2024

Published in: The Annals of Statistics (Search for Journal in Brave)

Abstract: In the standard Gaussian linear measurement model $Y=Xm{u}_0+xiinmathbb{R}^m$ with a fixed noise level $sigma>0$, we consider the problem of estimating the unknown signal $m{u}_0$ under a convex constraint $m{u}_{0}inK$, where $K$ is a closed convex set in $mathbb{R}^n$. We show that the risk of the natural convex constrained least squares estimator (LSE) $hatmu(sigma)$ can be characterized exactly in high dimensional limits, by that of the convex constrained LSE $hat{mu}_K^{mathsfseq}$ in the corresponding Gaussian sequence model at a different noise level. The characterization holds (uniformly) for risks in the maximal regime that ranges from constant order all the way down to essentially the parametric rate, as long as certain necessary non-degeneracy condition is satisfied for $hatmu(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 $mgg{n}^{1/3}$ samples in the noiseless setting, consistent signal recovery in the noisy setting requires as few as $mgglogn$ samples. Such a discrepancy occurs when the low and high noise risk behavior of $hat{mu}_K^{mathsfseq}$ differ significantly. In statistical languages, this occurs when $hat{mu}_K^{mathsfseq}$ estimates $0$ at a faster `adaptation rate' than the slower `worst-case rate' for general signals. Several other examples, including non-negative 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.

Full work available at URL: https://arxiv.org/abs/2201.08435

Recommendations

• A new perspective on least squares under convex constraint
• On the risk of convex-constrained least squares estimators under misspecification
• On risk bounds in isotonic and other shape restricted regression problems
• Geometric inference for general high-dimensional linear inverse problems
• Sharp MSE bounds for proximal denoising

zbMATH Keywords

high-dimensional asymptoticslinear inverse problemfixed-point equationGaussian sequence model

Mathematics Subject Classification ID

Nonparametric regression and quantile regression (62G08) Nonparametric hypothesis testing (62G10) Central limit and other weak theorems (60F05) Approximations to statistical distributions (nonasymptotic) (62E17)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A modern maximum-likelihood theory for high-dimensional logistic regression
• A multivariate analogue of the one-sided test
• A new perspective on least squares under convex constraint
• A precise high-dimensional asymptotic theory for boosting and minimum-\(\ell_1\)-norm interpolated classifiers
• Bayesian and frequentist regression methods
• Berry-Esseen bounds for Chernoff-type nonstandard asymptotics in isotonic regression
• Compressed sensing
• Concentration inequalities and model selection. Ecole d'Eté de Probabilités de Saint-Flour XXXIII -- 2003.
• Convex Recovery of a Structured Signal from Independent Random Linear Measurements
• Debiasing convex regularized estimators and interval estimation in linear models
• Exponential integrability and transportation cost related to logarithmic Sobolev inequalities
• From Denoising to Compressed Sensing
• From Gauss to Kolmogorov: localized measures of complexity for ellipses
• Fundamental barriers to high-dimensional regression with convex penalties
• Fundamental limits of symmetric low-rank matrix estimation
• Gaussian phase transitions and conic intrinsic volumes: steining the Steiner formula
• High dimensional robust M-estimation: asymptotic variance via approximate message passing
• High-dimensional asymptotics of likelihood ratio tests in the Gaussian sequence model under convex constraints
• Hypothesis tests for normal means constrained by linear inequalities
• Isotonic regression in general dimensions
• Limit distribution theory for block estimators in multiple isotonic regression
• Living on the edge: phase transitions in convex programs with random data
• Mathematical foundations of infinite-dimensional statistical models
• Mean field asymptotics in high-dimensional statistics: from exact results to efficient algorithms
• Multivariate extensions of isotonic regression and total variation denoising via entire monotonicity and Hardy-Krause variation
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Nonnegative Matrix Factorization Based on Alternating Nonnegativity Constrained Least Squares and Active Set Method
• Nonnegativity constraints in numerical analysis
• Nonparametric estimation under shape constraints. Estimators, algorithms and asymptotics
• Nonparametric shape-restricted regression
• On concentration for (regularized) empirical risk minimization
• On matrix estimation under monotonicity constraints
• On risk bounds in isotonic and other shape restricted regression problems
• On robust regression with high-dimensional predictors
• On the degrees of freedom in shrinkage estimation
• On the impact of predictor geometry on the performance on high-dimensional ridge-regularized generalized robust regression estimators
• Optimal errors and phase transitions in high-dimensional generalized linear models
• Oracle inequalities in empirical risk minimization and sparse recovery problems. École d'Été de Probabilités de Saint-Flour XXXVIII-2008.
• Precise Error Analysis of Regularized <inline-formula> <tex-math notation="LaTeX">$M$ </tex-math> </inline-formula>-Estimators in High Dimensions
• Recovering structured signals in noise: least-squares meets compressed sensing
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Sharp MSE bounds for proximal denoising
• Sharp Time–Data Tradeoffs for Linear Inverse Problems
• Sharp global convergence guarantees for iterative nonconvex optimization with random data
• Sharp oracle inequalities for least squares estimators in shape restricted regression
• Some inequalities for Gaussian processes and applications
• Stable signal recovery from incomplete and inaccurate measurements
• State evolution for approximate message passing with non-separable functions
• State evolution for general approximate message passing algorithms, with applications to spatial coupling
• The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing
• The LASSO Risk for Gaussian Matrices
• The Noise-Sensitivity Phase Transition in Compressed Sensing
• The convex geometry of linear inverse problems
• The distribution of the Lasso: uniform control over sparse balls and adaptive parameter tuning
• Universality laws for randomized dimension reduction, with applications
• Weak convergence and empirical processes. With applications to statistics

This page was built for publication: Noisy linear inverse problems under convex constraints: exact risk asymptotics in high dimensions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6183752)