Resolution beyond the diffraction limit for regularized object restoration

We propose a new formulation of Miller's regularization theory, which is particularly suitable for object restoration problems. By means of simple geometrical arguments, we obtain upper and lower bounds for the errors on regularized solutions. This leads to distinguish between ' Holder continuity ' which is quite good for practical computations and ` logarithmic continuity ' which is very poor. However, in the latter case, one can reconstruct local weighted averages of the solution. This procedure allows for precise valuations of the resolution attainable in a given problem. Numerical computations, made for object restoration beyond the diffraction limit in Fourier optics, show that, when logarithmic continuity holds, the resolution is practically independent of the data noise level. © 1980 Taylor & Francis Group, LLC.

Approximation limits of linear programs (beyond hierarchies)

We develop a framework for proving approximation limits of polynomial size linear programs (LPs) from lower bounds on the nonnegative ranks of suitably defined matrices. This framework yields unconditional impossibility results that are applicable to any LP as opposed to only programs generated by hierarchies. Using our framework, we prove that O(n^1/2-ε)-approximations for CLIQUE require LPs of size 2^nΩ(ε). This lower bound applies to LPs using a certain encoding of CLIQUE as a linear optimization problem. Moreover, we establish a similar result for approximations of semidefinite programs by LPs. Our main technical ingredient is a quantitative improvement of Razborov's [38] rectangle corruption lemma for the high error regime, which gives strong lower bounds on the nonnegative rank of shifts of the unique disjointness matrix.