Adaptive Rank Selection for Low-Rank Matrix Approximation via Multi-Objective Error–Cost Optimization

Source abstract

Low-rank matrix approximation is a fundamental tool in modern computational science, with applications ranging from image compression and signal processing to machine learning and scientific computing. A critical and often ad-hoc step in these methods is the selection of the approximation rank. Existing approaches typically rely on fixed ranks, heuristic thresholds, or application-specific criteria that fail to balance the competing demands of accuracy, computational cost, and memory usage. In this paper, we propose a novel multi-objective optimization framework for adaptive rank selection in low-rank matrix approximation. Unlike existing adaptive rank selection methods that optimize a single criterion or rely on manually selected thresholds, the proposed framework formulates rank selection as a multi-objective optimization problem that simultaneously optimizes reconstruction accuracy, computational cost, and memory consumption through automatically computed heuristic weights. We prove the existence and non-increasing property of the error function, and demonstrate that the heuristic weights correctly respond to extreme matrix properties. The algorithm is implemented with both full SVD and randomized SVD variants, the latter incorporating adaptive oversampling and boundary detection for scalability. Extensive numerical experiments on synthetic matrices (moderate-decay random, slow-decay random, ill-conditioned Hilbert, sparse diagonal) and a real-world grayscale image demonstrate that our method consistently selects ranks that achieve favorable error–cost trade-offs, outperforming fixed-rank SVD baselines under the evaluated settings. On a 1000x800 matrix, the randomized variant selects a rank within 8 of the full SVD optimum while providing approximately twofold speedup. The method is reproducible, with all code provided in the supplementary materials.