Optimal convex lifted sparse phase retrieval and PCA with an atomic matrix norm regularizer
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2021
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916212760379392 |
|---|---|
| author | McRae, Andrew D. Romberg, Justin Davenport, Mark A. |
| author_facet | McRae, Andrew D. Romberg, Justin Davenport, Mark A. |
| contents | We present novel analysis and algorithms for solving sparse phase retrieval and sparse principal component analysis (PCA) with convex lifted matrix formulations. The key innovation is a new mixed atomic matrix norm that, when used as regularization, promotes low-rank matrices with sparse factors. We show that convex programs with this atomic norm as a regularizer provide near-optimal sample complexity and error rate guarantees for sparse phase retrieval and sparse PCA. While we do not know how to solve the convex programs exactly with an efficient algorithm, for the phase retrieval case we carefully analyze the program and its dual and thereby derive a practical heuristic algorithm. We show empirically that this practical algorithm performs similarly to existing state-of-the-art algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2111_04652 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Optimal convex lifted sparse phase retrieval and PCA with an atomic matrix norm regularizer McRae, Andrew D. Romberg, Justin Davenport, Mark A. Statistics Theory We present novel analysis and algorithms for solving sparse phase retrieval and sparse principal component analysis (PCA) with convex lifted matrix formulations. The key innovation is a new mixed atomic matrix norm that, when used as regularization, promotes low-rank matrices with sparse factors. We show that convex programs with this atomic norm as a regularizer provide near-optimal sample complexity and error rate guarantees for sparse phase retrieval and sparse PCA. While we do not know how to solve the convex programs exactly with an efficient algorithm, for the phase retrieval case we carefully analyze the program and its dual and thereby derive a practical heuristic algorithm. We show empirically that this practical algorithm performs similarly to existing state-of-the-art algorithms. |
| title | Optimal convex lifted sparse phase retrieval and PCA with an atomic matrix norm regularizer |
| topic | Statistics Theory |
| url | https://arxiv.org/abs/2111.04652 |