We study the solution of the linear least-squares problem minx ∥b − Ax∥2 where the matrix A ∈ Rm×n (m ≥ n) has rank n and is large and sparse. We assume that A is available as a matrix, not an operator. The preconditioning of this problem is difficult because the matrix A does not have the properties of differential problems that make standard preconditioners effective. Incomplete Cholesky techniques applied to the normal equations do not produce a well-conditioned problem. We attempt to bypass the ill-conditioning by finding an n × n nonsingular submatrix B of A that reduces the Euclidean norm of AB−1. We use B to precondition a symmetric quasi-definite linear system whose condition number is then independent of the condition number of A and has the same solution as the original least-squares problem. We illustrate the performance of our approach on some standard test problems and show it is competitive with other approaches.

Preconditioning linear least-squares problems by identifying a basis matrix

Arioli M;
2015

Abstract

We study the solution of the linear least-squares problem minx ∥b − Ax∥2 where the matrix A ∈ Rm×n (m ≥ n) has rank n and is large and sparse. We assume that A is available as a matrix, not an operator. The preconditioning of this problem is difficult because the matrix A does not have the properties of differential problems that make standard preconditioners effective. Incomplete Cholesky techniques applied to the normal equations do not produce a well-conditioned problem. We attempt to bypass the ill-conditioning by finding an n × n nonsingular submatrix B of A that reduces the Euclidean norm of AB−1. We use B to precondition a symmetric quasi-definite linear system whose condition number is then independent of the condition number of A and has the same solution as the original least-squares problem. We illustrate the performance of our approach on some standard test problems and show it is competitive with other approaches.
preconditioner
least-squares
basis matrix selection
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.12572/6189
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
social impact