Principal Component Analysis by Optimization of Symmetric Functions has no Spurious Local Optima

DOI10.1137/18M1188495MaRDI QIDQ5215520zbMATH OpenOpenAlexFDO

Authors Armin Eftekhari, Raphael A. Hauser

Publication date 12 February 2020

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1805.07459

zbMATH Keywords

nonconvex optimizationprincipal component analysissaddle point property

Mathematics Subject Classification ID

Eigenvalues, singular values, and eigenvectors (15A18) Factorization of matrices (15A23) Factor analysis and principal components; correspondence analysis (62H25) Nonconvex programming, global optimization (90C26)

Abstract: 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 non-convex programs have 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 factorisation. More specifically, we study an unconstrained formulation of PCA using determinant optimisation that might provide an elegant alternative to the deflating scheme commonly used in sparse PCA.

Recommendations

• scientific article; zbMATH DE number 6129459
• scientific article; zbMATH DE number 4157706
• scientific article; zbMATH DE number 3940477
• Certifiably optimal sparse principal component analysis
• Principal component analysis in an asymmetric norm
• Optimal solutions for sparse principal component analysis
• Deterministic and probabilistic models for symmetrical and nonsymmetrical principal component analysis
• The sparse principal component analysis problem: optimality conditions and algorithms
• Non-linear generalization of principal component analysis: from a global to a local approach

Cites work

• A generalized Cauchy-Binet formula and applications to total positivity and majorization
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• An introduction to support vector machines and other kernel-based learning methods.
• Generalized power method for sparse principal component analysis
• scientific article; zbMATH DE number 47926 (Why is no real title available?)
• scientific article; zbMATH DE number 635657 (Why is no real title available?)
• scientific article; zbMATH DE number 961607 (Why is no real title available?)
• Modern multidimensional scaling: theory and applications
• On consistency and sparsity for principal components analysis in high dimensions
• Quadratic expansions of spectral functions
• RELATIONS BETWEEN TWO SETS OF VARIATES
• Streaming principal component analysis from incomplete data
• The Geometry of Algorithms with Orthogonality Constraints
• Theoretical Insights Into the Optimization Landscape of Over-Parameterized Shallow Neural Networks

Cited in

(1)

• Exact guarantees on the absence of spurious local minima for non-negative rank-1 robust principal component analysis

Describes a project that uses

Uses Software

• SDPLR
• ElemStatLearn

This page was built for publication: Principal Component Analysis by Optimization of Symmetric Functions has no Spurious Local Optima

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5215520)