Principal component analysis by optimisation of symmetric functions has no spurious local optima
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 theoretica...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Society for Industrial and Applied Mathematics
2020
|
| _version_ | 1797101678499987456 |
|---|---|
| author | Eftekhari, A Hauser, R |
| author_facet | Eftekhari, A Hauser, R |
| author_sort | Eftekhari, A |
| collection | OXFORD |
| description | 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.
Read More: https://epubs.siam.org/doi/abs/10.1137/18M1188495 |
| first_indexed | 2024-03-07T05:55:13Z |
| format | Journal article |
| id | oxford-uuid:ea47944f-07e6-4fe6-9db6-9a763767a0c1 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T05:55:13Z |
| publishDate | 2020 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | oxford-uuid:ea47944f-07e6-4fe6-9db6-9a763767a0c12022-03-27T11:00:51ZPrincipal component analysis by optimisation of symmetric functions has no spurious local optimaJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:ea47944f-07e6-4fe6-9db6-9a763767a0c1EnglishSymplectic Elements at OxfordSociety for Industrial and Applied Mathematics2020Eftekhari, AHauser, RPrincipal 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. Read More: https://epubs.siam.org/doi/abs/10.1137/18M1188495 |
| spellingShingle | Eftekhari, A Hauser, R Principal component analysis by optimisation of symmetric functions has no spurious local optima |
| title | Principal component analysis by optimisation of symmetric functions has no spurious local optima |
| title_full | Principal component analysis by optimisation of symmetric functions has no spurious local optima |
| title_fullStr | Principal component analysis by optimisation of symmetric functions has no spurious local optima |
| title_full_unstemmed | Principal component analysis by optimisation of symmetric functions has no spurious local optima |
| title_short | Principal component analysis by optimisation of symmetric functions has no spurious local optima |
| title_sort | principal component analysis by optimisation of symmetric functions has no spurious local optima |
| work_keys_str_mv | AT eftekharia principalcomponentanalysisbyoptimisationofsymmetricfunctionshasnospuriouslocaloptima AT hauserr principalcomponentanalysisbyoptimisationofsymmetricfunctionshasnospuriouslocaloptima |