What Does the Picard Condition Say About Matrix Solution?
Go to our page of Regularized Solvers which use the Picard Condition
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.