The Continuous Relaxation of Sparse PCA is NP-hard

Linbin Li, Yong Xia

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 Principa…