TY - JOUR
T1 - Effective Condition Number Bounds for Convex Regularization
AU - Amelunxen, Dennis
AU - Lotz, Martin
AU - Walvin, Jake
PY - 2020/4
Y1 - 2020/4
N2 - We derive bounds relating Renegar's condition number to quantities that govern the statistical performance of convex regularization in settings that include the l(1)-analysis setting. 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 and the kinematic formula from integral geometry.
AB - We derive bounds relating Renegar's condition number to quantities that govern the statistical performance of convex regularization in settings that include the l(1)-analysis setting. 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 and the kinematic formula from integral geometry.
KW - Convex regularization
KW - compressed sensing
KW - integral geometry
KW - convex optimization
KW - dimension reduction
KW - PHASE-TRANSITIONS
KW - COMPLEXITY
UR - http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=LinksAMR&SrcApp=PARTNER_APP&DestLinkType=FullRecord&DestApp=WOS&KeyUT=000522202300033
U2 - 10.1109/TIT.2020.2965720
DO - 10.1109/TIT.2020.2965720
M3 - 21_Publication in refereed journal
VL - 66
SP - 2501
EP - 2516
JO - IEEE Transactions on Information Theory
JF - IEEE Transactions on Information Theory
SN - 0018-9448
IS - 4
ER -