Tractable downfall of basis pursuit in structured sparse 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_ | 1866910052095361024 |
|---|---|
| author | Marmary, Maya V. Grussler, Christian |
| author_facet | Marmary, Maya V. Grussler, Christian |
| contents | The problem of finding the sparsest solution to a linear underdetermined system of equations, often appearing, e.g., in data analysis, optimal control, system identification, or sensor selection problems, is considered. This non-convex problem is commonly solved by convexification via $\ell_1$-norm minimization, known as basis pursuit (BP). In this work, a class of structured matrices, representing the system of equations, is introduced for which (BP) tractably fails to recover the sparsest solution. In particular, this enables efficient identification of matrix columns corresponding to unrecoverable non-zero entries of the sparsest solution and determination of the uniqueness of such a solution. These deterministic guarantees complement popular probabilistic ones and provide insights into the a priori design of sparse optimization problems. As our matrix structures appear naturally in optimal control problems, we exemplify our findings based on a fuel-optimal control problem for a class of discrete-time linear time-invariant systems. Finally, we draw connections of our results to compressed sensing and common basis functions in geometric modeling. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_19126 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Tractable downfall of basis pursuit in structured sparse optimization Marmary, Maya V. Grussler, Christian Optimization and Control Machine Learning 90C06, 90C25, 90C26, 90C59, 49M25 The problem of finding the sparsest solution to a linear underdetermined system of equations, often appearing, e.g., in data analysis, optimal control, system identification, or sensor selection problems, is considered. This non-convex problem is commonly solved by convexification via $\ell_1$-norm minimization, known as basis pursuit (BP). In this work, a class of structured matrices, representing the system of equations, is introduced for which (BP) tractably fails to recover the sparsest solution. In particular, this enables efficient identification of matrix columns corresponding to unrecoverable non-zero entries of the sparsest solution and determination of the uniqueness of such a solution. These deterministic guarantees complement popular probabilistic ones and provide insights into the a priori design of sparse optimization problems. As our matrix structures appear naturally in optimal control problems, we exemplify our findings based on a fuel-optimal control problem for a class of discrete-time linear time-invariant systems. Finally, we draw connections of our results to compressed sensing and common basis functions in geometric modeling. |
| title | Tractable downfall of basis pursuit in structured sparse optimization |
| topic | Optimization and Control Machine Learning 90C06, 90C25, 90C26, 90C59, 49M25 |
| url | https://arxiv.org/abs/2503.19126 |