An Orthonormalization-Free and Inversion-Free Algorithm for Online Estimation of Principal Eigenspace

Siyun Zhou and Liwei Xu ()
Additional contact information
Siyun Zhou: School of Mathematical Sciences, University of Electronic Science and Technology of China, Chengdu 610000, P. R. China
Liwei Xu: School of Mathematical Sciences, University of Electronic Science and Technology of China, Chengdu 610000, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2024, vol. 41, issue 06, 1-26

Abstract: In this paper, we study the problem of estimating the principal eigenspace over an online data stream. First-order optimization methods are appealing choices for this problem thanks to their high efficiency and easy implementation. The existing first-order solvers, however, require either per-step orthonormalization or matrix inversion, which empirically puts pressure to the parameter tuning, and also incurs extra costs of rank augmentation. To get around these limitations, we introduce a penalty-like term controlling the distance from the Stiefel manifold into matrix Krasulina’s method, and propose the first orthonormalization- and inversion-free incremental PCA scheme (Domino). The Domino is shown to achieve the computational speed-up, and own the ability of automatic correction on the numerical rank. It also maintains the advantage of Krasulina’s method, e.g., variance reduction on low-rank data. Moreover, both of the asymptotic and non-asymptotic convergence guarantees are established for the proposed algorithm.

Keywords: Online data stream; principal eigenspace estimation; first-order optimization; orthonormalization- and inversion-free updates (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595924500015
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:41:y:2024:i:06:n:s0217595924500015

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595924500015

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().