{"id":"arxiv/2607.09429","url":"https://arxiv.org/abs/2607.09429","tags":["math.OC"],"score":0,"title":"The Continuous Relaxation of Sparse PCA is NP-hard","domain":"math.OC","source":"arxiv","authors":["Linbin Li","Yong Xia"],"reviews":0,"subject":"math.OC","summary":"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.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-10","reactions":{}}