Efficient L1-Norm Principal-Component Analysis via Bit Flipping

View Researcher's Other Codes

Disclaimer: The provided code links for this paper are external links. Science Nest has no responsibility for the accuracy, legality or content of these links. Also, by downloading this code(s), you agree to comply with the terms of use as set out by the author(s) of the code(s).

Please contact us in case of a broken link from here

Authors P. Markopoulos, S. Kundu, Shubham Chamadia, D. Pados
Journal/Conference Name IEEE Transactions on Signal Processing
Paper Category
Paper Abstract It was shown recently that the <inline-formula><tex-math notation="LaTeX">$K$</tex-math></inline-formula> L1-norm principal components (L1-PCs) of a real-valued data matrix <inline-formula><tex-math notation="LaTeX">$\mathbf X \in \mathbb {R}^{D \times N}$</tex-math></inline-formula> (<inline-formula><tex-math notation="LaTeX">$N$</tex-math> </inline-formula> data samples of <inline-formula><tex-math notation="LaTeX">$D$</tex-math></inline-formula> dimensions) can be exactly calculated with cost <inline-formula><tex-math notation="LaTeX">$\mathcal {O}(2^{NK})$ </tex-math></inline-formula> or, when advantageous, <inline-formula><tex-math notation="LaTeX">$\mathcal {O}(N^{dK - K + 1})$</tex-math></inline-formula> where <inline-formula><tex-math notation="LaTeX">$d=\mathrm{rank}(\mathbf X)$ </tex-math></inline-formula>, <inline-formula><tex-math notation="LaTeX">$K<d$</tex-math></inline-formula>. In applications where <inline-formula><tex-math notation="LaTeX">$\mathbf X$</tex-math></inline-formula> is large (e.g., “big” data of large <inline-formula><tex-math notation="LaTeX">$N$</tex-math></inline-formula> and/or “heavy” data of large <inline-formula><tex-math notation="LaTeX">$d$</tex-math></inline-formula>), these costs are prohibitive. In this paper, we present a novel suboptimal algorithm for the calculation of the <inline-formula><tex-math notation="LaTeX">$K < d$</tex-math></inline-formula> L1-PCs of <inline-formula> <tex-math notation="LaTeX">$\mathbf X$</tex-math></inline-formula> of cost <inline-formula><tex-math notation="LaTeX"> $\mathcal O (ND \mathrm{min} \lbrace N,D\rbrace + N^2K^2(K^2 + d))$</tex-math></inline-formula>, which is comparable to that of standard L2-norm PC analysis. Our theoretical and experimental studies show that the proposed algorithm calculates the exact optimal L1-PCs with high frequency and achieves higher value in the L1-PC optimization metric than any known alternative algorithm of comparable computational cost. The superiority of the calculated L1-PCs over standard L2-PCs (singular vectors) in characterizing potentially faulty data/measurements is demonstrated with experiments in data dimensionality reduction and disease diagnosis from genomic data.
Date of publication 2017
Code Programming Language Python

Copyright Researcher 2022