Convex approximations to sparse PCA via Lagrangian duality

We derive a convex relaxation for cardinality constrained Principal Component Analysis (PCA) by using a simple representation of the L1L1 unit ball and standard Lagrangian duality. The resulting convex dual bound is an unconstrained minimization of the sum of two nonsmooth convex functions. Applying a partial smoothing technique reduces the objective to the sum of a smooth and nonsmooth convex function for which an efficient first order algorithm can be applied. Numerical experiments demonstrate its potential.