Abstract : Talks will be presented on recent developments in the numerical solution of least squares problems. Topics included are, numerical solution of least squares problems including preconditioners, rank-deficient and singular systems, quaternion least squares problems, total least squares problems including condition numbers and quantum-inspired algorithms, randomized algorithms such as the randomized Kaczmarz method, and regularization methods for the solution of ill-posed problems.
Organizer(s) : Ken Hayami, Yimin Wei, Raymond Chan, José Mas
[01652] MinAres: An Iterative Solver for Symmetric Linear Systems
Format : Talk at Waseda University
Author(s) :
Alexis Montoison (GERAD and Polytechnique Montréal)
Dominique Orban (GERAD and Polytechnique Montréal)
Michael Saunders (Stanford University)
Abstract : We introduce an iterative solver named MinAres for symmetric linear systems $Ax \approx b$, where $A$ is possibly singular.
MinAres is based on the symmetric Lanczos process, like Minres and Minres-QLP, but it minimizes $\|Ar_k\|$ in each Krylov subspace rather than $\|r_k\|$, where $r_k$ is the current residual vector.
In our experiments, MinAres terminates significantly earlier than Minres on ill-conditioned and singular linear systems.
[02064] Fast inverse LU preconditioner based on the Sherman--Morrison formula
Format : Talk at Waseda University
Author(s) :
José Mas (Universitat Politècnica de València)
José Marín (Universitat Politècnica de València)
Juana Cerdán (Universitat Politècnica de València)
Rafael Bru (Universitat Politècnica de València)
Abstract : A fast version of an approximate inverse $LU$ preconditioner to solve linear systems is constructed based on the Sherman--Morrison formula. A multiplicative decomposition of the approximate inverse of the coefficient matrix is obtained applying recursively the inversion formula. Moreover, this recursion can be expresed in a compact form which is used to compute the preconditioner.
The method is stable for nonsingular $M$-matrices and $H$-matrices.
Numerical results show that the new proposal is robust and competitive compared with other preconditioners.
[01679] GMRES using pseudoinverse for range symmetric singular systems
Format : Talk at Waseda University
Author(s) :
Kota Sugihara (National institute of informatics)
Ken Hayami (Professor Emeritus, National Institute of Informatics/The Graduate University for Advanced Studies (SOKENDAI))
Abstract : For range symmetric singular linear systems, GMRES converges to the least squares solution in exact arithmetic. We derive necessary and sufficient conditions for GMRES to converge assuming exact arithmetic except for the computation of the elements of the Hessenberg matrix. In practice, GMRES may not converge due to numerical instability. Thus, we propose using the pseudoinverse for the solution of severely ill-conditioned Hessenberg systems. Numerical experiments indicate that the method is effective.
[02051] Solving rank deficient mixed sparse-dense linear least-squares problems by updating preconditioned iterative methods
Format : Talk at Waseda University
Author(s) :
Ning Zheng (The Institute of Statistical Mathematics)
Abstract : We consider the preconditioning of linear least squares problem when the large sparse coefficient matrix contains a few dense rows. Such mixed sparse dense least squares problem arises from many scientific practical problems. We propose preconditioned iterative methods for solving the problem when the sparse part is rank deficient and the whole system is rank deficient, respectively. Numerical experiments are presented to show the feasibility and efficiency of the proposed methods.
[02061] Preconditioners based on random sampling for solving least squares problems
Format : Talk at Waseda University
Author(s) :
Junfeng Yin (Tongji University)
Yuxin Ye (Tongji University)
Aqin Xiao (Tongji University)
Nan Li (Tongji University)
Ning Zheng (Tongji University)
Abstract : For the solution of large sparse least squares problems, preconditioned Krylov subspace methods are usually the fist choice and the preconditioners play the important roles in accelerating the convergence of the iteration. After the study on incomplete QR decomposition preconditioners based on Givens rotation, we proposed the preconditioners on random sampling and QR decomposition for solving least squares problems. Theoretical analysis and numerical experiments are presented to show the efficiency of the preconditioners, compared with the existing preconditioners.
[01654] On Convergence Analysis of the Randomized Gauss-Seidel Method
Format : Online Talk on Zoom
Author(s) :
Lu Wang (Hebei Normal University)
Abstract : The Gauss-Seidel and Kaczmarz methods are two classical iteration methods for solving systems of linear equations, which operate in column and row spaces, respectively. In this report, by utilizing the inner connections between these two methods and the convergence analysis of the randomized Kaczmarz method, we give a new upper bound for the convergence rate of the randomized Gauss-Seidel method. Moreover, these convergence results are extended to the more general extrapolated randomized Gauss-Seidel method.
[01890] Condition numbers for the total least squares problems
Format : Online Talk on Zoom
Author(s) :
Huaian Diao (Jilin University)
Abstract : The total least squares problems (TLS) is a generalization of the linear least squares problem and has many applications in linear system theory, computer vision, image reconstruction, system identification, speech and audio processing, modal and spectral analysis, etc. Perturbation analysis and algorithms for TLS have been studied extensively in the past decades. In this talk, I shall report our recent progresses on condition numbers for TLS.
[02050] Quantum-inspired algorithm for truncated total least squares solution
Format : Talk at Waseda University
Author(s) :
Yimin Wei (Fudan University)
Abstract : Compared with the ordinary least squares method, for total least squares (TLS) problem we take
into account not only the observation errors, but also the errors in the measurement matrix, which
is more realistic in practical applications. For the large-scale discrete ill-posed problem Ax ≈ b,
we introduce the quantum-inspired techniques to approximate the truncated total least squares
(TTLS) solution.
[01317] Selecting Regularization Parameters for Nuclear Norm Type Minimization Problems
Format : Talk at Waseda University
Author(s) :
Raymond Honfu Chan (City University of Hong Kong)
Kexin Li (Hunan Normal University)
Hongwei Li (Captial Normal University)
Youwei Wen (Hunan Normal University)
Abstract : The reconstruction of low-rank matrix from its noisy observation is a constrained nuclear norm minimization problem, where the constraint bound $\eta$ can be estimated from the noise variance. Its solution can be obtained by the singular value thresholding operator where the thresholding parameter $\lambda$ is the same as the regularization parameter. We derive a closed-form solution for $\lambda$ in terms of $\eta$ which allows us to automatically choose $\lambda$ by the discrepancy principle.
[01895] A nonconvexly regularized least squares approach for sparsity aware estimation
Format : Talk at Waseda University
Author(s) :
Masao Yamagishi (Tokyo Institute of Technology)
Isao Yamada (Tokyo Institute of Technology)
Abstract : We present basic ideas and applications of a nonconvexly regularized least squares model ((\text{LiGME model})), which can achieve its overall convexity through strategic tuning of a matrix-valued parameter called the Generalized Moreau Enhancement ((\text{GME})) matrix. The LiGME model can exploit sparsity in a linearly transformed domain. Recent related advancements will also be introduced briefly.
[02058] Separable Quaternion Matrix Factorization
Author(s) :
Junjun Pan (The University of Hong Kong)
Michael Ng (The University of Hong Kong)
Abstract : This presentation proposes a separable low-rank quaternion linear mixed model for polarized signals. The corresponding problem is called Separable Quaternion Matrix Factorization (SQMF). We discussed some properties of matrices that SQMF can decompose. We propose a heuristic algorithm called the quaternion successive projection algorithm to determine the source matrix. To compute the activation matrix, we use the block coordinate descent algorithm. Polarization and spectro-polarimetric images are tested to verify the model's effectiveness.
[01543] GMRES methods for tomographic reconstruction with an unmatched back projector
Format : Talk at Waseda University
Author(s) :
Ken Hayami (Professor Emeritus, National Institute of Informatics/The Graduate University for Advanced Studies (SOKENDAI))
Per Christian Hansen (Technical University of Denmark)
Keiichi Morikuni (University of Tsukuba)
Abstract : Unmatched pairs of forward and back projectors are common in X-ray CT computations due to the need for fast algorithms that best utilize the computer hardware. We propose using preconditioned GMRES, namely, AB-, BA- GMRES, to handle the unmatched normal equations. They are simple to implement and rely only on available forward and back projectors. Numerical experiments show that they exhibit a desired semi-convergence behavior and are suited for large-scale CT reconstruction problems with noisy data.
