# Registered Data

## [00810] Recent Developments on the Numerical Solution of Least Squares Problems

**Session Date & Time**:- 00810 (1/3) : 1C (Aug.21, 13:20-15:00)
- 00810 (2/3) : 1D (Aug.21, 15:30-17:10)
- 00810 (3/3) : 1E (Aug.21, 17:40-19:20)

**Type**: Proposal of Minisymposium**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**Classification**:__65F10__,__65F20__,__65F08__,__65F22__,__68W20__**Speakers Info**:- José Marí Mas (Universitat Politècnica de València)
- Alexis Montoison (GERAD and Polytechnique Montreal)
- Ning Zheng (The Institute of Statistical Mathematics)
- Kota Sugihara (None)
- Junjun Pan (The University of Hong Kong)
- Yimin Wei (Fudan University)
- Huaian Diao (Jilin University)
- Lu Wang (Hebei Normal University)
- Jun-Feng Yin (Tongji University)
- Raymond Chan (City University of Hong Kong)
- Masao Yamagishi (Tokyo Institute of Technology)
**Ken Hayami**(National Institute of Informatics)

**Talks in Minisymposium**:**[01317] Selecting Regularization Parameters for Nuclear Norm Type Minimization Problems****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.

**[01543] GMRES methods for tomographic reconstruction with an unmatched back projector****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.

**[01652] MinAres: An Iterative Solver for Symmetric Linear Systems****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.

**[01654] On Convergence Analysis of the Randomized Gauss-Seidel Method****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.

**[01679] GMRES using pseudoinverse for range symmetric singular systems****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.

**[01890] Condition numbers for the total least squares problems****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.

**[01895] A nonconvexly regularized least squares approach for sparsity aware estimation****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.

**[02050] Quantum-inspired algorithm for truncated total least squares solution****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.

**[02051] Solving rank deficient mixed sparse-dense linear least-squares problems by updating preconditioned iterative methods****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.

**[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.

**[02061] Preconditioners based on random sampling for solving least squares problems****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.

**[02064] Fast inverse LU preconditioner based on the Sherman--Morrison formula****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.