Projection-based QLP Algorithm for Efficiently Computing Low-Rank Approximation of Matrices
This work addresses the problem of scalable low-rank approximation for large matrices in signal processing and data analysis, representing an incremental improvement over existing randomized methods.
The paper tackles the computational inefficiency of the pivoted QLP algorithm for low-rank matrix approximation by introducing the Projection-based Partial QLP algorithm, which uses randomization and avoids pivoting to achieve high accuracy with improved efficiency on synthetic and real-world data.
Matrices with low numerical rank are omnipresent in many signal processing and data analysis applications. The pivoted QLP (p-QLP) algorithm constructs a highly accurate approximation to an input low-rank matrix. However, it is computationally prohibitive for large matrices. In this paper, we introduce a new algorithm termed Projection-based Partial QLP (PbP-QLP) that efficiently approximates the p-QLP with high accuracy. Fundamental in our work is the exploitation of randomization and in contrast to the p-QLP, PbP-QLP does not use the pivoting strategy. As such, PbP-QLP can harness modern computer architectures, even better than competing randomized algorithms. The efficiency and effectiveness of our proposed PbP-QLP algorithm are investigated through various classes of synthetic and real-world data matrices.