Fast computation of the L1-principal component of real-valued data

Recently, Markopoulos et al. [1], [2] presented an optimal algorithm that computes the L₁ maximum-projection principal component of any set of N real-valued data vectors of dimension D with complexity polynomial in N, O(N^D). 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₁ principal component with complexity O(N³). 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.