Logo PTI Logo FedCSIS

Proceedings of the 18th Conference on Computer Science and Intelligence Systems

Annals of Computer Science and Information Systems, Volume 35

L1-Norm Principal Component Analysis Using Quaternion Rotations

DOI: http://dx.doi.org/10.15439/2023F3368

Citation: Proceedings of the 18th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 35, pages 883–888 ()

Full text

Abstract. 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.

References

  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.