Effective Condition Number Bounds for Convex Regularization

We derive bounds relating Renegar's condition number to quantities that govern the statistical performance of convex regularization in settings that include $\ell_1$-analysis minimization. Using results from conic integral geometry, we show that the bounds can be made to depend only on a random projection, or restriction, of the analysis operator to a lower dimensional space, and can still be effective if these operators are ill-conditioned. As an application, we get new bounds for the undersampling phase transition of composite convex regularizers. Key tools in the analysis are Slepian's inequality, interpreted as monotonicity property of moment functionals, and the kinematic formula from integral geometry.