Worst-Case Sparse Principal Subspace Estimation

Sparse principal component analysis is normally posed as the maximization of an aggregate of captured variance—a single Rayleigh quotient, or the trace of the projected covariance—subject to a sparsity constraint. This choice matters when more than one component is required. An aggregate objective is dominated by its leading term, so a shared feature budget is spent first on the strongest components, and the weakest is returned as little more than an arbitrary direction. We make this precise by exhibiting covariances for which every maximizer of the trace criterion returns a degenerate subspace, one of whose directions carries no variance at all, while a worst-case objective yields a subspace in which every component keeps a fixed share of what it has in the population. Motivated by this, we study sparse principal subspace estimation under the worst-case componentwise retention ratio, defined as the smallest, across the population directions we wish to recover, of the fractions of variance that survive the restriction to the selected features. We show that this criterion is attained exactly by a choice of support, that it is largest precisely at the target eigenspace, and that taking the worst case over the individual columns of the estimated basis instead would give nothing new, since the Schur–Horn theorem reduces it to the trace criterion. To solve the resulting non-convex max–min program we develop TRIM, built on minorization–maximization (MM). We apply a tangent-plane minorizer to each of the eigenvalue functions, solve the resulting subproblem on each candidate support in closed form by a polar factor, and accept a support only if it raises the exact objective. TRIM needs no tuning parameters and no relaxation (in the sense of losing tightness), and it does not build the subspace one direction at a time by projecting out what it has already found. It is monotone by construction, terminates finitely, and reports an a posteriori bound on its own optimality gap. It succeeds on general covariances for which one-shot thresholding provably fails, it outperforms the competing estimators on a real corpus at every sparsity level we test, and under a limited feature budget it keeps far more of the weakest component—the one an aggregate objective neglects.