Efficient L1-Norm Principal-Component Analysis via Bit Flipping

DOI10.1109/TSP.2017.2708023MaRDI QIDQ4621804zbMATH OpenOpenAlexWikidataFDO

Authors Panos P. Markopoulos, Sandipan Kundu, Shubham Chamadia, Dimitris A. Pados

Publication date 8 February 2019

Published in IEEE Transactions on Signal Processing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Factor analysis and principal components; correspondence analysis (62H25) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: It was shown recently that the $K$ L1-norm principal components (L1-PCs) of a real-valued data matrix $mathbfXinmathbb{R}^{DimesN}$ ($N$ data samples of $D$ dimensions) can be exactly calculated with cost $mathcalO(2^{NK})$ or, when advantageous, $mathcalO(N^{dK-K+1})$ where $d=mathrmrank(mathbfX)$, $K<d$ [1],[2]. In applications where $mathbfX$ is large (e.g., "big" data of large $N$ and/or "heavy" data of large $d$), these costs are prohibitive. In this work, we present a novel suboptimal algorithm for the calculation of the $K<d$ L1-PCs of $mathbfX$ of cost $mathcalO(NDmathrmminN,D+N^2(K^4+d{K}^2)+dN{K}^3)$, 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 on data dimensionality reduction and disease diagnosis from genomic data.

Recommendations

• Optimal algorithms for binary, sparse, and L₁-norm principal component analysis
• L1-norm projection pursuit principal component analysis
• A pure \(L_1\)-norm principal component analysis
• Reduced-Rank L1-Norm Principal-Component Analysis With Performance Guarantees
• L1-Norm Principal-Component Analysis of Complex Data
• L1-norm-based principal component analysis with adaptive regularization
• scientific article; zbMATH DE number 1163871
• Compressive-Projection Principal Component Analysis
• Bilinear Lanczos components for fast dimensionality reduction and feature extraction

Cited in

(9)

• On the robust PCA and Weiszfeld's algorithm
• Dimension reduction big data using recognition of data features based on copula function and principal component analysis
• Optimization for L₁-Norm Error Fitting via Data Aggregation
• ISLET: fast and optimal low-rank tensor regression via importance sketching
• On the minimax spherical designs
• Linear Convergence of a Proximal Alternating Minimization Method with Extrapolation for \(\boldsymbol{\ell_1}\) -Norm Principal Component Analysis
• T-product based _1-norm tensor principal component analysis and a finite-step convergence algorithm
• Optimization on the quaternion Stiefel manifold with applications. II: L1-QPCA
• _1-norm simultaneous approximate diagonalization and a proximal alternating maximization method

This page was built for publication: Efficient L1-Norm Principal-Component Analysis via Bit Flipping

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