Published May 2014
| Published + Submitted
Journal Article
Open
Matrix concentration inequalities via the method of exchangeable pairs
Abstract
This paper derives exponential concentration inequalities and polynomial moment inequalities for the spectral norm of a random matrix. The analysis requires a matrix extension of the scalar concentration theory developed by Sourav Chatterjee using Stein's method of exchangeable pairs. When applied to a sum of independent random matrices, this approach yields matrix generalizations of the classical inequalities due to Hoeffding, Bernstein, Khintchine and Rosenthal. The same technique delivers bounds for sums of dependent random matrices and more general matrix-valued functions of dependent random variables.
Additional Information
© 2014 Institute of Mathematical Statistics. Received February 2012; revised February 2013. Supported in part by the U.S. Army Research Laboratory and the U.S. Army Research Office under Contract/Grant number W911NF-11-1-0391. Supported by the National Defense Science and Engineering Graduate Fellowship. Supported by ONR awards N00014-08-1-0883 and N00014-11-1002, AFOSR award FA9550- 09-1-0643, DARPA award N66001-08-1-2065 and a Sloan Research Fellowship. The authors thank Houman Owhadi for helpful conversations. This paper is based on two independent manuscripts from mid-2011 that both applied the method of exchangeable pairs to establish matrix concentration inequalities. One manuscript is by Mackey and Jordan; the other is by Chen, Farrell and Tropp. The authors have combined this research into a single unified presentation, with equal contributions from both groups.Attached Files
Published - euclid.aop.1395838119.pdf
Submitted - 1201.6002v2.pdf
Files
1201.6002v2.pdf
Files
(696.0 kB)
| Name | Size | Download all |
|---|---|---|
|
md5:5fb9004ff3359892a046a0d043830164
|
417.7 kB | Preview Download |
|
md5:1452c51e9052871480d5f050f9fde2db
|
278.3 kB | Preview Download |
Additional details
- Eprint ID
- 46085
- Resolver ID
- CaltechAUTHORS:20140605-070821101
- Army Research Laboratory
- W911NF-11-1-0391
- Army Research Office (ARO)
- National Defense Science and Engineering Graduate (NDSEG) Fellowship
- N00014-08-1-0883
- Office of Naval Research (ONR)
- N00014-11-1002
- Office of Naval Research (ONR)
- FA9550-09-1-0643
- Air Force Office of Scientific Research (AFOSR)
- N66001-08-1-2065
- Defense Advanced Research Projects Agency (DARPA)
- Alfred P. Sloan Foundation
- Created
-
2014-06-05Created from EPrint's datestamp field
- Updated
-
2021-11-10Created from EPrint's last_modified field