The geometry and well-posedness of sparse regularized linear regression

Abstract In this work, we study the well-posedness of certain sparse regularized linear regression problems, i.e. the existence, uniqueness and continuity of the solution map with respect to the data. We focus on regularization functions that are convex piecewise linear, i.e. whose epigraphs are polyhedral. This includes LASSO, total variation (TV) on graphs and polyhedral constraints like nonnegativity and box constraints. We provide a geometric framework for these functions based on their connection to polyhedral sets and apply this to the study of the well-posedness of the corresponding sparse regularized linear regression problem. Using this framework, we provide geometric conditions for the well-posedness of regularized linear least squares problems and compare these conditions to those for smooth regularization. We furthermore construct various examples of ill-posed optimization problems commonly encountered in computed tomography. Finally, we show that verifying these conditions can be computationally difficult, i.e. co-NP-hard, for LASSO and (nonnegativity) constrained TV regularization.