Overview

From a general perspective, we can essentially choose between two classes of regularization methods: those that are based on some kind of "canonical decomposition" such as the QR factorization or the singular value decomposition (SVD), and those that avoid such decompositions. In the first class of methods we find the direct methods treated in this chapter, while the iterative methods (treated in the next chapter) belong to the second class of algorithms.

In this chapter we also briefly consider a third class of regularization problems, namely, those which lead to nonlinear optimization problems.

Since all direct regularization methods are based on standard operations and decompositions in numerical linear algebra (such as matrix multiplications, backsubstitutions, orthogonal transformations, QR factorizations, bidiagonal reductions, SVDs, etc.), the computational effort involved in a direct method can be estimated a priori.

The standard linear algebra operations and decompositions are almost always available on high-performance computers in highly efficient implementations, often based on the basic linear algebra subprograms (BLAS) and/or the LAPACK Library [4]. Efficient parallel numerical linear algebra routines [25], [83], [165] are available on most parallel computers. Hence, it is not too difficult to develop an efficient implementation of a direct regularization method.

We wish to emphasize again that there are no computational difficulties involved with the use of rectangular regularization matrices L in connection with general-form regularization, when the transformation algorithms from 2.3 are used. Moreover, as long as L is a banded matrix, the computational overhead is negligible compared to...