**What Does the Picard Condition Say About Matrix Solution?**

R. E Jones

**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

USV^{T}x = b

or

X= VS^{+}U^{T}b.

(S^{+} is the same as S^{-1}
except zero is used when S_{i} is zero.)

Here the Fourier coefficients are the elements of
U^{T}*b. If the Picard condition is satisfied then the elements of U^{T}b
decrease faster than the elements of S, so the elements of the “quotient”
vector S^{+}*U^{T}*b then **decrease**.
If instead the elements of S^{+}*U^{T}*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 U^{T}*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 U^{T}b 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, x_{r}, then compute the
corresponding right hand side Ax_{r}, 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 **to satisfy this condition** if a useful
solution is to be obtained. A solution based on a vector S^{+}*U^{T}*b
which does not decrease is generally not useful.

We use this Picard condition in our AUTOREG/AUTOREJ
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^{+}U^{T}b 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^{+}U^{T}b (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 U^{T}b.
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.