This perspective focuses on the fast algorithm design for singular value decomposition and inverse computation of nearly low-rank matrices that are potentially of big sizes.
Singular value decomposition (SVD) and matrix inversion are ubiquitous in scientific computing. Both tasks are computationally demanding for large scale matrices. Existing algorithms can approximatively solve these problems with a given rank, which however is unknown in practice and requires considerable cost for tuning. In this paper, we tackle the SVD and matrix inversion problems from a new angle, where the optimal rank for the approximate solution is explicitly guided by the distribution of the singular values. Under the framework, we propose a precision-induced random re-normalization procedure for the considered problems without the need of guessing a good rank. The new algorithms built upon the procedure simultaneously calculate the optimal rank for the task at a desired precision level and lead to the corresponding approximate solution with a substantially reduced computational cost. The promising performance of the new algorithms is supported by both theory and numerical examples.
Low-rank matrix approximation play a ubiquitous role in various applications such as image processing, signal processing, and data analysis. Recently, random algorithms of low-rank matrix approximation have gained widespread adoption due to their speed, accuracy, and robustness, particularly in their improved implementation on modern computer architectures. Existing low-rank approximation algorithms often require prior knowledge of the rank of the matrix, which is typically unknown. To address this bottleneck, we propose a low-rank approximation algorithm termed efficient orthogonal decomposition with automatic basis extraction (EOD-ABE) tailored for the scenario where the rank of the matrix is unknown. Notably, we introduce a randomized algorithm to automatically extract the basis that reveals the rank. The efficacy of the proposed algorithms is theoretically and numerically validated, demonstrating superior speed, accuracy, and robustness compared to existing methods. Furthermore, we apply the algorithms to image reconstruction, achieving remarkable results.
In this paper, we consider the problem of computing an arbitrary generalized singular value of a Grassman or real matrix pair and a triplet of associated generalized singular vectors. Based on the QR factorization, the problem is reformulated as two novel trace maximization problems, each of which has double variables with unitary constraints or orthogonal constraints. Theoretically, we show that the arbitrarily prescribed extreme generalized singular values and associated triplets of generalized singular vectors can be determined by the global solutions of the constrained trace optimization problems. Then we propose a geometric inexact Newton–conjugate gradient (Newton-CG) method for solving their equivalent trace minimization problems over the Riemannian manifold of all fixed-rank partial isometries. The proposed method can extract not only the prescribed extreme generalized singular values but also associated triplets of generalized singular vectors. Under some mild assumptions, we establish the global and quadratic convergence of the proposed method. Finally, numerical experiments on both synthetic and real data sets show the effectiveness and high accuracy of our method.