Randomized QLP algorithm and error analysis
Provides a faster randomized alternative to deterministic QLP decomposition for low-rank matrix approximation, with theoretical error guarantees.
The paper introduces randomized QLP (RQLP) and enhanced RQLP (ERQLP) algorithms for low-rank matrix approximation, achieving O(mnk) complexity and proving that the L-values accurately track singular values with bounded expected relative error.
In this paper, we describe the randomized QLP (RQLP) algorithm and its enhanced version (ERQLP) for computing the low rank approximation to $A$ of size $m\times n$ efficiently such that $A\approx QLP$, where $L$ is the rank-$k$ lower-triangular matrix, $Q$ and $P$ are column orthogonal matrices. The theoretical cost of the implementation of RQLP and ERQLP only needs $\mathcal{O}(mnk)$. Moreover, we derive the upper bounds of the expected approximation error $\mathbb{E}\left [ (σ_{j}(A) - σ_{j} (L))/ σ_{j}(A) \right] $ for $j=1,\cdots, k$, and prove that the $L$-values of the proposed methods can track the singular values of $A$ accurately. These claims are supported by extensive numerical experiments.