Matrix Infinitely Divisible Series: Tail Inequalities and Their Applications
点击次数：
论文类型：期刊论文
发表时间：2020-02-01
发表刊物：IEEE TRANSACTIONS ON INFORMATION THEORY
收录刊物：EI、SCIE
卷号：66
期号：2
页面范围：1099-1117
ISSN号：0018-9448
关键字：Linear matrix inequalities; Optimization; Random variables; Eigenvalues and eigenfunctions; Compressed sensing; Gaussian distribution; Covariance matrices; Random matrix; tail inequality; infinitely divisible distribution; largest eigenvalue; optimization; restricted isometry property; compressed sensing
摘要：In this paper, we study tail inequalities of the largest eigenvalue of a matrix infinitely divisible (i.d.) series, which is a finite sum of fixed matrices weighted by i.d. random variables. We obtain several types of tail inequalities, including Bennett-type and Bernstein-type inequalities. This allows us to further bound the expectation of the spectral norm of a matrix i.d. series. Moreover, by developing a new lower-bound function for $Q(s)=(s+1)\log (s+1)-s$ that appears in the Bennett-type inequality, we derive a tighter tail inequality of the largest eigenvalue of the matrix i.d. series than the Bernstein-type inequality when the matrix dimension is high. The resulting lower-bound function is of independent interest and can improve any Bennett-type concentration inequality that involves the function $Q(s)$ . The class of i.d. probability distributions is large and includes Gaussian and Poisson distributions, among many others. Therefore, our results encompass the existing work on matrix Gaussian series as a special case. Lastly, we show that the tail inequalities of a matrix i.d. series have applications in several optimization problems including the chance constrained optimization problem and the quadratic optimization problem with orthogonality constraints. In addition, we also use the resulting tail bounds to show that random matrices constructed from i.d. random variables satisfy the restricted isometry property (RIP) when it acts as a measurement matrix in compressed sensing.
发表时间：2020-02-01