Efficient CUR decomposition for interpretable low-rank approximations and imaging applications

Low-rank approximations based on the selected columns and rows from a given matrix are an alternative approach to singular value decomposition (SVD) and offer more interpretable outputs. They have been successfully used in pattern recognition, recommendation systems, bioinformatics, and social network analysis. One popular approach is CUR matrix decomposition, which represents the data matrix using three small matrices and can be achieved through randomized or deterministic approaches. Deterministic algorithms yield higher approximation accuracy than randomized ones. However, they are highly computationally expensive, especially with large datasets. To address these limitations, we introduce a new method for efficiently computing the CUR matrix decomposition called HyCUR. It incorporates a deterministic sampling strategy based on guided information of the singular vectors and a randomized sampling to select rows and columns for efficient CUR low-rank approximation. HyCUR overcomes the main drawbacks of deterministic methods and can estimate the approximation rank using an incremental QR factorization approach, which also approximates the SVD of the data matrix instead of the classical method. Therefore, HyCUR is suitable for applications with unknown data rank. Experimental results on synthetic and real datasets of varying sizes demonstrate that HyCUR achieves comparable accuracy to recent deterministic approaches while significantly improving computational efficiency for large low-rank datasets. We validate the proposed method in two real imaging applications: simultaneous sample and feature extraction from large datasets and hyperspectral unmixing to extract endmember signatures and estimate their fractions from hyperspectral image datasets (HSIs). The experiment results show promising performance in both applications. © 2025 Elsevier B.V.