{"ID":6497672,"CreatedAt":"2026-07-13T01:19:40.13847098Z","UpdatedAt":"2026-07-14T01:36:59.12045529Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.09429","arxiv_id":"2607.09429","title":"The Continuous Relaxation of Sparse PCA is NP-hard","abstract":"Maximizing a symmetric quadratic form under simultaneous L1 norm inequality and L2 norm equality constraints is a standard and widely used continuous relaxation for Sparse Principal Component Analysis (SPCA). This paper settles the computational complexity of this continuous formulation by proving it is NP-hard. Furthermore, the variant with both L1 and L2 norm inequalities is also shown to be NP-hard.","short_abstract":"Maximizing a symmetric quadratic form under simultaneous L1 norm inequality and L2 norm equality constraints is a standard and widely used continuous relaxation for Sparse Principal Component Analysis (SPCA). This paper settles the computational complexity of this continuous formulation by proving it is NP-hard. Furthe...","url_abs":"https://arxiv.org/abs/2607.09429","url_pdf":"https://arxiv.org/pdf/2607.09429v1","authors":"[\"Linbin Li\",\"Yong Xia\"]","published":"2026-07-10T13:56:07Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}