Sharpness and well-conditioning of nonsmooth convex formulations in statistical signal recovery
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916328646901760 |
|---|---|
| author | Ding, Lijun Wang, Alex L. |
| author_facet | Ding, Lijun Wang, Alex L. |
| contents | 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 $\ell_p$ or Schatten-$p$ norms ($p\in[1,2]$) of a nonsmooth formulation 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 well-controlled. Algorithmically, such a result ensures that a new restarted mirror descent method achieves nearly-dimension-independent linear convergence to the signal. This new first-order method is general and applies to any sharp convex function in an $\ell_p$ or Schatten-$p$ norm ($p\in[1,2]$). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_06873 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Sharpness and well-conditioning of nonsmooth convex formulations in statistical signal recovery Ding, Lijun Wang, Alex L. Optimization and Control 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 $\ell_p$ or Schatten-$p$ norms ($p\in[1,2]$) of a nonsmooth formulation 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 well-controlled. Algorithmically, such a result ensures that a new restarted mirror descent method achieves nearly-dimension-independent linear convergence to the signal. This new first-order method is general and applies to any sharp convex function in an $\ell_p$ or Schatten-$p$ norm ($p\in[1,2]$). |
| title | Sharpness and well-conditioning of nonsmooth convex formulations in statistical signal recovery |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2307.06873 |