LSV-based tail inequalities for sums of random matrices. (English) Zbl 1478.15052
Summary: The techniques of random matrices have played an important role in many machine learning models. In this letter, we present a new method to study the tail inequalities for sums of random matrices. Different from other work [R. Ahlswede and A. Winter, IEEE Trans. Inf. Theory 48, No. 3, 569–579 (2002; Zbl 1071.94530); J. A. Tropp, Found. Comput. Math. 12, No. 4, 389–434 (2012; Zbl 1259.60008); D. Hsu et al., Electron. Commun. Probab. 17, Paper No. 14, 13 p. (2012; Zbl 1243.60007)], our tail results are based on the largest singular value (LSV) and independent of the matrix dimension. Since the LSV operation and the expectation are noncommutative, we introduce a diagonalization method to convert the LSV operation into the trace operation of an infinitely dimensional diagonal matrix. In this way, we obtain another version of Laplace-transform bounds and then achieve the LSV-based tail inequalities for sums of random matrices.
MSC:
| 15B52 | Random matrices (algebraic aspects) |
| 15A45 | Miscellaneous inequalities involving matrices |
| 15A18 | Eigenvalues, singular values, and eigenvectors |
| 60B20 | Random matrices (probabilistic aspects) |
Software:
mftoolboxReferences:
| [1] | Ahlswede, R., & Winter, A. (2002). Strong converse for identification via quantum channels. IEEE Transactions on Information Theory, 48(3), 569-579. , · Zbl 1071.94530 |
| [2] | Bian, W., & Tao, D. (2014). Asymptotic generalization bound of Fisher’s linear discriminant analysis. IEEE Transactions on Pattern Analysis and Machine Intelligence, 36(12), 2325-2337. , |
| [3] | Cantrell, R., & Cosner, C. (2004). Spatial ecology via reaction-diffusion equations. Hoboken, NJ: Wiley. , · Zbl 1059.92051 |
| [4] | Dai, G., Ma, R., Wang, H., Wang, F., & Xu, K. (2015). Partial differential equations with Robin boundary condition in online social networks. Discrete and Continuous Dynamical Systems-Series B, 20(6), 1609-1624. , · Zbl 1334.35116 |
| [5] | Hein, M., & Bühler, T. (2010). An inverse power method for nonlinear eigenproblems with applications in 1-spectral clustering and sparse PCA. In J. D. Lafferty, C. K. I. Williams, J. Shawe-Taylor, R. S. Zemel, & A. Culotta (Eds.), Advances in neural information processing systems, 24 (pp. 847-855). Red Hook, NY: Curran. |
| [6] | Hein, M., & Setzer, S. (2011). Beyond spectral clustering: Tight relaxations of balanced graph cuts. In J. Shawe-Taylor, R. S. Zemel, P. L. Bartlett, F. Pereira, & K. Q. Weinberger (Eds.), Advances in neural information processing systems, 25 (pp. 2366-2374). Red Hook, NY: Curran. |
| [7] | Higham, N. (2008). Functions of matrices: Theory and computation. Philadelphia: SIAM. , · Zbl 1167.15001 |
| [8] | Hsu, D., Kakade, S., & Zhang, T. (2012). Tail inequalities for sums of random matrices that depend on the intrinsic dimension. Electronic Communications in Probability, 17(14), 1-13. · Zbl 1243.60007 |
| [9] | Jost, L., Setzer, S., & Hein, M. (2014). Nonlinear eigenproblems in data analysis: Balanced graph cuts and the ratiodca-prox. In S. Dahlke, W. Dahmen, M. Griebel, W. Hackbusch, K. Ritter, R. Schneider … H. Yserentant (Eds.), Extraction of quantifiable information from complex systems (pp. 263-279). New York: Springer. · Zbl 1329.68218 |
| [10] | Mackey, L., Jordan, M., Chen, R., Farrell, B., & Tropp, J. (2014). Matrix concentration inequalities via the method of exchangeable pairs. Annals of Probability, 42(3), 906-945. , · Zbl 1294.60008 |
| [11] | Marshall, A., Olkin, I., & Arnold, B. (2010). Inequalities: Theory of majorization and its applications. New York: Springer Science & Business Media. · Zbl 1219.26003 |
| [12] | Muir, D., & Mrsic-Flogel, T. (2015). Eigenspectrum bounds for semirandom matrices with modular and spatial structure for neural networks. Physical Review E, 91(4), 042808. , |
| [13] | Rajan, K., & Abbott, L. (2006). Eigenvalue spectra of random matrices for neural networks. Physical Review Letters, 97(18), 188104. , |
| [14] | Tropp, J. (2012). User-friendly tail bounds for sums of random matrices. Foundations of Computational Mathematics, 12(4), 389-434. , · Zbl 1259.60008 |
| [15] | Vershynin, R. (2010). Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3027 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
