Burer-Monteiro factorizability of nuclear norm regularized optimization
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909980541583360 |
|---|---|
| author | Ouyang, Wenqing Pong, Ting Kei Yue, Man-Chung |
| author_facet | Ouyang, Wenqing Pong, Ting Kei Yue, Man-Chung |
| contents | This paper studies the relationship between the nuclear norm-regularized minimization problem, which minimizes the sum of a $C^2$ function $h$ and a positive multiple of the nuclear norm, denoted by $f$, and its factorized problem obtained by the Burer-Monteiro technique. We are interested in deriving conditions that ensure every second-order stationary point of the factorized problem corresponds to a global minimizer of $f$, a property we call the $r$-factorizability of $f$ in this paper. Under suitable restricted isometry property (RIP) type assumptions on $h$, we prove the $r$-factorizability of $f$. Moreover, the RIP constant in our paper is tight, in the sense that we can construct concrete examples of $f$ that fail to be $r$-factorizable when the RIP constant is below the threshold. Our technique for constructing such examples is novel and may be of independent interest: specifically, we use a variant of the Von Neumann's trace inequality and relate the existence of such examples to the optimal value of a quadratic program involving the RIP constant, then we explicitly solve this optimization problem to detect all the possible counterexamples. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_00349 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Burer-Monteiro factorizability of nuclear norm regularized optimization Ouyang, Wenqing Pong, Ting Kei Yue, Man-Chung Optimization and Control This paper studies the relationship between the nuclear norm-regularized minimization problem, which minimizes the sum of a $C^2$ function $h$ and a positive multiple of the nuclear norm, denoted by $f$, and its factorized problem obtained by the Burer-Monteiro technique. We are interested in deriving conditions that ensure every second-order stationary point of the factorized problem corresponds to a global minimizer of $f$, a property we call the $r$-factorizability of $f$ in this paper. Under suitable restricted isometry property (RIP) type assumptions on $h$, we prove the $r$-factorizability of $f$. Moreover, the RIP constant in our paper is tight, in the sense that we can construct concrete examples of $f$ that fail to be $r$-factorizable when the RIP constant is below the threshold. Our technique for constructing such examples is novel and may be of independent interest: specifically, we use a variant of the Von Neumann's trace inequality and relate the existence of such examples to the optimal value of a quadratic program involving the RIP constant, then we explicitly solve this optimization problem to detect all the possible counterexamples. |
| title | Burer-Monteiro factorizability of nuclear norm regularized optimization |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2505.00349 |