Singular Value Decomposition (SVD) is a fundamental tool in numerous scientific and engineering domains. Many high-performance libraries, such as LAPACK, MAGMA, and cuSOLVER, provide general, truncated, and randomized SVD routines. However, when the input is a low-rank matrix whose rank is not explicitly known, existing routines usually treat it as full-rank, which leads to suboptimal performance. In this paper, we propose an efficient SVD algorithm specifically for rank-deficient matrices based on a recently proposed rank-revealing QR factorization, termed QB factorization. To further enhance numerical stability and efficiency, we introduce a Householder QB factorization and a mixed-precision SVD algorithm, accompanied by a rigorous error analysis demonstrating correctness and stability. Experimental results show that our method achieves up to 6978.71x speedup over the general (full) SVD routine in cuSOLVER and is 9.99x faster than randomized SVD in FP32 precision. Moreover, our method exhibits higher numerical accuracy than cuSOLVER full SVD, achieving substantially smaller backward errors while maintaining stable and reliable singular values. Beyond synthetic benchmarks, we also demonstrate its effectiveness in an image compression application with higher efficiency.

Abstract. Low-rank matrix approximation plays an important role in various applications such as image processing, signal processing, and data analysis. The existing methods require a guess of the ranks of matrices that represent images or involve additional costs to determine the ranks. A novel efficient orthogonal decomposition with automatic basis extraction (EOD-ABE) is proposed to compute the optimal low-rank matrix approximation with adaptive identification of the optimal rank. By introducing a randomized basis extraction mechanism, EOD-ABE eliminates the need for additional rank determination steps and can compute a rank-revealing approximation to a low-rank matrix. With a computational complexity of [Formula: see text], where [Formula: see text] and [Formula: see text] are the dimensions of the matrix and [Formula: see text] is its computed numerical rank, EOD-ABE achieves significant speedups compared to the state-of-the-art methods. Experimental results demonstrate the superior speed, accuracy, and robustness of EOD-ABE and indicate that EOD-ABE is a powerful tool for fast image compression and reconstruction and hyperspectral image dimensionality reduction in large-scale applications.

Linear discriminant analysis (LDA) faces challenges in practical applications due to the small sample size (SSS) problem and high computational costs. Various solutions have been proposed to address the SSS problem in both ratio trace LDA and trace ratio LDA (TRLDA). However, the iterative processing of large matrices often makes the computation process cumbersome. To address this issue, for TRLDA, we propose a novel random method that extracts orthogonal bases from matrices, allowing computations with small-sized matrices. This significantly reduces computational time without compromising accuracy. For ratio trace LDA, we introduce a fast generalized singular value decomposition (GSVD) algorithm, which demonstrates superior speed compared to MATLAB's built-in GSVD algorithm in experiments. By integrating this new GSVD algorithm into ratio trace LDA, we propose FGSVD-LDA, which exhibits low computational complexity and good classification performance. The experimental results show that both methods effectively achieve dimensionality reduction and deliver satisfactory classification accuracy.