Sparse Principal Component Analysis is a cardinal technique for obtaining
combinations of features, or principal components (PCs), that explain the
variance of high-dimensional datasets in an interpretable manner. At its heart,
this involves solving a sparsity and orthogonality constrained convex
maximization problem, which is extremely computationally challenging. Most
existing work address sparse PCA via heuristics such as iteratively computing
one sparse PC and deflating the covariance matrix, which does not guarantee the
orthogonality, let alone the optimality, of the resulting solution. We
challenge this status by reformulating the orthogonality conditions as rank
constraints and optimizing over the sparsity and rank constraints
simultaneously. We design tight semidefinite relaxations and propose tractable
second-order cone versions of these relaxations which supply high-quality upper
bounds. We also design valid second-order cone inequalities which hold when
each PC's individual sparsity is specified, and demonstrate that these
inequalities tighten our relaxations significantly. Moreover, we propose exact
methods and rounding mechanisms that exploit these relaxations' tightness to
obtain solutions with a bound gap on the order of 1%-5% for real-world datasets
with p = 100s or 1000s of features and r \in {2, 3} components. We investigate
the performance of our methods in spiked covariance settings and demonstrate
that simultaneously considering the orthogonality and sparsity constraints
leads to improvements in the Area Under the ROC curve of 2%-8% compared to
state-of-the-art deflation methods. All in all, our approach solves sparse PCA
problems with multiple components to certifiable (near) optimality in a
practically tractable fashion.

本研究提出一种新的方法，通过将正交性条件重新表述为秩约束，并同时优化稀疏性和秩约束，使得稀疏主成分分析问题更易解决。通过设计合理的半定松弛和可行的二阶锥不等式，本文的方法在实际数据集中可以获得最优解，并且相比现有方法具有更好的性能。

具有多个分量的稀疏 PCA

Sparse PCA With Multiple Components

Why is it that semidefinite relaxations have been so successful in numerous
applications in computer vision and robotics for solving non-convex
optimization problems involving rotations? In studying the empirical
performance we note that there are few failure cases reported in the
literature, in particular for estimation problems with a single rotation,
motivating us to gain further theoretical understanding.
A general framework based on tools from algebraic geometry is introduced for
analyzing the power of semidefinite relaxations of problems with quadratic
objective functions and rotational constraints. Applications include
registration, hand-eye calibration and rotation averaging. We characterize the
extreme points, and show that there exist failure cases for which the
relaxation is not tight, even in the case of a single rotation. We also show
that some problem classes are always tight given an appropriate
parametrization. Our theoretical findings are accompanied with numerical
simulations, providing further evidence and understanding of the results.

通过基于代数几何工具的一般框架分析，我们研究了用于解决涉及旋转的非凸优化问题的半定松弛的能力。研究中表明其在注册、手眼校准和旋转平均等应用中性能好、稳定。但在极端情况下会存在非常数解，需要适当的参数化方法。

关于旋转估计的半定松弛紧度

On the Tightness of Semidefinite Relaxations for Rotation Estimation

This paper studies the hierarchy of local minimums of a polynomial in the
space. For this purpose, we first compute H-minimums, for which the first and
second order optimality conditions are satisfied. To compute each H-minimum, we
construct a sequence of semidefinite relaxations, based on optimality
conditions. We prove that each constructed sequence has finite convergence,
under some generic conditions. A procedure for computing all local minimums is
given. When there are equality constraints, we have similar results for
computing the hierarchy of critical values and the hierarchy of local minimums.
Several extensions are discussed.

本研究探讨多项式中局部最小值的等级。为此，我们首先计算 H - 最小值，并构建半定松弛序列来满足一、二阶最优性条件，证明每个构建序列都在一些通用条件下有有限收敛。我们提供了计算所有局部最小值的程序，并在存在等式约束时得到了类似的结果，研究了若干扩展情况。