[tlb]

"Provably optimal" always involves unwarranted assumptions. For example, least-squares fitting is provably optimal, assuming all your distributions are independent and gaussian. Image compression quality is all about sensitivity of the human visual system to various kinds of errors, so nothing can be proven optimal, ever.

[eru]

Proving still retains value. Because you reduce the burden of choosing a good algorihtm to choosing good assumptions.

[jibiki]

One common set of assumptions in image denoising is that:

1. The pixels in the output image should be close in value to the corresponding pixels in the input image.

2. Neighboring pixels in the output image should have similar values.

I wonder if anyone has compared compression techniques using these sorts of assumptions.