PaperlayerView exact revision on arXiv

Source-linked AI summary

Generalized power method for sparse principal component analysis

Michel Journée, Yurii Nesterov, Peter Richtárik, Rodolphe Sepulchre

arXiv:0811.4724v1math.OC

TL;DR

Sparse PCA must balance explained variance with sparse, interpretable components. The paper reformulates four single-unit and block problems as convex-function maximization over compact sets and applies a gradient scheme. On random and gene-expression problems, the methods reportedly match or surpass existing variance–sparsity trade-offs while running faster, although convergence to a unique local maximizer is not guaranteed.

  • Problem

    Sparse PCA seeks components that explain substantial variability using few variables, trading some explained variance for greater interpretability.

  • Method

    The paper proposes two single-unit and two block formulations, reformulates them as convex-function maximization over compact sets, and applies a gradient method.

  • Results

    The methods achieve the same or better explained-variance–sparsity balance than existing methods and are faster on random Gaussian and breast-cancer gene-expression data.

  • Takeaways & Limitations

    The approach provides four algorithms for computing sparse principal components with reduced search dimension and favorable practical efficiency.

  • Takeaways & Limitations

    The analysis does not guarantee convergence to a unique local maximizer; the method may converge to a stationary point instead.

Abstract

from arXiv · show

In this paper we develop a new approach to sparse principal component analysis (sparse PCA). We propose two single-unit and two block optimization formulations of the sparse PCA problem, aimed at extracting a single sparse dominant principal component of a data matrix, or more components at once, respectively. While the initial formulations involve nonconvex functions, and are therefore computationally intractable, we rewrite them into the form of an optimization program involving maximization of a convex function on a compact set. The dimension of the search space is decreased enormously if the data matrix has many more columns (variables) than rows. We then propose and analyze a simple gradient method suited for the task. It appears that our algorithm has best convergence properties in the case when either the objective function or the feasible set are strongly convex, which is the case with our single-unit formulations and can be enforced in the block case. Finally, we demonstrate numerically on a set of random and gene expression test problems that our approach outperforms existing algorithms both in quality of the obtained solution and in computational speed.

1 Introduction

Sparse PCA seeks interpretable components that balance explained variance against sparsity, while this paper develops reformulations and gradient algorithms for single or multiple components.

  • Motivation: Sparse PCA trades explained variance against using few variables, improving interpretability but sacrificing some variance.This is especially relevant when variables have concrete meaning, such as genes in expression data.
  • Contributions: The paper proposes two single-unit and two block formulations, using either ℓ1 or ℓ0 penalties to extract sparse components.Single-unit formulations target m = 1, whereas block formulations target p ≥ m > 1 components.
  • Reformulation: The reformulations maximize a convex function over a unit Euclidean sphere or Stiefel manifold, reducing search dimension when n ≫ p.The sphere applies for one component and the Stiefel manifold for multiple components.
  • Optimization: A simple gradient scheme is analyzed, with strongest convergence properties when the objective or feasible set is strongly convex.Strong convexity holds in the single-unit case and can be enforced in the block case with regularization.
  • Evaluation: The resulting algorithms have per-iteration cost O(npm) and were reported faster than existing methods while achieving comparable or better variance–sparsity trade-offs.Experiments used random Gaussian and breast-cancer gene-expression data.

2 Some formulations of the sparse PCA problem

The paper develops four sparse PCA formulations: single-unit and block versions, each using either ℓ1 or cardinality penalties. Reformulations reduce high-dimensional optimization to convex maximization over lower-dimensional spherical or Stiefel feasible sets.

  • 2 Some formulations of the sparse PCA problem: Four formulations cover single-unit and block sparse PCA, with either ℓ1 or ℓ0 penalties for sparsity.
  • 2.1 Single-unit sparse PCA via ℓ1-penalty: The single-unit ℓ1 formulation trades explained variance against sparsity through the parameter γ.γ = 0 recovers the first principal component, while sufficiently large γ yields the zero solution.
  • 2.1 Single-unit sparse PCA via ℓ1-penalty: The single-unit ℓ1 problem is reformulated as convex optimization on a lower-dimensional sphere when p ≪ n.The reformulation addresses both nonconvexity and the large search dimension of the original problem.
  • 2.2 Single-unit sparse PCA via cardinality penalty: The cardinality-penalized single-unit formulation directly penalizes nonzero coefficients and produces a convex, generally nonsmooth reformulation on the lower-dimensional sphere.
  • 2.3 Block sparse PCA via ℓ1-penalty: The block ℓ1 formulation extracts m components using a sparsity parameter γ and diagonal matrix N, without generally enforcing orthogonal loading directions.For γ = 0, suitable distinct diagonal entries recover PCA; for γ > 0, the loading columns are not expected to remain orthogonal.
  • 2.3 Block sparse PCA via ℓ1-penalty: The block ℓ1 reformulation maximizes a convex function on the Stiefel manifold, while its sparsity pattern is determined by the solution X∗.When γ exceeds maxi,j µj∥ai∥2, the zero matrix is optimal.
  • 2.4 Block sparse PCA via cardinality penalty: The block cardinality formulation extends the single-unit cardinality penalty to m components and recovers PCA at γ = 0 when all µi are distinct.Its reformulation likewise maximizes a convex function on the Stiefel manifold.
  • 2.4 Block sparse PCA via cardinality penalty: The block cardinality formulation determines active entries of Z∗ from X∗, with sufficiently large γ producing the zero solution.

3 A gradient method for maximizing convex functions

The paper analyzes a subgradient-based scheme for maximizing a convex function over a compact set. Strong convexity of the objective or feasible-set hull sharpens convergence analysis, while spherical and Stiefel constraints connect the method to power-type iterations.

  • 3 A gradient method for maximizing convex functions: The method maximizes a convex function over a compact feasible set using a gradient-type iteration that may use subgradients.
  • 3 A gradient method for maximizing convex functions: The optimality measure vanishes when a subgradient belongs to the normal cone of Conv(Q) at the current point.
  • 3 A gradient method for maximizing convex functions: On a Euclidean ball or sphere, the iteration has an explicit form; for quadratic objectives on a sphere, it specializes to the power method.The block case uses Stiefel-manifold linear maximization solved by a polar-decomposition factor.
  • 3 A gradient method for maximizing convex functions: Each iteration maximizes the first-order affine approximation over Q, producing the next iterate as an approximate solution sequence.
  • 3 A gradient method for maximizing convex functions: The objective values are nondecreasing along the generated sequence.
  • 3 A gradient method for maximizing convex functions: Sharper convergence results require either strong convexity of f or strong convexity of Conv(Q), alongside the stated technical assumptions.
  • 3 A gradient method for maximizing convex functions: For single-unit sparse PCA, the convex hull of the spherical feasible set is the strongly convex unit ball, satisfying the relevant feasible-set condition.
  • 3 A gradient method for maximizing convex functions: Theorem 4 establishes convergence under convexity and at least one strong-convexity condition, but the method need not converge to a unique local maximizer.Limit points remain connected and satisfy the first-order optimality condition.

4 Algorithms for sparse PCA

The section presents four sparse PCA algorithms that identify sparsity patterns and fill their active loading entries, with single-unit and block variants and per-iteration costs stated for each.

  • Computational complexity: The single-unit algorithms have per-iteration complexity O(np), whereas the block algorithms have complexity O(npm).
  • Post-processing: For a fixed sparsity pattern, the active entries are filled by maximizing the variance explained by the resulting components.In the single-unit case, an explicit solution uses a rank-one singular value decomposition of the active-column submatrix.
  • Post-processing: In the block case, the exact solution is hard to compute, so alternating optimization efficiently computes a local maximizer.The subproblems have explicit solutions, including a polar-decomposition step for one update.
  • Post-processing: The stationary-point conditions set inactive entries of Z to zero and normalize the active columns using a unique positive diagonal matrix.The diagonal matrix is determined by the data and normalization conditions.
  • Post-processing: Algorithm 6 alternates updates of the active loading entries and component variables, serving as a postprocessing heuristic required strictly for the ℓ1 block formulation.For cardinality-penalized formulations, the resulting solution is already a local maximizer for the identified sparsity pattern.
  • Algorithm overview: The four algorithms combine identification of a locally optimal sparsity pattern with methods for filling the active entries of m loading vectors.They cover single-unit and block formulations with ℓ1- and ℓ0-based penalties.

5 Numerical experiments

The experiments compare GPower algorithms with existing sparse PCA methods on random and gene expression data, evaluating variance–sparsity trade-offs, computational speed, and biological interpretability. GPower methods generally match or exceed competing methods while running faster, and gene-expression components show strong biological content.

  • Experimental setup: The study compares GPower, SPCA, sPCA-rSVD, and Greedy algorithms on random and real data using variance, cardinality, running time, and interpretability criteria.The experiments include Gaussian random matrices and gene expression data related to breast cancer.
  • Trade-off curves: GPowerℓ1, GPowerℓ0, Greedy, and rSVDℓ0 explain more variance than SPCA and rSVDℓ1 at fixed cardinality on random problems.Postprocessing the active part of SPCA and rSVDℓ1 according to (36) brings all methods to the same performance.
  • Controlling sparsity with γ: Increasing the sparsity parameter γ produces solutions with smaller cardinality, although the resulting number of nonzero elements cannot be precisely predicted.The greedy method directly accepts the desired cardinality, whereas GPower methods control sparsity through γ.
  • Computational complexity: Greedy slows significantly as target cardinality increases, while the speed of the other considered algorithms is unaffected by cardinality.Because Greedy is much slower on average, it is excluded from the subsequent numerical comparisons.
  • Speed and interpretation: GPowerℓ1 is faster than rSVDℓ1 because it simultaneously optimizes explained variance and sparsity instead of solving unconstrained PCA before enforcing sparsity.Across multi-component experiments, the new power-like methods are significantly faster on all tested instances; gene-expression analyses also assess pathway and motif enrichment.

6 Conclusion

The paper develops four sparse PCA algorithms from convex-on-compact reformulations and analyzes their gradient-based properties. The methods reduce feasible-set dimension when variables outnumber samples and outperform existing algorithms on tested data.

  • Contributions: Four algorithms arise from two single-unit and two block sparse PCA formulations after reformulation as convex-function maximization on compact sets.The feasible sets are a unit Euclidean sphere or the Stiefel manifold.
  • Contributions: A simple gradient scheme supports iteration-complexity analysis for the reformulated sparse PCA problems.
  • Convergence: Strong convexity of the objective or feasible set improves convergence; it holds in the single-unit case and can be enforced for block formulations.
  • Computational structure: The feasible-set dimension depends on samples and extracted components rather than variables, which is desirable when p ≪ n.
  • Empirical evaluation: On random and real-life biological data, the methods systematically outperform existing algorithms in speed and trade-off performance.

7 Appendix A

The appendix establishes strong convexity properties for level sets of smooth strongly convex functions and illustrates them with Euclidean balls. It uses convexity and Lipschitz-gradient assumptions to characterize the resulting set parameter.

  • Preliminaries: Proposition 11 collects standard inequalities for strongly convex functions and convex differentiable functions with Lipschitz-continuous gradients.
  • Strongly convex level sets: Theorem 12 states that a nonnegative strongly convex function with Lipschitz-continuous gradient has strongly convex level sets.The theorem assumes convexity parameter σf > 0 and gradient Lipschitz constant Lf > 0.
  • Proof: The proof uses convexity to keep convex combinations of points in the level set before establishing the required bound.
  • Example: For f(x) = ∥x∥2, the level set Qω is the Euclidean ball r · B when ω = r2.
  • Example: The Euclidean-ball example recovers the strong-convexity parameter σQω = 1/r as a special case of Theorem 12.
Loading 0811.4724v1…