News

Seminar

Low-rank Matrix-valued Chernoff Bounds and Applications

Tasos Zouzias
University of Toronto

Date: April 7, 2010

Abstract:

In this talk we will discuss some recent results on a non-trivial generalization of the usual Chernoff bound for matrix-valued random variables by Ahlswede and Winter. I am going to present this generalization and compare it with Vershynin and Rudelson deviation inequality for rank-one symmetric operators. Then I will show how Vershynin and Rudelson's approach can be adapted to prove a sharper matrix-valued Chernoff bound when the (matrix) samples have low-rank. Finally, I will show the usefulness of the latter result on the problem of approximating (w.r.t. the spectral norm) matrix multiplication.
Joint work with Avner Magen.

References:

[AW] R. Ahlswede and A. Winter: Strong Converse for Identification via Quantum Channels

[VR] M. Rudelson and Roman Vershynin: Sampling from Large Matrices : An approach through Geometric Functional Analysis.

Last updated: March 31, 2010