What Does the Picard Condition Say About Matrix Solution?

 

Introduction. The Discrete Picard Condition was probably popularized most by Per Christian Hansen. For example, see The discrete picard condition for discrete ill-posed problems in BIT, Volumne 30, Number 4. Here is the abstract for that paper:

We investigate the approximation properties of regularized solutions to discrete ill-posed least squares problems. A necessary condition for obtaining good regularized solutions is that the Fourier coefficients of the right-hand side, when expressed in terms of the generalized SVD associated with the regularization problem, on the average decay to zero faster than the generalized singular values. This is the discrete Picard condition. We illustrate the importance of this condition theoretically as well as experimentally.

 

This topic has also been discussed in sources such as the book “Regularization of Inverse Problems” by Heinz W. Engl et al, in Theorem 2.8. (Note: the need for Fourier coefficients to converge has been understood for many years. We used this method in the 1980’s before the popularization of the concept, and it was well known to any advanced mathematics student far before that. But it was not widely discussed before the popularization by Hansen.)

 

The impact of this statement is significant for anyone attempting to regularize an ill-conditioned matrix system. But it is not obscure. If we are solving

Ax = b

by using the SVD then we have

USVTx = b

or

X= VS+UTb.

(S+ is the same as S-1 except zero is used when Si is zero.)

 

Here the Fourier coefficients are the elements of UT*b. If the Picard condition is satisfied then the elements of UTb decrease faster than the elements of S, so the elements of the “quotient” vector S+*UT*b then decrease. If instead the elements of S+*UT*b do something else – such as begin to drop then reverse and grow – then the Picard condition is not satisfied (and vice-versa).

 

Application. The value of noting this condition is, as the abstract says, that the condition must be satisfied in order to obtain “good regularized solutions”. Why is this condition often not satisfied? Usually because the elements of UT*b do not continue to decrease because random errors in b prevent the numeric cancellation that should occur to make the element get smaller. For example, an ill-conditioned set of equations might produce a UTb vector that decreases to a certain level, say about 0.001, then just randomly varies around that level. On the other hand, the elements of S my decrease straight to zero, or to round-off level (maybe 10-14).

 

So what must be done if the Picard condition is not satisfied, so we can get a usable solution? We must change the matrix, A, or the right side vector, b, or both, in some way. For example, Tikhonov regularization can be viewed as modifying A (by increasing the small singular values) or as modifying b. (To view Tikhonov as a modification to b, just compute the usual regularized solution, xr, then compute the corresponding right hand side Axr, and compare this to the original b.)

 

In other words, we must change either the model, or the observed data, or both.

 

Considerations. Note that Picard condition does not say that the system cannot be regularized to produce a useful solution; rather it says that an ill-conditioned system must be regularized (some way or another) if a useful solution is to be obtained. A solution based on a vector S+*UT*b which does not decrease is generally not useful.

 

We use this Picard condition in our AUTOREG automatic regularization scheme. We have developed heuristics which we use to decide exactly when to declare a system of equations as clearly ill-conditioned, and to decide a “usable rank”. This decision is harder than you may expect, because the vector S+UTb seldom smoothly decreases, even when the system is well conditioned. So we have to look instead at a moving average of the values in S+UTb (or their squares) and look for a minimum, followed by significant growth in the moving average. The point where the average grows above the minimum by a certain factor helps locate the point where error is evidently dominating UTb. Thus a “usable rank” is determined, and an error estimate for the right side vector can be made, and this facilitates Tikhonov regularization. See details and other documentation in this web site for more information.

 

Other details. We do not mean to imply that there are no other issues of interest here. There are. For example, note that we have no information yet on how closely a regularized solution may be to the “true” solution. Yet this may be very important to know in some situations. That is a topic for further study.