Effective Condition Number Bounds for Convex Regularization

2017/07/05 by Amelunxen, Dennis, Lotz, Martin, Walvin, Jake
#52A22 #53C65 #60B20 #60D05 #90C25 #FOS: Mathematics #Numerical Analysis (math.NA)

paper · doi:10.48550/arxiv.1707.01775

Abstract

We derive bounds relating Renegar's condition number to quantities that govern the statistical performance of convex regularization in settings that include the ℓ₁-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.

Related

• Living on the edge: Phase transitions in convex programs with random data
• A Reduced-Space Algorithm for Minimizing ℓ₁-Regularized Convex Functions
• Average-case thresholds for exact regularization of linear programs
• A theory of optimal convex regularization for low-dimensional recovery
• Don't relax: early stopping for convex regularization