Solving Sparsity Constrained PCA, Regression, and QCQP via the Spartrahedron
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915873722204160 |
|---|---|
| author | Cifuentes, Diego Li, Zhuorui |
| author_facet | Cifuentes, Diego Li, Zhuorui |
| contents | Sparsity is a fundamental modeling principle in statistics, signal processing, and data science. However, optimization with sparsity constraints is notoriously difficult. We introduce a new convex relaxation framework for {sparse quadratically constrained quadratic programs} (QCQPs), a class that subsumes sparse regression, sparse principal component analysis (PCA), and related problems. Our approach is based on a novel convex cone, the spartrahedron, which exactly characterizes sparsity at the matrix level. This leads to a semidefinite programming (SDP) relaxation that is tight whenever its solution is rank-one, providing a simple certificate of global optimality. We establish theoretical guarantees, including approximation bounds and exactness regions for sparse PCA and sparse ridge regression, as well as a general stability result under perturbations. Numerical experiments on sparse PCA, sparse regression, RIP constant estimation, and sparse canonical correlation analysis (CCA) demonstrate the practical success of our methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_18215 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Solving Sparsity Constrained PCA, Regression, and QCQP via the Spartrahedron Cifuentes, Diego Li, Zhuorui Optimization and Control 90C20, 90C22, 90C25 Sparsity is a fundamental modeling principle in statistics, signal processing, and data science. However, optimization with sparsity constraints is notoriously difficult. We introduce a new convex relaxation framework for {sparse quadratically constrained quadratic programs} (QCQPs), a class that subsumes sparse regression, sparse principal component analysis (PCA), and related problems. Our approach is based on a novel convex cone, the spartrahedron, which exactly characterizes sparsity at the matrix level. This leads to a semidefinite programming (SDP) relaxation that is tight whenever its solution is rank-one, providing a simple certificate of global optimality. We establish theoretical guarantees, including approximation bounds and exactness regions for sparse PCA and sparse ridge regression, as well as a general stability result under perturbations. Numerical experiments on sparse PCA, sparse regression, RIP constant estimation, and sparse canonical correlation analysis (CCA) demonstrate the practical success of our methods. |
| title | Solving Sparsity Constrained PCA, Regression, and QCQP via the Spartrahedron |
| topic | Optimization and Control 90C20, 90C22, 90C25 |
| url | https://arxiv.org/abs/2603.18215 |