--- abstract: 'This paper gives new concentration inequalities for the spectral norm of a wide class of matrix martingales in continuous time. These results extend previously established Freedman and Bernstein inequalities for series of random matrices to the class of continuous time processes. Our analysis relies on a new supermartingale property of the trace exponential proved within the framework of stochastic calculus. We provide also several examples that illustrate the fact that our results allow us to recover easily several formerly obtained sharp bounds for discrete time matrix martingales.' author: - Emmanuel Bacry - Stéphane Gaïffas - 'Jean-François Muzy' bibliography: - 'proba.bib' title: | Concentration inequalities for matrix martingales\ in continuous time --- Introduction ============ Matrix concentration inequalities control the deviation of a random matrix around its mean. Until now, results in literature consider the case of sums of independent random matrices, or matrix martingales in discrete time. A first matrix version of the Chernoff bound is given in @ahlswede2002strong and was adapted to yield matrix analogues of standard scalar concentration inequalities in @christofides2008expansion [@oliveira2009concentration; @oliveira2010sums; @minsker2011some]. Later, these results were improved in @tropp2012user [@tropp2011freedman], by the use of a theorem due to Lieb @lieb1973convex, about the concavity of a trace exponential function, which is a deep result closely related to the joint convexity of quantum entropy in physics. See also @mackey2014matrix for a family of sharper and more general results based on the Stein's method. These works contain extensions to random matrices of classical concentration inequalities for sums of independent scalar random variables, such as the Bernstein inequality for sub-exponential random variables, Hoeffding inequality for sub-Gaussian random variables or Freedman inequality for martingales, see e.g. @massart2007concentration for a description of these classical inequalities. Matrix concentration inequalities have a plethora of applications, in particular in compressed sensing and statistical estimation @koltchinskii2011oracle, to develop a simpler analysis of matrix completion @Gross11 [@recht2011simpler], for matrix regression @negahban2012restricted [@Koltchinskii11; @rohde2011estimation; @bunea2011optimal], for randomized linear algebra @gittens2011spectral [@mackey2011divide], and robust PCA @Candes09b, which are some examples from a large corpus of works. On the other hand, concentration inequalities for scalar continuous-time martingales are well-known, see for instance @liptser1989theory [@van1995exponential] and @reynaud2006compensator for uniform versions of scalar concentration, and have a large number of applications in high-dimensional statistics @hansen_reynaud_bouret_viroirard [@gaiffas2012high] among many others. Matrix martingales in continuous time are probabilistic objects that naturally appear in many problems like e.g., for statistical learning of time-dependent systems. No extension of the previously mentioned results in this framework is available in literature. The aim of this paper is to provide such results, by combining tools from random matrix theory and from stochastic calculus @liptser1989theory. We establish concentration inequalities for a large class of continuous-time matrix martingales with arbitrary predictable quadratic covariation tensor. More precisely, we provide a matrix version of Freedman's inequality for purely discontinuous matrix martingales (see Theorem \[thm:concentration\_counting\]) as well as continuous martingales (see Theorem \[thm:concentration\_continuous\]). We show that the variance term in the concentration inequalities is provided by the largest eigenvalue of the predictable quadratic covariation matrix. In that respect, our results can be understood as extensions to continuous time martingales of previously established results by Tropp @tropp2011freedman in the case of discrete time matrix martingales. Our proofs techniques required a very different analysis than the discrete-time case, involving tools from stochastic calculus. The paper is organized as follows. In Section \[sec:main\_results\], after introducing some notations and defining the class of matrix martingales we consider, we state our main results for purely discontinuous martingales, see Section \[sec:discountinuous\_martingale\] and continuous matrix martingales, see Section \[sec:continuous\_martingale\]. We provide some comments about the link with analogous results in discrete time and the sharpness of our bounds. In Section \[sec:Applications\], we discuss some examples of application of our Theorems. We consider various particular situations that notably allows us to recover some known results concerning series of random matrices or scalar point processes. Technical results and the proofs of the Theorems are gathered in Appendices \[sec:tools\], \[sec:proof\_of\_theorem\_1\] and \[sec:proof\_theorem2\]. We notably establish a matrix supermartingale property (Proposition \[prop:new-counting-supermart\]) that is essential for obtaining the concentration inequalities. Main results {#sec:main_results} ============ In this section, we give the main results of the paper, namely Theorems \[thm:concentration\_counting\] and \[thm:concentration\_continuous\], that provide concentration inequalities for purely discontinuous and continuous matrix martingales. We first begin by recalling some definitions from probability theory and stochastic calculus and set some notations. Probabilistic background and Notations {#sec:probback} -------------------------------------- #### Probabilistic background. {#par:proba} We consider a complete probability space $(\Omega, {\mathscr F}, {\mathbbm P})$ and a filtration $\{ {\mathscr F}_t \}_{t \geq 0}$ of $\sigma$-algebras included in ${\mathscr F}$. Expectation ${\mathbbm E}$ is always taken with respect to ${\mathbbm P}$. We assume that the stochastic system $(\Omega, {\mathscr F}, \{ {\mathscr F}_t \}_{t \geq 0}, {\mathbbm P})$ satisfies the *usual* conditions, namely that ${\mathscr F}_0$ is augmented by the ${\mathbbm P}$-null sets, and that the filtration is right continuous, namely ${\mathscr F}_t = \cap_{u > t} {\mathscr F}_u$ for any $t \geq 0$. We shall denote ${\mathscr F}_{t^-}$ as the smallest $\sigma$-algebra containing all ${\mathscr F}_s$ for $s < t$. A matrix-valued stochastic processes $\{ {{\boldsymbol X}}_t \}_{t \geq 0}$ is a family of random matrices of constant size (e.g. $m \times n$) defined on $(\Omega, {\mathscr F}, {\mathbbm P})$. We say that $\{ {{\boldsymbol X}}_t \}_{t \geq 0}$ is adapted if for each $t \geq 0$, all the entries of ${{\boldsymbol X}}_t$ are ${\mathscr F}_t$-measurable. We say that it is <span>càdlàg</span> if the trajectories on $[0, +\infty]$ of each entries have left limits and are right continuous for all $\omega \in \Omega$. If $\{ {{\boldsymbol X}}_t \}_{t \geq 0}$ is <span>càdlàg</span>, then we define its jump process $\{ \Delta {{\boldsymbol X}}_t \}_{t \geq 0}$ where $\Delta {{\boldsymbol X}}_t = {{\boldsymbol X}}_t - {{\boldsymbol X}}_{t^-}$. We say that $\{ {{\boldsymbol X}}_t \}_{t \geq 0}$ is predictable if all its entries are <span>càdlàg</span> and predictable. We recall that a <span>*predictable process*</span> is a process that is measurable with respect to the $\sigma$-field generated by left-continuous adapted processes. In particular, if $\tau$ is a stopping time and $X_t$ is a predictable process, then $X_\tau$ is ${\mathscr F}_{\tau^-}$ measurable. A *matrix semimartingale* is a matrix-valued stochastic process whose entries are all semimartingales. In the same way, a *matrix martingale* $\{ {{\boldsymbol M}}_t \}_{t \geq 0}$ is a matrix-valued stochastic process with entries that are all martingales. Namely, we assume that for all possible indexes $(i, j)$ of entries, $({{\boldsymbol M}}_t)_{i, j}$ is adapted, <span>càdlàg</span>, such that ${\mathbbm E}|({{\boldsymbol M}}_t)_{i, j}| < +\infty$ for all $t \geq 0$, and that $${\mathbbm E}[{{\boldsymbol M}}_t | {\mathscr F}_s] = {{\boldsymbol M}}_s$$ for any $0 \leq s \leq t$, where the conditional expectation is applied entry-wise on ${{\boldsymbol M}}_t$. More generally, expectations and conditional expectations are always applied entry-wise. A brief review of tools from stochastic calculus based on semimartingales is provided in appendix \[sec:ito\]. #### Notations. {#sec:notations} We denote by ${{\mathds 1}}$ the column vector with all entries equal to $1$ (with size depending on the context). Let ${{\boldsymbol X}}$ be a real matrix and $x$ a real vector. The notations $\operatorname{diag}[x]$ stands for the diagonal matrix with diagonal equal to $x$, while if ${{\boldsymbol X}}$ is a square matrix, $\operatorname{diag}[{{\boldsymbol X}}]$ stands for the diagonal matrix with diagonal equal to the one of ${{\boldsymbol X}}$, $\operatorname{tr}{{\boldsymbol X}}$ stands for the trace of ${{\boldsymbol X}}$. The operator norm (largest singular value) will be denoted by ${{\|{{\boldsymbol X}}\|}_{\operatorname{op}}}$. We define also $|{{\boldsymbol X}}|$ by taking the absolute value of each entry of ${{\boldsymbol X}}$. If ${{\boldsymbol Y}}$ is another real matrix, the notation ${{\boldsymbol X}}\odot {{\boldsymbol Y}}$ stands for the entry-wise product (Hadamard product) of ${{\boldsymbol X}}$ and ${{\boldsymbol Y}}$ with same dimensions, namely $({{\boldsymbol X}}\odot {{\boldsymbol Y}})_{j, k} = ({{\boldsymbol X}})_{j, k} ({{\boldsymbol Y}})_{j, k}$. We shall denote by ${{\boldsymbol X}}^{\odot k}$ the Hadamard power, where each entry of ${{\boldsymbol X}}^{\odot k}$ is the $k$-th power of the corresponding entry of ${{\boldsymbol X}}$. We also denote ${{\boldsymbol X}}_{{\bullet}, j}$ for the $j$-th column of ${{\boldsymbol X}}$ while ${{\boldsymbol X}}_{j, {\bullet}}$ stands for the $j$-th row. Moreover, for a matrix ${{\boldsymbol X}}$ and $p \geq 1$, we define the norms $${\|{{\boldsymbol X}}\|}_{p, \infty} = \max_j {\|{{\boldsymbol X}}_{j, {\bullet}}\|}_p \; \text{ and } \; {\|{{\boldsymbol X}}\|}_{\infty, p} = \max_j {\|{{\boldsymbol X}}_{{\bullet}, j}\|}_p,$$ where ${\|\cdot\|}_p$ is the vector $\ell_p$-norm. For a symmetric matrix ${{\boldsymbol X}}$, the largest eigenvalue is denoted ${\lambda_{\max}}({{\boldsymbol X}})$. Moreover, the symbol ${\preccurlyeq}$ stands for the positive semidefinite (p.s.d.) order on symmetric matrices, namely ${\boldsymbol}X {\preccurlyeq}{\boldsymbol}Y$ iff ${\boldsymbol}Y - {\boldsymbol}X$ is p.s.d. We shall denote, when well-defined, $\int_0^t {{\boldsymbol X}}_s ds$ for the matrix of integrated entries of ${{\boldsymbol X}}_s$, namely $(\int_0^t {{\boldsymbol X}}_s ds)_{i, j} = \int_0^t ({{\boldsymbol X}}_s)_{i, j} ds$. We use also matrix notations for stochastic integrals, for instance $\int_0^t {{\boldsymbol X}}_s d {{\boldsymbol Y}}_s$ stands for the matrix with entries given by the stochastic integral $$\Big(\int_0^t {{\boldsymbol X}}_s d {{\boldsymbol Y}}_s\Big)_{i, j} = \sum_k \int_0^t ({{\boldsymbol X}}_s)_{i, k} d ({{\boldsymbol Y}}_s)_{k, j},$$ for stochastic processes ${{\boldsymbol X}}_t$ and ${{\boldsymbol Y}}_t$ that are matrix-valued, such that the matrix product ${{\boldsymbol X}}_t {{\boldsymbol Y}}_t$ makes sense, and such that these stochastic integrals are well-defined for all $i, j$. We define similarly $\int_0^t d{{\boldsymbol X}}_s {{\boldsymbol Y}}_s$. Let ${\mathds{T}}$ be a rank 4 tensor of dimension $(m \times n \times p \times q)$ . It can be considered as a linear mapping from ${\mathbb R}^{p \times q}$ to ${\mathbb R}^{m \times n}$ according to the following "tensor-matrix" product: $$({\mathds{T}}\circ {{\boldsymbol A}})_{i,j} = \sum_{k=1}^p \sum_{l=1}^q {\mathds{T}}_{i,j;k,l} {{\boldsymbol A}}_{k,l}.$$ We will denote by ${\mathds{T}}^{\top}$ the tensor such that ${\mathds{T}}^\top \circ {{\boldsymbol A}}= ({\mathds{T}}\circ {{\boldsymbol A}})^{\top}$ (i.e., ${\mathds{T}}^{\top}_{i,j;k,l} = {\mathds{T}}_{j,i;k,l}$) and by ${\mathds{T}}_{{\bullet};k,l}$ and ${\mathds{T}}_{i,j;{\bullet}}$ the matrices obtained when fixing respectively the indices $k,l$ and $i,j$. Notice that $({\mathds{T}}\circ {{\boldsymbol A}})_{i,j} = \operatorname{tr}({\mathds{T}}_{i,j;{\bullet}} {{\boldsymbol A}}^{\top})$. If ${\mathds{T}}$ et ${\mathds{T}}'$ are two tensors of dimensions respectively $m \times n \times p \times q$ and $n \times r \times p \times q$, ${\mathds{T}}{\mathds{T}}'$ will stand for the tensor of dimension $m \times r \times p \times q$ defined as $({\mathds{T}}{\mathds{T}}')_{i,j;k,l} = ({\mathds{T}}_{{\bullet};k,l} {\mathds{T}}'_{{\bullet};k,l})_{i,j}$. Accordingly, for an integer $r \geq 1$, if ${\mathds{T}}_{{\bullet};a,b}$ are square matrices, we will denote by ${\mathds{T}}^{r}$ the tensor such that $({\mathds{T}}^{r})_{i,j;k,l} = ({\mathds{T}}_{{\bullet};k,l}^r)_{i,j}$. We also introduce ${\|{\mathds{T}}\|}_{\operatorname{op}; \infty} = \max_{k, l} {{\|{\mathds{T}}_{{\bullet}; k, l}\|}_{\operatorname{op}}}$, the maximum operator norm of all matrices formed by the first two dimensions of tensor ${\mathds{T}}$. #### The matrix martingale ${{\boldsymbol Z}}_t$. In this paper we shall consider the class of $m \times n$ matrix martingales that can be written as $$\label{eq:martingale} {{\boldsymbol Z}}_t = \int_0^t {\mathds{T}}_s \circ ({{\boldsymbol C}}_s \odot d {{\boldsymbol M}}_s),$$ where ${\mathds{T}}_s$ is a rank 4 tensor with dimensions $m \times n \times p \times q$, whose components are assumed to be locally bounded predictable random functions. The process ${{\boldsymbol M}}_t$ is a $p \times q$ is matrix with entries that are square integrable martingales with a diagonal quadratic covariation matrix (see Section \[sec:ito\] for the definition of the quadratic covariation matrix of a semimartingale matrix). The matrix ${{\boldsymbol C}}_s$ is a matrix of $p \times q$ predictable locally bounded functions. More explicitly, the entries of ${{\boldsymbol Z}}_t$ are given by $$({{\boldsymbol Z}}_t)_{i, j} = \sum_{k=1}^p \sum_{l=1}^q \int_0^t ({\mathds{T}}_s)_{i,j;k,l} ({{\boldsymbol C}}_s)_{k,l} (d {{\boldsymbol M}}_s)_{k,l}.$$ Note that Equation corresponds to a wide class of matrix martingales. This shape of matrix martingale, which involves a rank-4 tensor, is natural: all quadratic covariations between pairs of entries of ${{\boldsymbol Z}}_t$ are accounted by the linear transformation ${\mathds{T}}$. Let us remark that if one chooses ${\mathds{T}}_{i,j;k,l} = ({{\boldsymbol A}}_s)_{i,k} ({{\boldsymbol B}}_s)_{l,j}$ where ${{\boldsymbol A}}_s$ and ${{\boldsymbol B}}_s$ are respectively $m \times p$ and $q \times n$ matrices of predictable functions, then $$\label{eq:martingale_old} {{\boldsymbol Z}}_t = \int_0^t {{\boldsymbol A}}_s ({{\boldsymbol C}}_s \odot d {{\boldsymbol M}}_s) {{\boldsymbol B}}_s.$$ If one chooses ${\mathds{T}}$ of dimensions $(m \times n \times 1 \times 1)$ and ${{\boldsymbol M}}_t = M_t$ a scalar martingale, then $${{\boldsymbol Z}}_t = \int_0^t {{\boldsymbol A}}_s dM_s,$$ where $({{\boldsymbol A}}_s)_{i,j} = ({\mathds{T}}_s)_{i,j; 1,1}$ is a constant matrix linear transform. In Section \[sec:Applications\] below, we prove that such particular cases lead to generalizations to continuous-time martingales of previously known concentration inequalities for "static" random matrices. In the following we will distinguish situations where the entries of ${{\boldsymbol M}}_t$ are purely discontinuous martingales (see Section \[sec:discountinuous\_martingale\]) and continuous martingales (see Section \[sec:continuous\_martingale\]). We recall the definitions of continuous and purely discontinuous martingales, along with other important notions from stochastic calculus in Section \[sec:ito\]. Purely discontinuous matrix martingales {#sec:discountinuous_martingale} --------------------------------------- In this section, we consider the case of a purely discontinuous (this notion is defined in Appendix \[sec:ito\]) martingale ${{\boldsymbol M}}_t$. More specifically, we assume that ${{\boldsymbol M}}_t$ is a martingale coming from the compensation of a random matrix with entries that are compound counting processes. We denote by $[{\mathrm{vec}}{{\boldsymbol M}}]_t$ the quadratic covariation matrix of the vectorization of ${{\boldsymbol M}}_t$ (defined in Appendix \[sec:ito\]). \[ass:M\_d\] Assume that ${{\boldsymbol M}}_t$ is a purely discontinuous matrix-martingale with entries that are locally bounded. Moreover, we assume that they do not jump at the same time, i.e. $[{\mathrm{vec}}{{\boldsymbol M}}]_t$ is a diagonal matrix for any $t$. Moreover, assume that any $(i, j)$-entry satisfies $$\label{eq:defMdis} (\Delta {{\boldsymbol M}}_t)_{i, j} = ({{\boldsymbol J}}_{({{\boldsymbol N}}_t)_{i, j}})_{i, j} \times (\Delta {{\boldsymbol N}}_t)_{i, j}$$ where: - ${{\boldsymbol N}}_t$ is a $p \times q$ matrix counting process (i.e., each component is a counting process) with an intensity process ${{\boldsymbol \lambda}}_t$ which is predictable, continuous and with finite variations (FV); - $({{\boldsymbol J}}_n)_{n \in {\mathbb N}}$ is a sequence of $p \times q$ random matrices, independent of $({\mathds{T}}_t)_{t \geq 0}, ({{\boldsymbol C}}_t)_{t \geq 0}$ and $({{\boldsymbol N}}_t)_{t \geq 0}$ and identically distributed, such that $|({{\boldsymbol J}}_1)_{i, j}| \leq {J_{\max}}$ a.s. for any $i, j$ and $k \geq 1$, where ${J_{\max}}> 0$. Equation can be rewritten for short as $\Delta {{\boldsymbol M}}_t = {{\boldsymbol J}}_{{{\boldsymbol N}}_t} \odot \Delta {{\boldsymbol N}}_t$. It imposes a mild condition on the structure of the jumps of ${{\boldsymbol M}}_t$ that allows to derive an explicit form for the compensator of ${{\boldsymbol Z}}_t$ (see Section \[sec:proof\_of\_theorem\_1\]). Note that if ${{\boldsymbol M}}_t$ is the martingale associated with a matrix counting process, then one can simply choose the sequence $({{\boldsymbol J}}_n)_{n \in {\mathbb N}}$ as constantly equal to the matrix filled with ones. The next Theorem is a concentration inequality for ${{\|{{\boldsymbol Z}}_t\|}_{\operatorname{op}}}$, the operator norm of ${{\boldsymbol Z}}_t$. Let ${\langle {{\boldsymbol Z}}_{{\bullet},j} \rangle}_t$ (resp. ${\langle {{\boldsymbol Z}}_{j,{\bullet}} \rangle}_t$) be the matrices of predictable quadratic variations of the column (resp. row) vector $({{\boldsymbol Z}}_t)_{{\bullet},j}$ (resp. $({{\boldsymbol Z}}_t)_{{\bullet},j}$), and let us define $$\label{eq:def_sigma_Z_t} \sigma^2({{\boldsymbol Z}}_t) = \max \bigg( \Big\| \sum_{j=1}^n {\langle {{\boldsymbol Z}}_{{\bullet},j} \rangle}_t \Big\|_{\operatorname{op}}, \Big\| \sum_{j=1}^m {\langle {{\boldsymbol Z}}_{j, {\bullet}} \rangle}_t \Big\|_{\operatorname{op}} \bigg).$$ Let us introduce also $$\label{eq:W_def} {{\boldsymbol W}}_s = \begin{bmatrix} {\mathds{T}}_s {\mathds{T}}_s^\top \circ \left({\mathbbm E}({{\boldsymbol J}}_1^{\odot 2}) \odot {{\boldsymbol C}}^{\odot 2}_s \odot {{\boldsymbol \lambda}}_s \right) & {{\boldsymbol 0}}\\ {{\boldsymbol 0}}& {\mathds{T}}_s^\top {\mathds{T}}_s \circ \left( {\mathbbm E}({{\boldsymbol J}}_1^{\odot 2}) \odot {{\boldsymbol C}}^{\odot 2}_s \odot {{\boldsymbol \lambda}}_s \right) \end{bmatrix},$$ and $$\label{eq:b_t_def} b_t = J_{\max} \sup_{s \in [0, t]} {\|{{\boldsymbol C}}_s\|}_\infty \max\big( {\|{\mathds{T}}_s\|}_{\operatorname{op}; \infty},{\|{\mathds{T}}^\top\|}_{\operatorname{op}; \infty} \big),$$ and finally $\phi(x) = e^x - 1 - x$ for $x \in {\mathbb R}$. \[thm:concentration\_counting\] Let ${{\boldsymbol Z}}_t$ be the $m \times n$ matrix martingale given by Equation and suppose that Assumption \[ass:M\_d\] holds. Moreover, assume that $$\label{eq:ass_thm1} {\mathbbm E}\bigg[ \int_0^t \frac{\phi\big(3 J_{\max} {\|{{\boldsymbol C}}_s\|}_\infty \max({\|{\mathds{T}}_s\|}_{\operatorname{op}; \infty},{\|{\mathds{T}}_s^\top\|}_{\operatorname{op}; \infty})\big)}{J_{\max}^2 {\|{{\boldsymbol C}}_s\|}_\infty^2 \max({\|{\mathds{T}}_s\|}^2_{\operatorname{op}; \infty},{\|{\mathds{T}}_s^\top\|}^2_{\operatorname{op}; \infty})} ({{\boldsymbol W}}_s)_{i, j} ds \bigg] < +\infty,$$ for any $1 \leq i, j \leq m + n$. Then, for any $t, x, b, v > 0$, the following holds: $${\mathbbm P}\bigg[ {{\|{{\boldsymbol Z}}_t\|}_{\operatorname{op}}} \geq \sqrt{2 v (x + \log (m + n))} + \frac{b (x + \log (m + n))}{3}, \quad \sigma^2({{\boldsymbol Z}}_t) \leq v, \quad b_t \leq b \bigg] \leq e^{-x},$$ where $\sigma^2({{\boldsymbol Z}}_t)$ is given by Equation and $b_t$ by Equation . Moreover, we have $$\sigma^2({{\boldsymbol Z}}_t) = {\lambda_{\max}}({{\boldsymbol V}}_t),$$ where $$\label{eq:def_V_t_counting} {{\boldsymbol V}}_t = \int_0^t {{\boldsymbol W}}_s \; ds,$$ with ${{\boldsymbol W}}_s$ given by Equation . This theorem is proved in Appendix \[sec:proof\_of\_theorem\_1\]. It provides a first non-commutative version of a concentration inequality for continuous time matrix martingales, in the purely discontinuous case. This theorem can be understood as the generalization to continuous time martingales of a Freedman inequality for (discrete time) matrix martingales established in @tropp2011freedman. Let us notice that the two terms involved in the definition of $\sigma^2({{\boldsymbol Z}}_t)$ are precisely the matrices of predictable quadratic variations of the entries of respectively ${{\boldsymbol Z}}_t {{\boldsymbol Z}}_t^\top$ and ${{\boldsymbol Z}}_t^\top {{\boldsymbol Z}}_t$ in full agreement with the form provided in the discrete case @tropp2011freedman. Moreover, if ${\mathds{T}}_s$, ${{\boldsymbol \lambda}}_s$ and ${{\boldsymbol C}}_s$ are deterministic, we can actually write $$\label{eq:def_sigma_Z_t_deter} \sigma^2 ({{\boldsymbol Z}}_t) = \max \Big( {{\|{\mathbbm E}({{\boldsymbol Z}}_t {{\boldsymbol Z}}_t^\top)\|}_{\operatorname{op}}}, {{\| {\mathbbm E}({{\boldsymbol Z}}_t^\top {{\boldsymbol Z}}_t)\|}_{\operatorname{op}}} \Big).$$ This term has the same shape as the variance term from Bernstein inequality established for random series of bounded matrices ${{\boldsymbol Z}}_n = \sum_k {{\boldsymbol S}}_k$ as e.g., in @tropp2012user. This illustrates the fact that Theorem \[thm:concentration\_counting\] extends former results for discrete series of random matrices to continuous time matrix martingales. A detailed discussion and comparison with literature is given in Section \[sec:Applications\] below. Note that, since $\phi$ is an increasing function, is satisfied whenever ${{\boldsymbol V}}_t$ has finite expectation and both ${\|{{\boldsymbol C}}_s\|}_\infty$, ${\|{\mathds{T}}_s\|}_{\operatorname{op}; \infty}$ and ${\|{\mathds{T}}_s^\top\|}_{\operatorname{op}; \infty}$ are bounded a.s. by some fixed constant. In the scalar case ($m = n = p = q = 1$), the assumption required in Equation becomes $${\mathbbm E}\Big[ \int_0^t e^{3 |C_s|} \lambda_s ds \Big] < +\infty,$$ where matrices ${{\boldsymbol A}}_t$, ${{\boldsymbol B}}_t$ and tensor ${\mathds{T}}_t$ are scalars equal to one, and ${{\boldsymbol C}}_t = C_t$ is scalar. This matches the standard assumption for an exponential deviation of the scalar martingale $Z_t = {{\boldsymbol Z}}_t$, see for instance @bremaud1981point. Concentration inequality for continuous matrix martingales {#sec:continuous_martingale} ---------------------------------------------------------- In this section, we study the matrix-martingale ${{\boldsymbol Z}}_t$ given by when it is continuous. This mainly amounts to consider situations where the compensated counting processes are replaced by Brownian motions. More specifically, we will suppose that ${{\boldsymbol M}}_t$ satisfies the following. \[ass:M\_c\] Assume that $\{ {{\boldsymbol M}}_t\}$ is a matrix of independent standard Brownian motions. This notably implies that its entry-wise predictable quadratic variation matrix reads $${\langle {{\boldsymbol M}}\rangle}_t = t {{\boldsymbol I}}.$$ In this context, we can prove the analog of Theorem \[thm:concentration\_counting\], i.e, a Freedman concentration inequality for ${{\|{{\boldsymbol Z}}_t\|}_{\operatorname{op}}}$, the operator norm of ${{\boldsymbol Z}}_t$. Thus, following the same lines as in the previous section, let $\sigma^2({{\boldsymbol Z}}_t)$ be defined by Equation and let us consider for following matrix: $$\label{eq:W_def_cont} {{\boldsymbol W}}_t = \begin{bmatrix} {\mathds{T}}_t {\mathds{T}}_t^\top \circ {{\boldsymbol C}}^{\odot 2}_t & {{\boldsymbol 0}}\\ {{\boldsymbol 0}}& {\mathds{T}}_t^\top {\mathds{T}}_t \circ {{\boldsymbol C}}^{\odot 2}_t \end{bmatrix},$$ which corresponds to the previous definition where the sequence $({{\boldsymbol J}}_n)$ and the process ${{\boldsymbol \lambda}}_t$ are replaced by the constant matrix with all entries equal to one. We have the following. \[thm:concentration\_continuous\] Let ${{\boldsymbol Z}}_t$ be given by and suppose that Assumption \[ass:M\_c\] holds. Then, the following holds: $${\mathbbm P}\bigg[ {{\|{{\boldsymbol Z}}_t\|}_{\operatorname{op}}} \geq \sqrt{2v(x+\log(m+n))} ~,~\sigma^2( {{\boldsymbol Z}}_t) \le v \bigg] \leq e^{-x}$$ for any $v, x > 0$, where $\sigma^2({{\boldsymbol Z}}_t)$ is defined in . Moreover, we have $$\sigma^2({{\boldsymbol Z}}_t) = {\lambda_{\max}}({{\boldsymbol V}}_t),$$ where ${{\boldsymbol V}}_t$ is given by $$\label{eq:def_V_t_continuous} {{\boldsymbol V}}_t = \int_0^t {{\boldsymbol W}}_s \; ds,$$ with ${{\boldsymbol W}}_s$ given by Equation . We can remark that the above concentration inequality corresponds exactly to the result obtained in Theorem \[thm:concentration\_counting\] for purely discontinuous martingales, if one sets $b_t = 0$. The concentration obtained here is in the "Gaussian" regime: ${{\boldsymbol M}}_t$ is a Brownian motion, which leads to sub-Gaussian tails for ${{\boldsymbol Z}}_t$. This is to be contrasted with Theorem \[thm:concentration\_counting\], which is in a "Poisson" regime: the tails contains both sub-Gaussian and sub-exponential terms for ${{\boldsymbol Z}}_t$ in this case. Discussion {#sec:discussion} ---------- The concentration inequalities established for the two families of continuous-time matrix martingales considered above have the same form as the Freedman inequality obtained in the discrete-time case @oliveira2010sums [@tropp2011freedman]. In the case of deterministic functions ${\mathds{T}}_s$ and ${{\boldsymbol C}}_s$ a direct consequence of Theorems \[thm:concentration\_counting\] and \[thm:concentration\_continuous\] is $$\label{eq:mean_bound} {\mathbbm E}{{\|{{\boldsymbol Z}}_t\|}_{\operatorname{op}}} \leq \sigma({{\boldsymbol Z}}_t) \sqrt{2 \log(n+m)} + \frac{b_t \log(n+m)}{3},$$ where $\sigma({{\boldsymbol Z}}_t)$ is defined by and $b_t$ by , with $b_t = 0$ if Assumption \[ass:M\_c\] holds. By considering a piecewise constant tensor ${\mathds{T}}_s = \sum_{k=1}^n {\mathds{T}}_k \mathbbm{1}_{]k-1,k]}(s)$, where $\mathbbm{1}_{]k-1,k]}(t)$ stands for the indicator function of the interval $]k-1,k]$, ${{\boldsymbol Z}}_t$ reduces to a discrete sum of random matrices ${{\boldsymbol Z}}_n = \sum_{k=1}^n {{\boldsymbol S}}_k$ with ${{\boldsymbol S}}_k = {\mathds{T}}_k \circ \int_{k-1}^{k} {{\boldsymbol C}}_t \odot d{{\boldsymbol M}}_t$. In this very particular case, one recovers exactly the results obtained by Tropp @tropp2012user in this context, with a variance term given by $$\label{eq:vartropp} \sigma^2({{\boldsymbol Z}}_n) = \max \bigg( \Big\| \sum_k {\mathbbm E}({{\boldsymbol S}}_k {{\boldsymbol S}}_k^\top) \Big\|_{\operatorname{op}}, \Big\| \sum_k{\mathbbm E}({{\boldsymbol S}}_k^\top {{\boldsymbol S}}_k) \Big\|_{\operatorname{op}} \bigg).$$ Let us mention that, in the context of random series of matrices, a first tail bound for the norm was provided by Ahlswede and Winter @ahlswede2002strong. These authors established a concentration inequality involving the variance term $$\sigma^2_{AW}({{\boldsymbol Z}}_n) = \max\Big( \sum_k {\mathbbm E}{\| {{\boldsymbol S}}_k {{\boldsymbol S}}^\top_k\|}_{\operatorname{op}}, \sum_k {\mathbbm E}{\| {{\boldsymbol S}}^\top_k {{\boldsymbol S}}_k\|}_{\operatorname{op}} \Big),$$ which is greater than the expression in Equation . Ahlswede and Winter approach is based on the bounding of the matrix moment generating function $\xi \mapsto {\mathbbm E}\operatorname{tr}e^{\xi {{\boldsymbol Z}}_n}$ by iterating Golden-Thomson inequalities (which states that $\operatorname{tr}e^{{{\boldsymbol A}}+ {{\boldsymbol B}}} \leq \operatorname{tr}e^{{{\boldsymbol A}}} e^{{{\boldsymbol B}}}$ for any symmetric matrices ${{\boldsymbol A}}$ and ${{\boldsymbol B}}$). The improvement of $\sigma^2_{AW}({{\boldsymbol Z}}_n)$ to $\sigma^2({{\boldsymbol Z}}_n)$ obtained in @tropp2012user is based on a powerful result by Lieb @lieb1973convex, which says that ${{\boldsymbol X}}\mapsto \operatorname{tr}e^{{{\boldsymbol A}}+ \log {{\boldsymbol X}}}$ is concave over the SDP (semidefinite positive) cone, for any matrix ${{\boldsymbol A}}$. A surprising aspect of our results concerning continuous time martingales is that, as a by-product, they allow to recover previous sharp bounds without the use of the Lieb result. The infinitesimal approach introduced in this paper allows one, through Itô's Lemma (see Appendix \[sec:ito\]), to bound ${\mathbbm E}\operatorname{tr}\exp({{\boldsymbol Z}}_t)$ quite easily since it can be explicitly written as ${\mathbbm E}\int_0^t d (\operatorname{tr}\exp({{\boldsymbol Z}}_t))$. As far as the sharpness of our results is concerned, better bounds than can be manifestly obtained in some very specific cases. Indeed, it is well-known that for $n \times n$ matrices of symmetric i.i.d. Gaussian random variables (GOE ensemble), the expectation of the largest eigenvalue is of order $\sqrt{n}$. This result has been extended to more general matrices of i.i.d. random variables as, e.g., in the work of Seginer@seginer2000 or Latala @latala2005 where bounds without the $\sqrt{\log n}$ factor are obtained. However, for the general case considered in this paper, our results can be considered as being sharp since they match inequalities from @tropp2012user on several important particular cases. We develop some of these cases in Section \[sec:Applications\] below. Concerning the extra $\log (m+n)$ factor, a simple example is the case of a diagonal matrix of i.i.d. standard Gaussian variables. In that case the largest eigenvalue is simply the maximum of $m + n$, whose expectation is well-known to scale as $\sqrt{\log(m + n)}$. We refer the reader to the discussion in @bandeiraMit [@tropp2012user] for further details. Some specific examples {#sec:Applications} ====================== In this section we provide some examples of applications of Theorems \[thm:concentration\_counting\] and \[thm:concentration\_continuous\] and discuss their relationship with some former works. Further generalizations in an even more general context and application to statistical problems are then briefly presented. The martingale ${{\boldsymbol Z}}_t = \int_0^t {{\boldsymbol A}}_s ({{\boldsymbol C}}_s \odot d{{\boldsymbol M}}_s) {{\boldsymbol B}}_s$ ---------------------------------------------------------------------------------------------------------------------------------------- Let ${{\boldsymbol A}}_s$ and ${{\boldsymbol B}}_s$ two matrix-valued processes of bounded predictable functions of dimensions respectively $m \times p$ and $q \times n$. Let us suppose that $({\mathds{T}}_s)_{i,j,k,l} = ({{\boldsymbol A}}_s)_{i,k} ({{\boldsymbol B}}_s)_{l,j}$. This corresponds to the situation where the matrix martingale ${{\boldsymbol Z}}_t$ can be written as $$\label{eq:mart_AB} {{\boldsymbol Z}}_t = \int_0^t {{\boldsymbol A}}_s ({{\boldsymbol C}}_s\odot d {{\boldsymbol M}}_t) {{\boldsymbol B}}_t.$$ In that case, the entry $(i,j)$ of the matrix ${{\boldsymbol W}}_s$ defined by reads, when $1 \leq i,j \leq m$: $$\begin{aligned} ({{\boldsymbol W}}_s)_{i,j} = & \sum_{a=1}^n \sum_{k=1}^p \sum_{l=1}^q ({\mathds{T}}_s)_{i,a,k,l}({\mathds{T}}_s)_{j,a,k,l} ({\mathbbm E}({{\boldsymbol J}}_1^{\odot 2}) \odot {{\boldsymbol C}}^{\odot 2}_s \odot {{\boldsymbol \lambda}}_s))_{k,l} \\ = & \sum_{a=1}^n \sum_{k=1}^p \sum_{l=1}^q ({{\boldsymbol A}}_s)_{i,k} ({{\boldsymbol B}}_s)_{l,a}^2 ({{\boldsymbol A}}_s)_{j,k} ({\mathbbm E}({{\boldsymbol J}}_1^{\odot 2}) \odot {{\boldsymbol C}}^{\odot 2}_s \odot {{\boldsymbol \lambda}}_s))_{k,l}.\end{aligned}$$ In the same way, for $1 \leq i,j \leq n$, one has: $$({{\boldsymbol W}}_s)_{i+m,j+m} = \sum_{a=1}^m \sum_{k=1}^p \sum_{l=1}^q ({{\boldsymbol B}}_s)_{k,i} ({{\boldsymbol A}}_s)_{a,l}^2 ({{\boldsymbol B}}_s)_{k,j} ({\mathbbm E}({{\boldsymbol J}}_1^{\odot 2}) \odot {{\boldsymbol C}}^{\odot 2}_s \odot {{\boldsymbol \lambda}}_s))_{l,k} \; .$$ Then, Theorem \[thm:concentration\_counting\] leads to the following corollary, that follows from easy computations. \[prop:AMB\] If ${{\boldsymbol Z}}_t$ is given by , the matrix ${{\boldsymbol W}}_s$ defined by can be written as $$\label{eq:W_def_old} {{\boldsymbol W}}_t = {{\boldsymbol P}}_t^\top \begin{bmatrix} \operatorname{diag}[({\mathbbm E}({{\boldsymbol J}}_1^{\odot 2}) \odot {{\boldsymbol C}}^{\odot 2}_t \odot {{\boldsymbol \lambda}}_t) \operatorname{diag}[{{\boldsymbol B}}_t {{\boldsymbol B}}_t^\top] {{\mathds 1}}] & {{\boldsymbol 0}}\\ {{\boldsymbol 0}}& \operatorname{diag}[({\mathbbm E}({{\boldsymbol J}}_1^{\odot 2}) \odot {{\boldsymbol C}}^{\odot 2}_t \odot {{\boldsymbol \lambda}}_t)^\top \operatorname{diag}[{{\boldsymbol A}}_t^\top {{\boldsymbol A}}_t] {{\mathds 1}}\big] \end{bmatrix} {{\boldsymbol P}}_t$$ with $${{\boldsymbol P}}_t = \begin{bmatrix} {{\boldsymbol A}}_t^\top & {\boldsymbol}0 \\ {\boldsymbol}0 & {{\boldsymbol B}}_t \end{bmatrix}.$$ Furthermore, we have also that writes $$\label{eq:b_t_old} b_t = J_{\max} \sup_{s \in [0, t]} {\|{{\boldsymbol A}}_s\|}_{\infty, 2} {\|{{\boldsymbol B}}_s\|}_{2,\infty} {\|{{\boldsymbol C}}_s\|}_\infty.$$ The same expression holds for the matrix ${{\boldsymbol W}}_t$ of Theorem \[thm:concentration\_continuous\], provided that one takes $({{\boldsymbol \lambda}}_t)_{i,j} = ({{\boldsymbol J}}_1)_{i,j} = 1$. The particular structure enables the study of several particular cases, developed in the next sections. ### Counting processes An interesting example that fits the setting of purely discontinuous martingales is the situation where ${{\boldsymbol M}}_t$ comes from the compensation of a matrix-valued process ${{\boldsymbol N}}_t$, whose entries are counting processes. In this example we can write ${{\boldsymbol M}}_t = {{\boldsymbol N}}_t = {{\boldsymbol \Lambda}}_t$, where ${{\boldsymbol \Lambda}}_t$ is the compensator of ${{\boldsymbol N}}_t$. We fix ${{\boldsymbol A}}_t = {{\boldsymbol I}}_p$ and ${{\boldsymbol B}}_t = {{\boldsymbol I}}_q$ for all $t$, so that ${{\boldsymbol Z}}_t = \int_0^t {{\boldsymbol C}}_s \odot d {{\boldsymbol M}}_s$. We obtain in this case $${{\boldsymbol V}}_t = \int_0^t \begin{bmatrix} \operatorname{diag}\big[ ({{\boldsymbol C}}_s^{\odot 2} \odot {{\boldsymbol \lambda}}_s) {{\mathds 1}}\big] & {{\boldsymbol 0}}\\ {{\boldsymbol 0}}& \operatorname{diag}\big[ ({{\boldsymbol C}}_s^{\odot 2} \odot {{\boldsymbol \lambda}}_s)^\top {{\mathds 1}}\big] \end{bmatrix} ds,$$ so the largest eigenvalue is easily computed as $${\lambda_{\max}}({{\boldsymbol V}}_t) = \Big\| \int_0^t {{\boldsymbol C}}_s^{\odot 2} \odot {{\boldsymbol \lambda}}_s ds \Big\|_{1, \infty} \vee \Big\| \int_0^t {{\boldsymbol C}}_s^{\odot 2} \odot {{\boldsymbol \lambda}}_s ds \Big\|_{\infty, 1},$$ and $b_t = \sup_{s \in [0, t]} {\|{{\boldsymbol C}}_s\|}_\infty$. This leads to the following corollary. \[cor:1\] Let $\{ {{\boldsymbol N}}_t \}$ be a $p \times q$ matrix whose entries $({{\boldsymbol N}}_t)_{i, j}$ are independent counting processes with intensities $({{\boldsymbol \lambda}}_t)_{i, j}$. Consider the matrix martingale ${{\boldsymbol M}}_t = {{\boldsymbol N}}_t - {{\boldsymbol \Lambda}}_t$, where ${{\boldsymbol \Lambda}}_t = \int_0^t {{\boldsymbol \lambda}}_s ds$ and let $\{ {{\boldsymbol C}}_t \}$ be a $p \times q$ bounded deterministic process. We have that $$\begin{aligned} {\Big\|\int_0^t {{\boldsymbol C}}_s \odot d({{\boldsymbol N}}_t - {{\boldsymbol \Lambda}}_t)\Big\|_{\operatorname{op}}} \leq &\sqrt{2 \Big( \Big\| \int_0^t {{\boldsymbol C}}_s^{\odot 2} \odot {{\boldsymbol \lambda}}_s ds \Big\|_{1, \infty} \vee \Big\| \int_0^t {{\boldsymbol C}}_s^{\odot 2} \odot {{\boldsymbol \lambda}}_s ds \Big\|_{\infty, 1} \Big) (x + \log(p + q))} \\ & \quad \quad + \frac{\sup_{s \in [0, t]} {\|{{\boldsymbol C}}_s\|}_\infty (x + \log(p + q))}{3} \end{aligned}$$ holds with a probability larger than $1 - e^{-x}$. Another interesting situation is when ${{\boldsymbol A}}_s$ is of dimension $1 \times q$, ${{\boldsymbol M}}_t$ is of dimension $q \times 1$, ${{\boldsymbol C}}_s$ is the matrix of dimension $q \times 1$ will all entries equal to one, ${{\boldsymbol B}}_t = 1$ for all $t$. In that case ${{\boldsymbol Z}}_t$ is a scalar martingale denoted $Z_t$. Consider $A_t^{(1)}, \ldots, A^{(q)}_t$ and $N^{(1)}_t, \ldots, N^{(q)}_t$ the $q$ components of respectively the vector ${{\boldsymbol A}}_t^{\top}$ and the vector ${{\boldsymbol N}}_t$. Along the same line $\lambda^{(1)}_t, \ldots, \lambda^{(q)}_t$ denotes their associated intensities. We thus have $$Z_t = \sum_{k=1}^q \int_0^t A^{(k)}_s dN^{(k)}_s,$$ which is a martingale considered in @hansen_reynaud_bouret_viroirard. In this case we have from Proposition \[prop:AMB\]: $${{\boldsymbol V}}_t = \int_0^t \begin{bmatrix} \sum_{k=1}^q (A_s^{(k)})^2 \lambda^{(k)}_s & 0 \\ 0 & \sum_{k=1}^q (A_s^{(k)})^2 \lambda^{(k)}_s \end{bmatrix} ds,$$ which largest eigenvalue is simply $\int_0^t \sum_{k=1}^q (A_s^{(k)})^2 \lambda^{(k)}_s ds$. Theorem \[thm:concentration\_counting\] becomes in this particular case the following. Let $(N^{(1)}_t, \ldots, N^{(q)}_t)$ be $q$ counting processes of intensities $\lambda^{(1)}_t, \ldots, \lambda^{(q)}_t$. Let us consider the martingale $$Z_t = \sum_{k=1}^q \int_0^t A^{(k)}_s (dN^{(k)}_s - \lambda_s^{(k)} ds)$$ where $(A^{(k)})_{k=1,\ldots, q}$ are $q$ predictable functions. If one assumes that $b_t = \sup_{k,s\leq t} {\|A^{(k)}_s\|} \leq 1$, the following inequality $${\mathbbm P}\bigg( | Z_t| \geq \sqrt{2 x v} + \frac{x}{3}, \quad \sum_{k=1}^q \int_0^t (A^{(k)}_s)^2 \lambda^{(k)}_s ds \leq v \bigg) \leq 2 e^{-x}$$ holds for any $x,v >0$. This result exactly corresponds to the concentration inequality proved in @hansen_reynaud_bouret_viroirard in the context of statistical estimation of point processes. ### "Static" random matrices Theorems \[thm:concentration\_counting\] and \[thm:concentration\_continuous\] can be helpful to study the norm of some specific random matrices. Let us consider a $n \times m$ matrix ${{\boldsymbol G}}= [g_{i, j}]$ of independent centered Gaussian random variables $g_{i, j}$with variance $c_{i,j}^2$. This corresponds to the situation in Proposition \[prop:AMB\] when $t=1$, $ {{\boldsymbol A}}_t = {{\boldsymbol I}}_n$, ${{\boldsymbol B}}_t = {{\boldsymbol I}}_m$ and $({{\boldsymbol C}}_t)_{i,j} = ({{\boldsymbol C}})_{i,j} = c_{i,j}$. The $(n + m) \times (n + m)$ matrix ${{\boldsymbol W}}_t$ given by writes in this case as the diagonal matrix with entries equal to the square $\ell^2$-norms of respectively rows and columns of ${{\boldsymbol C}}$. In this setting, Theorem \[thm:concentration\_continuous\] entails the following. \[cor:grm\] Let ${{\boldsymbol G}}$ be a $n \times m$ random matrix with independent entries $g_{i, j}$ that are centered Gaussian with variance $c_{i,j}^2$. Then, $$\label{eq:gbt} {\mathbbm P}\Big( {{\|{{\boldsymbol G}}\|}_{\operatorname{op}}} \geq \sigma \sqrt{x + \log(n + m)} \Big) \leq e^{-x}$$ with $$\sigma^2 = \max\big({\|{{\boldsymbol C}}\|}_{\infty, 2}, {\|{{\boldsymbol C}}\|}_{2, \infty}\big) = \max\bigg(\max_{i=1, \ldots, n} \sum_{j=1}^m c^2_{i, j}, \max_{j=1, \ldots, m} \sum_{i=1}^n c^2_{i, j} \bigg).$$ In the case of standard Gaussian random variables, i.e., $b_{i,j}^2 = 1$, we simply have $\sigma^2= \max(n, m)$. Moreover, Equation entails in the case $n=m$: $${\mathbbm E}{{\|{{\boldsymbol G}}\|}_{\operatorname{op}}} \leq \sigma \sqrt{2 \log(2 n)}.$$ We therefore recover the bounds on ${\mathbbm E}{{{\|{{\boldsymbol G}}\|}_{\operatorname{op}}}}$ that results from concentration inequalities obtained by alternative methods @oliveira2010sums [@tropp2012user]. We refer the reader to Section \[sec:discussion\] and @tropp2012user for a discussion about the sharpness of this result. The same kind of result can be obtained for a random matrix ${{\boldsymbol N}}$ containing independent entries with a Poisson distribution. Take ${{\boldsymbol C}}_t ={{\boldsymbol C}}$ as the $n \times m$ matrix with all entries equal to one, and consider the $n \times m$ matrix ${{\boldsymbol N}}_t$ with entries $({{\boldsymbol N}}_t)_{i, j}$ that are homogeneous Poisson processes on $[0, 1]$ with (constant) intensity $\lambda_{i, j}$. Taking $t = 1$, and forming the matrix ${{\boldsymbol \lambda}}$ with entries $({{\boldsymbol \lambda}})_{i, j} = \lambda_{i, j}$, we obtain from Corollary \[cor:1\] the following. Let ${{\boldsymbol N}}$ be a $n \times m$ random matrix whose entries $({{\boldsymbol N}})_{i, j}$ have a Poisson distribution with intensity $\lambda_{i, j}$. Then, we have $${\mathbbm P}\bigg( {{\|{{\boldsymbol N}}- {{\boldsymbol \lambda}}\|}_{\operatorname{op}}} \geq \sqrt{2 (\| {{\boldsymbol \lambda}}\|_{1, \infty} \vee \| {{\boldsymbol \lambda}}\|_{\infty, 1})x } + \frac{x}{3} \bigg) \leq (n+m) e^{-x}$$ for any $x > 0$, where ${{\boldsymbol \lambda}}$ has entries $({{\boldsymbol \lambda}})_{i, j} = \lambda_{i, j}$. Such a result for random matrices with independent Poisson entries was not, up to the knowledge of the authors, explicitly exhibited in literature. Note that, in contrast to the Gaussian case considered in Corollary \[cor:grm\], the variance term depends on the maximum $\ell_1$ norm of rows and columns of ${{\boldsymbol \lambda}}$, which comes from the subexponentiality of the Poisson distribution. Stochastic integral of a matrix of functions -------------------------------------------- In this section we consider the simple case where ${{\boldsymbol M}}_s= M_s $ is scalar martingale and ${\mathds{T}}_s$ is a matrix of deterministic functions, i.e., $({\mathds{T}}_s)_{i,j;k,l} = ({{\boldsymbol A}}_s)_{i,j}$. Let us suppose, for the sake of simplicity, that ${{\boldsymbol C}}_s=1$. The matrix martingale ${{\boldsymbol Z}}_t$ therefore writes $$\label{newmart} {{\boldsymbol Z}}_t = \int_0^t {{\boldsymbol A}}_s dM_s.$$ If that case, Theorems \[thm:concentration\_counting\] and \[thm:concentration\_continuous\] lead to the following. \[prop:troppcont\] Let $b_t = \sup_{s \in [0, t]} \max({\|{{\boldsymbol A}}_s\|}_{2, \infty}, {\|{{\boldsymbol A}}_s\|}_{\infty, 2})$ if $M_t$ satisfies Assumption \[ass:M\_d\] and take $b_t = 0$ if $M_t$ is a Brownian motion. Let us define the variance $$\label{sigma2TroppCont} \sigma_t^2 = \max \bigg( \Big\| \int_0^t {{\boldsymbol A}}_s {{\boldsymbol A}}^\top_s ds \Big\|_{\operatorname{op}}, \Big\| \int_0^t {{\boldsymbol A}}^\top_s {{\boldsymbol A}}_s ds \Big\|_{\operatorname{op}} \bigg).$$ Then $$\label{eq:rgs} {\mathbbm P}\Big( {{\|{{\boldsymbol Z}}_t\|}_{\operatorname{op}}} \geq \sqrt{2 \sigma_t^2 x} + \frac{x b_t}{3} \Big) \leq (n+m) e^{-x}$$ for any $x > 0$. This result is a continuous time version of an analogous inequality obtained in @tropp2012user for series of random matrices ${{\boldsymbol Z}}_n$ of the form $${{\boldsymbol Z}}_n = \sum_{k=1}^n \gamma_k {{\boldsymbol A}}_k,$$ where $\gamma_k$ are i.i.d. zero mean random variables (e.g. standard normal) and ${{\boldsymbol A}}_k$ is a sequence of deterministic matrices. Note that Proposition \[prop:troppcont\] allows to recover the result for a discrete sequence ${{\boldsymbol Z}}_n$ simply by considering a piecewise constant matrix-valued process ${{\boldsymbol A}}_s$. Acknowledgments {#acknowledgments .unnumbered} =============== We gratefully acknowledge the anonymous reviewers of the first version of this paper for their helpful comments and suggestions. The authors would like to thank Carl Graham and Peter Tankov for various comments on our paper. This research benefited from the support of the Chair "Markets in Transition", under the aegis of "Louis Bachelier Finance and Sustainable Growth" laboratory, a joint initiative of École Polytechnique, Université d'Évry Val d'Essonne and Fédération Bancaire Francaise. Tools for the study of matrix martingales in continuous time {#sec:tools} ============================================================ In this section we give tools for the study of matrix martingales in continuous time. We proceed by steps. The main result of this section, namely Proposition \[prop:new-counting-supermart\], proves that the trace exponential of a matrix martingale is a supermartingale, when properly corrected by terms involving quadratic covariations. A first tool ------------ We give first a simple lemma that links the largest eigenvalues of random matrices to the trace exponential of their difference. \[lem:deviation\] Let ${\boldsymbol}X$ and ${\boldsymbol}Y$ be two symmetric random matrices such that $$\operatorname{tr}{\mathbbm E}[ e^{{{\boldsymbol X}}- {{\boldsymbol Y}}}] \leq k$$ for some $k > 0$. Then, we have $${\mathbbm P}[ {\lambda_{\max}}({{\boldsymbol X}}) \geq {\lambda_{\max}}({{\boldsymbol Y}}) + x ] \leq k e^{-x}$$ for any $x > 0$. Using the fact that @petz1994survey $$\label{eq:monotone_tr_exp} {{\boldsymbol A}}{\preccurlyeq}{{\boldsymbol B}}\Rightarrow \operatorname{tr}\exp({{\boldsymbol A}}) \leq \operatorname{tr}\exp({{\boldsymbol B}}),~~\mbox{for any}~{{\boldsymbol A}},{{\boldsymbol B}}~\mbox{symmetric},$$ along with the fact that ${{\boldsymbol Y}}{\preccurlyeq}{\lambda_{\max}}({{\boldsymbol Y}}) {{\boldsymbol I}}$, one has $$\operatorname{tr}\exp({\boldsymbol}X - {\boldsymbol}Y) {\mathbf 1_{E}} \geq \operatorname{tr}\exp({\boldsymbol}X - {\lambda_{\max}}({{\boldsymbol Y}}) {\boldsymbol}I) {\mathbf 1_{E}},$$ where we set $E = \{ {\lambda_{\max}}({{\boldsymbol X}}) \geq {\lambda_{\max}}({{\boldsymbol Y}}) + x \}$. Now, since ${\lambda_{\max}}({{\boldsymbol M}}) \leq \operatorname{tr}{{\boldsymbol M}}$ for any symmetric positive definite matrix ${{\boldsymbol M}}$, we obtain $$\begin{aligned} \operatorname{tr}\exp({\boldsymbol}X - {\boldsymbol}Y) {\mathbf 1_{E}} &\geq {\lambda_{\max}}(\exp({\boldsymbol}X - {\lambda_{\max}}({{\boldsymbol Y}}) {\boldsymbol}I)) {\mathbf 1_{E}} \\ &= \exp({\lambda_{\max}}({\boldsymbol}X) - {\lambda_{\max}}({\boldsymbol}Y)) {\mathbf 1_{E}} \\ &\geq e^x {\mathbf 1_{E}}, \end{aligned}$$ so that taking the expectation on both sides proves Lemma \[lem:deviation\]. Various definitions and Itô's Lemma for functions of matrices {#sec:ito} ------------------------------------------------------------- In this section we describe some classical notions from stochastic calculus @jacodshi [@liptser1989theory] and extend them to matrix semimartingales. Let us recall that the <span>*quadratic covariation*</span> of two scalar semimartingales $X_t$ and $Y_t$ is defined as $$[X,Y]_t = X_t Y_t - \int_0^t Y_{t^-} dX_t - \int_0^t X_{t^-} dY_t - X_0 Y_0 \; .$$ It can be proven (see e.g. @jacodshi) that the non-decreasing process $[X, X]_t$, often denoted as $[X]_t$, does correspond to the <span>*quadratic variation*</span> of $X_t$ since it is equal to the limit (in probability) of $\sum_i (X_{t_i}-X_{t_{i-1}})^2$ when the mesh size of the partition $\{t_i \}_i$ of the interval $[0,t]$ goes to zero. If $X_t$ is a square integrable scalar martingale, then its <span>*predictable quadratic variation*</span> ${\langle X \rangle}_t$ is defined as the unique predictable increasing process such that $X_t^2 - {\langle X \rangle}_t$ is a martingale. The predictable quadratic covariation between two square integrable scalar martingales $X_t$ and $Y_t$ is then defined from the polarization identity: $${\langle X ,Y \rangle} = \frac{1}{4} \big( {\langle X + Y, X + Y \rangle} - {\langle X - Y, X - Y \rangle} \big).$$ A martingale $X_t$ is said to be *continuous* if its sample paths $t\mapsto X_t$ are a.s. continuous, and <span>*purely discontinuous*</span>[^1] if $X_0 = 0$ and ${\langle X, Y \rangle}_t = 0$ for any continuous martingale $ Y_t$. The notion of predictable quadratic variation can be extended to semimartingales. Indeed, any semimartingale $X_t$ can be represented as a sum: $$\label{eq:dec} X_t = X_0 + X^{c}_t + X^{d}_t + A_t,$$ where $X^{c}_t$ is a continuous local martingale, $X^{d}_t$ is a purely discontinuous local martingale and $A_t$ is a process of bounded variations. Since in the decomposition , $X^{c}_t$ is unambiguously determined, ${\langle X^c \rangle}_t$ is therefore well defined @jacodshi. Within this framework, one can prove (see e.g. @jacodshi) that if $X_t$ and $Y_t$ are two semimartingales, then: $$\label{qv} [X,Y]_t = {\langle X^c,Y^c \rangle}_t + \sum_{0\leq s \leq t} \Delta X_s \Delta Y_s.$$ All these definitions can be naturally extended to matrix valued semimartingales. Let ${{\boldsymbol X}}_t$ be a $p \times q$ matrix whose entries are real-valued square-integrable semimartingales. We denote by ${\langle {{\boldsymbol M}}\rangle}_t$ the matrix of entry-wise predictable quadratic variations. The predictable quadratic covariation of ${{\boldsymbol X}}_t$ is defined with the help of the vectorization operator ${\mathrm{vec}}: {\mathbb R}^{p \times q} \rightarrow {\mathbb R}^{pq}$ which stacks vertically the columns of ${{\boldsymbol X}}$, namely if ${{\boldsymbol X}}\in {\mathbb R}^{p \times q}$ then $${\mathrm{vec}}({{\boldsymbol X}}) = \begin{bmatrix} {{\boldsymbol X}}_{1, 1} \cdots {{\boldsymbol X}}_{p, 1} {{\boldsymbol X}}_{1, 2} \cdots {{\boldsymbol X}}_{p, 2} \cdots {{\boldsymbol X}}_{1, q} \cdots {{\boldsymbol X}}_{p, q} \end{bmatrix}^\top.$$ We define indeed the predictable quadratic covariation matrix ${\langle {\mathrm{vec}}{{\boldsymbol X}}\rangle}_t$ of ${{\boldsymbol X}}_t$ as the $pq \times pq$ matrix with entries $$\label{eq:predictable_covariation} ({\langle {\mathrm{vec}}{{\boldsymbol X}}\rangle}_t)_{i,j} = {\langle ({\mathrm{vec}}{{\boldsymbol X}}_t)_i, ({\mathrm{vec}}{{\boldsymbol X}}_t)_j \rangle}$$ for $1 \leq i, j \leq pq$, namely such that ${\mathrm{vec}}({{\boldsymbol X}}_t) {\mathrm{vec}}({{\boldsymbol X}}_t)^\top - {\langle {\mathrm{vec}}{{\boldsymbol X}}\rangle}_t$ is a martingale. The matrices of quadratic variations $[{{\boldsymbol X}}]_t$ and quadratic covariations $[{\mathrm{vec}}{{\boldsymbol X}}]_t$ are defined along the same line. Then according to Equation , we have: $$\label{eq:quadratic-variation} [{{\boldsymbol X}}]_t = {\langle {{\boldsymbol X}}^c \rangle}_t + \sum_{0 \leq s \leq t} (\Delta {{\boldsymbol X}}_s)^2,$$ and $$[{\mathrm{vec}}{{\boldsymbol X}}]_t = {\langle {\mathrm{vec}}{{\boldsymbol X}}^c \rangle}_t + \sum_{0 \leq s \leq t} {\mathrm{vec}}(\Delta {{\boldsymbol X}}_{s}) {\mathrm{vec}}(\Delta {{\boldsymbol X}}_{s})^\top.$$ An important tool for our proofs is Itô's lemma, that allows to compute the stochastic differential $d F({{\boldsymbol M}}_t)$ where $F : {\mathbb R}^{p \times q} \rightarrow {\mathbb R}$ is a twice differentiable function. We denote by $\frac{d F}{d {\mathrm{vec}}({{\boldsymbol X}})}$ the $p q$-dimensional vector such that $$\Big[ \frac{d F}{d {\mathrm{vec}}({{\boldsymbol X}})} \Big]_i = \frac{\partial F}{\partial ({\mathrm{vec}}{{\boldsymbol X}})_i} \; \text{ for } \; 1 \leq i \leq p q.$$ The second order derivative is the $pq \times pq$ symmetric matrix given by $$\Big[ \frac{d^2 F}{d {\mathrm{vec}}({{\boldsymbol X}})d {\mathrm{vec}}({{\boldsymbol X}})^\top}\Big]_{i, j} = \frac{\partial^2 F}{\partial ({\mathrm{vec}}{{\boldsymbol X}})_i \partial ({\mathrm{vec}}{{\boldsymbol X}})_j} \; \text{for} \; 1 \leq i, j \leq pq.$$ A direct application of the multivariate Itô Lemma (@liptser1989theory Theorem 1, p. 118) writes for matrix semimartingales as follows. \[Itô's Lemma\] \[lem:ito\] Let $\{{{\boldsymbol X}}_t\}_{t \geq 0}$ be a $p \times q$ matrix semimartingale and $F : {\mathbb R}^{p \times q} \rightarrow {\mathbb R}$ be a twice continuously differentiable function. Then $$\begin{aligned} dF({{\boldsymbol X}}_t) &= \Big(\frac{d F}{d {\mathrm{vec}}({{\boldsymbol X}})}({{\boldsymbol X}}_{t^-}) \Big)^\top {\mathrm{vec}}(d {{\boldsymbol X}}_t) + \Delta F({{\boldsymbol X}}_t) - \Big(\frac{d F}{d {\mathrm{vec}}{{\boldsymbol X}}}({{\boldsymbol X}}_{t^-}) \Big)^\top {\mathrm{vec}}(\Delta {{\boldsymbol X}}_t) \\ & \quad + \frac 12 \operatorname{tr}\bigg(\Big(\frac{d^2 F}{d {\mathrm{vec}}({{\boldsymbol X}}) d {\mathrm{vec}}({{\boldsymbol X}})^\top} ({{\boldsymbol X}}_{t^-}) \Big)^\top d{\langle {\mathrm{vec}}{{\boldsymbol X}}^c \rangle}_t \bigg). \end{aligned}$$ As an application, let us apply Lemma \[lem:ito\] to the function $F({{\boldsymbol X}})= \operatorname{tr}\exp({{\boldsymbol X}})$ that acts on the set of symmetric matrices. This result will be of importance for the proof of our results. \[Itô's Lemma for the trace exponential\] \[lem:ito-trace-exp\] Let $\{{{\boldsymbol X}}_t\}$ be a $d \times d$ symmetric matrix semimartingale. The Itô formula for $F({{\boldsymbol X}}_t) = \operatorname{tr}\exp({{\boldsymbol X}}_t)$ gives $$ d(\operatorname{tr}e^{{{\boldsymbol X}}_t}) = \operatorname{tr}(e^{{{\boldsymbol X}}_{t^-}} d {{\boldsymbol X}}_t) + \Delta(\operatorname{tr}e^{{{\boldsymbol X}}_t}) - \operatorname{tr}(e^{{{\boldsymbol X}}_{t^-}} \Delta {{\boldsymbol X}}_t) + \frac 12 \sum_{i=1}^d \operatorname{tr}(e^{{{\boldsymbol X}}_{t^-}} d{\langle {{\boldsymbol X}}_{{\bullet}, i}^c \rangle}_t),$$ where ${\langle {{\boldsymbol X}}_{{\bullet}, i}^c \rangle}_t$ denotes the $d \times d$ predictable quadratic variation of the continuous part of the $i$-th column $({{\boldsymbol X}}_t)_{{\bullet}, i}$ of ${{\boldsymbol X}}_t$. An easy computation gives $$\operatorname{tr}e^{{{\boldsymbol X}}+ {{\boldsymbol H}}} = \operatorname{tr}e^{{{\boldsymbol X}}} + \operatorname{tr}(e^{{{\boldsymbol X}}} {{\boldsymbol H}}) + \operatorname{tr}(e^{{{\boldsymbol X}}} {{\boldsymbol H}}^2) + \text{ higher order terms in } {{\boldsymbol H}}$$ for any symmetric matrices ${{\boldsymbol X}}$ and ${{\boldsymbol H}}$. Note that $\operatorname{tr}(e^{{\boldsymbol X}}{{\boldsymbol H}}) = ({\mathrm{vec}}{{\boldsymbol H}})^\top {\mathrm{vec}}(e^{{\boldsymbol X}}) $, and we have from @johnson1991topics Exercise 25 p. 252 that $$\operatorname{tr}(e^{{{\boldsymbol X}}} {{\boldsymbol H}}^2) = \operatorname{tr}({{\boldsymbol H}}e^{{{\boldsymbol X}}} {{\boldsymbol H}}) = ({\mathrm{vec}}{{\boldsymbol H}})^\top ({{\boldsymbol I}}\otimes e^{{\boldsymbol X}}) ({\mathrm{vec}}{{\boldsymbol H}}),$$ where the Kronecker product ${{\boldsymbol I}}\otimes e^{{\boldsymbol X}}$ stands for the block matrix $${{\boldsymbol I}}\otimes {{\boldsymbol Y}}= \begin{bmatrix} e^{{\boldsymbol X}}& 0 & \cdots & 0 \\ 0 & e^{{\boldsymbol X}}& & \vdots \\ \vdots & & \ddots & 0 \\ 0 & \cdots & 0 & e^{{\boldsymbol X}}\end{bmatrix}.$$ This entails that $$\frac{d(\operatorname{tr}e^{{{\boldsymbol X}}})}{d {\mathrm{vec}}({{\boldsymbol X}})} = {\mathrm{vec}}(e^{{{\boldsymbol X}}}) \;\; \text{ and } \;\; \frac{d^2(\operatorname{tr}e^{{{\boldsymbol X}}})}{d {\mathrm{vec}}({{\boldsymbol X}}) d {\mathrm{vec}}({{\boldsymbol X}})^\top} = {{\boldsymbol I}}\otimes e^{{\boldsymbol X}}.$$ Hence, using Lemma \[lem:ito\] with $F({{\boldsymbol X}}) = \operatorname{tr}e^{{{\boldsymbol X}}}$ we obtain $$\begin{aligned} d(\operatorname{tr}e^{{{\boldsymbol X}}_t}) &= {\mathrm{vec}}(e^{{{\boldsymbol X}}_{t^-}})^\top {\mathrm{vec}}(d {{\boldsymbol X}}_t) + \Delta(\operatorname{tr}e^{{{\boldsymbol X}}_t}) - {\mathrm{vec}}(e^{{{\boldsymbol X}}_{t^-}})^\top {\mathrm{vec}}(\Delta {{\boldsymbol X}}_t) \\ & \quad + \frac 12 \operatorname{tr}\big( ({{\boldsymbol I}}\otimes e^{{{\boldsymbol X}}_{t^-}}) d{\langle {\mathrm{vec}}{{\boldsymbol X}}^c \rangle}_t \big). \end{aligned}$$ Since ${\mathrm{vec}}({{\boldsymbol Y}})^\top {\mathrm{vec}}({{\boldsymbol Z}}) = \operatorname{tr}({{\boldsymbol Y}}{{\boldsymbol Z}})$, one gets $$\begin{aligned} d(\operatorname{tr}e^{{{\boldsymbol X}}_t}) &= \operatorname{tr}(e^{{{\boldsymbol X}}_{t^-}} d {{\boldsymbol X}}_t) + \Delta(\operatorname{tr}e^{{{\boldsymbol X}}_t}) - \operatorname{tr}(e^{{{\boldsymbol X}}_{t^-}} \Delta {{\boldsymbol X}}_t) + \frac 12 \operatorname{tr}\big( ({{\boldsymbol I}}\otimes e^{{{\boldsymbol X}}_{t^-}}) d{\langle {\mathrm{vec}}{{\boldsymbol X}}^c \rangle}_t \big). \end{aligned}$$ To conclude the proof of Lemma \[lem:ito-trace-exp\], it remains to prove that $$\operatorname{tr}\big( ({{\boldsymbol I}}\otimes e^{{{\boldsymbol X}}_{t^-}}) d {\langle {\mathrm{vec}}{{\boldsymbol X}}^c \rangle}_t \big) = \sum_{i=1}^d \operatorname{tr}(e^{{{\boldsymbol X}}_{t^-}} d{\langle {{\boldsymbol X}}_{{\bullet}, i}^c \rangle}_t).$$ First, let us write $$d{\langle {\mathrm{vec}}{{\boldsymbol X}}^c \rangle}_t = \sum_{1 \leq i, j \leq d} {{\boldsymbol E}}^{i, j} \otimes d {\langle {{\boldsymbol X}}_{{\bullet}, i}^c, {{\boldsymbol X}}_{{\bullet}, j}^c \rangle}_t,$$ where ${{\boldsymbol E}}^{i, j}$ is the $d \times d$ matrix with all entries equal to zero excepted for the $(i, j)$-entry, which is equal to one. Since $$({{\boldsymbol A}}\otimes {{\boldsymbol B}})({{\boldsymbol C}}\otimes {{\boldsymbol D}}) = ({{\boldsymbol A}}{{\boldsymbol C}}) \otimes ({{\boldsymbol B}}{{\boldsymbol D}}) \quad \text{and} \quad \operatorname{tr}({{\boldsymbol A}}\otimes {{\boldsymbol B}}) = \operatorname{tr}({{\boldsymbol A}}) \operatorname{tr}({{\boldsymbol B}})$$ for any matrices ${{\boldsymbol A}}, {{\boldsymbol B}}, {{\boldsymbol C}}, {{\boldsymbol D}}$ with matching dimensions (see for instance @johnson1991topics), we have $$\operatorname{tr}\big(({{\boldsymbol I}}\otimes e^{{{\boldsymbol X}}_{t^-}}) d{\langle {\mathrm{vec}}{{\boldsymbol X}}^c \rangle}_t \big) = \sum_{1 \leq i, j \leq d} \operatorname{tr}({{\boldsymbol E}}^{i, j}) \operatorname{tr}(e^{{{\boldsymbol X}}_{t-}} d {\langle {{\boldsymbol X}}_{{\bullet}, i}^c,{{\boldsymbol X}}_{{\bullet}, j}^c \rangle}_t) = \sum_{i=1}^d \operatorname{tr}(e^{{{\boldsymbol X}}_{t-}} d{\langle {{\boldsymbol X}}_{{\bullet}, i}^c, {{\boldsymbol X}}_{{\bullet}, i}^c \rangle}_t)$$ since $\operatorname{tr}{{\boldsymbol E}}^{i, j} = 0$ for $i \neq j$ and $1$ otherwise. This concludes the proof of Lemma \[lem:ito-trace-exp\]. A matrix supermartingale property --------------------------------- The next proposition is a key property that is used below for the proofs of concentration inequalities both for purely discontinuous and continuous matrix martingales. \[prop:new-counting-supermart\] Let $\{ {{\boldsymbol Y}}_t \}_{t \geq 0}$ be a $d \times d$ symmetric matrix martingale such that ${{\boldsymbol Y}}_0 = {{\boldsymbol 0}}$ and whose entries are locally bounded. Let ${{\boldsymbol U}}_t$ be defined by $$\label{eq:ass_counting-supermart} {{\boldsymbol U}}_t = \sum_{s \leq t} \big(e^{\Delta {{\boldsymbol Y}}_{s}} - \Delta {{\boldsymbol Y}}_{s} - {{\boldsymbol I}}\big).$$ If the matrix ${{\boldsymbol U}}_t$ has an entry-wise compensator ${{\boldsymbol A}}_t$ (i.e., ${{\boldsymbol U}}_t - {{\boldsymbol A}}_t$ is a matrix martingale) which is predictable, continuous and has finite variation (FV) then the process $$L_t = \operatorname{tr}\exp \Big({{\boldsymbol Y}}_t - {{\boldsymbol A}}_t - \frac 12 \sum_{j=1}^d {\langle {{\boldsymbol Y}}_{{\bullet}, j}^c \rangle}_t\Big)$$ is a supermartingale. In particular, we have ${\mathbbm E}L_t \leq d$ for any $t \geq 0$. Proposition \[prop:new-counting-supermart\] can be understood as an extension to random matrices of the exponential supermartingale property given implicitly in the proof of Lemma 2.2 in @van1995exponential, or the supermartingale property for multivariate counting processes from @bremaud1981point, see Theorem 2, p. 165 and in Chapter 4.13 from @liptser1989theory. Define for short $${{\boldsymbol X}}_t = {{\boldsymbol Y}}_t - {{\boldsymbol A}}_t - \frac 12 \sum_{j=1}^d {\langle {{\boldsymbol Y}}_{{\bullet},j}^c \rangle}_t.$$ Since ${{\boldsymbol A}}_t$ and ${\langle {{\boldsymbol Y}}_{{\bullet}, j}^c \rangle}_t$ for $j=1, \ldots, d$ are FV processes, then $$\label{eq:quad_var_X_Y_equal} {\langle {\mathrm{vec}}{{\boldsymbol X}}^c \rangle} = {\langle {\mathrm{vec}}{{\boldsymbol Y}}^c \rangle}$$ and in particular ${\langle {{\boldsymbol Y}}_{{\bullet}, j}^c \rangle} = {\langle {{\boldsymbol X}}_{{\bullet}, j}^c \rangle}$ for any $j=1, \ldots, d$. Using Lemma \[lem:ito-trace-exp\], one has that for all $t_1 < t_2$: $$\begin{aligned} L_{t_2} - L_{t_1} &= \int_{t_1}^{t_2} \operatorname{tr}(e^{{{\boldsymbol X}}_{t^-}} d {{\boldsymbol X}}_t) + \sum_{t_1 \leq t \leq t_2} \big(\Delta(\operatorname{tr}e^{{{\boldsymbol X}}_{t}}) - \operatorname{tr}(e^{{{\boldsymbol X}}_{{t}^-}} \Delta {{\boldsymbol X}}_{t}) \big) \\ & \quad \quad + \frac 12 \int_{t_1}^{t_2} \sum_{j=1}^d \operatorname{tr}(e^{{{\boldsymbol X}}_{t^-}} d{\langle {{\boldsymbol X}}_{{\bullet},j}^c \rangle}_t) \\ &= \int_{t_1}^{t_2} \operatorname{tr}(e^{{{\boldsymbol X}}_{t^-}} d {{\boldsymbol Y}}_t) - \int_{t_1}^{t_2} \operatorname{tr}(e^{{{\boldsymbol X}}_{t^-}} d {{\boldsymbol A}}_t) \\ & \quad \quad + \sum_{t_1 \leq t \leq t_2} \big( \operatorname{tr}( e^{{{\boldsymbol X}}_{{t}^-} + \Delta {{\boldsymbol Y}}_{t}}) - \operatorname{tr}(e^{{{\boldsymbol X}}_{{t}^-}}) -\operatorname{tr}(e^{{{\boldsymbol X}}_{t^-}} \Delta {{\boldsymbol Y}}_{t}) \big), \end{aligned}$$ where we used together with the fact that $\Delta {{\boldsymbol X}}_t = \Delta {{\boldsymbol Y}}_t$, since ${{\boldsymbol A}}_t$ and ${\langle {{\boldsymbol Y}}_{{\bullet}, j}^c \rangle}_t$ are both continuous. The Golden-Thompson's inequality, see @bhatia1997matrix, states that $\operatorname{tr}e^{{{\boldsymbol A}}+ {{\boldsymbol B}}} \leq \operatorname{tr}( e^{{\boldsymbol A}}e^{{\boldsymbol B}})$ for any symmetric matrices ${{\boldsymbol A}}$ and ${{\boldsymbol B}}$. Using this inequality we get $$\begin{aligned} L_{t_2} - L_{t_1} &\leq \int_{t_1}^{t_2} \operatorname{tr}(e^{{{\boldsymbol X}}_{t^-}} d {{\boldsymbol Y}}_t) - \int_{t_1}^{t_2} \operatorname{tr}(e^{{{\boldsymbol X}}_{t^-}} d {{\boldsymbol A}}_t) + \sum_{t_1 \leq t \leq t_2} \operatorname{tr}\big( e^{{{\boldsymbol X}}_{{t}^-}}(e^{\Delta {{\boldsymbol Y}}_{t}} -\Delta {{\boldsymbol Y}}_{t} - {{\boldsymbol I}}) \big) \\ &= \int_{t_1}^{t_2} \operatorname{tr}(e^{{{\boldsymbol X}}_{t^-}} d {{\boldsymbol Y}}_t) + \int_{t_1}^{t_2} \operatorname{tr}\big(e^{{{\boldsymbol X}}_{t^-}}d({{\boldsymbol U}}_t - {{\boldsymbol A}}_t) \big). \end{aligned}$$ Since ${{\boldsymbol Y}}_t$ and ${{\boldsymbol U}}_t - {{\boldsymbol A}}_t$ are matrix martingales, $e^{{{\boldsymbol X}}_{t^-}}$ is a predictable process with locally bounded entries and $L_t \geq 0$, the r.h.s of the last equation corresponds to the variation between $t_1$ and $t_2$ of a non-negative local martingale, i.e., of a supermartingale. It results that ${\mathbbm E}[L_{t_2} - L_{t_1}| {\mathscr F}_{t_1}] \leq 0$, which proves that $L_t$ is also a supermartingale. Using this last inequality with $t_1 = 0$ and $t_2 = t$ gives ${\mathbbm E}[L_{t}] \leq d$. This concludes the proof of Proposition \[prop:new-counting-supermart\]. Bounding the odd powers of the dilation operator ------------------------------------------------ The process $\{ {{\boldsymbol Z}}_t \}$ is not symmetric, hence following @tropp2012user, we will force symmetry in our proofs by extending it in larger dimensions, using the symmetric dilation operator @paulsen2002completely given, for a matrix ${{\boldsymbol X}}$, by $$\label{eq:sx} {\mathscr S}({\boldsymbol}X) = \begin{bmatrix} {\boldsymbol}0 & {\boldsymbol}X \\ {\boldsymbol}X^\top & {\boldsymbol}0 \end{bmatrix}.$$ The following Lemma will prove useful: \[lem:boundSodd\] Let ${{\boldsymbol X}}$ be some $n \times m$ matrix and $k \in {\mathbb N}$. Then $${\mathscr S}({{\boldsymbol X}})^{2k+1} = \begin{bmatrix} {\boldsymbol}0 & {{\boldsymbol X}}({{\boldsymbol X}}^\top {{\boldsymbol X}})^{k} \\ {{\boldsymbol X}}^\top ({{\boldsymbol X}}{{\boldsymbol X}}^\top)^{k} & 0 \end{bmatrix} {\preccurlyeq}\begin{bmatrix} ({{\boldsymbol X}}{{\boldsymbol X}}^\top)^{k + 1/2} & {\boldsymbol}0 \\ {\boldsymbol}0 & ({{\boldsymbol X}}^\top {{\boldsymbol X}})^{k + 1/2} \end{bmatrix}.$$ The first equality results from a simple algebra. It can be rewritten as: $$\label{eq:sodd} {\mathscr S}({{\boldsymbol X}})^{2k+1} = \begin{bmatrix} {\boldsymbol}0 & ({{\boldsymbol X}}{{\boldsymbol X}}^\top)^{k} {{\boldsymbol X}}\\ {{\boldsymbol X}}^\top ({{\boldsymbol X}}{{\boldsymbol X}}^\top)^{k} & 0 \end{bmatrix} = {{\boldsymbol C}}\begin{bmatrix} {\boldsymbol}0 & ({{\boldsymbol X}}{{\boldsymbol X}}^\top)^{k} \\ ({{\boldsymbol X}}{{\boldsymbol X}}^\top)^{k} & 0 \end{bmatrix} {{\boldsymbol C}}^\top$$ where $${{\boldsymbol C}}= \begin{bmatrix} {\boldsymbol}0 & {{\boldsymbol I}}_n \\ {{\boldsymbol X}}^\top & 0 \end{bmatrix}.$$ Since $({{\boldsymbol X}}{{\boldsymbol X}}^\top)^{k} {\succcurlyeq}{\boldsymbol}0 $ and $${{\boldsymbol A}}= \begin{bmatrix} 1 & -1 \\ -1 & 1 \end{bmatrix} {\succcurlyeq}0,$$ we obtain that ${{\boldsymbol A}}\otimes ({{\boldsymbol X}}{{\boldsymbol X}}^\top)^{k} {\succcurlyeq}{\boldsymbol}0$, since the eigenvalues of a Kronecker product ${{\boldsymbol A}}\otimes {{\boldsymbol B}}$ are given by the products of the eigenvalues of ${{\boldsymbol A}}$ and ${{\boldsymbol B}}$, see @golub2013matrix. This leads to: $$\begin{bmatrix} {\boldsymbol}0 & ({{\boldsymbol X}}{{\boldsymbol X}}^\top)^{k} \\ ({{\boldsymbol X}}{{\boldsymbol X}}^\top)^{k} & 0 \end{bmatrix} {\preccurlyeq}\begin{bmatrix} ({{\boldsymbol X}}{{\boldsymbol X}}^\top)^{k} & {\boldsymbol}0 \\ {\boldsymbol}0 & ({{\boldsymbol X}}{{\boldsymbol X}}^\top)^{k} \end{bmatrix}.$$ Using the fact that @petz1994survey $$\label{eq:monotone_mult} {{\boldsymbol A}}{\preccurlyeq}{{\boldsymbol B}}\;\; \Rightarrow \;\; {{\boldsymbol C}}{{\boldsymbol A}}{{\boldsymbol C}}^\top {\preccurlyeq}{{\boldsymbol C}}{{\boldsymbol B}}{{\boldsymbol C}}^\top$$ for any real matrices ${{\boldsymbol A}}, {{\boldsymbol B}}, {{\boldsymbol C}}$ (with compatible dimensions), we have: $${\mathscr S}({{\boldsymbol X}})^{2k+1} {\preccurlyeq}{{\boldsymbol C}}\begin{bmatrix} ({{\boldsymbol X}}{{\boldsymbol X}}^\top)^{k} & {\boldsymbol}0 \\ {\boldsymbol}0 & ({{\boldsymbol X}}{{\boldsymbol X}}^\top)^{k} \end{bmatrix} {{\boldsymbol C}}^\top = \begin{bmatrix} ({{\boldsymbol X}}{{\boldsymbol X}}^\top)^{k} & {\boldsymbol}0 \\ {\boldsymbol}0 & ({{\boldsymbol X}}^\top {{\boldsymbol X}})^{k+1} \end{bmatrix}.$$ Along the same line, one can establish that: $${\mathscr S}({{\boldsymbol X}})^{2k+1} {\preccurlyeq}\begin{bmatrix} ({{\boldsymbol X}}{{\boldsymbol X}}^\top)^{k+1} & {\boldsymbol}0 \\ {\boldsymbol}0 & ({{\boldsymbol X}}^\top {{\boldsymbol X}})^{k} \end{bmatrix}.$$ The square root of the product of the two inequalities provides the desired result. Proof of Theorem \[thm:concentration\_counting\] {#sec:proof_of_theorem_1} ================================================ let us recall the definition of the dilation operator. Let us point out that ${\mathscr S}({{\boldsymbol X}})$ is symmetric and satisfies ${\lambda_{\max}}({\mathscr S}({{\boldsymbol X}})) = {{\|{\mathscr S}({{\boldsymbol X}})\|}_{\operatorname{op}}} = {{\|{{\boldsymbol X}}\|}_{\operatorname{op}}}$. Note that ${\mathscr S}({{\boldsymbol Z}}_t)$ is purely discontinuous, so that ${\langle {\mathscr S}({{\boldsymbol Z}})_{\bullet, j}^c \rangle}_t = {{\boldsymbol 0}}$ for any $j$. Recall that we work on events $\{ {\lambda_{\max}}({{\boldsymbol V}}_t) \leq v \}$ and $\{ b_t \leq b\}$. We want to apply Proposition \[prop:new-counting-supermart\] (see Section \[sec:tools\] above) to ${{\boldsymbol Y}}_t = \xi {\mathscr S}({{\boldsymbol Z}}_t) / b$. In order to do so, we need the following Proposition. \[prop:utmartingale\] Let the matrix ${{\boldsymbol W}}_t$ be the matrix defined in Equation . Let any $\xi \ge 0$ be fixed and consider $\phi(x) = e^x - x - 1$ for $x \in {\mathbb R}$.
{'source': 'arXiv_out/1412'}