Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Principal Component Analysis By Optimization Of Symmetric Functions Has No Spurious Local Optima
 
research article

Principal Component Analysis By Optimization Of Symmetric Functions Has No Spurious Local Optima

Eftekhari, Armin  
•
Hauser, Raphael A.
January 1, 2020
Siam Journal On Optimization

Principal component analysis (PCA) finds the best linear representation of data and is an indispensable tool in many learning and inference tasks. Classically, principal components of a dataset are interpreted as the directions that preserve most of its "energy," an interpretation that is theoretically underpinned by the celebrated Eckart-Young-Mirsky theorem. This paper introduces many other ways of performing PCA, with various geometric interpretations, and proves that the corresponding family of nonconvex programs has no spurious local optima, while possessing only strict saddle points. These programs therefore loosely behave like convex problems and can be efficiently solved to global optimality, for example, with certain variants of the stochastic gradient descent. Beyond providing new geometric interpretations and enhancing our theoretical understanding of PCA, our findings might pave the way for entirely new approaches to structured dimensionality reduction, such as sparse PCA and nonnegative matrix factorization. More specifically, we study an unconstrained formulation of PCA using determinant optimization that might provide an elegant alternative to the deflating scheme commonly used in sparse PCA.

  • Details
  • Metrics
Type
research article
DOI
10.1137/18M1188495
Web of Science ID

WOS:000546998300017

Author(s)
Eftekhari, Armin  
Hauser, Raphael A.
Date Issued

2020-01-01

Publisher

SIAM PUBLICATIONS

Published in
Siam Journal On Optimization
Volume

30

Issue

1

Start page

439

End page

463

Subjects

Mathematics, Applied

•

Mathematics

•

principal component analysis

•

nonconvex optimization

•

saddle point property

•

singular-value decomposition

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LIONS  
Available on Infoscience
November 4, 2020
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/172961
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés