Nearly Optimal Stochastic Approximation for Online Principal Subspace Estimation
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2017
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913254809272320 |
|---|---|
| author | Liang, Xin Guo, Zhen-Chen Wang, Li Li, Ren-Cang Lin, Wen-Wei |
| author_facet | Liang, Xin Guo, Zhen-Chen Wang, Li Li, Ren-Cang Lin, Wen-Wei |
| contents | Principal component analysis (PCA) has been widely used in analyzing high-dimensional data. It converts a set of observed data points of possibly correlated variables into a set of linearly uncorrelated variables via an orthogonal transformation. To handle streaming data and reduce the complexities of PCA, (subspace) online PCA iterations were proposed to iteratively update the orthogonal transformation by taking one observed data point at a time. Existing works on the convergence of (subspace) online PCA iterations mostly focus on the case where sample are almost surely uniformly bounded. In this paper, we analyze the convergence of a subspace online PCA iteration under more practical assumption and obtain a nearly optimal finite-sample error bound. Our convergence rate almost matches the minimax information lower bound. We prove that the convergence is nearly global in the sense that the subspace online PCA iteration is convergent with high probability for random initial guesses. This work also leads to a simpler proof of the recent work on analyzing online PCA for the first principal component only. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1711_06644 |
| institution | arXiv |
| publishDate | 2017 |
| record_format | arxiv |
| spellingShingle | Nearly Optimal Stochastic Approximation for Online Principal Subspace Estimation Liang, Xin Guo, Zhen-Chen Wang, Li Li, Ren-Cang Lin, Wen-Wei Optimization and Control 65F99, 62H25, 68W27, secondary 62H12 Principal component analysis (PCA) has been widely used in analyzing high-dimensional data. It converts a set of observed data points of possibly correlated variables into a set of linearly uncorrelated variables via an orthogonal transformation. To handle streaming data and reduce the complexities of PCA, (subspace) online PCA iterations were proposed to iteratively update the orthogonal transformation by taking one observed data point at a time. Existing works on the convergence of (subspace) online PCA iterations mostly focus on the case where sample are almost surely uniformly bounded. In this paper, we analyze the convergence of a subspace online PCA iteration under more practical assumption and obtain a nearly optimal finite-sample error bound. Our convergence rate almost matches the minimax information lower bound. We prove that the convergence is nearly global in the sense that the subspace online PCA iteration is convergent with high probability for random initial guesses. This work also leads to a simpler proof of the recent work on analyzing online PCA for the first principal component only. |
| title | Nearly Optimal Stochastic Approximation for Online Principal Subspace Estimation |
| topic | Optimization and Control 65F99, 62H25, 68W27, secondary 62H12 |
| url | https://arxiv.org/abs/1711.06644 |