Solving Sparsity Constrained PCA, Regression, and QCQP via the Spartrahedron
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2603.18215
curl -X POST /api/v1/records/arxiv/2603.18215/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2603.18215/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'