Spectral Dependence of Convex Regularization: Fundamental Limits under Right-Rotationally Invariant Designs
We study the fundamental limits of convex-regularized estimation in high-dimensional linear regression with right-rotationally invariant design matrices. We show that the asymptotic risks of convex-penalized least squares estimators are lower bounded by the risk of an approximate message passing algorithm known as Baye...