A Caltech Library Service

Deriving Matrix Concentration Inequalities from Kernel Couplings

Paulin, Daniel and Mackey, Lester and Tropp, Joel A. (2013) Deriving Matrix Concentration Inequalities from Kernel Couplings. . (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


This paper derives exponential tail bounds and polynomial moment inequalities for the spectral norm deviation of a random matrix from its mean value. The argument depends on a matrix extension of Stein's method of exchangeable pairs for concentration of measure, as introduced by Chatterjee. Recent work of Mackey et al. uses these techniques to analyze random matrices with additive structure, while the enhancements in this paper cover a wider class of matrix-valued random elements. In particular, these ideas lead to a bounded differences inequality that applies to random matrices constructed from weakly dependent random variables. The proofs require novel trace inequalities that may be of independent interest.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Tropp, Joel A.0000-0003-1024-1791
Additional Information:This paper is based on two independent manuscripts from late 2012 that both used kernel couplings to establish matrix concentration inequalities. One manuscript is by Paulin; the other is by Mackey and Tropp. The authors have combined this research into a unified presentation, with equal contributions from both groups. Paulin thanks his thesis advisors, Louis Chen and Adrian Röllin, for their helpful comments on this manuscript. Tropp was supported by ONR awards N00014-08-1-0883 and N00014-11-1002, AFOSR award FA9550-09-1-0643, and a Sloan Research Fellowship.
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-08-1-0883
Office of Naval Research (ONR)N00014-11-1002
Air Force Office of Scientific Research (AFOSR)FA9550-09-1-0643
Alfred P. Sloan FoundationUNSPECIFIED
Subject Keywords:Concentration inequalities, Stein’s method, random matrix, non-commutative, exchangeable pairs, coupling, bounded differences, Dobrushin dependence, Ising model, Haar measure, trace inequality
Classification Code:AMS 2000 subject classifications: Primary 60B20, 60E15; secondary 60G09, 60F10
Record Number:CaltechAUTHORS:20180831-112127106
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:89335
Deposited By: George Porter
Deposited On:04 Sep 2018 14:37
Last Modified:03 Oct 2019 20:15

Repository Staff Only: item control page