dorsal/arxiv
View SchemaGlobal convergence of the subgradient method for robust signal recovery
| Authors | Zesheng Cai, Lexiao Lai, Tiansheng Li |
|---|---|
| Categories | |
| ArXiv ID | 2601.10062vv2 |
| URL | https://arxiv.org/abs/2601.10062 |
| License | http://arxiv.org/licenses/nonexclusive-distrib/1.0/ |
Abstract
We study the subgradient method for factorized robust signal recovery problems, including robust PCA, robust phase retrieval, and robust matrix sensing. These objectives are nonsmooth and nonconvex, and may have unbounded sublevel sets, so standard arguments for analyzing first-order optimization algorithms based on descent and coercivity do not apply. For locally Lipschitz semialgebraic objectives, we develop a convergence framework under the assumption that continuous-time subgradient trajectories are bounded: for sufficiently small step sizes of order \(1/k\), any subgradient sequence remains bounded and converges to a critical point. We verify this trajectory boundedness assumption for the robust objectives by adapting and extending existing trajectory analyses, requiring only a mild nondegeneracy condition in the matrix sensing case. Finally, for rank-one symmetric robust PCA, we show that the subgradient method avoids spurious critical points for almost every initialization, and therefore converges to a global minimum under the same step-size regime.
{
"annotation_id": "b7bac6fb-aa92-422d-81f5-3b10a6a1727b",
"date_created": "2026-02-17T05:53:23.796000Z",
"date_modified": "2026-02-17T05:53:23.796000Z",
"file_hash": "d82fc8f555950c4f0e726c9df7f812b48fcc607a4cf3454a8abf1899d16e48f5",
"private": false,
"record": {
"abstract": "We study the subgradient method for factorized robust signal recovery problems, including robust PCA, robust phase retrieval, and robust matrix sensing. These objectives are nonsmooth and nonconvex, and may have unbounded sublevel sets, so standard arguments for analyzing first-order optimization algorithms based on descent and coercivity do not apply. For locally Lipschitz semialgebraic objectives, we develop a convergence framework under the assumption that continuous-time subgradient trajectories are bounded: for sufficiently small step sizes of order \\(1/k\\), any subgradient sequence remains bounded and converges to a critical point. We verify this trajectory boundedness assumption for the robust objectives by adapting and extending existing trajectory analyses, requiring only a mild nondegeneracy condition in the matrix sensing case. Finally, for rank-one symmetric robust PCA, we show that the subgradient method avoids spurious critical points for almost every initialization, and therefore converges to a global minimum under the same step-size regime.",
"arxiv_id": "2601.10062",
"authors": [
"Zesheng Cai",
"Lexiao Lai",
"Tiansheng Li"
],
"categories": [
"math.OC"
],
"license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
"title": "Global convergence of the subgradient method for robust signal recovery",
"url": "https://arxiv.org/abs/2601.10062",
"version": "v2"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "dc99336e-dbee-4d6b-9751-96ee4f80b293",
"id": "arXiv Dataset",
"type": "Model",
"variant": "snapshot-2026-01-17",
"version": "0.1.0"
},
"user_id": 1000002
}