L1-Norm Principal Component Analysis Using Quaternion Rotations

• Autorzy: Borowicz Adam

Identyfikatory

DOI

10.15439/2023F3368

• Języki publikacji: EN

Abstrakty

EN

Principal component analysis (PCA) based on L1-norm has drawn growing interest in recent years. It is especially popular in the machine learning and pattern recognition communities for its robustness to outliers. Although optimal algorithms for L1-norm maximization exist, they have very high computational complexity and can be used for evaluation purposes only. In practice, only approximate techniques have been considered so far. Currently, the most popular method is the bit-flipping technique, where the L1-norm maximization is viewed as a combinatorial problem over the binary field. Recently, we proposed exhaustive, but faster algorithm based on two-dimensional Jacobi rotations that also offer high accuracy. In this paper, we develop a novel variant of this method that uses three-dimensional rotations and quaternion algebra. Our experiments show that the proposed approach offers higher accuracy than other approximate algorithms, but at the expense of the additional computational cost. However, for large datasets, the cost is still lower than that of the bit-flipping technique.

Słowa kluczowe

EN

Jacobian matrix; estimation error; quaternion; simulation; approximation algorithm; robustness; computational efficiency

PL

Macierz Jakobiego; błędy estymacji; kwaternion; symulacja; algorytm; odporność; wydajność obliczeniowa

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2023
• Tom: Vol. 35
• Strony: 883--888
• Opis fizyczny: Bibliogr. 15 poz., wz., wykr.

Twórcy

autor

Borowicz Adam

• Faculty of Computer Science, Bialystok University of Technology Wiejska str. 45A, 15-351 Bialystok, Poland

• https://orcid.org/0000-0003-0320-5530

Bibliografia

• 1. A. Borowicz, “Maximization of L1-norm using Jacobi rotations,” in 2022 30th European Signal Processing Conference (EUSIPCO), 2022. http://dx.doi.org/10.23919/EUSIPCO55093.2022.9909924 pp. 1951–1955.
• 2. I. T. Jolliffe, Principal Component Analysis. New York: Springer Verlag, 2002.
• 3. G. Golub and C. Van Loan, Matrix Computations. USA: Johns Hopkins University Press, 2013.
• 4. N. Kwak, “Principal component analysis based on L1-norm maximization,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 30, no. 9, pp. 1672–1680, 2008. http://dx.doi.org/10.1109/TPAMI.2008.114
• 5. P. P. Markopoulos, G. N. Karystinos, and D. A. Pados, “Optimal algorithms for L1 -subspace signal processing,” IEEE Transactions on Signal Processing, vol. 62, no. 19, pp. 5046–5058, 2014. http://dx.doi.org/10.1109/TSP.2014.2338077
• 6. P. P. Markopoulos, S. Kundu, S. Chamadia, and D. A. Pados, “Efficient L1-norm principal-component analysis via bit flipping,” IEEE Transactions on Signal Processing, vol. 65, no. 16, pp. 4252–4264, 2017. http://dx.doi.org/10.1109/TSP.2017.2708023
• 7. M. Dhanaraj and P. P. Markopoulos, “Novel algorithm for incremental L1-norm principal-component analysis,” in 2018 26th European Signal Processing Conference (EUSIPCO), 2018. http://dx.doi.org/10.23919/EU-SIPCO.2018.8553239 pp. 2020–2024.
• 8. R. Martın-Clemente and V. Zarzoso, “On the link between L1-PCA and ICA,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 39, no. 3, pp. 515–528, 2017. http://dx.doi.org/10.1109/TPAMI.2016.2557797
• 9. A. Borowicz, “Independent component analysis based on Jacobi iterative framework and L1-norm criterion,” in 2022 17th Conference on Computer Science and Intelligence Systems (FedCSIS), 2022. http://dx.doi.org/10.15439/2022F157 pp. 305–312.
• 10. J. Cardoso and A. Souloumiac, “Blind beamforming for non-Gaussian signals,” IEE Proceedings F - Radar and Signal Processing, vol. 140, no. 6, pp. 362–370, 1993. http://dx.doi.org/10.1049/ip-f-2.1993.0054
• 11. J. Cardoso, “High-order contrasts for independent component analysis,” Neural Computation, vol. 11, no. 1, pp. 157–192, 1999. http://dx.doi.org/10.1162/089976699300016863
• 12. W. Ouedraogo, A. Souloumiac, and C. Jutten, “Non-negative independent component analysis algorithm based on 2D Givens rotations and a Newton optimization,” in Latent Variable Analysis and Signal Separation. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. http://dx.doi.org/10.1007/978-3-642-15995-4 pp. 522–529.
• 13. A. Borowicz, “Orthogonal approach to independent component analysis using quaternionic factorization,” EURASIP Journal on Advances in Signal Processing, vol. 2020, no. 39, p. 23, September 2020. http://dx.doi.org/10.1186/s13634-020-00697-0
• 14. J. B. Kuipers, Quaternions and Rotation Sequences: a Primer with Applications to Orbits, Aerospace, and Virtual Reality. Princeton, N.J.: Princeton University Press, 2002.
• 15. M. Parfieniuk, “A parallel factorization for generating orthogonal matrices,” in International Conference on Parallel Processing and Applied Mathematics (PPAM) 2019. Bialystok, Poland: Springer, 2019. http://dx.doi.org/10.1007/978-3-030-43229 pp. 567–578.

Uwagi

1. Thematic Tracks Short Papers

2. Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2024).