Matrix Chernoff Bound
Rudolf Ahlswede and Andreas Winter introduced (Ahlswede & Winter 2003) a Chernoff bound for matrix-valued random variables.
If is distributed according to some distribution over matrices with zero mean, and if are independent copies of then for any ,
where holds almost surely and is an absolute constant.
Notice that the number of samples in the inequality depends logarithmically on . In general, unfortunately, such a dependency is inevitable: take for example a diagonal random sign matrix of dimension . The operator norm of the sum of independent samples is precisely the maximum deviation among independent random walks of length . In order to achieve a fixed bound on the maximum deviation with constant probability, it is easy to see that should grow logarithmically with in this scenario.
The following theorem can be obtained by assuming has low rank, in order to avoid the dependency on the dimensions.
Read more about this topic: Chernoff Bound
Famous quotes containing the words matrix and/or bound:
“As all historians know, the past is a great darkness, and filled with echoes. Voices may reach us from it; but what they say to us is imbued with the obscurity of the matrix out of which they come; and try as we may, we cannot always decipher them precisely in the clearer light of our day.”
—Margaret Atwood (b. 1939)
“Women of a selected class, by the use of slaves and servants have become inactive, the mere recipients of values, no longer creators but “feeding on unearned wealth.” This hurts their nature and debases the social fabric. If a woman does no labor in her home which could properly make her self-supporting outside that home she is in duty bound to do something outside her home to justify her claim to support.”
—Anna Garlin Spencer (1851–1931)