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

DOI10.1214/23-AOS2301arXiv2201.08435OpenAlexW4387819051MaRDI 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

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

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)