Tikhonov regularization
Tikhonov Regularization, is the most commonly used method of regularization of ill-posed problems. In its simplest form, an ill-conditioned system of linear equations
- Ax = b,
where A is an m-by-n matrix above, x is a column vector with n entries and b is a column vector with m entries, is replaced by the problem of seeking an x to minimize
- ||Ax - b||2 + α2 ||x||2
for some suitably chosen Tikhonov factor α >0. Here ||.|| is the Euclidean norm.
This problem is now well conditioned and can be solved numerically. An explicit solution is given by
- (ATA + α2 I)-1 ATb
where I is the n-by-n identity matrix. For α =0 this reduced to the least squares solution of an overdetermined problem (m>n).
Statistical interpretation
Although at first the choice of the this regularized problem and indeed the parameter α seems rather arbitrary there is a sound statistical justification. Note that for an ill-posed problem one must necessarily introduce some additional assumptions in order to get a stable solution. Statistically we might assume that a priori we know that x is a random variable with a multivariate normal distribution, for simplicity we take the mean to be zero and assume that each component independent with standard deviation &sigmax. Our data is also subject to errors, and we take the error in b to be also independent with zero mean and standard deviation σb. Under these assumptions the Tikhonov regularized solution is the most probable solution given the data and the a priori distribution of x, according to Bayes theorem. The Tikhonov parameter is then α = σb/σx.
Generalized Tikhonov regularization
For general multivariate normal distributions for x and the data error, one can apply a transformation of the variables to reduce to the case above, equivalently one can seek an x to minimize
- ||Ax - b||P 2 + α2 ||x-x0|| Q 2
where we have used ||x||P to stand for the weighted norm xTx. In the statistical interpretation P is the inverse covariance matrix of b, -x0 the expected value of x, and Q is the inverse covariance matrix of x.
This can be solved explicitly, for example using the formula
- x0+ (ATQ A + P)-1ATQ(b- Ax0)
Regularization in Hilbert space
Typically discrete linear ill-condition problems result as discretization of integral equations, and one can formulate Tikhonov regularization in the original infinite dimensional context. In the above we can interpret A as a compact operator on Hilbert spaces, and x and b as elements in the domain and range of A. The operator ATA + α2 I is then a self adjoint bounded invertable operator for α >0.
History
Tikhonov regularization has been invented independently in many different contexts, it became widely known from its application to integral equations from the work of AN Tikhonov and of and DL Phillips on integral equations. Some authors use the term Tikhonov-Phillips regularization. The finite dimensional case expounded by AE Hoerl, who took a statistical approach. Following Hoerl it is known in the statistical literature as ridge regression.
References
- Hoerl AE, 1962, Application of ridge analysis to regression problems. Chemical Engineering Progress, 58, 54-59.
- Phillips DL, 1962, A technique for the numerical solution of certain integral equations of the first kind, J Assoc Comput Mach, 9, 84-97
- Tikhonov AN, 1963,Solution of incorrectly formulated problems andthe regularization method Soviet Math Dokl 4, 1035-1038 English translation of Dokl Akad Nauk SSSR 151, 1963, 501-504
- A Tarantola, 1987, Inverse Problem Theory, Elsevier, ISBN 0444427651.