Effective Condition Number Bounds for Convex Regularization

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)2501-2516
Journal / PublicationIEEE Transactions on Information Theory
Volume66
Issue number4
Online published10 Jan 2020
Publication statusPublished - Apr 2020

Abstract

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.

Research Area(s)

  • Convex regularization, compressed sensing, integral geometry, convex optimization, dimension reduction, PHASE-TRANSITIONS, COMPLEXITY

Citation Format(s)

Effective Condition Number Bounds for Convex Regularization. / Amelunxen, Dennis; Lotz, Martin; Walvin, Jake.

In: IEEE Transactions on Information Theory, Vol. 66, No. 4, 04.2020, p. 2501-2516.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review