TY - GEN

T1 - Precise high-dimensional error analysis of regularized M-estimators

AU - Thrampoulidis, Christos

AU - Abbasi, Ehsan

AU - Hassibi, Babak

N1 - KAUST Repository Item: Exported on 2022-06-28
Acknowledgements: This work was supported in part by the National Science Foundation under grants CNS-0932428, CCF-1018927, CCF-1423663 and CCF- 1409204, by a grant from Qualcomm Inc., by NASAs Jet Propulsion Laboratory through the President and Directors Fund, by King Abdulaziz University, and by King Abdullah University of Science and Technology.
This publication acknowledges KAUST support, but has no KAUST affiliated authors.

PY - 2016/4/7

Y1 - 2016/4/7

N2 - A general approach for estimating an unknown signal x0 n from noisy, linear measurements y = Ax0 + z m is via solving a so called regularized M-estimator: ◯ := arg minx (y-Ax)+λf(x). Here, is a convex loss function, f is a convex (typically, non-smooth) regularizer, and, λ > 0 a regularizer parameter. We analyze the squared error performance ◯ - x0.22 of such estimators in the high-dimensional proportional regime where m, n → ∞ and m/n → δ. We let the design matrix A have entries iid Gaussian, and, impose minimal and rather mild regularity conditions on the loss function, on the regularizer, and, on the distributions of the noise and of the unknown signal. Under such a generic setting, we show that the squared error converges in probability to a nontrivial limit that is computed by solving four nonlinear equations on four scalar unknowns. We identify a new summary parameter, termed the expected Moreau envelope, which determines how the choice of the loss function and of the regularizer affects the error performance. The result opens the way for answering optimality questions regarding the choice of the loss function, the regularizer, the penalty parameter, etc.

AB - A general approach for estimating an unknown signal x0 n from noisy, linear measurements y = Ax0 + z m is via solving a so called regularized M-estimator: ◯ := arg minx (y-Ax)+λf(x). Here, is a convex loss function, f is a convex (typically, non-smooth) regularizer, and, λ > 0 a regularizer parameter. We analyze the squared error performance ◯ - x0.22 of such estimators in the high-dimensional proportional regime where m, n → ∞ and m/n → δ. We let the design matrix A have entries iid Gaussian, and, impose minimal and rather mild regularity conditions on the loss function, on the regularizer, and, on the distributions of the noise and of the unknown signal. Under such a generic setting, we show that the squared error converges in probability to a nontrivial limit that is computed by solving four nonlinear equations on four scalar unknowns. We identify a new summary parameter, termed the expected Moreau envelope, which determines how the choice of the loss function and of the regularizer affects the error performance. The result opens the way for answering optimality questions regarding the choice of the loss function, the regularizer, the penalty parameter, etc.

UR - http://hdl.handle.net/10754/679377

UR - http://ieeexplore.ieee.org/document/7447033/

UR - http://www.scopus.com/inward/record.url?scp=84969816373&partnerID=8YFLogxK

U2 - 10.1109/ALLERTON.2015.7447033

DO - 10.1109/ALLERTON.2015.7447033

M3 - Conference contribution

SN - 9781509018239

SP - 410

EP - 417

BT - 2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton)

PB - IEEE

ER -