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:
““The matrix is God?”
“In a manner of speaking, although it would be more accurate ... to say that the matrix has a God, since this being’s omniscience and omnipotence are assumed to be limited to the matrix.”
“If it has limits, it isn’t omnipotent.”
“Exactly.... Cyberspace exists, insofar as it can be said to exist, by virtue of human agency.””
—William Gibson (b. 1948)
“... so far from thinking that a slaveholder is bound by the immoral and unconstitutional laws of the Southern States, we hold that he is solemnly bound as a man, as an American, to break them, and that immediately and openly ...”
—Angelina Grimké (1805–1879)