Fast computation of the L<inf>1</inf>-principal component of real-valued data

Abstract

Recently, Markopoulos et al. [1], [2] presented an optimal algorithm that computes the L <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> maximum-projection principal component of any set of N real-valued data vectors of dimension D with complexity polynomial in N, O(N <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">D</sup> ). Still, moderate to high values of the data dimension D and/or data record size N may render the optimal algorithm unsuitable for practical implementation due to its exponential in D complexity. In this paper, we present for the first time in the literature a fast greedy single-bit-flipping conditionally optimal iterative algorithm for the computation of the L <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> principal component with complexity O(N <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup> ). Detailed numerical studies are carried out demonstrating the effectiveness of the developed algorithm with applications to the general field of data dimensionality reduction and direction-of-arrival estimation.