Fast-Parallel Singular Value Thresholding for Low-rank Analysis with Small Columns Matrices

This paper proposes a fast-parallel method for singular value thresholding, aimed at low-rank analysis of many small matrices. In low-rank analysis, the problem of regularizing the nuclear norm, defined as the sum of singular values, is typically solved by iteratively applying singular value thresholding. However, this process often requires a long run-time due to the computational cost of singular value decomposition. To address this issue, we provide a method that is computationally inexpensive and can be executed in parallel. The core of our approach lies in the discovery of geometric properties of the nuclear norm, leading to a computational process that is fundamentally different from conventional methods. Our method is fast because it does not require singular value decomposition, which has been a bottleneck in terms of computational complexity and parallelism. We design the computation method for two-column matrices as the main proposal, and also demonstrate an optional method for approximately solving the three-column matrices problem. Through experiments, the proposed method calculated singular value thresholding up to 65.81 times faster with higher calculation accuracy than conventional methods. We also applied our method to real data for noise removal in 3D models and confirmed the improvement in computational speed.