First order algorithms for computing linear and polyhedral estimates
It was recently shown [6, 8] that “properly built” linear and polyhedral estimates nearly attain minimax accuracy bounds in the problem of recovery of unknown signal from noisy observations of linear images of the signal when the signal set is an ellitope. However, design of nearly optimal estimates...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Université de Montpellier
2024-10-01
|
| Series: | Open Journal of Mathematical Optimization |
| Online Access: | https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.35/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1825205135538651136 |
|---|---|
| author | Bekri, Yannis Juditsky, Anatoli Nemirovski, Arkadi |
| author_facet | Bekri, Yannis Juditsky, Anatoli Nemirovski, Arkadi |
| author_sort | Bekri, Yannis |
| collection | DOAJ |
| description | It was recently shown [6, 8] that “properly built” linear and polyhedral estimates nearly attain minimax accuracy bounds in the problem of recovery of unknown signal from noisy observations of linear images of the signal when the signal set is an ellitope. However, design of nearly optimal estimates relies upon solving semidefinite optimization problems with matrix variables, what puts the synthesis of such estimates beyond the reach of the standard Interior Point algorithms of semidefinite optimization even for moderate size recovery problems. Our goal is to develop First Order Optimization algorithms for the computationally efficient design of linear and polyhedral estimates. In this paper we (a) explain how to eliminate matrix variables, thus reducing dramatically the design dimension when passing from Interior Point to First Order optimization algorithms and (b) develop and analyse a dedicated algorithm of the latter type — Composite Truncated Level method. |
| format | Article |
| id | doaj-art-00946a2c5369483f9e90a8bb359b450e |
| institution | Kabale University |
| issn | 2777-5860 |
| language | English |
| publishDate | 2024-10-01 |
| publisher | Université de Montpellier |
| record_format | Article |
| series | Open Journal of Mathematical Optimization |
| spelling | doaj-art-00946a2c5369483f9e90a8bb359b450e2025-02-07T14:01:17ZengUniversité de MontpellierOpen Journal of Mathematical Optimization2777-58602024-10-01511510.5802/ojmo.3510.5802/ojmo.35First order algorithms for computing linear and polyhedral estimatesBekri, Yannis0Juditsky, Anatoli1Nemirovski, Arkadi2LJK, Université Grenoble Alpes, Campus de Saint-Martin-d’Hères, 38401 FranceLJK, Université Grenoble Alpes, Campus de Saint-Martin-d’Hères, 38401 FranceArkadi Nemirovski, Georgia Institute of Technology, Atlanta, Georgia 30332, USAIt was recently shown [6, 8] that “properly built” linear and polyhedral estimates nearly attain minimax accuracy bounds in the problem of recovery of unknown signal from noisy observations of linear images of the signal when the signal set is an ellitope. However, design of nearly optimal estimates relies upon solving semidefinite optimization problems with matrix variables, what puts the synthesis of such estimates beyond the reach of the standard Interior Point algorithms of semidefinite optimization even for moderate size recovery problems. Our goal is to develop First Order Optimization algorithms for the computationally efficient design of linear and polyhedral estimates. In this paper we (a) explain how to eliminate matrix variables, thus reducing dramatically the design dimension when passing from Interior Point to First Order optimization algorithms and (b) develop and analyse a dedicated algorithm of the latter type — Composite Truncated Level method.https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.35/ |
| spellingShingle | Bekri, Yannis Juditsky, Anatoli Nemirovski, Arkadi First order algorithms for computing linear and polyhedral estimates Open Journal of Mathematical Optimization |
| title | First order algorithms for computing linear and polyhedral estimates |
| title_full | First order algorithms for computing linear and polyhedral estimates |
| title_fullStr | First order algorithms for computing linear and polyhedral estimates |
| title_full_unstemmed | First order algorithms for computing linear and polyhedral estimates |
| title_short | First order algorithms for computing linear and polyhedral estimates |
| title_sort | first order algorithms for computing linear and polyhedral estimates |
| url | https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.35/ |
| work_keys_str_mv | AT bekriyannis firstorderalgorithmsforcomputinglinearandpolyhedralestimates AT juditskyanatoli firstorderalgorithmsforcomputinglinearandpolyhedralestimates AT nemirovskiarkadi firstorderalgorithmsforcomputinglinearandpolyhedralestimates |