Why Inverse Problems are Hard

The intersection of Ill-posedness, ill-conditioning and algorithmic constraints

Inverse problems show up all over, but they are hard. Why is this? Let's break it down:

𝗞𝗲𝘆 𝗧𝗲𝗿𝗺𝘀:

- forward operator G

- parameters x

- measurement data d

- mathematical model G(x) = d

𝗙𝗼𝗿𝘄𝗮𝗿𝗱 𝗣𝗿𝗼𝗯𝗹𝗲𝗺:

Use G to computed d from x

𝗜𝗻𝘃𝗲𝗿𝘀𝗲 𝗣𝗿𝗼𝗯𝗹𝗲𝗺:

Use G to computed x from d

An inverse problem is 𝘄𝗲𝗹𝗹-𝗽𝗼𝘀𝗲𝗱 provided it has a unique solution x that depends continuously on measurement data d. If not, we call it 𝗶𝗹𝗹-𝗽𝗼𝘀𝗲𝗱.

We also say the problem is 𝘄𝗲𝗹𝗹-𝗰𝗼𝗻𝗱𝗶𝘁𝗶𝗼𝗻𝗲𝗱 provided small changes in d yield small changes in x. If not, we call it 𝗶𝗹𝗹-𝗰𝗼𝗻𝗱𝗶𝘁𝗶𝗼𝗻𝗲𝗱.

Inverse problems are often ill-posed and/or ill-conditioned. Well-posed surrogates problems must be carefully crafted using the forward operator G and prior knowledge. Various constraints may also be imposed on algorithms for computing solutions x.

Together, ill-posedness, ill-conditioning, and algorithmic constraints make inverse problems hard.

Check out the slides below for more details and examples.

Cheers,

Howard

p.s. For more details, I recommend reading Chapter 1 of Richard Aster, Brian Borchers, and Clifford Thurber's book "Parameter Estimation and Inverse Problems" and Part 3 of Llyod Tefethen and David Bau's "Numerical Linear Algebra."