Title: Semidefinite Relaxation and Statistical Estimation
| Speaker: | Arkadi Nemirovski |
| Affiliation: | Georgia Institute of Technology |
| Location: | MC 5501 |
Abstract:
We consider the problem of recovering linear image Bx of an unknown signal x known to belong a given convex compact signal set X from corrupted by Gaussian noise observation of linear image Ax of the signal. Our main result states that under some structural assumptions on X (satisfied, e.g., when X is the intersection of ellipsoids centered at the origin, or the unit ball of the spectral norm in the space of matrices) one can build, in a computationally efficient fashion, a linear in observation estimate which is provably nearly optimal in terms of risk (worst-case, over signals from X, expected recovery error) among all estimates, linear and nonlinear alike. We demonstrate that similar results remain true in the case of "uncertain-but-bounded" observation noise (adversarial noise varying in a given convex compact set satisfying the same structural assumptions as X). An instrumental role in all our developments is played by important by their own right approximation results for semidefinite relaxation to be presented in the talk.
The talk is based on joint research with Dr. Anatoli Iouditski, University Grenoble-Alpes.