Conjugate gradients for symmetric positive semidefinite least-squares problems

ABSTRACT

The cgSLS (conjugate gradients for symmetric positive semidefinite least-squares) algorithm is presented. The algorithm exploits the cyclic property of invariant Krylov spaces to reduce the least-squares problem with a symmetric positive semidefinite matrix A to the minimization of the related energy function with the Hessian A on the range of A, so that a simple modification of the conjugate gradient (CG) method is applicable. At the same time, the algorithm generates approximations of the projection of the right-hand side to the range of A. The asymptotic rate of convergence of the new algorithm is proved to be the same as that of the CG method for the related consistent problem. An error bound in terms of the square root of the regular condition number of A is also given. The performance of the algorithm is demonstrated by numerical experiments.

KEYWORDS:

• Semidefinite least-squares
• conjugate gradients

2010 AMS SUBJECT CLASSIFICATIONS:

• Primary: 65F10
• Secondary: 65N22

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was supported by the European Regional Development Fund in the IT4Innovations Centre of Excellence project [CZ.1.05/1.1.00/02.0070], by the project SPOMECH reg. no. CZ.1.07/2.3.00/20.0070, and by the project of major infrastructures for research, development and innovation of MEYS with reg. num. LM2011033.