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.
Ding et al. (Tue,) studied this question.