Sharpness and Conditioning of Nonsmooth Convex Formulations in Statistical Signal Recovery

Abstract

Abstract. We study a sample complexity vs. conditioning tradeoff in modern signal recovery problems (including sparse recovery, low-rank matrix sensing, covariance estimation, and abstract phase retrieval), where convex optimization problems are built from sampled observations. We begin by introducing a set of condition numbers related to sharpness in the [Formula: see text] or Schatten-1 norm of nonsmooth formulations for these problems. Then, we show that these condition numbers become dimension- independent constants in each of the example signal recovery problems once the sample size exceeds some constant multiple of the recovery threshold. Structurally, this result ensures that the inaccuracy in the recovered signal due to both observation noise and optimization error is controlled. Algorithmically, such a result ensures that a new restarted mirror descent method achieves nearly dimension-independent linear convergence to the signal in terms of iterations. This new first-order method is general and applies to any sharp convex function in an [Formula: see text] or Schatten-[Formula: see text] norm for [Formula: see text].